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}
\begin{aligned} & \text { suj. a } & x_{1}+x_{3} & x_{2}+2 x_{3} \geq 5 \\ & x_{1}, x_{2}, x_{3} \geq 0 \end{aligned}

Passo 1

O enunciado pede resolver, pelo método simplex em forma de tabela, o problema de programação linear abaixo, e apresentar várias quantidades finais.
O problema é:
\text{minimizar }\; z = 3x_{1}+4x_{2}+9x_{3}
sujeito a
\begin{cases} x_{1}+x_{3} \ge 5,\\[4pt] x_{2}+2x_{3} \ge 5,\\[4pt] x_{1},x_{2},x_{3}\ge 0. \end{cases}
Informações relevantes dadas:
  1. Objetivo: minimizar z.
  2. Duas restrições do tipo \ge (exigem variáveis de folga negativas — “superavit” — e geralmente artificiais para obter uma base inicial).
  3. Duas restrições independentes, RHS iguais a 5.
  4. 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.
Escrevendo as equações de igualdade:
\begin{aligned} x_{1} + x_{3} - s_{1} + a_{1} &= 5,\\[4pt] x_{2} + 2x_{3} - s_{2} + a_{2} &= 5. \end{aligned}
Phase I: minimizamos a função artificial
w = a_{1} + a_{2},
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
[\,x_{1},x_{2},x_{3},s_{1},s_{2},a_{1},a_{2}\,] = [\,1,\,0,\,1,\,-1,\,0,\,1,\,0\,],\quad b_{1}=5.
Linha 2 (equação 2):
[\,0,\,1,\,2,\,0,\,-1,\,0,\,1\,],\quad b_{2}=5.
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}.
  • Inversa:
B^{-1} = \frac{1}{2}\begin{pmatrix}2 & -1\\[2pt]0 & 1\end{pmatrix} = \begin{pmatrix}1 & -\tfrac{1}{2}\\[4pt]0 & \tfrac{1}{2}\end{pmatrix}.
Com c_{B}=(1,0) (custos de a_{1} e x_{3} na Phase I), obtemos
\pi^{T} = c_{B}^{T}B^{-1} = [1,0]\begin{pmatrix}1 & -\tfrac{1}{2}\\[4pt]0 & \tfrac{1}{2}\end{pmatrix} = [1,\;-\tfrac{1}{2}].
Cálculo dos novos custos reduzidos:
  • \bar{c}_{x_{1}} = 0 - [1,-\tfrac{1}{2}]\cdot[1;0] = -1.
  • \bar{c}_{x_{2}} = 0 - [1,-\tfrac{1}{2}]\cdot[0;1] = +\tfrac{1}{2}.
  • \bar{c}_{s_{1}} = 0 - [1,-\tfrac{1}{2}]\cdot[-1;0] = +1.
  • \bar{c}_{s_{2}} = 0 - [1,-\tfrac{1}{2}]\cdot[0;-1] = -\tfrac{1}{2}.
  • \bar{c}_{a_{2}} = 1 - [1,-\tfrac{1}{2}]\cdot[0;1] = 1 - (-\tfrac{1}{2}) = \tfrac{3}{2}.
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}\}.
  • Matriz base A_{I} = [\text{col}(x_{1}),\text{col}(x_{3})] = \begin{pmatrix}1 & 1\\[2pt]0 & 2\end{pmatrix}.
  • Já calculamos sua inversa:
A_{I}^{-1} = \begin{pmatrix}1 & -\tfrac{1}{2}\\[4pt]0 & \tfrac{1}{2}\end{pmatrix}.
Isto é exatamente a matriz base inversa ótima A_{I^{*}}^{-1} do problema (pois a base final será esta).
Cálculo do vetor multiplicador ótimo \pi^{*} (regra):
\pi^{T} = c_{B}^{T} A_{I}^{-1},
onde c_{B} são os custos (do problema original) das variáveis básicas. No problema original, custos:
c_{x_{1}} = 3,\quad c_{x_{3}} = 9.
Então
\pi^{T} = [3,\;9]\begin{pmatrix}1 & -\tfrac{1}{2}\\[4pt]0 & \tfrac{1}{2}\end{pmatrix} = [\,3\cdot1 + 9\cdot0,\; 3\cdot(-\tfrac{1}{2}) + 9\cdot\tfrac{1}{2}\,] = [3,\;3].
Portanto \pi^{*} = \begin{pmatrix}3\\[2pt]3\end{pmatrix}.]

Passo 7

Verificação de otimalidade (cálculo dos custos reduzidos na Phase II):
Usamos \bar{c}_{j} = c_{j} - \pi^{T} a_{j} com \pi^{T}=[3,3].
Calculemos para as variáveis não básicas:
  • x_{2}: coluna a_{x_{2}}=[0;1]. \bar{c}_{x_{2}} = 4 - [3,3]\cdot[0;1] = 4 - 3 = 1.
  • s_{1}: coluna [-1;0]. \bar{c}_{s_{1}} = 0 - [3,3]\cdot[-1;0] = 0 - (-3) = 3.
  • s_{2}: coluna [0;-1]. \bar{c}_{s_{2}} = 0 - [3,3]\cdot[0;-1] = 0 - (-3) = 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:
Solução básica atual (já encontrada):
x_{1} = 2{,}5,\qquad x_{3} = 2{,}5,\qquad x_{2}=0.
Valor ótimo:
z^{*} = 3x_{1} + 4x_{2} + 9x_{3} = 3\cdot 2{,}5 + 4\cdot 0 + 9\cdot 2{,}5 = (3+9)\cdot 2{,}5 = 12\cdot 2{,}5 = 30.
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).
  • Matriz base inversa ótima
A_{I^{*}}^{-1} = \begin{pmatrix}1 & -\tfrac{1}{2}\\[4pt]0 & \tfrac{1}{2}\end{pmatrix}.
  • Vetor multiplicador ótimo \displaystyle \pi^{*} = \begin{pmatrix}3\\[2pt]3\end{pmatrix}.
  • Valor ótimo z^{*} = 30.
  • Natureza da solução: ótima única.]

Resposta

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

Exercícios relacionados