Question 3. (2.0) Considere o seguinte PPL.
(a) Coloque o PPL na forma padrão.
(b) Resolva o PPL utilizando o método simplex revisado. Considere como base inicial
.
(b) Resolva o PPL utilizando o método simplex revisado. Considere como base inicial
Passo 1
Temos um problema de programação linear cujo enunciado é
O conteúdo é transformação em forma padrão e solução por método simplex revisado. Para isso vamos:
- Introduzir variáveis de folga e escrever as equações em forma padrão.
- Montar as matrizes
, e vetor de custos . - Escolher base inicial (slacks), calcular
, custos reduzidos e iterar até a optimalidade.
Passo 2
Definimos as variáveis de folga
para as três restrições, obtendo a forma padrão
Passo 3
Organizamos as matrizes do problema. Na ordem de variáveis
(x1,x2,a3,a4,a5) temos
Escolhemos como base inicial os slacks
B=[a3,a4,a5] . Então
e a solução básica inicial é
Passo 4
Calculamos o vetor de preços dual
e os custos reduzidos para as não-básicas
x1,x2 :
Como
bar c1>0 ,
x1 entra na base.
Passo 5
O vetor direção para
x1 é
Aplicamos teste de razão
logo a variável que sai é
a4 (segunda componente da base).
Passo 6
Fazendo o pivô, a nova base é
[a3,x1,a5] . Atualizamos
Isto dá a solução básica
(a3,x1,a5)=(1,2,4) , ou seja
Passo 7
Recalculamos
pi^T=cB^TB^-1=(0,3,0) e os custos reduzidos das não-básicas
x2,a4 :
Como todos
bar cj<=0 , atingimos a optimalidade.
Resposta
(a) Forma padrão:
(b) Pelo método simplex revisado, a solução ótima é