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.
(d) \quad \min \quad z=3 x_{1}+4 x_{2}+9 x_{3}
Duas restrições do tipo \ge (exigem variáveis de folga negativas — “superavit” — e geralmente artificiais para obter uma base inicial).
Duas restrições independentes, RHS iguais a 5.
Variáveis não negativas.
O que devemos entregar no final:
solução ótima x^{*}, conjunto ótimo de variáveis básicas I^{*},
matriz base inversa ótima A_{I^{*}}^{-1},
vetor multiplicador ótimo \pi^{*},
valor ótimo z^{*},
indicar se a solução é ótima única, ótima múltipla ou ilimitada (e se múltipla/ilimitada, mostrar formato geral).]
Passo 2
Transformação para a forma adequada ao simplex (explicação didática):
Restrições do tipo \ge são transformadas subtraindo-se uma variável de excesso (surplus) e somando-se, se necessário, uma variável artificial para obter equações com igualdade e uma base inicial. A variável de excesso tem coeficiente -1 na respectiva equação; a variável artificial é usada para obter uma base inicial viável e depois deve ser eliminada (duas maneiras comuns: método do Grande M ou método em duas fases). Aqui usamos o método em duas fases (Phase I para eliminar artificiais, Phase II para otimizar o objetivo original).
Variáveis que introduzimos: para a primeira restrição introduzimos \;s_{1} (surplus) e a_{1} (artificial); para a segunda restrição introduzimos \;s_{2} e a_{2}. Todas essas novas variáveis satisfazem \ge 0.
com objetivo de obter w^{*}=0 (ou seja, eliminar as artificiais da base). Depois, se viável, passamos à Phase II com o objetivo original z.]
Passo 3
Montagem da tabela inicial da Phase I (explicando o que é cada coluna):
Colunas na ordem: x_{1},x_{2},x_{3},s_{1},s_{2},a_{1},a_{2}.
Base inicial: \{a_{1},a_{2}\}. Assim B= [\text{col}(a_{1}),\text{col}(a_{2})] = \begin{pmatrix}1 & 0\\[2pt]0 & 1\end{pmatrix}, cujo inverso é a identidade. RHS b=(5,5)^{T}.
Custos na Phase I: c_{a_1}=1,\; c_{a_2}=1; custos das demais variáveis =0.
Tabela inicial (vou mostrar cada equação em forma vetorial):
Linha 1 (equação 1): coeficientes correspondentes
Cálculo dos custos reduzidos iniciais (fórmula): para minimização, o custo reduzido de uma variável não-básica j é
\bar{c}_{j} = c_{j} - \pi^{T} a_{j},
onde \pi^{T}=c_{B}^{T}B^{-1}. No inicio c_{B}=(1,1) e B^{-1}=I, então \pi^{T}=(1,1).
Aplicando para cada coluna:
\bar{c}_{x_{1}} = 0 - [1,1]\cdot[1;0] = -1.
\bar{c}_{x_{2}} = 0 - [1,1]\cdot[0;1] = -1.
\bar{c}_{x_{3}} = 0 - [1,1]\cdot[1;2] = -3.
\bar{c}_{s_{1}} = 0 - [1,1]\cdot[-1;0] = +1.
\bar{c}_{s_{2}} = 0 - [1,1]\cdot[0;-1] = +1.
Artificiais são básicas, seus \bar{c}=0 (por padrão de tabela).
Interpretação didática: como estamos minimizando e alguns \bar{c}_{j} são negativos (x_{3} o mais negativo = -3), isso indica que aumentar x_{3} a partir de zero reduzirá w. Logo x_{3} entra na base.]
Passo 4
Primeiro pivô da Phase I (entrada de x_{3}):
Coluna de x_{3}: vetor a_{x_{3}}=[1;2].
Regra da razão (ratio test): para variáveis i com a_{ij}>0, razão b_{i}/a_{ij}:
Linha 1: 5/1 = 5.
Linha 2: 5/2 = 2{,}5.
Menor razão = 2{,}5 → saída da base: a_{2} (linha 2). Pivot na linha 2, coluna x_{3}.
Executando o pivot (mostrando os cálculos):
Dividimos a linha 2 por 2 (elemento pivot).
Linha 2 nova:[\,0,\;1/2,\;1,\;0,\;-1/2,\;0,\;1/2\,],\quad b_{2}=2{,}5.
Eliminamos x_{3} da linha 1: linha1 := linha1 - linha2 nova.
Linha 1 nova:[\,1,\;-1/2,\;0,\;-1,\;1/2,\;1,\;-1/2\,],\quad b_{1}=2{,}5.
Nova base: \{a_{1},x_{3}\}. Vamos calcular B^{-1} para essa base (explicando como obter):
Colunas da base originais: \text{col}(a_{1})=[1;0],\;\text{col}(x_{3})=[1;2].
Matriz B = \begin{pmatrix}1&1\\[2pt]0&2\end{pmatrix}.
Observação: ainda existem custos reduzidos negativos (\bar{c}_{x_{1}}=-1,\;\bar{c}_{s_{2}}=-\tfrac{1}{2}), então não terminamos Phase I.]
Passo 5
Segundo pivô da Phase I (entrada de x_{1}):
Escolhemos a variável com \bar{c} mais negativa para entrar: x_{1} com -1.
Coluna de x_{1} na base atual (usando B^{-1}a_{x_1} ou lendo a tabela): após o primeiro pivot, a coluna de x_{1} nas linhas básicas é [1;0] (veja linhas atualizadas).
Razões (apenas onde entrada da coluna >0):
Linha 1: b_{1}/1 = 2{,}5.
Linha 2: entrada 0 → não é candidata.
Saída: a_{1} (linha 1). Pivot em linha 1, coluna x_{1}.
Como a coluna de x_{1} já tem 1 na linha 1 e 0 na linha 2, após o pivot a base fica \{x_{1},x_{3}\} e as linhas não mudam em seus elementos de x_{3} e x_{1}. Os valores básicos (RHS) continuam:
x_{1} = 2{,}5,\qquad x_{3} = 2{,}5.
Estado das artificiais:
Ambas a_{1} e a_{2} tornaram-se não básicas (valendo zero).
Valor da função Phase I: w = a_{1}+a_{2} = 0. Conclusão: solução viável para o sistema original (sem artificiais).
Passo 6
Passagem para a Phase II (objetivo original) e cálculo de A_{I^{*}}^{-1} e \pi^{*}:
Base atual viável e sem artificiais: I = \{x_{1},x_{3}\}.
Todos os \bar{c}_{j} são maiores ou iguais a zero. Em um problema de minimização isso significa que não existe direção de redução do objetivo partindo da solução atual — logo a solução atual é ótima.
Passo 8
Cálculo do valor ótimo e conclusão sobre unicidade:
Verificação de unicidade: como todos os custos reduzidos das variáveis não-básicas são estritamente positivos (\bar{c}_{x_{2}}=1,\;\bar{c}_{s_{1}}=3,\;\bar{c}_{s_{2}}=3), não existe nenhuma variável não-básica com custo reduzido zero; isso implica que a solução ótima é única.
Resumo das quantidades pedidas (já calculadas):
Solução ótima x^{*} = (2{,}5,\;0,\;2{,}5)^{T}.
Conjunto ótimo de variáveis básicas I^{*} = \{1,3\} (ou seja, x_{1} e x_{3} são básicas).