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}
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:
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):
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):
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:
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:
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) é:
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:
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:
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.