2. (4,0) Considere o seguinte problema de programação linear: (P) max $$2x1 - x2 + x3 +…
- User
- (4,0) Considere o seguinte problema de programação linear:
(P) max
s.a.
$$x_1 + 2x_2 + 3x_3 + x_4 \leq 8$$ $$x_1, x_2, x_3, x_4 \geq 0$$Coloque o PPL na forma padrão e resolva pelo método simplex a partir da base gerada pelas variáveis de folga (siga a regra de bland). Diga qual a base ótima e o valor ótimo do problema.
- Assistant
Para resolver este problema, seguiremos os passos do método simplex, começando com as variáveis de folga como base inicial e aplicando a Regra de Bland para evitar ciclos.
1. Forma Padrão:
Primeiro, colocamos o problema na forma padrão, adicionando variáveis de folga (s_1) e (s_2):
Maximizar ( Z = 2x_1 - x_2 + x_3 + 4x_4 )
Sujeito a: [ \begin{cases} 5x_1 - x_2 + 0x_3 + 4x_4 + s_1 = 20 \ x_1 + 2x_2 + 3x_3 + x_4 + s_2 = 8 \ x_1, x_2, x_3, x_4, s_1, s_2 \geq 0 \end{cases} ]
2. Montagem do Tableau Inicial do Simplex:
Montamos o tableau inicial com as variáveis básicas (s_1) e (s_2):
[ \begin{array}{c|cccccc|c} \text{Base} & x_1 & x_2 & x_3 & x_4 & s_1 & s_2 & \text{RHS} \ \hline s_1 & 5 & -1 & 0 & 4 & 1 & 0 & 20 \ s_2 & 1 & 2 & 3 & 1 & 0 & 1 & 8 \ \hline Z & -2 & 1 & -1 & -4 & 0 & 0 & 0 \end{array} ]
3. Iterações do Método Simplex:
Primeira Iteração:
-
Escolha da Variável Entrante: As variáveis com coeficientes negativos no Z (linha de custos reduzidos) são candidatas. Pela Regra de Bland, escolhemos a de menor índice: (x_1).
-
Teste da Razão Mínima:
- Para (s_1): ( \frac{20}{5} = 4 )
- Para (s_2): ( \frac{8}{1} = 8 )
- Menor razão é 4, então (s_1) sai.
-
Atualização do Tableau:
Realizamos pivotamento em (x_1) na linha (s_1) dividindo a linha por 5 e ajustando as outras linhas para zerar o coeficiente de (x_1) nelas.
Segundo Tableau:
[ \begin{array}{c|cccccc|c} \text{Base} & x_1 & x_2 & x_3 & x_4 & s_1 & s_2 & \text{RHS} \ \hline x_1 & 1 & -\frac{1}{5} & 0 & \frac{4}{5} & \frac{1}{5} & 0 & 4 \ s_2 & 0 & \frac{11}{5} & 3 & \frac{1}{5} & -\frac{1}{5} & 1 & 4 \ \hline Z & 0 & -\frac{3}{5} & 1 & \frac{12}{5} & -\frac{2}{5} & 0 & -8 \end{array} ]
Segunda Iteração:
-
Escolha da Variável Entrante: Variáveis com custos reduzidos negativos: (x_2) e (s_1), mas (x_3) e (x_4) têm custos positivos. Pela Regra de Bland, escolhemos (x_3).
-
Teste da Razão Mínima:
- Para (s_2): ( \frac{4}{3} = 1.\overline{3} )
-
Atualização do Tableau:
Pivotamos em (x_3) na linha (s_2).
Terceiro Tableau:
[ \begin{array}{c|cccccc|c} \text{Base} & x_1 & x_2 & x_3 & x_4 & s_1 & s_2 & \text{RHS} \ \hline x_1 & 1 & -\frac{1}{5} & 0 & \frac{4}{5} & \frac{1}{5} & 0 & 4 \ x_3 & 0 & \frac{11}{15} & 1 & \frac{1}{15} & -\frac{1}{15} & \frac{1}{3} & \frac{4}{3} \ \hline Z & 0 & -\frac{4}{3} & 0 & \frac{7}{3} & -\frac{1}{3} & -\frac{1}{3} & -\frac{28}{3} \end{array} ]
Terceira Iteração:
-
Escolha da Variável Entrante: (x_4) tem custo reduzido positivo.
-
Teste da Razão Mínima:
- Para (x_1): ( \frac{4}{\frac{4}{5}} = 5 )
-
Atualização do Tableau:
Pivotamos em (x_4) na linha (x_1).
Quarto (e Último) Tableau:
[ \begin{array}{c|cccccc|c} \text{Base} & x_1 & x_2 & x_3 & x_4 & s_1 & s_2 & \text{RHS} \ \hline x_4 & \frac{5}{4} & -\frac{1}{4} & 0 & 1 & \frac{1}{4} & 0 & 5 \ x_3 & -\frac{1}{12} & \frac{3}{4} & 1 & 0 & -\frac{1}{12} & \frac{1}{3} & 1 \ \hline Z & -\frac{35}{12} & -\frac{3}{4} & 0 & 0 & -\frac{11}{12} & -\frac{1}{3} & -21 \end{array} ]
4. Solução Ótima:
Analisando o último tableau, todos os custos reduzidos são não positivos, indicando que a solução é ótima.
- Variáveis Básicas:
- (x_3 = 1) (da linha de (x_3))
- (x_4 = 5) (da linha de (x_4))
- Variáveis Não Básicas (zero):
- (x_1 = 0)
- (x_2 = 0)
- (s_1 = 0)
- (s_2 = 0)
- Valor Ótimo:
- (Z = 21) (como (-Z = -21), então (Z = 21))
Resposta Final:
- Base Ótima: As variáveis básicas na solução ótima são (x_3) e (x_4).
- Valor Ótimo do Problema: (Z = 21).
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.