aula 5 Pesquisa Operacional

Prévia do material em texto

Dualidade em Programação 
Linear 
Fabiana Gomes dos Passos 
Referências 
 
 
 
 
• ANDRADE, Eduardo Leopoldino de. 
Introdução à pesquisa operacional: métodos e 
modelos para análise de decisões. 3. ed. Rio 
de Janeiro: LTC, 2004.192 p. 
 
• LACHTERMACHER, Gerson. Pesquisa 
operacional na tomada de decisões. 2. ed. 
rev. e atual. Rio de Janeiro: Elsevier, 2004. 
384 p. 
 
 
Roteiro da aula 
 
• Dualidade em Programação Linear 
 
– Montagem de um problema dual 
– Relações ente os modelos primal e dual 
– Exemplo de Aplicação 
 
 
 
 
Dualidade em Programação Linear 
 
• Todo problema de Programação linear, denominado de 
primal, possui um segundo problema associado, chamado 
dual; ambos são completamente inter-relacionados, de forma 
que a solução ótima de um fornece a informações completas 
sobre o outro; 
 
• Dependendo do número de restrições e variáveis do 
problema de programação linear, em algumas situações pode 
ser mais interessante computacionalmente resolver o 
problema dual em vez do problema primal. 
Montagem do Problema Dual 
 
 
Problema Primal (P) 
definido como: 
O problema Dual (D) é 
definido como: 
 
O problema Dual 
 De uma forma geral: 
Primal Dual 
 
 
),...,2,1(
),...,2,1(
0
:.
1
1
nj
mi
x
bxaas
xc
j
n
j
iiij
n
j
jj







Max Min 
),...,2,1(
),...,2,1(
0
:.
1
1
nj
mi
y
cyaas
yb
i
m
i
jiij
m
i
ii







n é o número de variáveis 
m é o número de restrições do problema 
Montagem do Problema Dual 
• O problema dual, para modelos em que as restrições são desigualdades do 
tipo (≤), é construído a partir do primal da seguinte forma: 
 
1. Cada restrição, em um problema, corresponde a uma variável no outro; 
2. Os elementos do lado direito das restrições, em um problema são os 
coeficientes da função-objetivo do outro problema. 
3. Se o objetivo de um problema é maximizar, o do outro será de minimizar, 
e vice-versa. 
4. O problema de maximização tem restrição com sentido (≤), e o problema 
de minimização tem restrições com o sentido (≥). 
5. As variáveis de ambos os problemas são não negativas. 
 
 
Relações entre os modelos primal e dual 
 
• RESUMO 
o Se a função objetivo do dual é de minimização, a do primal de 
maximização, e vice-versa; 
o Os termos constantes das restrições do dual (lado direito das restrições) 
são os coeficientes da função objetivo do primal; 
o Os coeficientes da função objetivo do dual são os termos constantes das 
restrições do primal; 
o As restrições do dual são do tipo ≥ e as do primal são do tipo ≤; 
 
• O número de variáveis do dual é igual ao número de restrições do 
primal; 
• O número de restrições do dual é igual ao número de variáveis do 
primal; 
• A matriz dos coeficientes do dual é a transposta da matriz dos 
coeficientes do primal. 
 
Resumo das Relações anteriores 
• Caso a função objetivo primal seja de minimização, então o quadro deve 
ser lido da direita para a esquerda. 
 
 
Para ilustrar a teoria, vejamos agora um exemplo numérico: 
• Modelo matemático primal: 
 Maximizar Z = 300 X1 + 500 X2 
 sujeito a: 
 2 X1 + X2  16 
 X1 + 2X2  11 
 X1 + 3X2  15 
 X1 e X2 ≥ 0 
 
• O modelo matemático dual associado ao modelo matemático primal: 
 Minimizar z = 16 Y 1 + 11Y 2 + 15 Y 3 
 sujeito a: 
 2 Y 1 + Y 2 + Y 3  300 
 Y 1 + 2Y 2 + 3Y 3  500 
 y1 , y2 e y3 ≥ 0 
 
 
Exemplo - Problema Dual 
Exemplo - Problema Dual 
Problema de Minimização 
 
Min z = 7y1 + 30y2 
Sujeito a 
2y1 + 7y2 ≥ 110 
y1 + 7y2 ≥ 65 
y1, y2 ≥ 0 
 
Problema de Maximização 
 
Max Z = 110X1 + 65X2 
Sujeito a 
2X1 + X2 ≤ 7 
7X1 + 7X2 ≤ 30 
X1, X2 ≥ 0 
 
Relação entre os valores ótimos do 
primal e do dual 
 
• Existe uma relação básica entre os valores das funções 
objetivo do problema primal e do problema dual que pode 
ser enunciada da seguinte forma: 
• Sendo Z o valor da função objetivo do primal e z o 
correspondente valor do dual, duas propriedades ocorrem 
durante o processo de solução: 
 
◦ Para quaisquer duas soluções viáveis do primal e do dual, 
tem-se: Z ≤z 
◦ As soluções ótimas de ambos os problemas guardam entre 
si a seguinte relação: max Z = min z 
 
Exemplo - Relação entre os valores 
ótimos do primal e do dual 
Max Z = 5x1+ 6x2 
Sujeito a: 
 x1+ 2x2 ≤ 14 
 x1 + x2 ≤ 9 
 7x1 + 4x2 ≤ 56 
 x1 e x2 ≥ 0 
 
 
Quadro final do Simplex Primal 
Min Z = 14y1+9y2+56y3 
Sujeito a: 
 y1+y2+7y3 ≥ 5 
 2y1+y2+4y3 ≥6 
 y1,y2,y3≥0 
 
 
Quadro final do Simplex Dual 
y1 y2 y3 y4 y5 b 
Y2 0 1 10 -2 1 4 
y1 1 0 -3 1 -1 1 
Base 0 0 8 4 5 50 
x1 x2 x3 x4 x5 b 
X2 0 1 1 -1 0 5 
X1 1 0 -1 2 0 4 
x5 0 0 3 -10 1 8 
Base 0 0 1 4 0 50 
Relação entre os valores ótimos do 
primal e do dual 
 
• As soluções ótimas dos dois problemas guardam a relação: 
max Z = min z = 50; 
 
• Os valores das variáveis não-básicas no primal, são iguais aos 
valores das variáveis básicas do dual, e vice-versa. 
 
O problema Dual 
 
• Existem algumas razões para o estudo dos problemas 
duais. 
– A primeira e mais importante são as interpretações 
econômicas que podemos obter dos valores das variáveis do 
Dual na solução ótima, tais como variações marginais. 
 
– A segunda está ligada ao número de restrições. 
Computacionalmente falando é, algumas vezes, mais 
eficiente resolver o problema Dual. 
Interpretação Econômica das variáveis 
Duais 
 Uma indústria dispõe de três recursos A, B e C, em quantidades limitadas, com os 
quais pretende produzir dois produtos a que chamaremos PROD 1 e PROD 2. A 
Tabela, logo abaixo, dá a utilização unitária de cada recurso em cada um dos 
produtos e a disponibilidade de cada recurso. 
 A indústria sabe que cada unidade produzida do PROD 1 dá uma margem unitária 
de lucro de $ 5, e cada unidade produzida do PROD 2 dá uma margem unitária de 
lucro de $ 6. O problema de programação da produção da empresa é determinar 
a quantidade a ser feita de PROD 1 e PROD 2 de forma a maximizar a margem de 
lucro total. 
Recurso 
Recurso gasto para fazer 1 unidade de 
Disponibilidade 
PROD 1 PROD 2 
A 1 2 14 
B 1 1 9 
C 7 4 56 
Lucro Unitário $ 5,00 $ 6,00 
• Variáveis 
X1 = qtde. de PROD 1 a ser feita; 
X2 = qtde. de PROD 2 a ser feita; 
Z = lucro total obtido com os produtos. 
• Restrições 
a) disponibilidade do recurso A; 
b) disponibilidade do recurso B; 
c) disponibilidade do recurso C; 
d) quantidades não negativas. 
• Objetivo 
Maximizar o lucro total da indústria 
0,
5647
911
1421:.
65
21
21
21
21
21




xx
xx
xx
xxas
xxZMax
Interpretação Econômica das variáveis Duais 
 
Recurso 
Recurso gasto para fazer 1 unidade de 
Disponibilidade 
PROD 1 PROD 2 
A 1 2 14 
B 1 1 9 
C 7 4 56 
Lucro Unitário $ 5,00 $ 6,00 
Interpretação Econômica das variáveis 
Duais 
 Por outro lado, vamos supor que a indústria tenha a alternativa de vender os 
recursos A, B e C, em vez de empregá-los na produção dos dois produtos. 
 O problema que se coloca agora é encontrar o valor da unidade de cada 
recurso. É evidente que a venda dos recursos deve fornecer um ganho pelo 
menos igual ao obtido com a utilização deles na produção. 
Recurso 
Recurso gasto para fazer 1 unidade de 
Disponibilidade 
PROD 1 PROD 2 
A 1 2 14 
B 1 1 9 
C 7 4 56 
Lucro Unitário $ 5,00 $ 6,00 
• Variáveis 
y1 = valor do recurso A por unidade; 
y2 = valor do recurso B por unidade; 
y3 = valor do recurso C por unidade; 
Z = valor total do estoque de recursos. 
• Restrições 
a) Utilização dos recursos por unidade fabricada de PROD 1; 
b) Utilização dos recursos por unidade fabricada de PROD 2; 
c) quantidades não negativas. 
• Objetivo 
Minimizar o valor total do estoque de recursos 
0,,
6412
5711:.
56914
321
321
321
321




yyy
yyy
yyyas
yyyZMin
Interpretação Econômica das variáveis Duais 
 
Recurso 
Recurso gasto para fazer 1 unidade de 
Disponibilidade 
PROD 1 PROD 2 
A 1 2 14 
B 1 1 9 
C 7 4 56 
Lucro Unitário $ 5,00 $ 6,00 
Interpretação Econômica das variáveis 
Duais 
 
• Assim, as variáveis duais podem ser interpretadas como as 
avaliações unitárias dos recursos, relativas às contribuições de 
cada um para a obtenção do lucro total. 
 
• Isso significa que, resolvidos os problemas, as variáveis duais 
indicam as variações que ocorrem no valor da função objetivo 
do primal, para variações unitárias nos níveis de recursos. 
Método Dual-Simplex 
• As diferenças com relação ao Método Simplex se resumem 
nas regras de entrada e saída de variáveis da base, que são as 
seguintes: 
• Variável que sai: é a variável com o valor mais negativo (a variável 
correspondente ao b mais negativo). A linha dessa variável passa a ser a 
linha pivô. Se todas a variáveis básicas tiverem valores positivos, a solução 
é ótima. 
• Variável que entra: é escolhida entre as variáveis fora da base, da 
seguinte forma: 
– Dividir os coeficientes do lado esquerdo da equação Z – 
transformada, linha da função objetivo, pelos correspondentes 
coeficientes negativos da equação da variável que sai, linha pivô; 
– A variável que entra é a que tem o menor valor entre os quocientes 
encontrados (problemas de minimização) ou o menor valor absoluto 
(problema de maximização). 
• Quando, em ambos os casos, não houver coeficientes negativos na linha 
da variável que sai da base, linha pivô,o problema não tem solução viável. 
 
Exemplo 
 
x1 x2 x3 x4 b 
Base 0 0 -3/5 -2/5 -12/5 
X2 0 1 1/5 4/5 6/5 
X1 1 0 -2/5 -3/5 3/5 
 
•Quadro final do Simplex Primal 
Exemplo: 
Min Z = 2x1+ x2 
Sujeito a: 4x1+ 3x2 ≥ 6 
 x1 + 2x2 ≤ 3
 x1 e x2 ≥ 0 
 
 
• Quadro Inicial do Simplex Primal 
x1 x2 x3 x4 b 
Base -2 -1 0 0 0 
X3 -4 -3 1 0 -6 
X4 1 2 0 1 3 Z - 2x1 - x2 - 0x3 - 0x4 = 0 
 Sujeito a: 
 - 4x1- 3x2 + x3 = - 6 
 x1 + 2x2 + x4 = 3
 x1, x2, x3, x4 ≥ 0 
 A solução inicial é 
inviável, já que: 
x3 = - 6 e x4 = 3 
 
A variável que sai será: x3 
 A variável que entra será 
determinada por: 
x1 = (-2) ÷ (-4) = 0,5 e 
x2 = (-1) ÷ (-3) = 0,33... 
 
 
x1 x2 x3 x4 b 
Base -2/3 0 -1/3 0 2 
X2 4/3 1 -1/3 0 2 
X4 -5/3 0 2/3 1 -1 
 A solução ótima 
viável , pois as 
variáveis 
básicas x2 e x1 
são positivas e 
z = 12/5 
 
Exercício de Fixação 
Dado o problema de programação linear: 
 
 
 
 
• Pede-se: 
1. Formular o problema dual. 
2. Resolver o primal pelo método simplex. 
3. Resolver o dual pelo método dual-simplex. 
4. Verificar a relação entre as soluções dos dois problemas, isto é, indicar 
em cada iteração de um problema a solução complementar do outro. 
 
Exercício de Fixação 
Dado o problema de programação linear: 
 
 
 
 
 
• Pede-se: 
1. Formular o problema dual. 
2. Resolver o primal pelo método simplex. 
3. Resolver o dual pelo método dual-simplex. 
4. Verificar a relação entre as soluções dos dois problemas, isto é, indicar 
em cada iteração de um problema a solução complementar do outro. 
 








0,
6
102
21
21
21
xx
xx
xx
21 2015 xxZMin 
Referências 
 
 
 
 
• ANDRADE, Eduardo Leopoldino de. 
Introdução à pesquisa operacional: métodos e 
modelos para análise de decisões. 3. ed. Rio 
de Janeiro: LTC, 2004.192 p. 
 
• LACHTERMACHER, Gerson. Pesquisa 
operacional na tomada de decisões. 2. ed. 
rev. e atual. Rio de Janeiro: Elsevier, 2004. 
384 p.