Modelos Primal e Dual em Pesquisa Operacional

Prévia do material em texto

PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
 
DUALIDADE 
 
Modelos Primal e Dual 
Cada modelo de P.Linear consiste de 2 formas. A primeira, ou original, é chamada de primal 
e a segunda forma do modelo é chamada de dual. As propriedades de uma das formas do modelo 
estão relacionadas com as propriedades da outra. Assim, dada a solução ótima de uma das formas 
do modelo, podemos encontrar a solução ótima da outra forma. Considere os modelos abaixo: 
(MAX) Z = 4 x1 + 5 x2 + 9 x3 (MIN) Y = 16 y1 + 25 y2 
x1 + 2 x2 + 2 x3 ≤ 16 y1 + 7 y2 ≥ 4 
7 x1 + 5 x2 + 3 x3 ≤ 25 y1 + 5 y2 ≥ 5 
xi ≥ 0 2 y1 + 3 y2 ≥ 9 
 yi ≥ 0 
A partir de um dos modelos podemos construir o outro, pois as constantes do lado direito do 
1o modelo são os coeficientes da função objetivo do 2o. Os coeficientes da função objetivo do 1o são 
as constantes do lado direito do 2o. Os coeficientes da 1a linha do primeiro são os coeficientes da 1a 
coluna do 2o e assim por diante. 
 
Explorando as relações dos modelos Primal e Dual 
Suponha que, no exemplo acima, x1, x2 e x3 sejam valores praticáveis para o modelo primal 
e y1 e y2 sejam valores praticáveis para o modelo dual. 
Se multiplicarmos a 1a restrição do primal por y1 e a 2a por y2 e somarmos as duas, vamos 
ter: 
y1x1 + y1x2 + 2y1x3 + 7y2x1 + 5y2x2 + 3y2x3 ≤ 16y1 + 25y2 
Da mesma forma, multiplicando a iésima restrição do dual por xi e somando as 3, teremos: 
x1y1 + 7y2x1 + y1x2 + 5y2x2 + 2y1x3 + 3y2x3 ≥ 4x1 + 5x2 + 9x3 
Os lados esquerdos das 2 inequações são iguais, logo: 
16y1 + 25y2 ≥ 4x1 + 5x2 + 9x3 ∴ Y ≥ Z 
Primal Dual 
 PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
Este resultado implica em que o valor da função objetivo de uma solução praticável de um 
dos modelos é um limite para qualquer solução praticável do outro modelo. 
Por exemplo, considerando a solução praticável, para o modelo primal, em que x1 = 1, x2 = 2 
e x3 = 2, dando Z = 32, e a solução praticável y1 = 0 e y2 = 3 para o dual, dando Y = 75, qual 
conclusão podemos tirar ? 
Qualquer solução praticável, inclusive a ótima, para o primal será menor ou igual a 75 e 
qualquer solução praticável, inclusive a ótima, para o dual será maior ou igual a 32. A conclusão 
óbvia é que a solução ótima será aquela em que Z = Y . 
Teorema Dual: 
 
 
 
 
Formalizando as relações entre primal e dual: 
PRIMAL DUAL 
(MAX) com restrições ≤ ou = (MIN) com restrições ≥ ou = 
restrição variável 
Coeficientes da função objetivo Constantes do lado direito 
j-ésima coluna de coeficientes j-ésima linha de coeficientes 
j-ésima restrição ≥ ou ≤ j-ésima variável ≥ 0 
j-ésima restrição com sinal de = j-ésima variável irrestrita 
Exemplo: Construir o Dual do modelo a seguir: 
(MIN) Z = 3x1 − 4x2 + x3 − 2x4 
2x1 + x2 + 2x3 + x4 = 10 
x3 + 2x4 ≤ 10 
Quando tanto o modelo dual quanto o primal possuem soluções 
praticáveis, temos que: Z* = Y*, ou seja, o valor ótimo dos 2 
modelos é o mesmo. 
 
 PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
−x1 + x2 − x4 ≤ 5 
2x1 + 3x2 + x3 + x4 ≥ 5 
2x1 + 3x2 + x3 + x4 ≤ 20 
x1, x2, x3 ≥ 0 
x4 ⇒ Irrestrita em sinal 
Antes de se aplicar a tabela devemos colocar o modelo primal dentro das regras que 
permitem o uso da tabela. 
Como o primal é um modelo de minimização, devemos fazer com que todas as restrições 
sejam do tipo ≥ ou =. 
É necessário então que todas as restrições do tipo ≤ sejam multiplicadas (ambos os lados) 
por −1, invertendo seu sinal. 
Devemos lembrar também que à cada restrição do primal teremos uma variável 
correspondente no Dual. 
2x1 + x2 + 2x3 + x4 = 10 ⇒ y1 
−x3 − 2x4 ≥ −10 ⇒ y2 
x1 − x2 + x4 ≥ −5 ⇒ y3 
2x1 + 3x2 + x3 + x4 ≥ 5 ⇒ y4 
−2x1 − 3x2 − x3 − x4 ≥ −20 ⇒ y5 
x1, x2, x3 ≥ 0 
x4 ⇒ Irrestrita em sinal 
Construindo o modelo dual: 
(MAX) Y = 10y1 − 10y2 − 5y3 + 5y4 − 20y5 
2y1 + y3 + 2y4 − 2y5 ≤ 3 ⇒ x1 
y1 − y3 + 3y4 − 3y5 ≤ −4 ⇒x2 
2y1 − y2 + y4 − y5 ≤ 1 ⇒ x3 
y1 − 2y2 + y3 + y4 − y5 = −2 ⇒ x4 
y2, y3, y4, y5 ≥ 0; 
 PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
y1 ⇒ Irrestrita em sinal 
Assumindo que o primal foi resolvido por maximização temos: 
a) Y* = Z* (teorema dual) 
b) O valor ótimo da variável y*j é igual ao coeficiente da variável de folga da j-ésima 
restrição na equação (1) do sistema ótimo primal. 
c) O coeficiente de xj na equação (1)F primal é igual à diferença entre os lados esquerdo e 
direito da j-ésima restrição dual. 
Voltando ao modelo do início da Análise de Sensibilidade: 
 (MAX) Z = 4 x1 + 5 x2 + 3 x3 
x1 + 2 x2 + 2 x3 ≤ 100 (matéria prima) 
6 x1 + 6 x2 + 4 x3 ≤ 360 (espaço de armazenamento) 
8 x1 + 4 x2 + 4 x3 ≤ 400 (mão de obra) 
x1 , x2 e x3 ≥ 0 (quantidades positivas) 
O modelo dual é: 
(MIN) Y = 100y1 + 360y2 + 400y3 
y1 + 6 y2 + 8 y3 ≥ 4 
2 y1 + 6 y2 + 4 y3 ≥ 5 
2 y1 + 4 y2 + 4 y3 ≥ 3 
yi ≥ 0 
Da solução (F), ótima, podemos tirar os valores ótimos do Dual: 
Y* = Z* = 280 
y*1 = coeficiente de F1 em (1)F = 1 (veja (F) na pág. 28) 
y*2 = coeficiente de F2 em (1)F = 1/2 
y*3 = coeficiente de F3 em (1)F = 0 
Vamos usar estes resultados para verificar a propriedade c enunciada anteriormente. O 
coeficiente de x1 na equação (1)F é 0. Se a propriedade é válida, a diferença entre os lados esquerdo 
e direito da 1a restrição do modelo dual tem que ser igual a 0. 
 PESQUISA OPERACIONAL I 
 
Crédito do conteúdo desta nota de aula: Prof. José Gomes de Carvalho Júnior 
 
Restrição Dual ⇒ y1 + 6y2 + 8y3 ≥ 4 
Lado Esquerdo ⇒ y1 + 6y2 + 8y3 
Lado Direito ⇒ 4 
Pela propriedade: Lesq − Ldir = 0 
Temos, usando os valores ótimos dos yi′s: 
Lesq = 1 + 6 × 1/2 + 8 × 0 = 4 
Lesq − Ldir = 4 − 4 = 0 
 
Exercício: Verificar a propriedade para os coeficientes de x2 e x3.