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=15 x_{1}+6 x_{2}+9 x_{3}+2 x_{4}
\begin{array}{rl} \text { suj. a } & 2 x_{1}+x_{2}+5 x_{3}+6 x_{4} \leq 20 \\ & 3 x_{1}+x_{2}+3 x_{3}+25 x_{4} & \leq 24 \\ & 7 x_{1}+x_{4} & \leq 70 \\ x_{i} \geq 0 & i=1, \ldots 4 \end{array}

Passo 1

Vamos deixar claro o que o enunciado pede e quais dados temos.
  • Problema: maximizar a função objetivo
\max\quad z=15x_{1}+6x_{2}+9x_{3}+2x_{4}
sujeito a
\begin{array}{rl} 2x_{1}+x_{2}+5x_{3}+6x_{4} & \le 20\\[4pt] 3x_{1}+x_{2}+3x_{3}+25x_{4} & \le 24\\[4pt] 7x_{1}+x_{4} & \le 70\\[4pt] x_i\ge 0,& i=1,\dots,4. \end{array}
  • O enunciado pede, pela forma de tabela do método simplex:
    • a solução ótima x^{*} (valores de x_{1},x_{2},x_{3},x_{4}),
    • 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 z^{*},
    • e se a solução é única, múltipla ou ilimitada. Caso fosse múltipla ou ilimitada, pediria o formato geral das soluções — aqui avaliaremos isso ao final.
  • Informações importantes que usaremos:
    • Precisamos introduzir variáveis de folga (slack) s_{1},s_{2},s_{3} para transformar as desigualdades em igualdades.
    • A matriz de restrições (colunas de x_{1},x_{2},x_{3},x_{4}) e o vetor b (termos à direita) serão usados para formar a base inicial.
    • A solução inicial básica factível óbvia é x_{1}=x_{2}=x_{3}=x_{4}=0 com s_{1}=20,\;s_{2}=24,\;s_{3}=70.]

Passo 2

Colocando o problema em forma padrão (introduzindo slacks). As restrições ficam:
\begin{aligned} 2x_{1}+x_{2}+5x_{3}+6x_{4}+s_{1} &= 20,\\\\ 3x_{1}+x_{2}+3x_{3}+25x_{4}+s_{2} &= 24,\\\\ 7x_{1}+x_{4}+s_{3} &= 70, \end{aligned}
com x_{i},s_{j}\ge 0. A base inicial natural é I^{(0)}=\{s_{1},s_{2},s_{3}\} com custos c_{s_1}=c_{s_2}=c_{s_3}=0.
Escrevo as colunas da matriz de restrições A (cada coluna é a coluna de uma variável):
\begin{array}{c|ccc} & \text{eq1} & \text{eq2} & \text{eq3}\\hline x_{1} & 2 & 3 & 7\\\ x_{2} & 1 & 1 & 0\\\ x_{3} & 5 & 3 & 0\\\ x_{4} & 6 & 25 & 1\\\ s_{1} & 1 & 0 & 0\\\ s_{2} & 0 & 1 & 0\\\ s_{3} & 0 & 0 & 1 \end{array} \quad\text{e}\quad b=\begin{pmatrix}20\\[2pt]24\\[2pt]70\end{pmatrix}.]

Passo 3

Montamos a tabela simplex inicial. Para ser didático, vou mostrar as linhas correspondentes às equações e a linha de custo reduzido (os c_j - \pi^T a_j; no inicial \pi=\mathbf{0} e então os reduzidos são simplesmente os custos c_j).
Tabela inicial (colunas pela ordem x_{1},x_{2},x_{3},x_{4},s_{1},s_{2},s_{3} e RHS):
\begin{array}{c|ccccccc|c} \text{base} & x_{1} & x_{2} & x_{3} & x_{4} & s_{1} & s_{2} & s_{3} & \text{RHS}\\hline s_{1} & 2 & 1 & 5 & 6 & 1 & 0 & 0 & 20\\\ s_{2} & 3 & 1 & 3 & 25 & 0 & 1 & 0 & 24\\\ s_{3} & 7 & 0 & 0 & 1 & 0 & 0 & 1 & 70\\hline \text{\text{(c)}} & 15 & 6 & 9 & 2 & 0 & 0 & 0 & 0 \end{array}
Explicação prática do método (resumo): a cada iteração selecionamos uma variável não básica com custo reduzido positivo para entrar na base (aquela que aumenta z mais rápido) e determinamos qual variável básica sai pela razão mínima \min \{ \text{RHS}_i / a_{i,\text{enter}} : a_{i,\text{enter}}>0\}. Depois fazemos pivot (Gauss-Jordan) para atualizar a tabela. Repetimos até todos os custos reduzidos serem \le 0 (termos c_j - \pi^T a_j \le 0 para maximização), o que garante ótimalidade.

Passo 4

Primeira iteração: escolha da variável que entra.
  • Os custos reducidos iniciais são c_j (pois \pi=\mathbf{0}). O maior custo é c_{1}=15, então escolhemos x_{1} como variável que entra.
  • Determinamos quem sai pela razão mínima usando a coluna de x_{1}: coeficientes (2,3,7) e razões \frac{20}{2}=10,\quad \frac{24}{3}=8,\quad \frac{70}{7}=10.A menor razão é 8, na segunda equação; logo s_{2} sai da base e x_{1} entra. Pivotamos na entrada (linha 2, coluna x_{1}, elemento 3).

Passo 5

Fazendo o pivot para x_{1} (normalização da linha 2 e eliminação nas outras linhas).
  • Linha 2 (pivot) dividida por 3:
\text{(nova linha 2)}:\quad x_{1}+{\tfrac{1}{3}}x_{2}+1x_{3}+{\tfrac{25}{3}}x_{4}+0\cdot s_{1}+{\tfrac{1}{3}}s_{2}+0\cdot s_{3}=8.
  • Eliminamos x_{1} das outras linhas:
    • Linha 1 ← Linha1 − 2 × (nova Linha2)
    • Linha 3 ← Linha3 − 7 × (nova Linha2)
Após os cálculos obtemos (vou mostrar as linhas resultantes):
\begin{array}{c|ccccccc|c} \text{base} & x_{1} & x_{2} & x_{3} & x_{4} & s_{1} & s_{2} & s_{3} & \text{RHS}\\hline s_{1} & 0 & \tfrac{1}{3} & 3 & -\tfrac{32}{3} & 1 & -\tfrac{2}{3} & 0 & 4\\\ x_{1} & 1 & \tfrac{1}{3} & 1 & \tfrac{25}{3} & 0 & \tfrac{1}{3} & 0 & 8\\\ s_{3} & 0 & -\tfrac{7}{3} & -7 & -\tfrac{172}{3} & 0 & -\tfrac{7}{3} & 1 & 14 \end{array}
  • O novo valor parcial da função objetivo (em termos de base) é z = c_B^T \cdot \text{RHS} = 15\cdot 8 = 120 (a base atual é \{s_{1},x_{1},s_{3}\} com custos 0,15,0).

Passo 6

Segunda iteração: escolha da variável que entra.
  • Calculamos os custos reduzidos r_j = c_j - \pi^T a_j. Com a base atual \{s_{1},x_{1},s_{3}\} e \pi associado (não precisamos formar \pi explicitamente aqui), podemos usar a tabela transformada: os coeficientes das colunas já são A_{B}^{-1} A_{j}. Multiplicando pela c_B obtemos os termos \pi^T a_j. De forma prática, basta observar os coeficientes resultantes: para x_{2} a combinação dá \pi^T a_{2}=15\cdot \tfrac{1}{3}=5, logo o custo reduzido de x_{2} é 6-5=1>0. Para x_{3} e x_{4} os custos reduzidos ficam negativos.
  • Então x_{2} tem custo reduzido positivo e entra na base.
Para decidir quem sai, olhamos a coluna de x_{2} na tabela atual: coeficientes \bigl(\tfrac{1}{3},\tfrac{1}{3},-\tfrac{7}{3}\bigr). As razões positivas são:
\frac{\text{RHS}_1}{1/3}=\frac{4}{1/3}=12,\qquad \frac{\text{RHS}_2}{1/3}=\frac{8}{1/3}=24,
a terceira linha tem coeficiente negativo e não participa. A menor razão é 12 na linha 1, então s_{1} sai e x_{2} entra. Pivotamos na linha 1, coluna x_{2} (elemento 1/3).

Passo 7

Pivot para x_{2}: normalizamos a linha 1 dividindo por 1/3 (multiplicando por 3) e eliminamos x_{2} nas outras linhas.
  • Nova linha 1 (após dividir por 1/3):
x_{2}+9x_{3}-32x_{4}+3s_{1}-2s_{2}=12.
  • Eliminando x_{2} das outras linhas (linha 2 e linha 3), obtemos a tabela final:
\begin{array}{c|ccccccc|c} \text{base} & x_{1} & x_{2} & x_{3} & x_{4} & s_{1} & s_{2} & s_{3} & \text{RHS}\\hline x_{2} & 0 & 1 & 9 & -32 & 3 & -2 & 0 & 12\\\ x_{1} & 1 & 0 & -2 & 19 & -1 & 1 & 0 & 4\\\ s_{3} & 0 & 0 & 14 & -132 & 7 & -7 & 1 & 42 \end{array}

Passo 8

Teste de ótimalidade e interpretação final.
  • Agora a base é \{x_{2},x_{1},s_{3}\} (ordem das linhas: linha1 \to x_{2}, linha2 \to x_{1}, linha3 \to s_{3}). Calculamos os custos reduzidos r_j = c_j - \pi^T a_j (pelo método da tabela, isso equivale a computar c_j - c_B^T\cdot(\text{coluna }j \text{ na tabela})). Podemos verificar:
    • Para x_{3}: o valor c_3 - \pi^T a_3 = 9 - 24 = -15 (negativo).
    • Para x_{4}: 2 - 93 = -91 (negativo).
    • As demais variáveis não-básicas (aqui x_{3},x_{4},s_{1},s_{2}) têm custos reduzidos \le 0.
  • Como todos os custos reduzidos das variáveis não básicas são \le 0, a solução atual é ótima para maximização.
A solução básica extraída da tabela (valores das variáveis básicas na RHS, não-básicas zero) é:
x_{1}=4,\qquad x_{2}=12,\qquad x_{3}=0,\qquad x_{4}=0.
Os valores de folga: s_{1}=0,\;s_{2}=0,\;s_{3}=42.
O valor ótimo da função objetivo é
z^{*}=15\cdot 4 + 6\cdot 12 + 9\cdot 0 + 2\cdot 0 = 60 +72 =132.

Passo 9

Cálculo da matriz base inversa ótima A_{I^{*}}^{-1} e do vetor multiplicador \pi^{*} — ensinando o conceito.
  • Por definição, se I^{*} é o conjunto de índices das variáveis básicas na solução ótima e A_{I^{*}} é a matriz formada pelas colunas correspondentes de A, então a matriz base inversa ótima é A_{I^{*}}^{-1}. Essa matriz é justamente a que transforma o vetor b nos valores básicos: x_{B}=A_{I^{*}}^{-1}b.
  • No nosso problema a base ótima (em ordem natural dos índices dos x) escolhi apresentá-la como I^{*}=\{x_{1},x_{2},s_{3}\}. As colunas correspondentes em A são:
A_{I^{*}}=\big[\,a_{x_{1}}\;\;a_{x_{2}}\;\;a_{s_{3}}\,\big] =\begin{pmatrix} 2 & 1 & 0\\[2pt] 3 & 1 & 0\\[2pt] 7 & 0 & 1 \end{pmatrix}.
  • Invertendo essa matriz (Gauss-Jordan ou métodos usuais) obtemos
A_{I^{*}}^{-1}= \begin{pmatrix} -1 & 1 & 0\\[2pt] 3 & -2 & 0\\[2pt] 7 & -7 & 1 \end{pmatrix}.
Verificação rápida: A_{I^{*}}^{-1}b=\begin{pmatrix}-1&1&0\\[2pt]3&-2&0\\[2pt]7&-7&1\end{pmatrix}\begin{pmatrix}20\\[2pt]24\\[2pt]70\end{pmatrix}=\begin{pmatrix}4\\[2pt]12\\[2pt]42\end{pmatrix}, que são exatamente os valores básicos (x_{1},x_{2},s_{3}) obtidos na tabela.
  • O vetor multiplicador ótimo \pi^{*} (também chamado preços sombra ou multiplicadores duales) satisfaz
\pi^{*T}A_{I^{*}}=c_{I^{*}}^{T},
ou, de forma equivalente,
\pi^{*T}=c_{I^{*}}^{T}A_{I^{*}}^{-1}.
Aqui c_{I^{*}} (custos das variáveis básicas na mesma ordem) é (15,6,0) — notem que o custo de x_{1} é 15, de x_{2} é 6 e de s_{3} é 0. Fazendo o produto:
\pi^{*T}=(15,6,0)\begin{pmatrix}-1 & 1 & 0\\[2pt]3 & -2 & 0\\[2pt]7 & -7 & 1\end{pmatrix} =(3,3,0).
Logo \pi^{*}=(3,3,0)^{T}. Interpretando: \pi_{1}=3 é o preço sombra da primeira restrição, \pi_{2}=3 da segunda, \pi_{3}=0 da terceira.]

Passo 10

Análise de unicidade da solução.
  • Para verificar se a solução ótima é única, observamos os custos reduzidos (valores c_j - \pi^{*T} a_j) das variáveis não básicas. Se existir alguma variável não básica com custo reduzido exatamente zero, então há solução ótima alternativa (ótima múltipla) — porque podemos entrar essa variável sem alterar o valor de z.
  • No nosso caso os custos reduzidos das não-básicas foram todos negativos ( x_{3}: -15, x_{4}: -91, s_{1}: -3, s_{2}: -3). Não existe custo reduzido zero para uma não-básica, portanto a solução ótima é única.

Resposta

x^{*}=(x_{1},x_{2},x_{3},x_{4})=(4,\;12,\;0,\;0)
I^{*}=\{x_{1},x_{2},s_{3}\}
A_{I^{*}}^{-1}=\begin{pmatrix}-1 & 1 & 0\\[2pt]3 & -2 & 0\\[2pt]7 & -7 & 1\end{pmatrix}
\pi^{*}=(3,\;3,\;0)^{T}
z^{*}=132
Solução ótima: única.]

Exercícios relacionados