Capitulo 04 - Dualidade em Programação Linear

Prévia do material em texto

Dualidade em Programação Linear
Pesquisa Operacional
Desenvolvimento do material
Julio Loureiro
1ª Edição
Copyright © 2021, Afya.
Nenhuma parte deste material poderá ser reproduzida, 
transmitida e gravada, por qualquer meio eletrônico, 
mecânico, por fotocópia e outros, sem a prévia 
autorização, por escrito, da Afya.
Sumário
Dualidade em Programação Linear
Para Início de Conversa... ............................................................................... 4
Objetivo ........................................................................................................ 4
1 Introdução .................................................................................................... 5
2 Analogias entre a Solução 
Primal e Dual. ..................................................................................................... 9
3 Interpretação Econômica 
do Dual. .................................................................................................... 10
Referências ......................................................................................................... 11
Para Início de Conversa...
Neste capítulo, vocês serão apresentados à dualidade na Programação 
Linear, uma forma de reescrever um problema de Programação Linear 
que facilita a busca de uma solução para um problema que se pretenda 
solucionar.
As buscas de otimização de um problema podem se dar pela 
maximização ou minimização da função objetivo, sempre sujeitas às 
restrições decorrentes. 
O conceito de dualidade possibilita que um problema de maximização 
possa ser transformado em um problema de minimização ou o oposto. 
Ao se obter a solução do algoritmo dual, ela corresponderá também 
à solução do algoritmo primal. Ao se trabalhar em um modelo dual, 
chamaremos o modelo inicial de modelo primal, aquele que o originou.
Além disso, a utilização da dualidade permite a obtenção de outras 
análises do mesmo problema, como, por exemplo, a sua análise 
econômica, o que pode levar ao cálculo da utilidade marginal dos 
recursos envolvidos. Bons estudos!
Objetivo
Formular analogias entre a solução primal e a solução dual de um 
problema, interpretando o aspecto econômico da solução dual. 
 
 
 3
1 Introdução 
Como vimos nos capítulos anteriores, os problemas de Pesquisa 
Operacional são organizados e constituídos matematicamente por meio 
de uma função objetiva que precisa ser otimizada pelas restrições do 
problema que são representadas por equações (igualdades) ou por 
inequações (desigualdades). Essas equações representam as limitações 
de capacidades físicas ou operacionais que são impostas às variáveis de 
decisão que precisam ser determinadas. 
Ao conhecer e saber aplicar o método gráfico e o método Simplex – 
ambos possuem baixo grau de complexidade – o profissional estará em 
condições de avançar para solucionar outros problemas que envolvam as 
possíveis relações entre o objetivo desejado e as limitações de recursos 
disponíveis.
O conjunto de restrições e a função objetivo podem ser lineares em 
muitos casos, o que remete a um problema de Programação Linear. 
Para Andrade (2015), ao se buscar a otimização de um problema, 
desejamos encontrar a maximização ou minimização da função objetivo, 
que está sempre sujeita às restrições decorrentes. 
O conceito de dualidade torna possível um problema de maximização 
ser transformado em um problema de minimização ou o oposto. 
Com isso, considere a possibilidade de se optar pela estrutura 
matemática que se deseja empregar para solucionar um modelo de 
Programação Linear. 
Os problemas de maximização ou de minimização estão profundamente 
inter-relacionados, pois a solução ótima de um deles espelha com 
exatidão a solução ótima do outro. 
A técnica do Método Dual-Simplex foi desenvolvida para viabilizar 
soluções ótimas de uma forma mais acessível. Todavia, a dualidade 
não se trata de uma nova forma de cálculo para os algoritmos, é 
simplesmente um rearranjo lógico para a estrutura algébrica do mesmo 
problema inicial.
Para fins de simplificação iremos considerar que todo problema de 
Programação Linear, que chamaremos de primal, implica na existência de 
um segundo problema, chamado de dual, os dois são inter-relacionados 
e a solução ótima de um fornece informações completas sobre o outro.
O seu surgimento possibilitou que em muitos casos seja observada a 
limitação das entradas dos números de variáveis (colunas) ou de restrições 
(linhas) em programas de resolução de problemas de Programação Linear, 
tema que será aprofundado na unidade oito desta disciplina.
Para facilitar o entendimento, imagine que você está em frente a um 
espelho e observa a sua figura, a imagem que você vê é simetricamente 
 4
a mesma, mas está invertida, o mesmo ocorre com um problema primal 
transformado em dual. 
Figura 1: Analogia entre o primal e o dual, imagem refletida no espelho.
Fonte: Dreamstime.
Como se fosse a imagem do algoritmo primal refletida em um espelho, 
o algoritmo dual terá os mesmos coeficientes, porém dispostos de 
maneira diferente.
Para Caixeta-Filho (2011), a solução do algoritmo dual também 
corresponderá à mesma solução do algoritmo primal. Ao se trabalhar em 
um modelo dual, chamaremos o modelo inicial de modelo primal, aquele 
que o originou.
O Processo de Conversão de um Algoritmo Primal em Dual
Vamos conhecer agora a sequência para a transformação de um 
algoritmo primal em seu correspondente dual. 
 ▪ O primeiro passo é definir as variáveis duais e o número de restrições 
do modelo dual. 
 ▪ O segundo passo é o estabelecimento da função objetivo dual.
 ▪ E, finalmente, as restrições duais são implementadas.
O passo seguinte é definir as variáveis e o número de restrições do dual 
(que se pretende obter).
Com a ajuda de um exemplo, veremos a transformação de um modelo 
primal para dual. A definição das variáveis duais de um problema está 
 5
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.
De acordo com Longaray (2013), a variável dual será representada 
matematicamente por Yn, em que n remete ao número da restrição do 
primal da qual ela foi originada.
Observe o seguinte modelo primal de minimização: 
Min Z = 20X1 + 30X2
Restrições do problema (primal):
X1 + 6X2 ≥ 18 
30X1 + 15X2 ≥ 90 
3X1 + 6X2 ≥ 30
X1 ≥ 0
X2 ≥ 0
Como o modelo primal do exemplo apresentado possui três restrições: 
X1 + 6X2 ≥ 18; 30X1 + 15X2 ≥ 90; 3X1 + 6X2 ≥ 30, o seu modelo dual 
correspondente será composto por três variáveis duais, Y1, Y2 e Y3, que 
serão originadas, respectivamente, da primeira, segunda e terceira 
restrições do problema.
Da mesma forma, a determinação do número de restrições do modelo 
dual está associada ao número de variáveis do modelo primal. Assim, o 
número de variáveis originais (X1, X2, ..., Xn) do modelo primal indica a 
quantidade de restrições do modelo dual.
Para o nosso exemplo, quando o algoritmo primal for formado pelas 
variáveis X1 e X2, teremos o modelo dual composto por duas restrições.
Após serem estabelecidos o número de variáveis e a quantidade 
de restrições que vão formar o modelo dual, pode-se, então, iniciar o 
processo de conversão da função objetivo e das restrições do modelo 
primal em seu correspondente algoritmo dual.
Elaboração da Função Objetivo do Modelo Dual
A função objetivo de um modelo de Programação Linear é formada por 
seu objetivo (maximização ou minimização) e o somatório dos produtos 
entre os coeficientes do objetivo e das variáveis (X1, X2, ..., Xn ou Y1, Y2, ..., 
Yn) do modelo.
A minimização gera um objetivo dual de maximização e a maximização 
gera um objetivo dual de minimização.
Como o objetivo no primal foi representado por Z, aqui no dual ele será 
representado por D.
 6
Na função objetivo dual, o termo independentede uma restrição primal 
(valor do lado direito da inequação) será o coeficiente da variável dual 
oriunda dessa restrição.
Retomando o exemplo citado, tem-se a seguinte função objetivo dual:
Max D = 18Y1 + 90Y2 + 30Y3
Note que a função objetivo dual (D) do nosso exemplo é formada pelo 
objetivo de maximização (o objetivo primal Z era de minimização), três 
variáveis duais, Y1, Y2 e Y3, (pois o modelo primal possui três restrições, 
como observado no destaque) e pelos seus componentes equivalentes: 
o 18 (termo independente da primeira restrição primal), o 90 (termo 
independente da segunda restrição primal) e o 30 (termo independente 
da terceira restrição primal).
Estabelecimento das Restrições do Modelo Dual
A restrição de um modelo de Programação Linear é formada pelo 
lado esquerdo da expressão matemática com as suas variáveis e seus 
Primal
Min Z = 20X1 + 30X2
X1 + 6X2 ≥ 18
30X1 + 15X2 ≥ 90
3X1 + 6X2 ≥ 30
X1 ≥ 0;
X2 ≥ 0
Dual
coeficientes, por um sinal lógico (≤, =, ≥) e pelo lado direito (termo 
independente), formando o conjunto da expressão matemática completa.
Como já se sabe, 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.
O sinal lógico da restrição dual será sempre o oposto da restrição do 
modelo primal. Isto é, se no primal tivermos restrições com o sinal ≥, as 
restrições do dual serão do tipo ≤.
O termo independente de uma restrição do dual corresponde ao 
coeficiente da variável que originou essa restrição na linha da função 
objetivo do primal.
Em nosso exemplo, a primeira e a segunda restrições da dual são dadas por: 
1Y1 +30Y2 +3Y3 ≤ 20 
6Y1 +15Y2 +6Y3 ≤ 30 
Min Z = 20X1 + 30X2
X1 + 6X2 ≥ 18
30X1 + 15X2 ≥ 90
3X1 + 6X2 ≥ 30
X1 ≥ 0;
X2 ≥ 0
Dual
 7
Os coeficientes do lado esquerdo da primeira restrição dual foram 
retirados da coluna da variável X1 nas três restrições do modelo primal e 
multiplicados por suas respectivas variáveis duais, Y1, Y2 e Y3.
Como as restrições do primal do nosso exemplo são todas com sinal ≥, o 
sinal da restrição dual é ≤.
O lado direito da primeira restrição do dual é o coeficiente da variável X1 
na função objetivo primal.
As variáveis duais devem obedecer à condição da não negatividade da 
Programação Linear com Y1 ≥ 0; Y2 ≥ 0 e Y3 ≥ 0. Para nosso exemplo, o 
modelo dual completo fica assim:
Max D = 18 Y1 + 90 Y2 + 30 Y3
E as suas restrições:
1 Y1 + 30 Y2 + 3 Y3 ≤ 20 
6 Y1 + 15 Y2 + 6 Y3 ≤ 30 
Y1 ≥ 0
Y2 ≥ 0
Y3 ≥ 0
2 Analogias entre a Solução Primal e Dual. 
Conforme Longaray (2013), conhecemos a possibilidade de uso da 
dualidade para converter um modelo primal de Programação Linear 
em seu oposto simétrico, que é o modelo dual. O grande objetivo de 
efetuarmos tal transformação, usualmente, se explica pelo menor 
número de cálculos a serem executados no dual em comparação ao 
primal, que o originou.
Há, contudo, outras finalidades que justificam o uso da dualidade em 
modelos de Programação Linear. Todavia, nem sempre é necessário 
transformar um algoritmo primal em seu relativo modelo dual e 
realizar todo o processo de cálculo. A busca da solução pelo seu primal 
será suficiente para a solução ótima do problema apresentado. Tal 
transformação é possível e torna-se viável devido à existência de uma 
correlação entre as variáveis primais e duais a partir de seus valores na 
base e nos coeficientes da função objetivo, conforme a tabela abaixo:
Valor de: Coeficiente na função objetivo de:
xi yFi
xFi yi
yi xFi
yFi xi
Tabela 1: Correspondência entre as variáveis do primal e do dual.
Fonte: Longaray (2013).
 8
Um olhar atento à tabela permite verificar que para o valor de determinada 
variável primal de índice i sempre haverá um correspondente coeficiente 
de uma variável na função objetivo dual de mesmo valor e índice.
Da mesma forma, para o valor de determinada variável dual de índice 
i sempre haverá um correspondente coeficiente de uma variável na 
função objetivo primal de mesmo valor e índice.
O Modelo dual é definido diretamente a partir do modelo primal do 
problema de Programação Linear (PL), que possui uma forte relação com 
o problema de origem, uma vez que a solução ótima de um problema 
fornece automaticamente a solução ótima do outro.
Pode-se estabelecer como vantagens desta aplicação a possibilidade 
de se gerar um problema menor, cuja solução seja mais rápida ou 
menos cara que no modelo original; principalmente se tratando da 
utilização de programas especialistas para a resolução desse problema, 
considerando possíveis restrições no número de variáveis. Além disso, 
pode-se transformar um problema de minimização em um problema de 
maximização.
3 Interpretação Econômica do Dual. 
O objetivo da análise de sensibilidade do dual de um modelo de 
Programação Linear (PL) é o de interpretar o valor de oportunidade 
dos recursos envolvidos para o alcance de uma solução ótima para um 
problema, além de examinar os custos de cada atividade que pode ser 
obtida com esses recursos.
Ao se obter a solução ótima no modelo primal em um problema de 
Programação Linear (PL) a solução ótima será a mesma do problema 
dual dele derivado.
A análise das variáveis duais pode fornecer uma interpretação 
econômica interessante ao profissional, podendo levar a uma série de 
outras possibilidades como a identificação da utilidade marginal do 
preço (o  valor  de um determinado bem ou serviço diminui à medida 
que o seu consumo é feito em larga escala), preço de sombra (variação 
do  valor  objetivo da solução ótima de um problema de otimização 
obtido através da folga de uma unidade) e valor marginal dos recursos 
envolvidos (o valor está associado à utilidade e a escassez do recurso 
em análise), entre outros.
Neste quarto capítulo vimos que quando buscamos a otimização de um 
problema, isso faz com que busquemos a maximização ou minimização 
da função objetivo, sempre sujeitos às restrições decorrentes. 
 9
A aplicação da solução dual poderá fazer com que um problema 
com muitas variáveis se torne mais simples de ser resolvido, pois no 
processo ocorre uma redução na complexidade, aspecto que pode ser 
relevante para a aplicação, em modelos matemáticos, em planilhas 
eletrônicas ou computacionais que apresentem limitação no número 
de entrada de dados.
O conceito de dualidade torna possível um problema de maximização 
ser transformado em um problema de minimização ou o oposto. 
Ao se obter a solução do algoritmo dual, esta também corresponderá à 
mesma solução do algoritmo primal. Ao se trabalhar em um modelo dual, 
chamaremos o modelo inicial de modelo primal, aquele que o originou.
Referências 
ANDRADE, E. L. Introdução à Pesquisa Operacional: métodos e modelos 
para análise de decisões. 5 ed. Rio de Janeiro: LTC, 2015. 
CAIXETA-FILHO, J. V. Pesquisa Operacional: técnicas de otimização 
aplicada a sistemas agroindustriais. 2 ed. São Paulo: Atlas, 2011. 
LONGARAY, A. A. Introdução à Pesquisa Operacional. São Paulo: 
Saraiva, 2013.
 10