Questão 27

Considere o PPL
max & x1-2 x2 & x1+2 x2 <= 4 & 3 x1+2 x2 <= 6 & x1, x2 >= 0
(1) Resolva o PPL através do métodos simplex revisado. Considere como base inicial as colunas a3 e a4 da forma padrão.
(2) Qual a solução e valor ótimo?

Passo 1

O enunciado pede para resolver o PPL
max;&x1-2x2 sujeito a &x1+2x2<=4, &3x1+2x2<=6, &x1,x2>=0
usando o método simplex revisado, partindo da base inicial formada pelas variáveis de folga x3 e x4. Vamos precisar montar a base inicial, calcular o vetor dos multiplicadores dual y^T=cB^TB^-1, obter os custos reduzidos bar cj=cj-y^Taj, escolher variável que entra, fazer teste de razão e iterar até que todos os bar cj<=0.

Passo 2

Na forma padrão introduzimos as folgas x3,x4 e obtemos
A= 1&2&1&0 3&2&0&1 , b=46, c=(1,-2,0,0)
A base inicial é B=[a3;a4]=I2 com cB=(0,0)^T. Logo
y^T=cB^TB^-1=(0,0),
e os custos reduzidos das não-básicas x1,x2 são
bar c1=1-(0,0)cdot13=1, bar c2=-2-(0,0)cdot22=-2
Como bar c1=1>0, x1 entra na base.

Passo 3

Calculamos a direção de aumento
d=B^-1a1=1&00&1 13=13
Aplicamos o teste de razão sobre b=(4,6)^T:
41=4, 63=2;longrightarrow; min=2
logo a variável que sai é x4.

Passo 4

A nova base é B=[a3;a1]=1&10&3. Seu inverso é
B^-1=1&-tfrac130&tfrac13,
e a nova solução básica é
xB=B^-1b =1&-tfrac130&tfrac13 46 =22,
isto é, x3=2, x1=2. O valor da função-objetivo é
z=cB^TxB=(0,1)cdot22=2

Passo 5

Recalculamos y^T=cB^TB^-1=(0,1)1&-tfrac130&tfrac13=(0,tfrac13).
Os custos reduzidos das não-básicas x2,x4 são
bar c2=-2-(0,tfrac13)cdot22 =-2-tfrac23=-tfrac83, bar c4=0-(0,tfrac13)cdot01=-tfrac13
Como ambos são negativos, a solução é ótima.

Resposta

A solução ótima é
(x1,x2)=(2,0),
com valor ótimo
zmax=2

Exercícios relacionados