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}
\begin{array}{ccc} \text { suj. a } & 2 x_{1}+3 x_{2} & \leq 18 \\ & 2 x_{1}+x_{2} & \leq 12 \\ & 3 x_{1}+3 x_{2} & \leq 24 \\ & x_{1} \geq 0 & \\ & x_{2} \geq 0 & \end{array}

Passo 1

O enunciado pede para resolver o problema por simplex (tabela), e apresentar:
  • a solução ótima x^{*} (valores de x_{1},x_{2});
  • 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^{*};
  • dizer se a solução é ótima única, ótima múltipla ou ilimitada (e, se for o caso, o formato geral da solução).
O problema é:
\begin{aligned} \max\quad & z=5x_{1}+6x_{2} \\\ \text{s.a.}\quad & 2x_{1}+3x_{2}\le 18,\\\ & 2x_{1}+x_{2}\le 12,\\\ & 3x_{1}+3x_{2}\le 24,\\\ & x_{1}\ge0,\; x_{2}\ge0. \end{aligned}
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):
\begin{array}{rcl} 2x_{1}+3x_{2}+s_{1} & = & 18,\\\\ 2x_{1}+x_{2}+s_{2} & = & 12,\\\\ 3x_{1}+3x_{2}+s_{3} & = & 24. \end{array}
A base inicial natural é s_{1},s_{2},s_{3} com x_1=x_2=0. Montamos a tabela inicial (colunas: x_1,x_2,s_1,s_2,s_3; última coluna RHS):
\begin{array}{c|ccccc|c} & x_1 & x_2 & s_1 & s_2 & s_3 & \text{RHS} \\\ \hline \text{R}_1 & 2 & 3 & 1 & 0 & 0 & 18\\\ \text{R}_2 & 2 & 1 & 0 & 1 & 0 & 12\\\ \text{R}_3 & 3 & 3 & 0 & 0 & 1 & 24\\\ \hline \text{Z-row} & -5 & -6 & 0 & 0 & 0 & 0 \end{array}
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:
\frac{18}{3}=6,\quad \frac{12}{1}=12,\quad \frac{24}{3}=8.
Menor razão é 6 (linha 1). Assim x_{2} entra e s_{1} sai (pivot na linha 1 coluna x_{2}, valor pivot 3). Normalizamos a linha 1 dividindo por 3:
\text{R}_1 \leftarrow \frac{1}{3}\text{R}_1: \quad \begin{array}{ccccc|c} x_1 & x_2 & s_1 & s_2 & s_3 & \text{RHS}\\\ \hline \frac{2}{3} & 1 & \frac{1}{3} & 0 & 0 & 6 \end{array}
Agora eliminamos x_2 das outras linhas usando operações elementares:
  • \text{R}_2 \leftarrow \text{R}_2 - 1\cdot\text{R}_1
  • \text{R}_3 \leftarrow \text{R}_3 - 3\cdot\text{R}_1
  • Z-row \leftarrow Z-row +\;6\cdotR1 (para zerar o coeficiente -6)
Fazendo as contas obtemos a tabela após o primeiro pivô:
\begin{array}{c|ccccc|c} & x_1 & x_2 & s_1 & s_2 & s_3 & \text{RHS} \\\ \hline \text{R}_1 & \tfrac{2}{3} & 1 & \tfrac{1}{3} & 0 & 0 & 6\\[4pt] \text{R}_2 & \tfrac{4}{3} & 0 & -\tfrac{1}{3} & 1 & 0 & 6\\[4pt] \text{R}_3 & 1 & 0 & -1 & 0 & 1 & 6\\\ \hline \text{Z-row} & -1 & 0 & 2 & 0 & 0 & 36 \end{array}
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:
\frac{\text{RHS}}{\text{coef }x_1}:\quad \frac{6}{2/3}=9,\quad \frac{6}{4/3}= \frac{6\cdot3}{4}= \tfrac{18}{4}=\tfrac{9}{2}=4{,}5,\quad \frac{6}{1}=6.
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):
\text{R}_2 \leftarrow \frac{3}{4}\text{R}_2: \quad \begin{array}{ccccc|c} x_1 & x_2 & s_1 & s_2 & s_3 & \text{RHS}\\\ \hline 1 & 0 & -\tfrac{1}{4} & \tfrac{3}{4} & 0 & \tfrac{9}{2} \end{array}
Eliminamos x_1 das outras linhas:
  • \text{R}_1 \leftarrow \text{R}_1 - \tfrac{2}{3}\text{R}_2
  • \text{R}_3 \leftarrow \text{R}_3 - 1\cdot\text{R}_2
  • Z-row \leftarrow Z-row +1\cdotR2 (pois coef de x_1 na Z-row era -1)
Fazendo as contas (mostro uma operação como exemplo: nova R1 RHS =6 -\tfrac{2}{3}\cdot\tfrac{9}{2}=6-3=3), obtemos a tabela final:
\begin{array}{c|ccccc|c} & x_1 & x_2 & s_1 & s_2 & s_3 & \text{RHS} \\\ \hline \text{R}_1 & 0 & 1 & \tfrac{1}{2} & -\tfrac{1}{2} & 0 & 3\\[4pt] \text{R}_2 & 1 & 0 & -\tfrac{1}{4} & \tfrac{3}{4} & 0 & \tfrac{9}{2}\\[4pt] \text{R}_3 & 0 & 0 & -\tfrac{3}{4} & -\tfrac{3}{4} & 1 & \tfrac{3}{2}\\\ \hline \text{Z-row} & 0 & 0 & \tfrac{7}{4} & \tfrac{3}{4} & 0 & \tfrac{81}{2} \end{array}
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) é
z^{*}=\tfrac{81}{2}=40{,}5.
Conferência direta: 5\cdot \tfrac{9}{2} + 6\cdot 3 = \tfrac{45}{2}+18=\tfrac{45+36}{2}=\tfrac{81}{2}.

Passo 6

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) é
A_{I^{*}}= \begin{pmatrix} 2 & 3 & 0\\[4pt] 2 & 1 & 0\\[4pt] 3 & 3 & 1 \end{pmatrix}.
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}.
Assim
A_{I^{*}}^{-1}= \begin{pmatrix} -\tfrac{1}{4} & \tfrac{3}{4} & 0\\[4pt] \tfrac{1}{2} & -\tfrac{1}{2} & 0\\[4pt] -\tfrac{3}{4} & -\tfrac{3}{4} & 1 \end{pmatrix}.
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
\pi^{T} = (5,6,0)\cdot \begin{pmatrix} -\tfrac{1}{4} & \tfrac{3}{4} & 0\\[4pt] \tfrac{1}{2} & -\tfrac{1}{2} & 0\\[4pt] -\tfrac{3}{4} & -\tfrac{3}{4} & 1 \end{pmatrix} = \bigl(\tfrac{7}{4},\;\tfrac{3}{4},\;0\bigr).
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):
  • c_{s_1}=0,\; a_{s_1}=(1,0,0)^{T}\Rightarrow c_{s_1}-\pi^{T}a_{s_1}=0-\tfrac{7}{4}=-\tfrac{7}{4}<0.
  • c_{s_2}=0,\; a_{s_2}=(0,1,0)^{T}\Rightarrow c_{s_2}-\pi^{T}a_{s_2}=0-\tfrac{3}{4}=-\tfrac{3}{4}<0.
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.

Resposta

x^{*}=\Bigl(\tfrac{9}{2},\;3\Bigr)\
I^{*}=\{1,2,5\}\
A_{I^{*}}^{-1}= \begin{pmatrix} -\tfrac{1}{4} & \tfrac{3}{4} & 0\\[4pt] \tfrac{1}{2} & -\tfrac{1}{2} & 0\\[4pt] -\tfrac{3}{4} & -\tfrac{3}{4} & 1 \end{pmatrix}\
\pi^{*}=\bigl(\tfrac{7}{4},\;\tfrac{3}{4},\;0\bigr)\
z^{*}=\tfrac{81}{2}\
Solução ótima: ótima única.]

Exercícios relacionados