Solucione pelo método simplex, em sua forma de algoritmo, os problemas de otimização linear a seguir, indicando o valor ótimo z^{*} da função objetivo, o valor ótimo x^{*} do vetor de variáveis de decisão e a base ótima I^{*}. Indique, em cada caso, se a solução é ótima finita única, ótima finita múltipla ou ilimitada. Caso seja múltipla ou ilimitada, mostre o formato geral da solução, tanto para as variáveis de decisão quanto para a função objetivo. Compare, caso possível, cada iteração com os vértices encontrados na respectiva solução geométrica do mesmo problema.
\quad \max \quad z=2 x_{1}-x_{2}+x_{3}
suj a \quad 3 x_{1}+x_{2}+x_{3} \leq 50
x_{1}-x_{2}+x_{3} \leq 20
x_{1}+x_{2}-x_{3} \leq 8
x_{1} \geq 0
x_{2} \geq 0
x_{3} \geq 0

Passo 1

O enunciado pede: resolver por simplex (algoritmo) o problema de programação linear e indicar (1) o valor ótimo \,z^{*}, (2) o vetor ótimo \,x^{*} das variáveis de decisão, (3) a(s) base(s) ótima(s) I^{*}, e (4) se a solução é ótima finita única, ótima finita múltipla ou ilimitada. Se for múltipla ou ilimitada, mostrar a forma geral da solução (variáveis e função objetivo).\n
Informações dadas:
\begin{aligned} \max\quad & z = 2x_{1}-x_{2}+x_{3}\\[4pt] \text{s.a.}\quad & 3x_{1}+x_{2}+x_{3}\le 50\\\ & x_{1}-x_{2}+x_{3}\le 20\\\ & x_{1}+x_{2}-x_{3}\le 8\\\ & x_{1}\ge 0,\quad x_{2}\ge 0,\quad x_{3}\ge 0. \end{aligned}]

Passo 2

Passo inicial: transformar para a forma padrão (igualdades) adicionando variáveis de folga (slack) \,s_{1},s_{2},s_{3}\ge 0\). As equações ficam: \[\begin{cases} 3x_{1}+x_{2}+x_{3}+s_{1}=50,\\[4pt] x_{1}-x_{2}+x_{3}+s_{2}=20,\\[4pt] x_{1}+x_{2}-x_{3}+s_{3}=8. \end{cases}
A função objetivo em forma de equação (para o tableau) é
z-2x_{1}+x_{2}-x_{3}=0.
Inicialmente escolhemos a base formada pelas folgas \{s_{1},s_{2},s_{3}\}\], que corresponde à solução básica inicial \(x_{1}=x_{2}=x_{3}=0, s_{1}=50, s_{2}=20, s_{3}=8.]

Passo 3

Breve explicação do método simplex (algoritmo) que vou usar, passo a passo (sem pular etapas):
  • Montamos o tableau com variáveis na ordem \,x_{1},x_{2},x_{3},s_{1},s_{2},s_{3} e o RHS.
  • A linha da função (linha z) está na forma z - 2x_{1} + x_{2} - x_{3} = 0. No critério de entrada, para maximização, escolhemos a variável não-básica com coeficiente negativo mais “favorável” na linha z (pois esse coeficiente indica quanto aumenta z ao aumentar a variável).
  • Para a variável escolhida como entrante, aplicamos o teste da razão mínima \min\{\text{RHS}/\text{coef. positivo na coluna}\} para decidir qual variável básica sai (garante factibilidade).
  • Fazemos pivot (normalização da linha pivô e eliminação nas outras linhas).
  • Repetimos até que não haja coeficientes negativos na linha z (condição de otimalidade para maximização com esta convenção).
  • Se na otimalidade existir alguma variável não-básica com coeficiente zero na linha z, então há soluções ótimas múltiplas ao longo de um segmento; se alguma coluna permitir razão mínima infinita (nenhuma entrada positiva), o problema é ilimitado.

Passo 4

Tableau inicial (base \{s_{1},s_{2},s_{3}\}, ordem das colunas \,x_{1}\;x_{2}\;x_{3}\;s_{1}\;s_{2}\;s_{3}\;|\;\text{RHS}):
\begin{array}{c|rrrrrr|r} \text{Base} & x_{1} & x_{2} & x_{3} & s_{1} & s_{2} & s_{3} & \text{RHS}\\hline s_{1} & 3 & 1 & 1 & 1 & 0 & 0 & 50\\\ s_{2} & 1 & -1 & 1 & 0 & 1 & 0 & 20\\\ s_{3} & 1 & 1 & -1 & 0 & 0 & 1 & 8\\hline z & -2 & 1 & -1 & 0 & 0 & 0 & 0 \end{array}
A solução básica atual é (x_{1},x_{2},x_{3})=(0,0,0) com z=0.

Passo 5

Olho a linha z: coeficientes (-2,\;1,\;-1). Para maximização escolho a variável com coeficiente mais negativo: \,x_{1} (coeficiente -2) como entrante.
Teste de razão para coluna x_{1} (considero apenas linhas com coeficiente positivo na coluna):
\frac{50}{3}\approx 16{,}67,\quad \frac{20}{1}=20,\quad \frac{8}{1}=8.
A menor razão é 8 (linha de s_{3}), logo s_{3} sai; pivot em posição linha s_{3}, coluna x_{1}.
Fazendo operações de linha (dividir a linha pivô por 1 e zerar a coluna nas outras linhas) obtemos o novo tableau:
\begin{array}{c|rrrrrr|r} \text{Base} & x_{1} & x_{2} & x_{3} & s_{1} & s_{2} & s_{3} & \text{RHS}\\hline s_{1} & 0 & -2 & 4 & 1 & 0 & -3 & 26\\\ s_{2} & 0 & -2 & 2 & 0 & 1 & -1 & 12\\\ x_{1} & 1 & 1 & -1 & 0 & 0 & 1 & 8\\hline z & 0 & 3 & -3 & 0 & 0 & 2 & 16 \end{array}
Interpretação imediata: nova solução básica (com x_{2}=x_{3}=0, s_{2}=s_{3}=0 por serem não-básicas) é x_{1}=8, x_{2}=0, x_{3}=0, com z= RHS da linha z = 16. Geometricamente, o simplex saiu do vértice (0,0,0) e foi para o vértice (8,0,0).

Passo 6

Na linha z os coeficientes agora são (0,\;3,\;-3,\;0,\;0,\;2). Procuramos coeficientes negativos para maximizar; o mais negativo é -3 associado a x_{3}. Logo x_{3} entra.
Teste de razão na coluna x_{3} (apenas linhas com coeficiente positivo):
\frac{26}{4}=6{,}5,\quad \frac{12}{2}=6,\quad \frac{8}{-1}\\ \text{(não conta, coeficiente negativo)}.ã
Menor razão é 6 (linha de s_{2}), então s_{2} sai; pivot na entrada (linha s_{2}, coluna x_{3}).
Normalizando a linha s_{2} e eliminando a coluna x_{3} nas outras linhas, obtemos o tableau final:
\begin{array}{c|rrrrrr|r} \text{Base} & x_{1} & x_{2} & x_{3} & s_{1} & s_{2} & s_{3} & \text{RHS}\\hline s_{1} & 0 & 2 & 0 & 1 & -2 & -1 & 2\\\ x_{3} & 0 & -1 & 1 & 0 & 0{,}5 & -0{,}5 & 6\\\ x_{1} & 1 & 0 & 0 & 0 & 0{,}5 & 0{,}5 & 14\\hline z & 0 & 0 & 0 & 0 & 1{,}5 & 0{,}5 & 34 \end{array}
Agora a linha z não tem coeficientes negativos nas colunas de variáveis originais \,x_{1},x_{2},x_{3} (todos são zero nesta forma), portanto a condição de otimalidade é satisfeita: chegamos a uma solução ótima.
A solução básica correspondente (colocando as não-básicas igual a zero: aqui as não-básicas são x_{2},s_{2},s_{3}) é
x_{1}=14,\quad x_{2}=0,\quad x_{3}=6,
com valor objetivo
z^{*}=34.
Geometricamente, o simplex passou pelos vértices (0,0,0)\to(8,0,0)\to(14,0,6).

Passo 7

Na tabela final, observe que a coluna de x_{2} na linha z tem coeficiente zero (entrada 0). Isso significa que a variável não-básica x_{2} tem custo reduzido zero: podemos aumentar x_{2} sem alterar o valor de z até que alguma variável básica fique em zero (restrição de factibilidade). Vamos explorar esse movimento:
Usando o sistema representado pelo tableau final (leitura das equações básicas):
\begin{aligned} \text{(linha }s_{1})\\ &: \; s_{1}+2x_{2}-2s_{2}-s_{3}=2,\\[4pt] \text{(linha }x_{3})\\ &: \; -x_{2}+x_{3}+0{,}5s_{2}-0{,}5s_{3}=6,\\[4pt] \text{(linha }x_{1})\\ &: \; x_{1}+0{,}5s_{2}+0{,}5s_{3}=14. \end{aligned}
Se fixarmos as folgas s_{2}=s_{3}=0 (mantendo as correspondentes não-básicas como zero) e deixarmos x_{2}=t\ge 0 variável, as equações reduzem para
s_{1}=2-2t,\quad x_{3}=6+t,\quad x_{1}=14.
Para manter factibilidade precisamos de s_{1}\ge 0, logo 2-2t\ge 0\Rightarrow t\le 1. Assim obtemos um conjunto de soluções factíveis e todas com mesmo valor objetivo z=34. Portanto as soluções ótimas são infinitas ao longo do segmento parametrizado por t\in[0,1]:
x(t) = \bigl(14,\;t,\;6+t\bigr),\qquad 0\le t\le 1,
e para todo t neste intervalo z=34. Verificação rápida nas restrições:
\begin{aligned} 3x_{1}+x_{2}+x_{3} &= 3\cdot14 + t +(6+t)=48+2t\le 50 \Leftrightarrow t\le 1,\\\ x_{1}-x_{2}+x_{3} &=14-t+6+t=20,\\\ x_{1}+x_{2}-x_{3} &=14+t-(6+t)=8, \end{aligned}
ou seja, todas as soluções do tipo acima são factíveis e de mesma qualidade. Em particular os extremos do segmento são:
t=0\Rightarrow x=(14,0,6)\quad\text{(base obtida pelo simplex: }\{x_{1},x_{3},s_{1}\}\text{)},
t=1\Rightarrow x=(14,1,7)\quad\text{(outro vértice extremo, base } \{x_{1},x_{2},x_{3}\}\text{)}.é
Conclusão: existe uma aresta do politopo ótimo entre os dois vértices acima; o simplex encontrou um dos vértices extremos e a tabela revela a existência de ótimos múltiplos (coeficiente zero para variável não-básica).]

Passo 8

  • Valor ótimo: z^{*}=34.
  • Conjunto de soluções ótimas (infinitas): \;x(t)=(14,\;t,\;6+t),\;0\le t\le 1.
  • Uma base ótima encontrada pelo simplex é I^{*}=\{x_{1},x_{3},s_{1}\} (índices \{1,3,4\} na ordem que usamos). Outro vértice ótimo extremo tem base \{x_{1},x_{2},x_{3}\} (índices \{1,2,3\}).
  • Tipo de solução: ótima finita múltipla (infinitas soluções ótimas ao longo de um segmento).

Resposta

z^{*}=34
x^{*}=(14,\;t,\;6+t),\qquad 0\le t\le 1
I^{*}=\{x_{1},x_{3},s_{1}\}\\ (\text{uma base ótima};\\ \text{outro extremo ótimo: }\{x_{1},x_{2},x_{3}\})óó
Solução ótima: ótima finita múltipla.

Exercícios relacionados