Apostila com exercicos

˜
CENTRO FEDERAL DE EDUCAC
¸ AO
´
TECNOLOGICA
DE MINAS GERAIS
Departamento de Ensino Superior
Curso de Engenharia de Produ¸ c˜ ao Civil

Pesquisa Operacional I

4. Dualidade em Otimiza¸c˜ ao Linear
Sum´
ario
1

Dualidade em Programa¸c˜ ao Linear

2

M´ etodo Dual-Simplex

24

3

Algoritmo Dual-Simplex

27

Professor:

S´ergio Ricardo de Souza

Belo Horizonte, dezembro de 2014

2

2

1

Dualidade em Programa¸c˜ ao Linear

Exemplo 1 Considere um problema de produ¸c˜ao no qual as mat´erias primas s˜ ao couro e pano.
Problema de Produ¸c˜ ao (Problema Primal) max z = 25x1 + 35x2 + 50x3 suj. a
3x1 + 4x2 + 5x3
2x1 + 3x2 + 4x3 x1 x2 x3 x4 x5 + 33x4 + 36x5
+ 3x4 + 6x5 ≤ 42
+ 3x4 + 3x5 ≤ 24
≥ 0
≥ 0
≥ 0
≥ 0
≥ 0

xi: quantidade do produto i a ser fabricada: i=1 i=2 i=3 i=4 i=5 →
→
→
→
→

sapato; botina; carteira; chap´eu; malas.

3

Um concorrente prop˜ oe a compra de toda a mat´eria-prima da f´abrica, na seguinte forma:
a) Cada unidade de couro valer´a π1 ≥ 0;
b) Cada unidade de pano valer´a π2 ≥ 0;
c) O custo de compra da mat´eria-prima ser´a dado pela quantidade total da mat´eria-prima j dispon´ıvel, multiplicada pelo seu custo:
Φ = 42π1 + 24π2
O concorrente deseja minimiz´a-lo, manipulando os custos das mat´erias-primas;
d) Os valores de π1 e π2 ser˜ao fixados pelo concorrente.
Entretanto, devem assegurar uma vantagem para o dono da f´ abrica. A vantagem do dono da f´abrica ser´a garantida, desde que o valor de venda da mat´eria-prima utilizada na fabrica¸c˜ ao de cada produto seja maior ou igual ao lucro, caso o produto seja fabricado. Assim:
3π1 + 2π2 ≥ 25
4π1 + 3π2 ≥ 35
5π1 + 4π2 ≥ 50
3π1 + 3π2 ≥ 33
6π1 + 3π2 ≥ 36

−→
−→
−→
−→
−→

sapato botina carteira chap´eu malas

4

Problema do concorrente (Problema Dual) min Φ = 42π1 suj. a
3π1
4π1
5π1
3π1
6π1

+
+
+
+
+
+

24π2
2π2
3π2
4π2
3π2
3π2
π1 π1 ≥
≥
≥
≥
≥