Pesquisa Operacional
Prof. José Luiz
1
DUALIDADE
DUALIDADE
2
DUALIDADE
DUALIDADE
Exercício Resolvido: – Escreva o Dual do seguinte modelo Primal
3
DUALIDADE
Exercício 2 – Escreva o Dual do seguinte modelo Primal
MAX Z = x1 + 2x2 + 3x3
Sujeito à: x1 + x2 + x3 ≤ 10
2x1 + x2 + 4x3 ≤ 12
x1 + 3x2 – x3 ≤ 9
x1, x2, x3 ≥ 0
DUALIDADE
Exercício 3 – Escreva o Dual do seguinte modelo Primal
MAX Z = 2x1 + 3x2
Sujeito à: x1 + x2 ≥ 10
2x1 + x2 ≤ 16
x1, x2 ≥ 0
4
DUALIDADE
Exercício 4 – Escreva o Dual do seguinte modelo Primal
MIN Z = 3x1 + 2x2
Sujeito à: 2x1 + x2 ≥ 10
x1 + 5x2 ≥ 15
x1, x2 ≥ 0
DUALIDADE
Exercício 5 – Escreva o Dual do seguinte modelo Primal
MAX Z = x1 + x2 + 2x3
Sujeito à: x1 + 2x2 ≤ 10
3x1 + 4x2 + x3 ≤ 20
x1, x3 ≥ 0; x2 é livre
5
DUALIDADE
Exercício 6 – Escreva o Dual do seguinte modelo Primal
Min Z = 2x1 + 4x2 + 10x3
Sujeito à: x1 + x2 + x3 ≤ 120
x1 + 2x2 + 5x3 ≤ 30
x1, x2, x3 ≥ 0;
Analogia entre as Soluções Primal e Dual
a. A cada solução viável básica primal não ótima corresponde
uma solução básica inviável dual.
b. A solução ótima primal corresponde à solução ótima dual com
Z=0.
c. O coeficiente da variável de decisão na função objetivo primal
é o valor da variável de folga correspondente na solução dual.
(coeficiente de xi = valor de yFi)
d. O coeficiente da variável de folga da função objetivo primal é o
valor da variável de decisão correspondente na solução dual.
(coeficiente de xFi = valor de yi)
Como o primal é dual do próprio dual, vale o raciocínio no sentido
dual → primal.
(coeficiente de yi = valor de xFi)
(coeficiente de yFi = valor de xi).
6
O modelo dual correspondente é:
7
Min D – 10y1 – 12y2 – 9y3 = 0 ou
Max (-D) + 10y1 + 12y2 + 9y3 = 0
PRIMAL
DUAL
8
Solução do DUAL através da solução definitiva do SIMPLEX
A próxima solução viável básica do primal, com a entrada da variável x3
(coeficiente -3) e a saída da variável xF2 (12÷4 = 3), após a pivotamento, será:
Solução:
Usando a correspondência descrita, vamos montar o quadro dual
correspondente:
coeficientes de xi → valores de yFi
coeficientes de xFi → valores de yi
valores de xi → coeficientes de yFi
valores de xFi → coeficiente de yi
9
PRIMAL
DUAL
Exercício 1:
Transforme a solução definitiva do Primal no quadro correspondente do Dual
10
Exercício 1:
Transforme a solução definitiva do Primal no quadro correspondente do Dual
Conclusão: Dado um problema de programação linear, podemos escolher
entre solucionar o modelo primal ou o modelo dual correspondente. A escolha
leva em consideração o esforço computacional, que depende do número de
restrições, variáveis artificiais, etc.
11
2º) Escreva o Dual do seguinte quadro primal do Simplex (Solução ótima):
2º) Escreva o Dual do seguinte quadro primal do Simplex (Solução ótima):
12
2º) Resposta:
13