Dualidade e Método Simplex: Construção do Dual e Solução Ótima
Construa o dual do seguinte primal
Primal (minimização)
Min z = 2x1 + x2 - 3x3 + 4x4 + 5x5
s.a. 2x1 + x2 - 8x3 + x4 + x5 ≤ 20
-x1 + 2x2 + 2x3 - 2x4 + 2x5 ≥ 15
x1, x3 ≥ 0; x2, x4, x5 ≤ 0
Regras de conversão: primal (min) para dual (max)
Primal (min) Dual (max)
2 restrições 2 variáveis
1 não típica 1 não típica
2 não típica 2 não típica
5 variáveis 5 restrições (igual)
1 típica 2 não típica
2 não típica
3 típica
4 não típica
5 não típica
Dual
Max w = 20y1 + 15y2
s.a. 2y1 - y2 ≤ 2
y1 + 2y2 ≥ 1
8y1 + 2y2 ≤ -3
y1 - 2y2 ≥ 4
y1 + 2y2 ≥ 5
y1 ≤ 0; y2 ≥ 0
Primal, dual e Simplex
Primal (máximo)
Max z = x1 + 3x2
s.a. x1 - 2x2 ≤ 4
x1 + x2 ≤ 3
x1, x2 ≥ 0
Primal (max) Dual (min)
2 restrições 2 variáveis
1 típica 1 típica
2 típica 2 típica
2 variáveis 2 restrições
1 típica 1 típica
2 típica 2 típica
Dual
Min w = 4y1 + 3y2
s.a. y1 + y2 ≥ 1
-2y1 + y2 ≥ 1
y1 ≥ 0; y2 ≥ 0
Forma padrão
Primal
Max z = x1 + 3x2
s.a. x1 - 2x2 + x3 = 4
x1 + x2 + x4 = 3
x1, x2, x3, x4 ≥ 0
Dual
Min w = 4y1 + 3y2
s.a. y1 + y2 - y3 = 1
-2y1 + y2 - y4 = 3
y1, y2, y3, y4 ≥ 0
Variáveis básicas e não básicas
Primal: V.B = x3, x4; V.N.B = x1, x2
Dual: V.B = y3, y4; V.N.B = y1, y2
Tabelas do Simplex (primal)
Tabela 1
Base x1 x2 x3 x4 LD
z -1 -3 0 0 0
x3 1 -2 1 0 4
x4 1 1 0 1 3
Entra x2 (coluna pivô). Razões: L1 = 4/(-2) = -2 (desconsiderada); L2 = 3/1 = 3. Sai x4.
Tabela 2
Base x1 x2 x3 x4 LD
z -2 0 0 -3 -4
x3 3 0 0 2 10
x2 1 1 0 1 3
Operações: L0 = L0 - 3·L2; L1 = L1 + 2·L2.
Solução ótima
Primal: Z = 9; x1 = 0; x2 = 3; x3 = 10; x4 = 0
Dual: W = 9; y1 = 0; y2 = 3; y3 = 2; y4 = 0