Pesquisa Operacional - Dualidade

Prévia do material em texto

Definição de dualidade
Diversos autores conceituam dualidade como a possibilidade de existência matemática de um algoritmo simétrico (dual) para todo modelo original (primal) de programação linear que conduz a uma mesma solução.
 À solução do algoritmo dual também corresponderá a mesma
solução do algoritmo primal. Note que, quando estamos 
trabalhando com um modelo dual, chamamos ao modelo inicial, que lhe deu origem, de modelo primal.
Definição das variáveis e do número de restrições do dual 
A definição das variáveis duais de um problema está diretamente relacionada ao número de restrições de seu modelo primal.
Desse modo, o modelo dual terá um número de variáveis duais na mesma proporção do número de restrições do modelo primal.
Cont...
Elaboração da função-objetivo do modelo dual
 A função-objetivo de um modelo de programação linear é formada por seu objetivo e o somatório dos produtos entre os coeficientes do objetivo e as variáveis do modelo. Nesse sentido, o objetivo de um modelo dual será sempre o oposto de seu primal, ou seja, um objetivo primal de minimização gera um objetivo dual de maximização e vice-versa.
 Na função-objetivo dual, o termo independente de uma restrição primal será o coeficiente da variável dual oriunda dessa restrição
Estabelecimento das restrições do modelo dual
 A restrição de um modelo de programação linear é formada pelo
 lado esquerdo (variáveis e seus coeficientes), por um sinal lógico
(≤, =, ≥), e pelo lado direito (termo independente) de uma
expressão matemática.
Cada variável de decisão do primal origina uma restrição do
modelo dual. Desse modo, o lado esquerdo de uma restrição dual
é formado pela coluna dos coeficientes da variável que o origina
no modelo primal, multiplicados, termo a termo, pela variável dual
oriunda da respectiva restrição primal
Dual... Primol para Dual
Escreva o dual do seguinte modelo primal.
 1 - Zmáx = x1 + x2 + 3x3
s.a 1º coluna
x1 + x2 + x3 ≤ 10 y1 (1,1,1) 
2 x1 + x2 +4 x3 ≤ 12 y2 (2,1,4) 
x1 + 3 x2 - x3 ≤ 9 y3(1,3, - 1) 
x1 , x2 e x3 ≥ 0
1º Começar pelas restrições pegar os coeficientes de cada linha e transportar em coluna.
1y1 + 2 y2 +1 y3 ≥ 1
1Y1 + 1 y2 + 3 y3 ≥ 2
1Y1 + 4 y2 - 1 y3 ≥ 3
2º Desigualdade ≤ vai passar a ser ≥ ( COLOCAR OS SINAIS DA DESIGUALDADE INVERTIDO)
3º Após as desigualdades vou pegar o coeficiente da equação Z (1,2 e 3)
4º A função Z vai passar ser D e com os coeficientes das restrições.
 D = 10 Y1 + 12 y2 + 9y3 
Y1 , y2 e y3 ≥ 0
 2 - Zmin = 2x1 + 4x2 + 10x3
 x1 + x2 + x3 ≥ 120 Y1 ( 1,1,1)
 x1 + x2 + 5x3 ≥ 30 y2 ( 1,1,5)
 x1 , x2 e x3 ≥ 0
1 y1 + 1y2 ≤ 2
1y1 +1 y2 ≤ 4
1y1 + 5 y2 ≤ 10
y1 e y2 ≥ 0
D = 120 y1 + 30 y2
Exercícios
1 - Escreva o dual dos seguintes modelo primal abaixo:
 a) Zmin = 2x1 + 4x2 + 10x3
s.a 
x1 + x2 + x3 ≥ 120
x1 + x2 + 5x3 ≥ 30
x1 , x2 e x3 ≥ 0
b) Zmin = 5x1 + 3x2 + 12x3
s.a 
x1 + x2 + x3 ≥ 50
x1 + x2 + 5x3 ≥ 100
x1 , x2 e x3 ≥ 0
c) Zmáx= 2x1 + x2 + 5x3
s.a 
x1 -2 x2 + x3 ≤ 5
3x1 + x2 + 3x3 ≤ 8
x1 +2 x2 - 2x3 ≤ 10
 x1 , x2 e x3 ≥ 0
d) Zmáx= 20x1 +10 x2 + 50x3
s.a 
2x1 - x2 +3x3 ≤115
3x1 + x2 - 3x3 ≤ 80
x1 +2 x2 - 5x3 ≤ 100
 x1 , x2 e x3 ≥ 0
Cont...
2 – Resolva pelo método simplex o seguinte problema de programação linear.
a) Zmáx= 3x1 + 5x2
s.a 
2x1 +4 x2 ≤ 10
6x1 + x2 ≤ 20
x1 - x2 ≤ 30
 x1 , x2 e x3 ≥ 0
3 – O preço de x1 é de $50,00 e de x2 é de $65,00 o objetivo é maximizar o lucro no período, qual é a função objetiva desse problema?
Cont...
4 - Considere um problema de Programação Linear com duas variáveis (X1 e X2) e três inequações, cujo primeiro quadro do simplex é:
_________________________________
 BASE    X1       X2       X3     X4        X5      b
__________________________________
  X3         2         5        1         0         0       60
  X4         1         1        0         1         0       18
  X5         3         1        0         0         1       44
 __________________________________
    -Z      -2       - 1         0       0           0        0
___________________________________
b = LD
X3,X4 e X5 = folgas
Na construção do 2º quadro do simplex, a variável que entrará na base e a que sairá da base serão respectivamente?