Exercício 3:
Considere o seguinte problema de otimização:
a) Determine o problema dual associado;
b) Resolva um dos dois problemas (primal ou dual) pelo método Dual-Simplex
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
sujeito a:
sujeito a:
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₃:
(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).
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
. Encontramos que
(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.
– 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.
x₁ = 0, x₂ = 0, x₃ = 2.
Passo 7
Nesse ponto o valor ótimo do primal é
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.
– 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
sujeito a
sujeito a
com
.
Resolvendo o primal por Dual-Simplex, obtemos a solução ótima
Resolvendo o primal por Dual-Simplex, obtemos a solução ótima
válida somente para