15/09/2011

Universidade do Estado do Par Centro de Cincias Naturais e Tecnologia Curso de Engenharia de Produo

Introduo Pesquisa OperacionalAula 4 DualidadeProf. Mariana Carneiro

Castanhal-Par 2011

Em determinadas situaes, a quantidade de clculos necessria para resolver um modelo linear pelo mtodo Simplex pode ser reduzida. O modelo inicial, chamado de Primal, pode ser substitudo por outro modelo chamado Dual, cuja soluo mais rpida. Ser mostrado que, uma vez conhecida a soluo do Dual, conhece-se, em conseqncia, a soluo do Primal, o que resolve o problema. Tanto do ponto de vista terico como prtico, a Teoria da Dualidade um dos mais importantes tpicos da Programao Linear (PL).

1

15/09/2011

Estudos mostraram que intrinsecamente associado a cada modelo de PL (denominado Primal) h outro modelo (denominado Dual) com vrias interessantes propriedades.Possibilitou o surgimento de variaes do Mtodo Simplex (como o Mtodo Dual Simplex ou Mtodos Primais-Duais).

Todas variveis devem ser no-negativas; Todas restries devem ser desigualdades com: Modelo de maximizao = restries do tipo Modelo de minimizao = restries do tipo

Definio: a todo modelo de maximizao da forma (1), denominado Primal, est associado um modelo de minimizao da forma (2), chamado Dual:(1) Primal Max Z = CT X (2) Dual Min W = YB sujeito a: AX B , X 0. sujeito a: YA C, Y 0.

Definir uma varivel Dual (Y 0) para cada restrio do Primal. Fazer o vetor C de coeficientes de variveis primais na funo objetivo ser o vetor de constantes das restries do Dual. Fazer o vetor B de constantes nas restries do Primal ser o vetor de coeficientes de variveis duais na funo objetivo do Dual.

2

15/09/2011

A transposta da matriz a de coeficientes de variveis primais nas restries do Primal, At, ser a matriz dos coeficientes das variveis duais nas restries do Dual. O sentido das desigualdades das restries do Dual ser o inverso do sentido das desigualdades das restries do Primal. O critrio de otimizao da funo objetivo do Dual ser maximizao se o Primal for de minimizao, e ser de minimizao caso contrrio.

Considere o seguinte modelo Primal: Max Z = x1 + 2x2 -3x3 + 4x4 s. a: x1 + 2x2 + 2x3 3x4 25 2x1 + x2 3x3 + 2x4 15 xi 0, i =1, 4. As regras apresentadas levam ao modelo Dual abaixo: Min W = 25y1 + 15y2 s.a: y1 + 2y2 1 2y1 + y2 2 2y1 3y2 -3 -3y1 + 2y2 4 y1 0, y2 0.

3

15/09/2011

Para designar o dual, observe o sentido das setas. Se o problema primal for de maximizao, utilizar as regras da esquerda para a direita Se o problema primal for de minimizao, utilizar as regras da direita para a esquerda.

4

15/09/2011

Considerando o modelo abaixo de PL, escreva o modelo dual do mesmo:

5

15/09/2011

Considerando o modelo abaixo de PL, escreva o modelo dual do mesmo:

Considerando o modelo abaixo de PL, escreva o modelo dual do mesmo:

6