Question 3. (2.0) Considere o seguinte PPL.
max 3 x1-2 x2 x1+x2 <= 3 x1 <= 2 x2 <= 4 x1, x2 >= 0
(a) Coloque o PPL na forma padrão.
(b) Resolva o PPL utilizando o método simplex revisado. Considere como base inicial B=[lla3 & a4].

Passo 1

Temos um problema de programação linear cujo enunciado é
max;&3x1-2x2 sa;&x1+x2<=3, &x1<=2, &x2<=4, &x1,x2>=0
O conteúdo é transformação em forma padrão e solução por método simplex revisado. Para isso vamos:
  1. Introduzir variáveis de folga e escrever as equações em forma padrão.
  2. Montar as matrizes A, b e vetor de custos c.
  3. Escolher base inicial (slacks), calcular B^-1, custos reduzidos e iterar até a optimalidade.

Passo 2

Definimos as variáveis de folga ;a3,a4,a5 para as três restrições, obtendo a forma padrão
x1+x2+a3=3, x1+a4=2, x2+a5=4, x1,x2,a3,a4,a5>=0

Passo 3

Organizamos as matrizes do problema. Na ordem de variáveis (x1,x2,a3,a4,a5) temos
A = 1 & 1 & 1 & 0 & 0 1 & 0 & 0 & 1 & 0 0 & 1 & 0 & 0 & 1 , b = 324, c = 3-2000
Escolhemos como base inicial os slacks B=[a3,a4,a5]. Então
AB=I3, B^-1=I3, cB=(0,0,0)^T,
e a solução básica inicial é
xB=B^-1b=b=(3,2,4)^T, xN=(x1,x2)=(0,0)

Passo 4

Calculamos o vetor de preços dual
pi^T=cB^TB^-1=(0,0,0)
e os custos reduzidos para as não-básicas x1,x2:
bar c1=c1-pi^Ta1=3-0=3, bar c2=c2-pi^Ta2=-2-0=-2
Como bar c1>0, x1 entra na base.

Passo 5

O vetor direção para x1 é
d=B^-1a1=a1=110
Aplicamos teste de razão
theta^*=minltfrac31,,tfrac21r=2,
logo a variável que sai é a4 (segunda componente da base).

Passo 6

Fazendo o pivô, a nova base é [a3,x1,a5]. Atualizamos
B^-1long<=ftarrow 1 & -1 & 0 0 & 1 & 0 0 & 0 & 1 , xB=B^-1b=124
Isto dá a solução básica (a3,x1,a5)=(1,2,4), ou seja
x1=2,;x2=0,;a3=1,;a4=0,;a5=4

Passo 7

Recalculamos pi^T=cB^TB^-1=(0,3,0) e os custos reduzidos das não-básicas x2,a4:
bar c2=-2-l(0,3,0r)cdot101=-2, bar c4=0-l(0,3,0r)cdot010=-3
Como todos bar cj<=0, atingimos a optimalidade.

Resposta

(a) Forma padrão:
x1+x2+a3=3, x1+a4=2, x2+a5=4, x1,x2,a3,a4,a5>=0
(b) Pelo método simplex revisado, a solução ótima é
x1=2, x2=0, zmax=3cdot2-2cdot0=6

Exercícios relacionados