Questão 19

Considere o PPL
max & x1+x2 & x1+2 x2 <= 6 & 5 x1+2 x2 <= 10 & x1, x2 >= 0
(1) Resolva o PPL utilizando o simplex revisado.
(2) Considere como base inicial as colunas a3 e a4 após colocar o problema na forma padrão.

Passo 1

O enunciado pede para resolver por simplex revisado o programa linear
max;&x1+x2 sa &x1+2x2<=6, &5x1+2x2<=10, &x1,x2>=0,
usando como base inicial as colunas a3 e a4 (as folgas) depois de pôr em forma padrão. O conteúdo é o método do simplex revisado: reformular em matriz, computar B^-1, multiplicadores pi, custos reduzidos bar c, determinar variável de entrada, direção, teste de razão, atualizar base até a optimalidade.

Passo 2

Colocando em forma padrão, introduzimos as variáveis de folga s1,s2 de modo que
x1+2x2+s1=6, 5x1+2x2+s2=10, x1,x2,s1,s2>=0
Escrevendo em forma matricial
A=l[a1;a2;a3;a4r] = 1&2&1&0 5&2&0&1 , b=610, c=1100
Base inicial B=a3,a4, então
B=1&00&1, B^-1=I, xB=B^-1b=610
Os multiplicadores são
pi^T=cB^TB^-1=(0,0),
e os custos reduzidos para não-básicas x1,x2 são
bar c1=c1-pi^Ta1=1, bar c2=c2-pi^Ta2=1
Como ambos são positivos, podemos entrar com x1 (menor índice).

Passo 3

Escolhida x1 como variável de entrada, calculamos a direção
d=B^-1a1=a1=15
Fazemos o teste da razão mínima em xB/d:
61=6, 105=2,
logo o mínimo é 2, e a variável de saída é s2 (coluna a4). Atualizando a base para B=a3,a1, temos
B=1&10&5, B^-1=155&-10&1
Então a nova solução básica é
xB=B^-1b =155&-10&1610 =42,
isto é, s1=4,;x1=2. Os custos básicos agora são cB=(0,1) e
pi^T=cB^TB^-1=(0,1)155&-10&1 =l(0,tfrac15r)
O custo reduzido de x2 é
bar c2=1-pi^Ta2 =1-l(0,tfrac15r)!cdot!(2,2) =1-tfrac25=tfrac35>0,
logo x2 entra. O custo reduzido de s2 fica negativo e não entra.

Passo 4

Para x2 como entrada, a direção é
d=B^-1a2 =155&-10&122 =8/52/5
Teste da razão mínima em ,(s1,x1)/d:
48/5=2,5, 22/5=5,
o mínimo é 2,5, então sai s1 (coluna a3). A base torna-se B=a1,a2, isto é, x1,x2 básicos.
B=1&25&2, B^-1=1-82&-2-5&1 =-tfrac14&tfrac14tfrac58&-tfrac18
A solução é
xB=B^-1b =-tfrac14&tfrac14tfrac58&-tfrac18 610 =12,5,
ou seja x1=1,;x2=2,5. Os novos multiplicadores são
pi^T=(1,1)B^-1 =l(tfrac38,tfrac18r),
e os custos reduzidos de s1,s2 são negativos, indicando optimalidade.

Resposta

A solução ótima é
x1=1, x2=2,5, zmax=1+2,5=3,5

Exercícios relacionados