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=5 x_{1}+6 x_{2}
Informações dadas relevantes: coeficientes das restrições e da função objetivo, desigualdades do tipo \le (podemos acrescentar variáveis folga/slack), todas as variáveis não-negativas. A solução pedida inclui objetos da solução primal e dual.
Passo 2
Vamos colocar em forma padrão (adicionando variáveis folga \;s_{1},s_{2},s_{3}\ge0):
Explicação rápida do que está na Z-row: para maximização, colocamos os coeficientes negativos da função objetivo; uma coluna com coeficiente negativo indica que podemos aumentar a variável correspondente para melhorar z.
Passo 3
Critério de entrada e razão: escolhemos a variável não-básica com coeficiente mais negativo na Z-row para entrar (maior potencial de aumento de z). Aqui o coeficiente mais negativo é -6 em x_{2}, logo x_{2} entra. Fazemos teste de razão \text{RHS}/\text{coluna }x_2 apenas nas linhas com coeficiente positivo em x_2:
Expliquei como calcular cada entrada: por exemplo, em \text{R}_2, novo coeficiente de x_1 é 2 - 1\cdot(2/3)=4/3, RHS 12-1\cdot6=6, etc. Z-row RHS atualiza pois aumentamos z ao introduzir x_2.]
Passo 4
Agora, na Z-row o coeficiente mais negativo é -1 em x_1, então x_{1} entra. Fazemos teste de razão nas linhas com coeficiente positivo em x_1:
Menor razão é 4{,}5=\tfrac{9}{2} na linha 2. Portanto x_1 entra e a variável básica correspondente à linha 2 (s_{2}) sai. Pivot é 4/3 na linha 2 coluna x_1. Normalizamos a linha 2 dividindo por 4/3 (multiplicar por 3/4):
Na Z-row não há mais coeficientes negativos nas colunas de variáveis não-básicas (s_1,s_2 têm coeficientes positivos na nossa convenção), o que indica ótimo alcançado (não existe variável não-básica com potencial de aumentar z).]
Passo 5
Leitura da solução básica ótima a partir da tabela final (cada linha corresponde a uma variável básica com coluna identidade):
Linha 1 básica: x_{2}=3.
Linha 2 básica: x_{1}=\tfrac{9}{2}=4{,}5.
Linha 3 básica: s_{3}=\tfrac{3}{2}=1{,}5.
As variáveis não-básicas s_{1}=0,\; s_{2}=0. Portanto a solução primal:
x^{*}=(x_{1},x_{2})=\Bigl(\tfrac{9}{2},\;3\Bigr).
O valor ótimo da função objetivo (lido na Z-row RHS) é
Identificamos a base ótima I^{*}. As variáveis básicas são x_{1},x_{2},s_{3}, que correspondem aos índices \{1,2,5\} se numerarmos as variáveis como x_1,x_2,s_1,s_2,s_3. Logo:
I^{*}=\{1,2,5\}.
A matriz base A_{I^{*}} (colunas 1,2,5 da matriz de restrições) é
Vamos encontrar A_{I^{*}}^{-1}. Calculamos as colunas de A_{I^{*}}^{-1} resolvendo A_{I^{*}}y=e_{i}. Resumo das soluções (detalhes das equações já resolvidas no cálculo):
Para e_{1}=(1,0,0)^{T} obtemos y^{(1)}=\bigl(-\tfrac{1}{4},\tfrac{1}{2},-\tfrac{3}{4}\bigr)^{T}.
Para e_{2}=(0,1,0)^{T} obtemos y^{(2)}=\bigl(\tfrac{3}{4},-\tfrac{1}{2},-\tfrac{3}{4}\bigr)^{T}.
Para e_{3}=(0,0,1)^{T} obtemos y^{(3)}=(0,0,1)^{T}.
Observação: esta matriz é coerente com as linhas da tabela final que representam A_{I^{*}}^{-1}A e A_{I^{*}}^{-1}b.]
Passo 7
Cálculo do vetor multiplicador ótimo \pi^{*} (variáveis duais) pela fórmula \pi^{T}=c_{B}^{T}A_{I^{*}}^{-1}, onde c_{B} são os custos das variáveis básicas. Na base I^{*}=\{1,2,5\} temos c_{B}=(5,6,0). Então
Verificação de ótimalidade (condição complementar / custos reduzidos): para cada variável não-básica j devemos ter c_{j}-\pi^{T}a_{j}\le 0 (no máximo). Calculando para s_{1} e s_{2} (as não-básicas):
Como nenhum custo reduzido de variável não-básica é zero, não há direção degenerada de custo nulo — a solução ótima é única.]
Passo 8
Conclusão final e motivação: encontramos uma solução viável básica ótima \bigl(\tfrac{9}{2},3\bigr) com matriz base inversa e multiplicadores dados acima. Não existem variáveis não-básicas com custo reduzido igual a zero, então não há alternativas com o mesmo valor ótimo — a solução é ótima e única. Força aí — você já tem tudo que precisa escrever na prova: tableau, pivot, A_{I^{*}}^{-1}, \pi^{*} e justificativa da unicidade.