1^{\text {a }} Questão (13 pontos): Sejam os problemas de Programação Linear:
\max z=6 x_{1} +2 x_{2}
sujeito às -1 x_{1} +x_{2} \geq 1
retricọos (1) +x_{2} \leq 4 (2)
x_{1} \in R\left(3^{\prime}\right) x_{2} \geq-1 \left(3^{\prime \prime}\right)
  • ( 1 - pontos): mostre a solução básica inicial
  • ( 4 - pontos): resolva graficamente o problema
  • ( 4 - pontos): construa o quadro inicial do simplex
  • ( 4 - pontos): faça iteraçōes do simplex até obter uma soluçāo ótima ou interrompoer o simplex por uma outra razão, diga qual a razāo, se interromper as iterações do simplex.

Passo 1

Resumindo o enunciado, temos o problema de Programação Linear
\max\;z = 6x_{1} + 2x_{2}
sujeito a
\begin{cases} -\,x_{1} + x_{2} \ge 1,\\\ x_{2} \le 4,\\\ x_{1}\in\mathbb{R},\quad x_{2}\ge -1. \end{cases}
O conteúdo aqui envolve:
  1. tratar variável livre x_{1} e limite inferior x_{2}\ge -1;
  2. encontrar solução básica inicial (usando variáveis de folga e artificiais, método das Duas Fases);
  3. resolver graficamente para comparar;
  4. montar o tableau inicial do Simplex;
  5. iterar até a solução ótima.

Passo 2

Para obter uma solução básica inicial válida no Simplex por Duas Fases, fazemos:
  1. Eliminar o limite x_{2}\ge-1\) por substituição \[\hat x_{2} = x_{2} + 1\;\Rightarrow\;x_{2}=\hat x_{2}-1,\quad \hat x_{2}\ge0.
  2. Tratar x_{1} livre como diferença de não-negativos
x_{1}=x_{1}^{+}-x_{1}^{-},\quad x_{1}^{+}\ge0,\;x_{1}^{-}\ge0.
  1. Escrever as restrições em forma padrão e introduzir folgas/superávit e artificiais:
\begin{cases} -\,(x_{1}^{+}-x_{1}^{-}) + (\hat x_{2}-1)\;\ge1 &\Longrightarrow\;-x_{1}^{+}+x_{1}^{-}+\hat x_{2}-s_{1}+a_{1}=2,\\\ (\hat x_{2}-1)\;\le4 &\Longrightarrow\;\hat x_{2}+s_{2}=5, \end{cases}
com s_{1},s_{2}\ge0\] e \(a_{1}\ge0 artificial.
  1. Escolhemos como básicos a_{1} e s_{2}; todos os demais (incluindo x_{1}^{+},x_{1}^{-},\hat x_{2},s_{1}) ficam zerados.
    Da equação a_{1}=2 + x_{1}^{+}-x_{1}^{-}-\hat x_{2}+s_{1}, em x_{1}^{+}=x_{1}^{-}=\hat x_{2}=s_{1}=0 obtemos
a_{1}=2,\quad s_{2}=5.
Essa é a solução básica inicial para a Fase I.

Passo 3

Para conferir, resolvemos graficamente o problema original.
  1. A região viável é
    \{(x_{1},x_{2})\mid -x_{1}+x_{2}\ge1,\,-1\le x_{2}\le4\}.
  2. A reta de nível de z tem inclinação -3 e, para maximizar, “puxa” o ponto mais à direita.
  3. A interseção das restrições atinge-se em \bigl(x_{1},x_{2}\bigr)=(3,4), e
z_{\max}=6\cdot3+2\cdot4=18+8=26.

Passo 4

Quadro inicial do Simplex (Fase I)
\begin{array}{c|rrrrr|r} \text{Base} & x_{1}^{+} & x_{1}^{-} & \hat x_{2} & s_{1} & s_{2} & \text{RHS}\\hline a_{1} & -1 & +1 & +1 & -1 & 0 & 2\\\ s_{2} & 0 & 0 & +1 & 0 & +1 & 5\\hline w\,(=a_{1}) & -1 & +1 & +1 & -1 & 0 & 2 \end{array}
Aqui w é a função-objetivo da Fase I: minimizar w=a_{1}.

Passo 5

Iterações do Simplex
  1. Fase I:
  • Na linha de w, o coeficiente mais positivo é +1 em x_{1}^{-}, então x_{1}^{-} entra.
  • Somente a restrição de a_{1} tem coeficiente positivo em x_{1}^{-}, razão 2/1=2. Pivô na interseção (a_{1},x_{1}^{-}).
  • Após o pivô, a_{1} sai da base, x_{1}^{-} entra e obtém-se w_{\min}=0. Como w=0, removemos a_{1} e seguimos para a Fase II com base \{x_{1}^{-},s_{2}\}.
  1. Fase II (reajustando a função z):
  • Em variáveis transformadas, z=6(x_{1}^{+}-x_{1}^{-})+2(\hat x_{2}-1)\;\Longrightarrow\;z' =6x_{1}^{+}-6x_{1}^{-}+2\hat x_{2}, constante -2 à parte.
  • Monta‐se o tableau inicial da Fase II com base \{x_{1}^{-},s_{2}\}, linha- z atualizada.
  • O coeficiente positivo mais forte na linha- z é de \hat x_{2}; entra \hat x_{2}, sai s_{2}.
  • Após esse pivô, todos os coeficientes de z são \le0; atingimos a ótima.
Na solução final da Fase II, obtém-se
x_{1}^{+}=3,\quad x_{1}^{-}=0,\quad \hat x_{2}=5,
logo
x_{1}=x_{1}^{+}-x_{1}^{-}=3,\quad x_{2}=\hat x_{2}-1=4,\quad z=6\cdot3+2\cdot4=26.

Resposta

x_{1}=3,\quad x_{2}=4,\quad z_{\max}=26.

Exercícios relacionados