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}
\begin{aligned} \text { suj. a } & \begin{aligned} x_{1}+2 x_{2}+3 x_{3}+x_{4} & \geq 3 \\ -2 x_{1}+x_{2}-x_{3}+3 x_{4} & \leq-4 \\ x_{1}, x_{2}, x_{3}, x_{4} & \geq 0 \end{aligned} \end{aligned}

Passo 1

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.
Dados do problema:
\begin{aligned} &\max\quad z=2x_{1}+3x_{2}+6x_{3}+8x_{4},\\[4pt] &\text{suj. a}\quad \begin{cases} x_{1}+2x_{2}+3x_{3}+x_{4} &\ge 3,\\[4pt] -2x_{1}+x_{2}-x_{3}+3x_{4} &\le -4,\\[4pt] x_{1},x_{2},x_{3},x_{4} &\ge 0. \end{cases} \end{aligned}
O que o enunciado pede explicitamente:
  • A solução ótima \;x^{*} (ou dizer que não existe se for o caso).
  • O conjunto ótimo de variáveis básicas I^{*}.
  • A matriz base inversa ótima A_{I^{*}}^{-1}.
  • O vetor multiplicador ótimo \pi^{*}.
  • O valor ótimo da função objetivo z^{*}.
  • Indicar se a solução é ótima única, ótima múltipla ou ilimitada.
  • Se for ótima múltipla ou ilimitada, apresentar o formato geral da solução (para variáveis e para z).
Observação importante (não resolvo nada aqui, só enumerei o que foi pedido).]

Passo 2

Primeiro colocamos o sistema na forma adequada para aplicar o simplex (introduzimos variáveis de excesso/sobra e artificiais quando necessário).
Começamos transformando a segunda restrição (que tem RHS negativo) multiplicando por -1 para obter uma forma mais conveniente:
-2x_1+x_2-x_3+3x_4\le -4 \quad\Longrightarrow\quad 2x_1 - x_2 + x_3 - 3x_4 \ge 4.
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):
\begin{array}{rcl} x_1+2x_2+3x_3+x_4 & - & s_1 + a_1 = 3,\\[4pt] 2x_1 - x_2 + x_3 -3x_4 & - & s_2 + a_2 = 4. \end{array}
Na Fase 1 vamos minimizar w=a_1+a_2 (equivalente a maximizar Z^{(1)}=-a_1-a_2). A base inicial natural é B=\{a_1,a_2\} com a_1=3,a_2=4.
Vou aplicar a técnica das duas fases (Fase 1 para eliminar artificiais e encontrar viabilidade, depois Fase 2 para otimizar a função original).]

Passo 3

Fase 1 — montar o tableau inicial e calcular custos reduzidos.
Matriz das colunas (cada coluna é o vetor de coeficientes nas equações, em duas linhas):
\begin{array}{c|cccccccc} & x_1 & x_2 & x_3 & x_4 & s_1 & s_2 & a_1 & a_2\\\ \hline \text{eq1} & 1 & 2 & 3 & 1 & -1 & 0 & 1 & 0\\\ \text{eq2} & 2 & -1 & 1 & -3 & 0 & -1 & 0 & 1 \end{array}
RHS b=\begin{pmatrix}3\\\ 4\end{pmatrix}. Base inicial B=[a_1,a_2], portanto B^{-1}=I. Custos na Fase 1 (maximização de Z^{(1)}=-a_1-a_2) são:
c_{x_1}=\cdots=c_{s_2}=0,\qquad c_{a_1}=c_{a_2}=-1.
Calculamos os custos reduzidos iniciais r_j = c_j - c_B^T B^{-1} A_j com c_B^T=[-1\\\ -1]. Fazendo as contas (detalhes aritméticos):
\begin{aligned} r_{x_1}&=0 -((-1)\cdot1+(-1)\cdot2)=3,\\\ r_{x_2}&=0 -((-1)\cdot2+(-1)\cdot(-1))=1,\\\ r_{x_3}&=0 -((-1)\cdot3+(-1)\cdot1)=4,\\\ r_{x_4}&=0 -((-1)\cdot1+(-1)\cdot(-3))=-2,\\\ r_{s_1}&=0 -((-1)\cdot(-1)+(-1)\cdot0)=-1,\\\ r_{s_2}&=0 -((-1)\cdot0+(-1)\cdot(-1))=-1,\\\ r_{a_1}&=-1 -((-1)\cdot1+(-1)\cdot0)=0,\\\ r_{a_2}&=-1 -((-1)\cdot0+(-1)\cdot1)=0. \end{aligned}
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].
A nova matriz base:
B = \begin{pmatrix}3 & 0\\[4pt]1 & 1\end{pmatrix}, \qquad B^{-1}=\frac{1}{3}\begin{pmatrix}1 & 0\\[4pt]-1 & 3\end{pmatrix}.
Valores básicos x_B = B^{-1} b:
x_B = \begin{pmatrix}1\\[4pt]3\end{pmatrix},
ou seja x_3=1,\\ a_2=3. Custos da base (na Fase 1) c_B^T=[0,\,-1] (porque c_{x_3}=0,\\ c_{a_2}=-1). O vetor multiplicador (preço relativo) é
\pi^T = c_B^T B^{-1} = [\,\tfrac{1}{3},\,-1\,].
Calculamos os custos reduzidos atuais r_j = c_j - \pi^T A_j; os que interessam são:
r_{x_1} = \tfrac{5}{3},\quad r_{x_2}=-\tfrac{5}{3},\quad r_{x_4}=-\tfrac{10}{3},\quad r_{s_1}=\tfrac{1}{3},\quad r_{s_2}=-1,\quad r_{a_1}=-\tfrac{4}{3}.
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 é
B=\begin{pmatrix}3 & 1\\[4pt]1 & 2\end{pmatrix},\qquad B^{-1}=\frac{1}{5}\begin{pmatrix}2 & -1\\[4pt]-1 & 3\end{pmatrix}.
Os valores básicos:
x_B = B^{-1} b = \frac{1}{5}\begin{pmatrix}2 & -1\\[4pt]-1 & 3\end{pmatrix}\begin{pmatrix}3\\[4pt]4\end{pmatrix} = \begin{pmatrix}2/5\\[4pt]9/5\end{pmatrix},
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)
\pi^T = c_B^T B^{-1} = [6,\;2]\cdot\frac{1}{5}\begin{pmatrix}2 & -1\\[4pt]-1 & 3\end{pmatrix} = \frac{1}{5}[10,\;0]=\bigl[\,2,\;0\,\bigr].
Agora os custos reduzidos r_j = c_j - \pi^T A_j (para não-básicas) são:
\begin{aligned} r_{x_2}&=3 - \pi^T A_{x_2} = 3 - (2\cdot2 + 0\cdot(-1)) = 3-4 = -1,\\[4pt] r_{x_4}&=8 - \pi^T A_{x_4} = 8 - (2\cdot1 + 0\cdot(-3)) = 8-2 = 6,\\[4pt] r_{s_1}&=0 - \pi^T A_{s_1} = 0 - (2\cdot(-1)+0\cdot0) = 2,\\[4pt] r_{s_2}&=0 - \pi^T A_{s_2} = 0 - (2\cdot0+0\cdot(-1)) = 0. \end{aligned}
Como r_{x_4}=6 é o maior positivo, escolhemos x_4 para entrar na base.
Fazemos o ratio test com a coluna A_{x_4}=[1,-3]^T. Calculamos B^{-1}A_{x_4}:
B^{-1}A_{x_4}=\frac{1}{5}\begin{pmatrix}2 & -1\\[4pt]-1 & 3\end{pmatrix}\begin{pmatrix}1\\[4pt]-3\end{pmatrix} =\frac{1}{5}\begin{pmatrix}5\\[4pt]-10\end{pmatrix}=\begin{pmatrix}1\\[4pt]-2\end{pmatrix}.
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:
B=\begin{pmatrix}1 & 1\\[4pt]-3 & 2\end{pmatrix},\qquad B^{-1}=\frac{1}{5}\begin{pmatrix}2 & -1\\[4pt]3 & 1\end{pmatrix}.
Os valores básicos resultantes são
x_B = B^{-1} b = \frac{1}{5}\begin{pmatrix}2 & -1\\[4pt]3 & 1\end{pmatrix}\begin{pmatrix}3\\[4pt]4\end{pmatrix} = \begin{pmatrix}2/5\\[4pt]13/5\end{pmatrix},
ou seja
x_4=\frac{2}{5},\qquad x_1=\frac{13}{5},
e x_2=x_3=0 no momento. Custos de base c_B^T=[8,\;2]. Então o multiplicador (vetor \pi^T) é
\pi^T = c_B^T B^{-1} = [8,\;2]\cdot\frac{1}{5}\begin{pmatrix}2 & -1\\[4pt]3 & 1\end{pmatrix} = \frac{1}{5}[22,\,-6] = \bigl[\,\tfrac{22}{5},\;-\tfrac{6}{5}\,\bigr].
Agora calculamos os custos reduzidos para as não-básicas (relevantes):
\begin{aligned} r_{x_2} &= 3 - \pi^T A_{x_2} = 3 -\Bigl(\tfrac{22}{5}\cdot2 + \bigl(-\tfrac{6}{5}\bigr)\cdot(-1)\Bigr) = 3 - 10 = -7,\\[6pt] r_{x_3} &= 6 - \pi^T A_{x_3} = 6 -\Bigl(\tfrac{22}{5}\cdot3 + \bigl(-\tfrac{6}{5}\bigr)\cdot1\Bigr) = 6 - 12 = -6,\\[6pt] r_{s_1} &= 0 - \pi^T A_{s_1} = 0 -\Bigl(\tfrac{22}{5}\cdot(-1) + \bigl(-\tfrac{6}{5}\bigr)\cdot0\Bigr)=\tfrac{22}{5}>0,\\[6pt] r_{s_2} &= 0 - \pi^T A_{s_2} = 0 -\Bigl(\tfrac{22}{5}\cdot0 + \bigl(-\tfrac{6}{5}\bigr)\cdot(-1)\Bigr) = -\tfrac{6}{5}. \end{aligned}
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
B^{-1} A_{s_1} = \frac{1}{5}\begin{pmatrix}2 & -1\\[4pt]3 & 1\end{pmatrix}\begin{pmatrix}-1\\[4pt]0\end{pmatrix} = \frac{1}{5}\begin{pmatrix}-2\\[4pt]-3\end{pmatrix} = \begin{pmatrix}-\tfrac{2}{5}\\[4pt]-\tfrac{3}{5}\end{pmatrix}.
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,
d_B = -B^{-1}A_{s_1} = -\begin{pmatrix}-\tfrac{2}{5}\\[4pt]-\tfrac{3}{5}\end{pmatrix} = \begin{pmatrix}\tfrac{2}{5}\\[4pt]\tfrac{3}{5}\end{pmatrix}.
Lendo as variáveis na ordem base B=[x_4,x_1], isto significa que ao aumentar s_1 em t\ge0 temos
\Delta x_4 = \tfrac{2}{5}t,\qquad \Delta x_1 = \tfrac{3}{5}t,\qquad \Delta s_1 = t,
e as demais variáveis não mudam.
Portanto a família de soluções factíveis é
\begin{aligned} x_1(t)&=\frac{13}{5}+\frac{3}{5}t,\\[4pt] x_2(t)&=0,\\[4pt] x_3(t)&=0,\\[4pt] x_4(t)&=\frac{2}{5}+\frac{2}{5}t,\\[4pt] s_1(t)&=0 + t,\\[4pt] s_2(t)&=0, \end{aligned}\qquad t\ge 0.
O incremento do objetivo por unidade de t é exatamente o custo reduzido r_{s_1}=\tfrac{22}{5}, logo
z(t)=z(0)+\frac{22}{5}t,
onde z(0) é o valor atual do objetivo para t=0. Calculamos z(0):
z(0)=2\cdot\frac{13}{5}+8\cdot\frac{2}{5}=\frac{26}{5}+\frac{16}{5}=\frac{42}{5}.
Assim
z(t)=\frac{42}{5}+\frac{22}{5}t\to +\infty\quad\text{quando }t\to+\infty.
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:
A_{I}^{-1}=\frac{1}{5}\begin{pmatrix}2 & -1\\[4pt]3 & 1\end{pmatrix}.
Vetor multiplicador associado a essa base:
\pi^{T}=\bigl[\,\tfrac{22}{5},\;-\tfrac{6}{5}\,\bigr].
Valor ótimo da função objetivo: z^{*}=+\infty (ilimitado). \n
Família geral de soluções factíveis que demonstra a ilimitade (para t\ge 0):
\begin{aligned} x_1(t)&=\dfrac{13}{5}+\dfrac{3}{5}t,\\[4pt] x_2(t)&=0,\\[4pt] x_3(t)&=0,\\[4pt] x_4(t)&=\dfrac{2}{5}+\dfrac{2}{5}t, \end{aligned} \qquad\text{com}\qquad z(t)=\dfrac{42}{5}+\dfrac{22}{5}t\to+\infty\\ \text{quando }t\to+\infty.]

Exercícios relacionados