Questão 6 0%
Utilizando a versão adequada do método Simplex, resolva o problema de programação linear abaixo:
\begin{gathered} \min 4 x_{1}+x_{2} \\\ \text { sujeito a: }\left\{\begin{aligned} 3 x_{1}+x_{2} & =3 \\\\ 4 x_{1}+3 x_{2} & \geq 6 \\\ x_{1}+2 x_{2} & \leq 4 \\\ x_{1}, & x_{2} \end{aligned}\right] 0 \end{gathered}

Passo 1

O enunciado pede que se minimize a função objetivo
\min 4x_{1}+x_{2}
sujeito às restrições
\begin{cases} 3x_{1}+x_{2}=3,\\[4pt] 4x_{1}+3x_{2}\ge 6,\\[4pt] x_{1}+2x_{2}\le 4,\\[4pt] x_{1},x_{2}\ge 0. \end{cases}
Informações relevantes extraídas do enunciado:
  • Objetivo: encontrar valores de (x_{1},x_{2}) que satisfazem as restrições e que minimizam \;4x_{1}+x_{2}.
  • Há uma equação de igualdade (primeira restrição), uma desigualdade do tipo \ge (segunda) e uma do tipo \le (terceira).
  • As variáveis são não-negativas: \;x_{1},x_{2}\ge 0.
    Questão a responder: determinar a solução ótima (x_{1},x_{2}) e o valor mínimo da função objetivo.]

Passo 2

Escolher a versão adequada do método Simplex. Como há uma igualdade e uma desigualdade \ge, é prática padrão usar o método em duas fases (Two-Phase Simplex):
  • Fase 1: introduz-se variáveis artificiais para obter uma solução básica inicial viável e minimiza-se a soma das artificiais; se a soma mínima for zero, há solução básica viável do problema original.
  • Fase 2: com a base viável encontrada sem artificiais, resolve-se o problema original.
Vamos colocar todas as restrições em forma de igualdade adicionando folgas/excesso e variáveis artificiais quando necessário.
Transformação das restrições:
  • Primeira (igualdade): \;3x_{1}+x_{2}=3. Para obter uma base inicial, adiciona-se uma variável artificial \;a_{1}:
3x_{1}+x_{2}+a_{1}=3.
  • Segunda ( \ge): \;4x_{1}+3x_{2}\ge6. Subtrai-se uma variável de excesso \;s_{2} e adiciona-se artificial \;a_{2}:
4x_{1}+3x_{2}-s_{2}+a_{2}=6.
  • Terceira ( \le): \;x_{1}+2x_{2}\le4. Soma-se uma folga \;s_{3}:
x_{1}+2x_{2}+s_{3}=4.
Todas as variáveis são não-negativas:
x_{1},x_{2},s_{2},s_{3},a_{1},a_{2}\ge 0.
Base inicial natural para a Fase 1: \{a_{1},a_{2},s_{3}\} com valores de RHS 3,6,4 respectivamente.
Fase 1: minimizar
w=a_{1}+a_{2}.

Passo 3

Montar o tableau inicial da Fase 1 (colunas: x_{1},x_{2},s_{2},s_{3},a_{1},a_{2}; linhas: as três equações básicas e o objetivo w). Escrever as equações da base:
Linha a_{1}:
3x_{1}+1x_{2}+0s_{2}+0s_{3}+1a_{1}+0a_{2}=3.
Linha a_{2}:
4x_{1}+3x_{2}-1s_{2}+0s_{3}+0a_{1}+1a_{2}=6.
Linha s_{3}:
1x_{1}+2x_{2}+0s_{2}+1s_{3}+0a_{1}+0a_{2}=4.
Os coeficientes-custo para a Fase 1 são: c_{x_1}=0,\\ c_{x_2}=0,\\ c_{s_2}=0,\\ c_{s_3}=0,\\ c_{a_1}=1,\\ c_{a_2}=1.
Calcular o rótulo da função auxiliar w (linha objetivo) através de z_j=\sum_{B} c_B a_{ij} e r_j=c_j-z_j. Inicialmente a base é (a_1,a_2,s_3) com custos (1,1,0).
Calcular z_j para cada coluna:
\begin{aligned} z_{x_1}&=1\cdot 3 + 1\cdot 4 + 0\cdot 1 =7,\\[4pt] z_{x_2}&=1\cdot 1 + 1\cdot 3 + 0\cdot 2 =4,\\[4pt] z_{s_2}&=1\cdot 0 + 1\cdot(-1) + 0\cdot 0 =-1,\\[4pt] z_{s_3}&=1\cdot 0 + 1\cdot 0 + 0\cdot 1 =0,\\[4pt] z_{a_1}&=1\cdot 1 + 1\cdot 0 + 0\cdot 0 =1,\\[4pt] z_{a_2}&=1\cdot 0 + 1\cdot 1 + 0\cdot 0 =1,\\[4pt] z_{\text{RHS}}&=1\cdot 3 + 1\cdot 6 + 0\cdot 4 =9. \end{aligned}
Agora r_j=c_j-z_j:
\begin{aligned} r_{x_1}&=0-7=-7,\quad r_{x_2}=0-4=-4,\quad r_{s_2}=0-(-1)=1,\\[4pt] r_{s_3}&=0-0=0,\quad r_{a_1}=1-1=0,\quad r_{a_2}=1-1=0. \end{aligned}
Como existem r_j<0 (para minimização isso indica possibilidade de reduzir w), escolhe-se a variável com menor r_j (mais negativa) para entrar: \;x_{1} entra ( r_{x_1}=-7).
Aplicar o teste da razão mínima para escolher a variável que sai: dividir \text{RHS} / \text{coef}_{x_1} apenas para coeficientes positivos na coluna de x_{1}:
\frac{3}{3}=1,\qquad \frac{6}{4}=1{,}5,\qquad \frac{4}{1}=4.
Menor razão é 1 (linha de a_{1}), então a_{1} sai e x_{1} entra. Pivotar na posição (linha a_{1}, coluna x_{1}), elemento pivô 3.
Dividindo a linha a_{1} por 3 e eliminando x_{1} das outras linhas obtém‑se a nova tabela (apresento apenas as linhas transformadas em forma equacional):
Nova linha x_{1} (antes a_{1}):
x_{1}+{\tfrac{1}{3}}x_{2}+{\tfrac{1}{3}}a_{1}=1.
Linha a_{2} atualizada (linha2 − 4×linha1):
0\cdot x_{1}+{\tfrac{5}{3}}x_{2}-1s_{2}-{\tfrac{4}{3}}a_{1}+1a_{2}=2.
Linha s_{3} atualizada (linha3 − 1×linha1):
0\cdot x_{1}+{\tfrac{5}{3}}x_{2}+0s_{2}-{\tfrac{1}{3}}a_{1}+1s_{3}=3.
Atualizar z_j com a nova base (x_1,a_2,s_3) e recomputar r_j. Os cálculos dão:
r_{x_2}=-\tfrac{5}{3}\quad(\text{mais negativo}),\\ \text{logo }x_{2}\text{ entra.}
Fazer teste da razão mínima na coluna x_{2}: razões positivas
\frac{1}{1/3}=3,\quad \frac{2}{5/3}=\tfrac{6}{5}=1{,}2,\quad \frac{3}{5/3}=\tfrac{9}{5}=1{,}8.
Menor razão é \tfrac{6}{5} (linha correspondente a a_{2}), então a_{2} sai e x_{2} entra. Pivotar e eliminar.
Após a segunda iteração da Fase 1 obtém‑se a base (x_{1},x_{2},s_{3}) com valores solução
x_{1}=\tfrac{3}{5},\qquad x_{2}=\tfrac{6}{5},\qquad s_{3}=1,
e as variáveis artificiais assumem valor zero: a_{1}=a_{2}=0. O valor da função auxiliar é
w=a_{1}+a_{2}=0,
logo existe solução viável para o problema original (soma das artificiais mínima igual a zero). Conclui-se a Fase 1 com sucesso.]

Passo 4

Preparar a Fase 2: remover as colunas das variáveis artificiais a_{1},a_{2} (elas saíram da base e valem zero) e resolver o problema original de minimização com base atual \{x_{1},x_{2},s_{3}\}.
A função objetivo original tem custos c_{x_1}=4,\\ c_{x_2}=1,\\ c_{s_2}=0,\\ c_{s_3}=0.
Usando a tabela final da Fase 1 (após remover as colunas artificiais), escrevemos as linhas básicas na forma atual (mostradas abaixo em ordem: linha de x_{1}, linha de x_{2}, linha de s_{3}):
Linha x_{1}:
x_{1} + 0\cdot x_{2} + \tfrac{1}{5}s_{2} + 0\cdot s_{3} = \tfrac{3}{5}.
Linha x_{2}:
0\cdot x_{1} + x_{2} - \tfrac{3}{5}s_{2} + 0\cdot s_{3} = \tfrac{6}{5}.
Linha s_{3}:
0\cdot x_{1} + 0\cdot x_{2} + 1\cdot s_{2} + 1\cdot s_{3} = 1.
Agora montar a linha objetivo da Fase 2 (original): calcular z_j=\sum_{B} c_B a_{ij} com custos da base c_{x_1}=4,\\ c_{x_2}=1,\\ c_{s_3}=0.
Calcular z_j:
\begin{aligned} z_{x_1}&=4\cdot 1 + 1\cdot 0 + 0\cdot 0 =4,\\[4pt] z_{x_2}&=4\cdot 0 + 1\cdot 1 + 0\cdot 0 =1,\\[4pt] z_{s_2}&=4\cdot \tfrac{1}{5} + 1\cdot(-\tfrac{3}{5}) + 0\cdot 1 = \tfrac{4}{5}-\tfrac{3}{5}=\tfrac{1}{5},\\[4pt] z_{s_3}&=4\cdot 0 + 1\cdot 0 + 0\cdot 1 =0,\\[4pt] z_{\text{RHS}}&=4\cdot \tfrac{3}{5} + 1\cdot \tfrac{6}{5} + 0\cdot 1 = \tfrac{12}{5}+\tfrac{6}{5}=\tfrac{18}{5}. \end{aligned}
Agora os custos originais c_j menos z_j dão os reduzidos r_j=c_j-z_j:
r_{x_1}=4-4=0,\quad r_{x_2}=1-1=0,\quad r_{s_2}=0-\tfrac{1}{5}=-\tfrac{1}{5},\quad r_{s_3}=0-0=0.
Como existe r_{s_2}=-\tfrac{1}{5}<0, ainda não estamos em solução ótima para minimização: a variável s_{2} (coluna do excesso/slack) pode entrar e reduzir o valor da função objetivo.
Selecionar s_{2} como variável que entra. Aplicar teste da razão mínima nas linhas com coeficiente positivo na coluna de s_{2}:
  • linha x_{1}: coeficiente \tfrac{1}{5}>0: razão \dfrac{3/5}{1/5}=3.
  • linha x_{2}: coeficiente -\tfrac{3}{5}<0: não considerada.
  • linha s_{3}: coeficiente 1>0: razão \dfrac{1}{1}=1.
A menor razão é 1 (linha s_{3}), então s_{3} sai e s_{2} entra. Pivotar na linha de s_{3} (pivô = 1).
Fazendo as operações de linha, obtém-se a nova base \{x_{1},x_{2},s_{2}\} e as linhas atualizadas:
Linha x_{1} atualizada:
x_{1} + 0\cdot x_{2} + 0\cdot s_{2} - \tfrac{1}{5}s_{3} = \tfrac{2}{5}.
Linha x_{2} atualizada:
0\cdot x_{1} + x_{2} + 0\cdot s_{2} + \tfrac{3}{5}s_{3} = \tfrac{9}{5}.
Linha s_{2} (nova básica):
0\cdot x_{1} + 0\cdot x_{2} + 1\cdot s_{2} + 1\cdot s_{3} = 1.
Recalcular z_j com a base atual e custos c_{x_1}=4,\\ c_{x_2}=1,\\ c_{s_2}=0:
\begin{aligned} z_{x_1}&=4\cdot 1 + 1\cdot 0 + 0\cdot 0 =4,\\[4pt] z_{x_2}&=4\cdot 0 + 1\cdot 1 + 0\cdot 0 =1,\\[4pt] z_{s_2}&=4\cdot 0 + 1\cdot 0 + 0\cdot 1 =0,\\[4pt] z_{s_3}&=4\cdot(-\tfrac{1}{5}) + 1\cdot \tfrac{3}{5} + 0\cdot 1 = -\tfrac{4}{5}+\tfrac{3}{5} = -\tfrac{1}{5},\\[4pt] z_{\text{RHS}}&=4\cdot \tfrac{2}{5} + 1\cdot \tfrac{9}{5} + 0\cdot 1 = \tfrac{8}{5}+\tfrac{9}{5} = \tfrac{17}{5}. \end{aligned}
Agora os reduzidos são
r_{x_1}=4-4=0,\quad r_{x_2}=1-1=0,\quad r_{s_2}=0-0=0,\quad r_{s_3}=0-(-\tfrac{1}{5})=\tfrac{1}{5}.
Todos os r_j\ge 0 (condição de ótimo para minimização), logo a solução atual é ótima para o problema original.]

Passo 5

Ler a solução ótima da tabela final: as variáveis básicas e seus valores (RHS):
x_{1}=\tfrac{2}{5},\qquad x_{2}=\tfrac{9}{5},\qquad s_{2}=1.
As variáveis não apresentadas como básicas valem zero: s_{3}=0,\\ a_{1}=a_{2}=0.
Verificação rápida nas restrições originais:
3x_{1}+x_{2}=3\cdot\tfrac{2}{5}+\tfrac{9}{5}=\tfrac{6}{5}+\tfrac{9}{5}=\tfrac{15}{5}=3.
4x_{1}+3x_{2}=4\cdot\tfrac{2}{5}+3\cdot\tfrac{9}{5}=\tfrac{8}{5}+\tfrac{27}{5}=\tfrac{35}{5}=7\ge 6.
x_{1}+2x_{2}=\tfrac{2}{5}+2\cdot\tfrac{9}{5}=\tfrac{2}{5}+\tfrac{18}{5}=\tfrac{20}{5}=4\le 4.
Todas satisfazem, bom.
Valor ótimo da função objetivo:
4x_{1}+x_{2}=4\cdot\tfrac{2}{5}+\tfrac{9}{5}=\tfrac{8}{5}+\tfrac{9}{5}=\tfrac{17}{5}.

Resposta

x_{1}=\dfrac{2}{5}
x_{2}=\dfrac{9}{5}
\min 4x_{1}+x_{2}=\dfrac{17}{5}

Exercícios relacionados