Solucione pelo método simplex, em sua forma de tabela, os problemas de otimização linear a seguir, apresentando a solução ótima x^{*}, o conjunto ótimo de variáveis básicas I^{*}, a matriz base inversa ótima A_{I^{*}}^{-1}, o vetor multiplicador ótimo
(\pi^{*}) e o valor ótimo da função objetivo z^{*}. Indique, em cada caso, se a solução é ótima única, ótima múltipla ou ilimitada. Caso seja ótima 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. \quad \max \quad z=2 x_{1}+3 x_{2}+6 x_{3}+8 x_{4}
O enunciado pede: usar o método simplex em forma de tabela para resolver o seguinte problema de programação linear e informar vários objetos da solução.
Agora ambas as restrições ficam do tipo ``\ge’’. Introduzimos para cada restrição uma variável de excesso (surplus) s_i\ge0 e uma variável artificial a_i\ge0 para obter igualdade inicial com a_i na base:
Equações padrão (colunas na ordem x_1,x_2,x_3,x_4,s_1,s_2,a_1,a_2):
Escolhemos a variável com maior custo reduzido positivo para entrar na base: \,x_3 (com r_{x_3}=4).
Razões para o teste de pivot (ratio test): as componentes da coluna A_{x_3} são [3,1]^T e b=[3,4]^T, então as razões válidas são 3/3=1 e 4/1=4. A menor razão é 1 (linha 1), logo sai a_1. Fazemos o pivot em (linha1,coluna x_3).
Passo 4
Após o primeiro pivot (entrando x_3, saindo a_1) a nova base é B=[x_3,a_2].
O maior reduzido positivo é r_{x_1}=\tfrac{5}{3}, então x_1 entra. Ratio test com coluna A_{x_1}=[1,2]^T e B^{-1}A_{x_1}=[\tfrac{1}{3},\tfrac{5}{3}]^T dá razões 1/(\tfrac{1}{3})=3 e 3/(\tfrac{5}{3})=\tfrac{9}{5}=1{,}8. A menor razão é \tfrac{9}{5}, correspondente à segunda linha — sai a_2.]
Passo 5
Após pivot (entrando x_1, saindo a_2) obtemos a base B=[x_3,x_1]. A matriz base é
ou seja x_3=\tfrac{2}{5},\\ x_1=\tfrac{9}{5}. Na Fase 1 os custos de base agora são zeros (c_{x_3}=c_{x_1}=0), então \pi^T=0 e todos os custos reduzidos são simplesmente os c_j da Fase 1; como os artificiais a_1,a_2 têm custo -1 e estão fora da base e seus valores são zero, o valor da Fase 1 w=a_1+a_2=0 foi alcançado — encontramos solução factível para o problema original (as artificiais foram eliminadas da base).
Concluímos a Fase 1 com uma solução básica viável (sem artificiais na base): base atual B=[x_3,x_1], B^{-1}=\dfrac{1}{5}\begin{pmatrix}2 & -1\\[4pt]-1 & 3\end{pmatrix} e x_3=\tfrac{2}{5},\\ x_1=\tfrac{9}{5}. As demais variáveis (incluindo x_2,x_4,s_1,s_2) estão temporariamente em zero.
Agora passamos à Fase 2 (retomando a função objetivo original).]
Passo 6
Fase 2 — aplicar o simplex para a função original \max z=2x_1+3x_2+6x_3+8x_4.
Na base atual B=[x_3,x_1] os custos da função original são c_B^T=[6,\;2] (porque c_{x_3}=6,\\ c_{x_1}=2). Calculamos o vetor multiplicador (preço relativo)
Somente a primeira componente é positiva (1), portanto a razão válida é x_{3}/1=(2/5)/1=2/5. Logo ocorre pivot na linha 1 e x_3 sai da base; entra x_4.]
Passo 7
Após esse pivot a nova base é B=[x_4,x_1]. A matriz base e sua inversa são:
Observamos que r_{s_1}=\tfrac{22}{5}>0, ou seja aumentar s_1 aumentaria o valor objetivo. Para ver se existe um limite (razão finita) aplicamos o ratio test com a coluna A_{s_1}=[-1,0]^T. Calculamos
Todas as componentes de B^{-1}A_{s_1} são não positivas. Isso significa que, ao aumentar s_1 (variável não básica) em \theta>0, os componentes básicos mudam segundo
x_B(\theta) = x_B(0) - \theta\, B^{-1}A_{s_1},
mas como B^{-1}A_{s_1}\le 0 componente a componente, temos -B^{-1}A_{s_1}\ge 0, portanto todos os componentes básicos aumentam quando \theta aumenta, e nenhum componente básico tende a zero para limitar \theta. Assim não existe razão finita — o problema é ilimitado (unbounded): podemos aumentar s_1 indefinidamente e o valor objetivo cresce sem limite.
Para caracterizar a direção de aumento e a família de soluções factíveis que faz z crescer, calculamos o vetor direção d correspondente ao aumento de s_1 (entrante):
A componente da variável entrante s_1 vale 1 em d.
As componentes básicas mudam com d_B = -\,B^{-1}A_{s_1}. Calculando,
Concluímos: o problema é ilimitado (ilimitado para maximização); não existe solução ótima finita.]
Resposta
Solução ótima: não existe (problema ilimitado; z\to+\infty).\n
Conjunto de variáveis básicas no vértice onde a ilimitade foi detectada: I=\{x_{4},x_{1}\}.\n
Matriz base inversa nessa base: