Considere o problema a seguir:

minimizar: Z = 2x1 + 3x2 + x3
sujeito a: x1 + 4x2 + 2x3 ≥ 8
3x1 + 2x2 ≥ 6
com: xi ≥ 0 para i = 1, 2, 3

(a) Reformule este problema para que se adapte à nossa forma-padrão para um
modelo de programação linear.
(b) Usando o método do “grande número (M)”, avance pelo método Simplex,
passo a passo, para solucionar o problema.
(c) Usando o método das duas fases, avance pelo método Simplex, passo a passo,
para resolver o problema.
(d) Compare a sequência das soluções BV adjacentes obtidas nos itens (b) e (c).
Qual destas soluções são viáveis somente para o problema artificial obtido

introduzindo-se variáveis artificiais que são, na verdade, viáveis para o prob-
lema real?

(e) Use um pacote de software baseado no método Simplex para resolver o problema.

Question

Considere o problema a seguir:

minimizar: Z = 2x1 + 3x2 + x3
sujeito a: x1 + 4x2 + 2x3 ≥ 8
3x1 + 2x2 ≥ 6
com: xi ≥ 0 para i = 1, 2, 3

(a) Reformule este problema para que se adapte à nossa forma-padrão para um
modelo de programação linear.
(b) Usando o método do “grande número (M)”, avance pelo método Simplex,
passo a passo, para solucionar o problema.
(c) Usando o método das duas fases, avance pelo método Simplex, passo a passo,
para resolver o problema.
(d) Compare a sequência das soluções BV adjacentes obtidas nos itens (b) e (c).
Qual destas soluções são viáveis somente para o problema artificial obtido

introduzindo-se variáveis artificiais que são, na verdade, viáveis para o prob-
lema real?

(e) Use um pacote de software baseado no método Simplex para resolver o problema.

Accepted Answer

Vamos abordar cada um dos itens do problema de programação linear proposto.

### (a) Reformulação para a Forma-Padrão

Para reformular este problema na forma-padrão, precisamos transformar as desigualdades em igualdades adicionando variáveis de folga e artificiais.

O problema original é:

$$
\begin{aligned}
& \text{Minimizar} & Z = 2x_1 + 3x_2 + x_3 \
& \text{sujeito a} & x_1 + 4x_2 + 2x_3 & \geq 8 \
& & 3x_1 + 2x_2 & \geq 6 \
& & x_i & \geq 0 \quad \text{para} \ i = 1, 2, 3
\end{aligned}
$$

Primeiro, transformamos as desigualdades em igualdades:

1. Para $ x_1 + 4x_2 + 2x_3 \geq 8 $, subtraímos uma variável de excesso $ s_1 $ e adicionamos uma variável artificial $ A_1 $:
   $$
   x_1 + 4x_2 + 2x_3 - s_1 + A_1 = 8
   $$

2. Para $ 3x_1 + 2x_2 \geq 6 $, subtraímos uma variável de excesso $ s_2 $ e adicionamos uma variável artificial $ A_2 $:
   $$
   3x_1 + 2x_2 - s_2 + A_2 = 6
   $$

Assim, o problema reformulado na forma-padrão é:

$$
\begin{aligned}
& \text{Minimizar} & Z = 2x_1 + 3x_2 + x_3 \
& \text{sujeito a} & x_1 + 4x_2 + 2x_3 - s_1 + A_1 & = 8 \
& & 3x_1 + 2x_2 - s_2 + A_2 & = 6 \
& & x_i, s_j, A_k & \geq 0 \quad \text{para} \ i = 1, 2, 3, \ j = 1, 2, \ k = 1, 2
\end{aligned}
$$

### (b) Método do Grande Número (M)

Usamos o método do grande número $ M $ para penalizar as variáveis artificiais na função objetivo. A nova função objetivo se torna:

$$
Z = 2x_1 + 3x_2 + x_3 + MA_1 + MA_2
$$

A tabela inicial do Simplex é:

$$
\begin{array}{c|cccccc|c}
\text{Base} & x_1 & x_2 & x_3 & s_1 & s_2 & A_1 & A_2 & \text{RHS} \
\hline
A_1 & 1 & 4 & 2 & -1 & 0 & 1 & 0 & 8 \
A_2 & 3 & 2 & 0 & 0 & -1 & 0 & 1 & 6 \
\hline
Z & -2 & -3 & -1 & 0 & 0 & -M & -M & 0
\end{array}
$$

Executamos o método Simplex passo a passo, pivotando para eliminar as variáveis artificiais da base.

### (c) Método das Duas Fases

Na Fase 1, minimizamos a soma das variáveis artificiais:

$$
Z' = A_1 + A_2
$$

Tabela inicial da Fase 1:

$$
\begin{array}{c|cccccc|c}
\text{Base} & x_1 & x_2 & x_3 & s_1 & s_2 & A_1 & A_2 & \text{RHS} \
\hline
A_1 & 1 & 4 & 2 & -1 & 0 & 1 & 0 & 8 \
A_2 & 3 & 2 & 0 & 0 & -1 & 0 & 1 & 6 \
\hline
Z' & -4 & -6 & -2 & 1 & 1 & 0 & 0 & -14
\end{array}
$$

Executamos o método Simplex para a Fase 1 até que todas as variáveis artificiais sejam eliminadas da base. Em seguida, passamos para a Fase 2, onde otimizamos a função objetivo original.

### (d) Comparação das Soluções BV Adjacentes

Comparar as soluções adjacentes obtidas nos itens (b) e (c) envolve verificar quais soluções são viáveis apenas para o problema artificial. As variáveis artificiais que permanecem na base com valor não zero indicam soluções que são viáveis apenas para o problema modificado, não para o problema real.

### (e) Uso de Software

Para resolver o problema usando software baseado no método Simplex, como o MATLAB, Python (SciPy), ou LINDO, podemos utilizar os seguintes comandos:

Em Python (usando SciPy):

```python
from scipy.optimize import linprog

c = [2, 3, 1]
A = [[-1, -4, -2], [-3, -2, 0]]
b = [-8, -6]

res = linprog(c, A_ub=A, b_ub=b, bounds=(0, None), method='simplex')
print(res)
```

Este código resolve o problema de programação linear e retorna os valores ótimos das variáveis e o valor mínimo da função objetivo.

Considere o problema a seguir: minimizar: Z = 2x1 + 3x2 + x...

Ask a question and receive an answer instantly