PO1_Aula_04

Prévia do material em texto

Pesquisa Operacional I 
(CEP/CT025) – Aula 04
UNIVERSIDADE FEDERAL DO PIAUÍ
CAMPUS MINISTRO PETRÔNIO PORTELLA – CT
CURSO DE ENGENHARIA DE PRODUÇÃO
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: a lvaro.ferre i ra@ufpi .edu.br 
5. Dualidade
5.1. O par primal-dual;
5.2. Interpretação econômica do problema dual.
5.1. O par primal-dual
• Para cada problema de PL denominado primal, há um 
correspondente denominado dual formulado à partir do primal;
• Um problema é dito na forma primal quando ele é um problema de 
maximização e quando todas as suas restrições são do mesmo tipo 
de desigualdades ≤ 𝑜𝑢 ≥ ;
5.1. O par primal-dual
• Notação matricial do primal:
𝑀𝑎𝑥	𝑍 = 𝑐𝑥
	
𝑠. 𝑎.
	
	𝐴𝑥{≤,≥}𝑏
𝑥 ≥ 0
5.1. O par primal-dual
• Notação matricial do dual:
𝑀𝑖𝑛	𝑊 = 𝑏!𝑦
	
𝑠. 𝑎.
	
	𝐴!𝑦{≥,≤}𝑐!
𝑦 ≥ 0
5.1. O par primal-dual
• Observações:
• O problema primal não precisa ser colocado na forma padrão e não é 
exigido que 𝑏 ≥ 0;
• Se um primal for um problema de maximização, seu dual será um 
problema de minimização (e vice-versa);
• O transposto do vetor de coeficientes 𝑐 da função objetivo 𝑍 se torna o 
vetor resposta;
• O transposto do vetor reposta 𝑏 se torna o vetor de coeficientes da 
função objetivo 𝑊;
5.1. O par primal-dual
• Observações:
• A matriz de coeficientes das restrições do dual é igual à transposta da 
matriz de coeficientes das restrições do primal;
• Cada restrição do problema primal corresponde à uma variável do 
problema dual;
• Cada variável do problema primal corresponde à uma restrição do 
problema dual.
5.1. O par primal-dual
• Exemplo 1 (primal):
𝑀𝑎𝑥 𝑍 = 600𝑥" + 800𝑥#
	
𝑠. 𝑎.
	
𝑥" + 𝑥# ≤ 100
3𝑥" + 2𝑥# ≤ 240
𝑥" ≤ 60
𝑥# ≤ 80
𝑥", 𝑥# ≥ 0
5.1. O par primal-dual
• Exemplo 1 (dual):
𝑀𝑖𝑛	𝑊 = 100𝑦" + 240𝑦# + 60𝑦$ + 80𝑦%
	
𝑠. 𝑎.
	
y" + 3y# + y$ ≥ 600
𝑦" + 2𝑦# + 𝑦% ≥ 800
𝑦", 𝑦#, 𝑦$, 𝑦% ≥ 0
5.1. O par primal-dual
• Caso o problema apresente uma restrição de igualdade, ela deve ser 
desdobrada em um par de restrições de desigualdades ≤ e ≥; 
5.1. O par primal-dual
• Exemplo 2:
𝑀𝑖𝑛 𝑉 = −2,5𝑥" + 3𝑥# + 𝑥$
	
𝑠. 𝑎.
	
𝑥" + 4𝑥# ≤ 20
2𝑥" − 3𝑥$ ≥ 5
𝑥" + 𝑥# + 𝑥$ = 12
𝑥", 𝑥#, 𝑥$ ≥ 0
5.1. O par primal-dual
• Exemplo 2 (primal):
𝑀𝑎𝑥 𝑍 = 2,5𝑥" − 3𝑥# − 𝑥$
	
𝑠. 𝑎.
	
𝑥" + 4𝑥# ≤ 20
−2𝑥" + 3𝑥$ ≤ −5
𝑥" + 𝑥# + 𝑥$ ≤ 12
−𝑥" − 𝑥# − 𝑥$ ≤ −12
𝑥", 𝑥#, 𝑥$ ≥ 0
5.1. O par primal-dual
• Exemplo 2 (dual):
𝑀𝑖𝑛	𝑊 = 20𝑦" − 5𝑦# + 12𝑦$ − 12𝑦%
	
𝑠. 𝑎.
	
y" − 2y# + y$ − y% ≥ 2,5
4𝑦" + 𝑦$ − 𝑦% ≥ −3
3𝑦# + 𝑦$ − 𝑦% ≥ −1
𝑦", 𝑦#, 𝑦$, 𝑦% ≥ 0
5.2. Interpretação econômica do problema 
dual
• A interpretação do problema dual se torna útil quando a função 
objetivo expressa o lucro proveniente de uma atividade produtiva e 
as restrições estão relacionadas à finitude dos recursos de produção;
• Nesse contexto, as variáveis duais podem ser interpretadas como os 
preços associados aos diversos custos de produção;
5.2. Interpretação econômica do problema 
dual
• Um agricultor deseja cultivar duas variedades de cereal, A e B. Os 
recursos produtivos são: terra para o plantio, homens-hora de 
trabalho e horas de trabalho de um trator. Com base na tabela de 
consumo de recursos, o agricultor deseja otimizar a sua produção de 
modo a maximizar seu lucro.
Cereal Área de plantio (ha)
Homens-hora 
de trabalho 
por ha
Horas de 
trabalho do 
trator por ha
Lucro por ha 
cultivado
A 1 10 1,4 600
B 1 20 0,9 800
Disponível 100 1600 126
5.2. Interpretação econômica do problema 
dual
•	Modelagem:
𝑀𝑎𝑥 𝑍 = 600𝑥" + 800𝑥#
	
𝑠. 𝑎.
	
𝑥" + 𝑥# ≤ 100
10𝑥" + 20𝑥# ≤ 1600
1,4𝑥" + 0,9𝑥# ≤ 126
𝑥", 𝑥# ≥ 0
5.2. Interpretação econômica do problema 
dual
• Considere agora que o agricultor se disponha a vender todos os 
seus recursos de produção e deseja determinar o preço que deve ser 
pago por cada um desses recursos;
• Assim, devem ser considerados:
• 𝑦! = preço por are de planHo;
• 𝑦" = preço por homem-hora de trabalho;
• 𝑦# = preço da hora de uso do trator.
5.2. Interpretação econômica do problema 
dual
• Para o comprador, o objetivo passa a ser pagar uma quantia 𝑊 
mínima por todos esses recursos, i.e.:
𝑀𝑖𝑛	𝑊 = 100𝑦" + 1600𝑦# + 126𝑦$
• Existem, no entanto, restrições impostas pelo agricultor vendedor 
dos recursos tal que o seu ganho vendendo os recursos seja maior 
ou igual ao ganho que obteria produzindo os cereais;
5.2. Interpretação econômica do problema 
dual
• Assim, o preço do consumo de recursos destinado à produção de 
um ha do cereal A não pode ser inferior ao lucro que o agricultor 
poderia obter caso ele mesmo realizasse a produção, i.e.:
𝑦" + 10𝑦# + 1,4𝑦$ ≥ 600
5.2. Interpretação econômica do problema 
dual
• De modo similar ao cereal B:
𝑦" + 20𝑦# + 0,9𝑦$ ≥ 800
5.2. Interpretação econômica do problema 
dual
• Chegando então ao dual correspondente:
𝑀𝑖𝑛	𝑊 = 100𝑦" + 1600𝑦# + 126𝑦$
	
𝑠. 𝑎.
	
𝑦" + 10𝑦# + 1,4𝑦$ ≥ 600
𝑦" + 20𝑦# + 0,9𝑦$ ≥ 800
𝑦", 𝑦#, 𝑦$ ≥ 0
Pesquisa Operacional I 
(CEP/CT025) – Aula 04
UNIVERSIDADE FEDERAL DO PIAUÍ
CAMPUS MINISTRO PETRÔNIO PORTELLA – CT
CURSO DE ENGENHARIA DE PRODUÇÃO
PROF. ÁLVARO LÉDO FERREIRA
CONTATO: a lvaro.ferre i ra@ufpi .edu.br