Considere o seguinte PPL.
min & -x1+2 x2 & x1+2 x2 <= 4 & 3 x1+2 x2 <= 6 & x1, x2 >= 0
(1) Resolva o problema (10)-(13) usando o método simplex. Considere como base inicial as colunas
(a_{3}) e
(a_{4}), associadas as variáveis de folgas
(x_{3}) (restrição 7) e
(x_{4}) (restrição 8).
(2) Qual a solução otima?
(3) Qual o valor ótimo?

Passo 1

O enunciado dá um problema de programação linear no formato de minimização:
min;&f(x1,x2)=-x1+2x2, &x1+2x2<=4, &3x1+2x2<=6, &x1,x2>=0
O método simplex que vamos usar aqui requer colocar variáveis de folga x3 e x4 para transformar em igualdades e montar o tableau inicial com base x3,x4. Em seguida, aplicamos as regras de pivoteamento próprias para minimização (entrar a variável com coeficiente positivo na linha do objetivo e saída pela razão mínima).

Passo 2

Introduzimos as folgas e escrevemos o tableau canônico. As igualdades são
x1+2x2+x3=4, 3x1+2x2+x4=6,
e a forma canônica do objetivo é
f + x1 -2x2=0
No tableau isso dá
c|cccc|c Base&x1&x2&x3&x4&RHShline x3&1&2&1&0&4 x4&3&2&0&1&6hline f&1&-2&0&0&0

Passo 3

Procuramos na linha de f coeficientes positivos (regra de entrada para minimização). O coeficiente de x1 é +1, de x2 é -2. Logo, x1 entra na base. Fazemos a razão mínima apenas nas linhas com coeficiente positivo em x1:
RHSai1: 41=4, 63=2
O menor quociente é 2, na segunda linha, então x4 sai da base e pivoteamos na posição (linha x4,coluna x1).

Passo 4

Pivoteando na linha 2 coluna 1 (elemento 3):
  1. Novo pivô x1 na linha 2: dividimos a linha 2 por 3, x1 + tfrac23x2 + tfrac13x4=2
  2. Atualizamos linha 1: subtraímos 1 vez a nova linha 2 da linha 1, 0cdot x1 + tfrac43x2 +1cdot x3 -tfrac13x4=2
  3. Atualizamos linha do objetivo: subtraímos 1 vez a nova linha 2 da linha f, f - tfrac83x2 - tfrac13x4=-2
O tableau fica
c|cccc|c Base&x1&x2&x3&x4&RHShline x3&0&tfrac43&1&-tfrac13&2 x1&1&tfrac23&0&tfrac13&2hline f&0&-tfrac83&0&-tfrac13&-2

Passo 5

Na linha de f não há mais coeficientes positivos ( -tfrac83 e -tfrac13 são negativos e o de x3 é zero), logo chegamos à solução ótima do problema de minimização. Lemos da base:
x1=2, x2=0,
e substituindo em f obtemos
f^*=-x1+2x2=-2+0=-2

Resposta

A solução ótima é (x1,x2)=(2,0) e o valor ótimo é -2.

Exercícios relacionados