Exercício 3:

Considere o seguinte problema de otimização:
& Minimizar 2 x1+5 x2 & sujeito a: & & x1-2 x2+4 x3 <= r & x1+x2+2 x3 <= 10 & 2 x1-x2+x3 >= 2 & x >= 0
a) Determine o problema dual associado;
b) Resolva um dos dois problemas (primal ou dual) pelo método Dual-Simplex

Passo 1

A questão é um problema de Programação Linear (PL), do tipo minimização, com 3 variáveis de decisão e 3 restrições (duas do tipo “≤” e uma do tipo “>=”). Vamos precisar formular o dual e depois resolver o primal pelo método Dual-Simplex.

Passo 2

O dual de um PL de minimização com restrições mistas se constrói atribuindo variáveis duais y₁≥0, y₂≥0 para as duas restrições “≤” e y₃≤0 para a restrição “>=”. O dual é:
Maximizar r y1 + 10 y2 + 2 y3
sujeito a:
y1 + y2 + 2 y3 ,>=, 2
-2 y1 + y2 - y3 ,>=, 5
4 y1 + 2 y2 + y3 ,>=, 0
com y_{1} \ge 0,; y_{2} \ge 0,; y_{3} \le 0.

Passo 3

Para aplicar Dual-Simplex no primal, primeiro colocamos em forma canônica de igualdade:
(i) x₁ − 2x₂ + 4x₃ + s₁ = r
(ii) x₁ + x₂ + 2x₃ + s₂ = 10
(iii) 2x₁ − x₂ + x₃ − s₃ = 2
E multiplicamos (iii) por −1 para ter coeficiente +1 em s₃:
[-2x₁ + x₂ - x₃ + s₃ = -2.
As variáveis básicas iniciais são s₁,s₂,s₃, mas s₃ fica com RHS = −2, ou seja, primal inviável. Tomamos o objetivo original Min Z = 2x₁+5x₂ e definimos o objetivo auxiliar de Dual-Simplex como Max W = −2x₁ − 5x₂.
No tableau inicial todas as reduções E_j = c_j ≤ 0, então temos dual-viabilidade mas falta primal-viabilidade (RHS de s₃ é negativo).

Passo 4

Procuramos a linha com RHS negativo (linha de s₃) e, entre as colunas com coeficiente negativo nessa linha, calculamos o menor quociente Ej / arj. Encontramos que a3,3 = -1 (coluna x₃) dá o menor quociente, então x₃ entra e s₃ sai. Fazendo o pivô na linha 3, coluna x₃, obtemos uma nova base com variáveis básicas s₁, s₂, x₃.

Passo 5

Após o pivô, o tableau mostra:
– as reduções E_j continuam todas ≤ 0 (mantemos dual-viabilidade),
– os novos RHS são s₁ = r − 8, s₂ = 6, x₃ = 2.
Para que todos os RHS fiquem ≥ 0 (primal-viabilidade), precisamos de r − 8 ≥ 0, i.e. r ≥ 8.

Passo 6

Portanto, para r ≥ 8 atingimos simultaneamente a dual-viabilidade e a primal-viabilidade, logo a base é ótima. Lê-se a solução primária:
x₁ = 0, x₂ = 0, x₃ = 2.

Passo 7

Nesse ponto o valor ótimo do primal é
Z^* = 2cdot 0 + 5cdot 0 = 0

Passo 8

Em resumo:
– O dual foi formulado conforme o passo 2.
– Pelo método Dual-Simplex no primal chegamos à solução ótima x* = (0,0,2) com valor mínimo Z* = 0, válida apenas se r ≥ 8.

Resposta

O dual é
Maximizar r y1 + 10 y2 + 2 y3
sujeito a
y1 + y2 + 2 y3 >= 2, -2y1 + y2 - y3 >= 5, 4y1 + 2y2 + y3 >= 0,
com y1 >= 0,; y2 >= 0,; y3 <= 0.
Resolvendo o primal por Dual-Simplex, obtemos a solução ótima
x1 = 0,; x2 = 0,; x3 = 2, Zmin = 0,
válida somente para r >= 8.

Exercícios relacionados