Programação Linear 1

Prévia do material em texto

Programação Linear
1. Introdução
A programação linear visa fundamentalmente encontrar a melhor solução para 
problemas que tenham seus modelos representados por expressões lineares. A grande 
aplicabilidade e simplicidade que a caracterizam devem-se à linearidade do modelo. 
A tarefa da programação linear consiste na maximização ou minimização de uma 
função linear, conceitualmente denominada função objetivo, respeitando-se um 
sistema linear de igualdades ou desigualdades que recebem o nome de restrições do 
modelo. As restrições representam normalmente limitações de recursos disponíveis 
(capital, mão-de-obra, recursos minerais, etc.) ou, então, exigências e condições que 
devem ser cumpridas no problema. Essas restrições do modelo determinam uma 
região à qual damos o nome de conjunto das soluções viáveis. A melhor das soluções 
viáveis, isto é, aquela que maximiza ou minimiza a função objetivo denomina-se 
solução ótima. 
2. Exemplo de Modelo de Programação Linear
Uma empresa pode fabricar dois produtos (1 e 2). Na fabricação do produto 1 a 
empresa gasta nove horas-homem e três horas-máquina. Na fabricação do produto 2 a 
empresa gasta uma hora-homem e uma hora-máquina. Sendo x1 e x2 as quantidades 
fabricadas dos produtos 1 e 2 e sabendo-se que a empresa dispõe de dezoito horas-
homem e doze horas-máquina e ainda que os lucros dos produtos são R$ 4,00 e R$ 
1,00, respectivamente, quanto deve a empresa fabricar de cada produto para obter o 
maior lucro possível.
Modelagem:
variável x1 variável x2 capacidade disponível
9 h-h 1 h-h 18 h-h
3 h-m 1 h-m 12 h-m
Lucro de x1 = 4
Lucro de x2 = 1
Problema:
Max. Q(x) = 4x1 + x2 → Função Objetivo
s.a. 9x1 + x2 ≤ 18 → 1ª Restrição
3x1 + x2 ≤ 12 → 2ª Restrição
x1 , x2 ≥ 0 → Condição de não negatividade
Graficamente podemos visualizar o problema da seguinte forma:
Resta agora maximizar o Lucro: Q(x) = 4x1 + x2 . Sabe-se que o lucro é uma constante 
para cada uma das combinações de x1 e x2 . Assim, lucros diferentes geram retas 
paralelas, sendo o lucro constante em cada reta. O nosso problema consiste, portanto, 
em procurar o ponto pertencente ao conjunto viável, tal que por ele passe a reta que 
maximiza Q(x), ou seja, a nossa solução ótima. Estes fatos condicionam a solução 
ótima (quando existe) a localizar-se em ao menos um ponto extremo ou vértice do 
conjunto de soluções viáveis de um problema de programação linear (PPL).
Ponto (x1 , x2) Função objetivo Q(x)
0,0 0
0,12 12
1,9 13 ← Solução ótima
2,0 2
Assim, o objetivo da programação linear consiste na determinação da solução ótima. 
Dois passos são fundamentais para a resolução de um PPL. O primeiro é a modelagem 
do problema, seguindo-se o método de solução do problema, no caso, o método mais 
utilizado é o SIMPLEX.
3. Forma-Padrão de um PPL
O desenvolvimento de um método (ou algoritmo) que determine a solução de um PPL 
torna necessária a redução do problema a uma forma tal que permita a aplicação 
direta deste algoritmo. No caso da programação linear, o algoritmo mais utilizado é o 
SIMPLEX. Para que o SIMPLEX seja aplicado, é fundamental reduzir o PPL à forma-
padrão a seguir:
A x = b , onde b ≥ 0
x ≥ 0
cT x = Q(x) → MIN
A : matriz m x n, constituída por todas as unidades dos recursos. O número de linhas 
(m) consiste no número de restrições do problema e o número de colunas (n) é igual à 
quantidade de variáveis presentes no problema.
b : vetor m x 1, constituído pela capacidade disponível para cada recurso.
c : vetor n x 1, constituído pelo lucro dado por cada produto.
x : vetor n x 1, variáveis do problema.
Resumindo, a forma-padrão implica que o primeiro grupo de restrições envolva apenas 
igualdades e que todas as variáveis do modelo sejam não negativas. Além disso, 
queremos minimizar a função objetivo.
Por vez, torna-se necessário reduzir um PPL qualquer a forma-padrão, para que 
possamos, assim, aplicar o algoritmo SIMPLEX. A seguir alguns casos particulares que 
podem ocorrer:
a) Ocorrência de desigualdades: evidentemente qualquer desigualdade ou 
inequação linear pode ser transformada em uma equação se subtrairmos ou 
adicionarmos variáveis positivas denominadas variáveis de folga.
b) Ocorrência de bi < 0: bastará neste caso multiplicar a restrição i por -1, pois os 
coeficientes da matriz A podem assumir qualquer valor.
c) Variáveis livres: chamam-se livres as variáveis que não têm qualquer restrição 
de sinal. Seja xk uma variável dita livre, podemos substituí-la por duas outras 
variáveis xk’ e xk’’ de maneira que xk = xk’ - xk’’, sendo xk’ ≥ 0 e xk’’ ≥ 0. Assim, 
substituímos uma variável livre por duas variáveis não negativas.
d) Variável não positiva: se o modelo for formulado com uma variável xk ≤ 0 basta 
substituí-la pela sua simétrica, isto é, basta fazer xk’ = - xk e substituir xk por xk’ 
nas equações do problema. Evidentemente, teremos xk’ ≥ 0.
e) A função objetivo é de maximização: neste caso, basta substituir a função 
objetivo dada pela sua simétrica, passando a minimizar esta última: MAX {Q(x)} 
= - MIN {-Q(x)}.
4. Definições Fundamentais:
a) Os vetores x1
 
, x2
 
, ... , xn são linearmente dependentes se e só se algum deles é 
combinação linear dos outros, ou seja, se existem escalares α1
 
, α2
 
, ... , αn não todos 
nulos tais que: x1
 
α1
 
+ x2
 
α2
 
+ ... + xn αn = 0
b) Se a igualdade x1
 
α1
 
+ x2 α2
 
+ ... + xn
 
αn = 0 é satisfeita apenas com todos os 
escalares iguais a zero, então os vetores x1
 
, x2
 
, ... , xn são linearmente 
independentes.
c) O conjunto de pontos ( x1
 
, x2
 
, ... , xn ) que satisfazem a equação x1
 
α1
 
+ x2
 
α2
 
+ ... 
+ xn
 
αn = α0 , com α0
 
, α1
 
, α2
 
, ... , αn Є R. Diz-se então que esta equação define um 
hiperplano em Rn. Por exemplo, a reta é o hiperplano em R2
 
e o plano é o hiperplano 
em R3. Um hiperplano separa o plano em duas regiões chamadas semi-planos.
d) Chama-se x = x1
 
α1
 
+ x2
 
α2
 
+ ... + xn
 
αn a combinação linear convexa de um número 
finito de pontos se:
α1
 
+ α2
 
+ ... + αn = 1 ; e
αi ≥ 0 , onde i = 1, 2, ..., n
Geometricamente, podemos interpretar um combinação linear convexa de dois pontos 
como um ponto contido no segmento de reta que os une.
e) O conjunto convexo K é um conjunto que contém todas as combinações lineares 
convexas dos seus pontos, ou seja, quaisquer que sejam dois pontos x1
 
e x2 Є K, tem-
se que:
x = x1
 
α + x2 ( α – 1) , onde
 
x Є K e 0 ≤ α ≤ 1
f) Um conjunto convexo K é fechado se contém a sua fronteira.
g) Um ponto extremo de um conjunto convexo K é um ponto de K que não pode ser 
obtido por combinação linear convexa de outros pontos de K.
h) Definimos um politopo ou, mais precisamente, politopo convexo como a interseção 
de um número finito de semi-planos fechados. Já um politopo convexo limitado 
denomina-se poliedro convexo.
5. Teoremas Fundamentais:
a) O conjunto das soluções viáveis do PPL é convexo fechado.
b) O ponto x é vértice do conjunto de soluções viáveis do PPL se, e somente se, x for 
solução básica viável.
c) Existe um número finito de soluções básicas viáveis, associadas a um PPL, isto é, o 
conjunto de soluções viáveis de um PPL tem um número finito de vértices ou pontos 
extremos.
d) Uma função linear (função objetivo) sobre um politopo convexo K atinge o ótimo 
num ponto extremo de K. No caso de atingir o ótimo em mais de um ponto extremo, 
qualquer combinação linear convexa destes pontos corresponde ainda a uma solução 
ótima.
Dado que o conjunto de soluções viáveis Kde um PPL resulta da interseção de um 
número finito de hiperplanos, então decorrem as seguintes três situações, 
mutualmente exclusivas:
− Conjunto K é vazio: o problema não tem solução.
− Conjunto K é não vazio e limitado: o problema possui solução ótima que pode ser 
única ou não.
− Conjunto K é não vazio e não limitado: o problema pode ou não ter solução ótima, 
neste último caso o valor da função objetivo pode crescer ou decrescer 
indefinidamente.
Método SIMPLEX
Ǝ c
j
 > 0
Seja c
s
 = max c
j
Então x
s
 será a nova variável básica
SIM
Ǝ a
is
 > 0 Solução 
impossível
SIM
Seja b
r
 / a
rs
 = min b
i
 / a
i s
 a
rs
 será o elemento pivô
 X
r
 será a nova variável não-básica
Reduzir a nova solução básica viável 
aplicando as operações de pivoteamento
Última solução 
obtida é ótima
 NÃO
 NÃO