15.053
14 de fevereiro de 2002
• Colocando Programas Lineares na forma padrão
• Introdução ao Algoritmo Simplex
• Obs.: esta apresentação é projetada com animação para ser
vista como apresentação de slides.
1
Programas Lineares em Forma
Padrão
1. Restrições de não-negatividade para todas as
variáveis.
2. Todas as restrições restantes são expressas
como restrições de igualdade.
3. O vetor do lado direito, b, é não-negativo.
Uma PL fora da Forma-Padrão
2
Convertendo Desigualdades em
Igualdades
Antes
x1 + 2x2 + x3 - x4 =5
Depois
x1 + 2x2 + x3 - x4 +s = 5
s=0
s é chamado de variável de transigência (slack),
que mede a quantidade de “recurso não utilizado”.
Observe que s = 5 - x1 - 2x2 - x3 + x4.
Para converter um “=” em uma igualdade,
adicione uma variável de transigência
(slack).
3
Convertendo restrições “=”
• Considere a desigualdade -2x1 - 4x2 + x3 + x4 = -1;
• Passo 1. Elimine o RHS negativo
2x1 + 4x2 - x3 - x4 = 1
• Passo 2. Converta para uma igualdade
2x1 + 4x2 - x3 - x4 - s = 1
s =0
• A variável adicionada será chamada de “variável de
sobra” (surplus).
Para converter uma restrição “=” em
igualdade, subtraia uma variável de sobra
(surplus).
4
Mais Transformações
Como é possível converter um problema de
maximização em um problema de minimização?
Exemplo: Maximizar 3W + 2P
Sujeito a “restrições”
Possui as mesmas soluções ótimas de
Minimize -3W -2P
Sujeito a “restrições”
5
As Últimas Transformações (por hora)
Transformando variáveis que podem assumir valores
negativos.
maximizar 3x1 + 4x2 + 5 x3
Sujeito a
2x1 - 5x2 + 2x3 = 17
outras restrições
x1 = 0, x2 é irrestrito em sinal, x3 = 0
Transformando x1: substitua x1 por y1 = -x1; y1 = 0.
máx -3 y1 + 4x2 +5 x3
-2 y1 -5 x2 +2 x3 = 17
y1 = 0, x2 é irrestrito em sinal, x3 = 0
É possível recuperar x1 de y1.
6
Transformando variáveis que podem
assumir valores negativos.
máx -3 y1 + 4x2 +5 x3
-2 y1 -5 x2 +2 x3 =17
y1 =0, x2 é irrestrito em sinal, x3 = 0
Transformando x2: substitua x2 por x2 = y3 - y2; y2 =
0, y3 = 0.
máx -3 y1 + 4(y3 - y2) +5 x3
-2 y1 -5 y3 +5 y2 +2 x3 = 17
todas as vars = 0
É possível recuperar x2 de y2, y3.
7
Outro Exemplo
• Exercício: transforme a equação a seguir na
forma-padrão (maximização):
Minimize
Sujeito a
x1 + 3x2
2x1 + 5x2 = 12
x1 + x2 = 1
x1 = 0
Faça a transformação com seu colega
8
Apresentação do Algoritmo Simplex
maximizar
sujeito a
z = -3x1 + 2x2
-3x1 + 3x2 +x3
-4x1 + 2x2 + x4
x1, x2, x3, x4 =0
=6
=2
9
Forma Canônica da PL =
Forma-Padrão da PL + Forma Canônica de Jordan
não é uma
variável de
decisão
As variáveis básicas são x3 e x4.
As variáveis não-básicas são x1 e x2.
A solução básica viável é x1 = 0, x2 = 0, x3 = 6, x4 = 2
10
Para cada restrição, há uma variável básica
Restrição 1
Restrição 2
Restrição 1: a variável básica é x3
Restrição 2: a variável básica é x4
A base é formada pelas variáveis x3 e x4
11
Apresentação das Condições de Otimalidade
Obs.:
z = -3x1 + 2x2
Fato óbvio: se for possível melhorar a solução x
viável básica atual, então x não será ótimo.
Idéia: atribuir um pequeno valor para apenas uma
das variáveis não-básicas e depois ajustar as
variável básicas.
12
A solução básica viável atual não é ótima!
Se houver um
coeficiente
positivo na
linha z, a base
não é ótima**
Lembre-se: z = -3x1 + 2x2
Aumente x2 para > 0. Faça x1 ficar em 0.
O que acontece a x3, x4 e z? .
13
Condições de Otimalidade
(observe que os dados são diferentes aqui)
Fato Importante.
Se não houver
coeficiente positivo
na linha z, a
solução básica
viável é ótima!
z = -2x1 - 4x2 + 8.
Portanto z =8 para todas as soluções viáveis.
Mas z = 8 na solução básica viável atual
Esta solução básica viável é ótima!
14
Faça x2 = ?. Qual o tamanho que ? pode ficar?
Qual é a solução depois de trocar x2?
Qual é o valor de ? que maximiza z, mas deixa
uma solução viável?
? = 1.
Fato. A solução resultante é a solução
básica viável para uma base diferente.
15
Fazendo o "pivotamento" para obter uma
solução melhor
Nova Solução: as variáveis
básicas são x2 e x3.
Não-básicas: x1 e x4.
Se fizermos o "pivotamento" no coeficiente 2,
obteremos a nova solução básica viável.
16
Resumo do Algoritmo Simplex
• Inicia na forma canônica com uma solução
básica viável
1. Verifica condições otimalidade
2. Se não for ótima, determine uma variável não
básica que deve ser feita positiva
3. Aumente essa variável não-básica e realize um
"pivotamento", obtendo uma nova solução básica
viável
4. Continue até o ótimo (ou ilimitado).
17
OK. Vamos iterar novamente.
z = x1 - x2 + 2
O coeficiente de custo de x1 é positivo.
Faça x1 = ? e x4 = 0.
Qual o tamanho que ? pode ter?
18
Digressão: E se tivéssemos um problema no
qual pudéssemos aumentar para o infinito?
Suponha que troquemos o 3 para um –3. Se os não-coeficientes
Faça x1 = ? e x4 = 0.
de custo na coluna de
Qual o tamanho que ? pode ter?
entrada forem =0,
então a solução é
ilimitada.
19
Digressão Final: Faça outro "pivotamento"
Qual é o maior valor de ??
?=1
A variável x1 se torna a base, x3 se torna não-básica.
Faça um "pivotamento" no coeficiente com um 3.
20
Verifique a otimalidade
Não há coeficiente positivo na linha z.
A solução básica viável atual é ótima!
21
Novo Resumo do Algoritmo Simplex
? Inicie na forma canônica com uma solução
básica viável
1. Verifique as condições de otimalidade.
? Há um coeficiente positivo na linha de custo?
2. Se não for ótima, determine uma variável nãobásica que deve ser feita positiva
? Escolha uma variável com um coeficiente positivo
na linha de custo.
3. Aumente essa variável não-básica e realize um
"pivotamento", obtendo uma nova solução básica
viável
? Iremos revisar este passo e mostrar um atalho
4. Continue até atingir o ótimo (ou ilimitado).
22
Realizando um “pivotamento”. Em direção ao
atalho.
z = 2x1 + 3
Exercício: para fazer
com seu colega.
1. Determine qual o tamanho que ? pode ter.
2. Determine a solução seguinte.
3. Determine sobre qual coeficiente deve-se fazer o "pivotamento".
23
4. Veja se há um atalho para encontrar o coeficiente.
Mais sobre a realização de um
"pivotamento"
• Para determinar a coluna na qual realizar um
"pivotamento", selecione uma variável com
um coeficiente de custo positivo
• Para determinar uma linha qual realizar um
"pivotamento", selecione um coeficiente de
acordo com a regra de proporção mínima
• Execução de um pivotamento com se faz na
resolução de um sistema de equações.
24
Próxima Aula
• Revisão do Algoritmo Simplex
• Formalizando o Algoritmo Simplex
• Como descobrir uma solução básica viável
inicial, se existir
• Uma prova de que o Algoritmo Simplex é finito
(assumindo a não-degeneração)
25