Dualidade e Analise de Sensibilidade

Prévia do material em texto

UNIVERSIDADE POLITÉCNICA – A POLITÉCNICA 
 
Instituto Superior de Humanidades, Ciência e Tecnologias 
 
 
 
Engenharia Informática e de Telecomunicações 
 
 
 
 
 
Dualidade e Analise de Sensibilidade 
 
 
 
 
 
Helton Rodolfo Lourenço 
 
 
 
 
 
 
 
Quelimane 
2021 
Helton Rodolfo Lourenço 
 
 
 
 
Engenharia Informática e de Telecomunicações 
 
 
 
 
 
 
Dualidade e Analise de Sensibilidade 
 
 
 
 
 
 
Docente: Neil Jacinto Martins 
 
 
 
 
 
 
Quelimane 
2021 
Trabalho de pesquisa apresentado ao 
Instituto Superior de Humanidades, 
Ciências e Tecnologias de caráter 
avaliativo para a disciplina de 
Investigação Operacional 
Sumário 
 
Introdução ............................................................................................................................... 1 
Objetivos ................................................................................................................................. 2 
Objetivos Gerais ..................................................................................................................... 2 
Objetivos Específicos ............................................................................................................. 2 
Dualidade na Programação Linear ......................................................................................... 3 
Dualidade ................................................................................................................................ 3 
Relações entre os problemas primal e dual ............................................................................ 4 
Exemplo de problema primal e dual de um problema de PL ................................................. 5 
Método Dual – Simplex .......................................................................................................... 7 
Vantagens e Desvantagens do Algoritmo Dual Simplex...................................................... 10 
Análise de Sensibilidade em Programação Linear ............................................................... 11 
Tipos de Análise de Sensibilidade em Programação Linear ................................................ 12 
Conclusão ............................................................................................................................. 13 
Bibliografia ........................................................................................................................... 14 
 
 
1 
 
Introdução 
No presente trabalho fala-se de temas bastante importante na Investigação Operacional, tais 
como dualidade em programação linear, método dual – simplex, e analise de sensibilidade 
em programação linear. Tem de se perceber o termo dualidade como sendo a existência de 
dois caracteres numa mesma coisa ou estado. Ou por outra, em muitos smartphones tem lá 
escrito “dual”, que por nosso perceber é a capacidade daquele mesmo dispositivo suportar 
dois (2) cartões SIM. Na qual tem um cartão principal e o outro secundário. Na programação 
Linear o conceito é igual, e todo o problema em PL pode ser expresso de duas formas. Não 
se pode falar de dualidade sem se falar de método simplex – dual, que é nada mais uma 
técnica de resolução de problemas de forma simples e pratica. Quando se fala de análise de 
sensibilidade temos que perceber como sendo um método de decisão assente num estudo 
técnico de carácter financeiro com o objetivo de determinar qual a viabilidade ou sucesso de 
um determinado projeto. 
2 
 
Objetivos 
Objetivos Gerais 
 Conhecer a importância da dualidade e análise de sensibilidade em programação 
linear 
Objetivos Específicos 
 Saber a utilidade de um dual numa PL 
 Compreender a utilidade da análise de sensibilidade em exercícios de PL 
3 
 
Dualidade na Programação Linear 
Dualidade 
Segundo CAIXETA-FILHO (2011, p. 54) A característica importante dos problemas de PL 
é a sua dualidade, isto é, todo problema de PL pode ser expresso de duas formas. O problema 
original é chamado de primal e o problema associado a ele, dual. “As propriedades do primal 
estão intimamente ligadas às do dual, sendo o valor ótimo da função objetivo o mesmo para 
as duas formas” (Lopes, 2019). 
A Dualidade na Programação Linear afirma que todo problema de programação linear tem 
outro problema de programação linear relacionado a ele e, portanto, pode ser derivado dele. 
O problema original da programação linear é chamado de "Primal", enquanto o problema 
linear derivado é chamado de "Dual" (Business Jargons, 2016). 
Antes de resolver para a dualidade, o problema original da programação linear deve ser 
formulado em sua forma padrão. A forma padrão significa que todas as variáveis do problema 
devem ser não negativas e "≥", o sinal "≤" é usado no caso de minimização e no caso de 
maximização, respectivamente (Business Jargons, 2016). 
O conceito de Dualidade pode ser bem compreendido através de um problema dado abaixo: 
Maximizar 
𝑍 = 50𝑥1 + 30𝑥2 
Sujeito à: 
4𝑥1 + 3𝑥2 ≤ 100 
3𝑥1 + 5𝑥2 ≤ 150 
𝑥1𝑥2 ≥ 0 
A dualidade pode ser aplicada ao problema de programação linear original acima como: 
Minimizar 
𝐺 = 100𝑦1 + 150𝑦2 
Sujeito à: 
4𝑦1 + 3𝑦2 ≥ 50 
3𝑦1 + 5𝑦2 ≥ 30 
4 
 
𝑦1𝑦2 ≥ 0 
As seguintes observações foram feitas ao formar o problema de programação linear dupla: 
O problema de programação linear primal ou original é do tipo maximização, enquanto o 
problema duplo é do tipo de minimização. 
Os valores de restrição 100 e 150 do problema primal tornaram-se o coeficiente de variáveis 
duplas 𝑦1 e 𝑦2 na função objetiva de um problema duplo e enquanto o coeficiente das 
variáveis na função objetiva de um problema primitivo tornou-se o valor de restrição no 
duplo problema. 
A primeira coluna na restrição da desigualdade do problema primal tornou-se a primeira linha 
em um problema duplo e, da mesma forma, a segunda coluna de restrição tornou-se a segunda 
linha no problema dual. 
Os rumos das desigualdades também mudaram, ou seja, no duplo problema, o sinal é o 
inverso de um problema primitivo. Tanto que, no problema primitivo, o sinal de desigualdade 
era "≤" mas, no duplo problema, o sinal da desigualdade torna-se "≥" (Business Jargons, 
2016). 
O primal e o dual possuem diversas relações. O Quadro apresenta algumas das relações que 
devem ser consideradas ao transformar o primal em dual, ou vice-versa. 
Relações entre os problemas primal e dual 
Problema primal Problema dual 
Função objetivo de maximizar Função objetivo de minimizar 
Coeficientes da função objetivo Constantes das restrições 
Constantes das restrições Coeficientes da função objetivo 
Número de variáveis Número de restrições 
Número de restrições Número de variáveis 
Restrição tipo ≤ Restrição tipo ≥ 
Restrição tipo ≥ Variável ≤ 0 
Restrição tipo = Variável sem restrição de sinal 
 
Fonte: (Lopes, 2019) 
 
5 
 
De acordo com o Quadro, quando o problema primal é de maximização, o seu problema dual 
será de minimização. O mesmo vale para o inverso, ou seja, se o primal for de minimização, 
seu dual será de maximização. Além disso, observa-se uma relação entre os coeficientes da 
função objetivo e as constantes das restrições (Lopes, 2019). 
Os coeficientes da função objetivo no primal tornam-se as constantes das restrições no dual, 
logo o número de variáveis de decisão do primal é igual ao número de restrições do dual. O 
mesmo ocorre em relação às constantes de restrições do primal e os coeficientes da função 
objetivo no dual. Os tipos de restrição também variam: se no primal elas são do tipo ≤, no 
dual elas serão do tipo ≥ (Lopes, 2019). 
Observa-se que essa última afirmação refere-se ao formato padrão das restrições de um 
problema primal de maximização, caso as restrições não estejam nesse padrão e sejam do 
tipo ≥, as variáveis do dual relacionadas a elas serão menor ou igual a zero. Nocaso de 
restrições de igualdade, as variáveis do dual relacionadas serão sem restrição de sinal (Lopes, 
2019). 
Para exemplificar isso, a Tabela apresenta um exemplo de primal e o dual para um problema 
de PL. 
Exemplo de problema primal e dual de um problema de PL 
 
 
 
 
 
 
 
Fonte: HILLIER, LIEBERMAN, 2013, p. 186 (Lopes, 2019). 
 
 
Problema Primal Problema Dual 
𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒂𝒓 𝒛
= 𝟑𝒙𝟏 + 𝟓𝒙𝟐 
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 
𝒙𝟏 ≤ 𝟒 
𝟐𝒙𝟐 ≤ 𝟏𝟐 
𝟑𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟏𝟖 
𝒆 
𝒙𝟏 ≥ 𝟏, 𝒙𝟐 ≥ 𝟎 
𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒂𝒓 𝒘
= 𝟒𝒚𝟏 + 𝟏𝟐𝒚𝟐
+ 𝟏𝟖𝒚𝟑 
𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎: 
𝒚𝟏 + 𝟑𝒚𝟑 ≥ 𝟑 
𝟐𝒚𝟐 + 𝒚𝟑 ≥ 𝟓 
𝒆 
𝒚𝟏 ≥ 𝟏, 𝒚𝟐 ≥ 𝟎, 𝒚𝟑 ≥ 𝟎 
 
6 
 
Observa-se na Tabela as relações apresentadas anteriormente. Como a função objetivo do 
primal é de maximização, seu dual é de minimização. Além disso, o problema primal descrito 
possui duas variáveis de decisão e três restrições. Logo, seu dual ficou com três variáveis de 
decisão e duas restrições. Por fim, as restrições do primal são do tipo ≤, portanto as restrições 
do dual são do tipo ≥. Além das relações já apresentadas, existem alguns teoremas 
importantes sobre o primal e o dual. 
Segundo os autores Fávero e Belfiore (2013) e Lachtermacher (2018), que aglomerou 
teoremas apresentados por Hiller e Liberman (1995) e Chvátal (1983), existem os seguintes 
teoremas (Lopes, 2019). 
Teorema 1) O dual do problema dual é o próprio primal e vice-versa. 
Teorema 2) Se uma restrição do problema primal for de igualdade, a variável dual 
correspondente será sem restrição de sinal, isto é, poderá ter valor positivo, zero ou negativo. 
Teorema 3) O mesmo vale para o inverso do Teorema 2, ou seja, se uma variável do problema 
primal é sem restrição de sinal, então a restrição do dual correspondente será de igualdade. 
Teorema 4) Propriedade da Dualidade Fraca: Se o primal (𝑚𝑎𝑥 𝑧) e o dual (𝑚𝑖𝑛 𝑤) 
tiverem soluções factíveis, então o valor da função objetivo do primal é menor ou igual ao 
valor da função objetivo do dual (𝑧 ≤ 𝑤). Se a mesma situação ocorrer para um primal 
(𝑚𝑖𝑛 𝑧) e um dual (𝑚𝑎𝑥 𝑤), a relação é de 𝑧 ≥ 𝑤. 
Teorema 5) Propriedade da Dualidade Forte: Se o primal ou o dual tiver uma solução viável 
e finita, os valores da função objetivo de ambos os problemas são iguais, ou seja, 𝑚𝑎𝑥 𝑧 =
 𝑚𝑖𝑛 𝑤 ou 𝑚𝑖𝑛 𝑧 = 𝑚𝑎𝑥 𝑤. 
Teorema 6) Teorema da Dualidade: Engloba as seguintes relações entre primal e dual: 
a) Se o primal ou o dual tiver solução viável com uma função objetivo limitada (ou seja, 
b) Existe solução ótima), então o outro também terá solução ótima. Nesse caso, as 
Propriedades de Dualidade Fraca e Forte podem ser aplicadas; 
c) Se o primal ou o dual tiver solução viável, porém com uma função objetivo ilimitada 
(ou seja, não existe solução ótima), então o outro terá solução inviável; 
7 
 
d) Se o primal ou o dual tiver solução inviável, então o outro também terá solução 
inviável ou a função objetivo será ilimitada. 
Teorema 7) Teorema da Folga Complementar: Engloba as relações entre as variáveis do 
primal e do dual. Assim, temos que: as variáveis originais no primal serão variáveis de 
folga/excesso no dual; e as variáveis de folga/excesso do primal serão variáveis originais no 
dual, sendo que variáveis de folga/excesso são aquelas adicionadas ao lado esquerdo (left 
hand side - LHS) da restrição a fim de converter uma desigualdade (≤ ou ≥) em uma equação 
de igualdade (=). Assim, variáveis de folga/excesso representam a diferença entre o lado 
esquerdo (LHS) e direito (right hand side – RHS) da restrição. Da mesma forma, as variáveis 
básicas do primal serão variáveis não básicas no dual e as variáveis não básicas no primal 
serão variáveis básicas no dual. Tais relações facilitam a resolução dos problemas e a 
definição das soluções ótimas (Lopes, 2019). 
 
Por fim, segundo Lachtermacher (2018), existem duas razões para o estudo de problemas 
duais. A primeira está relacionada à quantidade de restrições. Quando o primal possui muitas 
restrições é mais fácil resolver o problema pelo seu dual, pois a quantidade de restrições será 
igual ao número de variáveis da função objetivo do primal. Portanto, provavelmente será um 
número menor de restrições, o que facilita para encontrar a solução ótima. A segunda refere-
se às interpretações econômicas obtidas com os valores das variáveis de decisão do problema 
dual (também chamadas de preço-sombra – shadow price – ou preço dual). Como foi visto 
no Teorema de Folga Complementar, as variáveis de decisão do dual estão associadas as 
variáveis de folga/excesso do primal. De forma geral, elas representam o valor pelo qual a 
função objetivo seria alterada, caso a quantidade de recurso fosse reduzida/aumentada uma 
unidade. Para analisar esse tipo de mudança, existe um procedimento realizado nos modelos 
de PL que é chamado de análise de sensibilidade (Lopes, 2019). 
Método Dual – Simplex 
O método Dual-Simplex lida diretamente com soluções básicas incompatíveis porém 
“melhor que a ótima”, e procura achar a compatibilidade do problema. Ele lida com um 
problema exatamente como se o método simplex estivesse sendo, simultaneamente, aplicado 
ao seu problema dual. No método simplex, algumas vezes é melhor começar com uma 
solução básica incompatível porém “melhor que a ótima” e procurar a compatibilidade, do 
8 
 
que obter uma solução compatível básica inicial e depois otimizá-la, como se faz no método 
simplex (Taha, 2008). 
O algoritmo primal simplex (e suas variações) começa com uma base primal viável e caminha 
para uma base terminal (que pode ser ótima ou não), passando por uma sequência de bases 
primal viáveis. Todas essas bases, com exceção possivelmente da base terminal, obtidas no 
algoritmo primal são bases dual inviáveis. A cada passo de pivotamento o algoritmo procura 
reduzir a inviabilidade dual ao mesmo tempo que mantém a viabilidade primal (Senne, 2014). 
O algoritmo dual simplex faz exatamente o contrário. Começa com uma base dual viável, 
mas primal inviável, e caminha para uma base terminal passando por bases dual viáveis 
adjacentes. À cada passo de pivotamento o algoritmo tenta reduzir a inviabilidade primal ao 
mesmo tempo que mantém a viabilidade dual (Senne, 2014). 
O algoritmo dual simplex pode ser executado usando a tabela canônica 
𝑉𝐵 𝑥1 . . . 𝑥𝑚 𝑥𝑚 + 1 . . . 𝑥𝑗 . . . 𝑥𝑛 𝑏 
𝑋1 1 . . . 0 𝑎′1, 𝑚 + 1 . . . 𝑎′1, 𝑗 . . . 𝑎′1, 𝑛 𝑏′1 
. . . . . . . . . . . . . . . . . . 
𝑥𝑚 0 . . . 1 𝑎′𝑚, 𝑚
+ 1 
 𝑎′𝑚, 𝑗 𝑎′𝑚, 𝑛 𝑏′𝑚 
−𝑧 0 . . . 0 𝑐′𝑚 + 1 . . . 𝑐′𝑗 . . . 𝑐′𝑛 −𝑧′ 
 
Ou usando a tabela inversa (método dual simplex revisado): 
 
 
Critério de Otimalidade no Algoritmo Dual Simplex 
No algoritmo dual simplex, B é base ótima se 𝑏′𝑖 ≥ 0 (𝑖 = 1, . . . , 𝑚). 
A Linha do Pivô (ou Variável que Sai da Base) 
Se o critério de otimalidade não está satisfeito, então existe i tal que 𝑏′𝑖 < 0. 
Seja r a linha do pivô, tal que: 
𝑏′𝑖 = 𝑚𝑖𝑛 { 𝑏′𝑖, 𝑖 = 1, . . . , 𝑚 } 
9 
 
Se 𝑏′𝑖 < 0, então na solução básica, o valor da i-ésima variável básica é igual a 𝑏′𝑖 (ou seja, 
um valor negativo, o que caracteriza a inviabilidade primal). O objetivo do pivotamento nesta 
linha é obter um novo vetor básico tal que o valor da i-ésima variável básica correspondente 
seja positivo. 
Para isso, o pivô 𝑎′𝑖𝑗deve ser escolhido entre os valores negativos na linha do pivô. Portanto, 
no método dual simplex todos os pivôs serão negativos (exatamente o contrário do método 
primal simplex, onde todos os pivôs têm que ser positivos para manter a viabilidade primal). 
Como resultado do pivotamento, a constante do lado direito da linha do pivô torna-se 
positiva. 
Critério de Inviabilidade do Problema 
O PPL será inviável se na tabela canônica existir uma linha i tal que: 
𝑏′𝑖 < 0 𝑒 𝑎′𝑖𝑗 ≥ 0 (𝑗 = 1, . . . , 𝑚) 
A Coluna do Pivô 
Se o critério de inviabilidadedo problema não é satisfeito, seja r a linha do pivô. A coluna 
do pivô deve ser determinada de tal forma a se ter uma nova base dual viável. Se o pivô for 
o elemento 𝑎′𝑟𝑠, os coeficientes de custo relativo na nova base serão: 
𝑐′𝑗 − 𝑐
′
𝑠
𝑎′𝑟𝑗
𝑎′𝑟𝑠
 (𝑗 = 1, . . . 𝑛) 
A nova base irá continuar dual viável se esses coeficientes forem não negativos, ou seja: 
𝑐′𝑗 − 𝑐
′
𝑠
𝑎′𝑟𝑗
𝑎′𝑟𝑠
 ≥ 0 (𝑗 = 1, . . . 𝑛) 
Como a base atual é dual viável, 𝑐′𝑗 ≥ 0 (𝑗 = 1, . . . , 𝑛). Logo, para satisfazer: 
 𝑎′𝑟𝑗 < 0 𝑒 𝑐
′
𝑠
𝑎′𝑟𝑗
𝑎′𝑟𝑠
 ou seja 
𝑐′𝑠
−𝑎′𝑟𝑠
≤
𝑐′𝑗
−𝑎′𝑟𝑗
 
Ou seja, a coluna s do pivô deve ser tal que: 
𝑐′𝑠
−𝑎′𝑟𝑠
= 𝑚𝑖𝑛 {
𝑐′𝑗
−𝑎′𝑟𝑗
| 𝑎′𝑟𝑗 < 0} 
10 
 
Após as operações de pivotamento, a coluna do pivô será transformada em um r-ésimo vetor 
unitário. 
Exemplo - Seja o PPL: 
 
 
Temos, então, a seguinte tabela canônica: 
 
Logo, a variável 𝑥4 entra na base, em substituição a 𝑥2. 
A nova tabela canônica será: 
 
Como todos os 𝑏′𝑖 ≥ 0, a base atual é ótima. 
Logo, a solução ótima é: 𝑥∗ = (4, 0, 1, 1, 0, 0)𝑇 𝑒 𝑧∗ = 1. 
Vantagens e Desvantagens do Algoritmo Dual Simplex 
No algoritmo dual simplex, todas as soluções básicas (exceto a solução final) são primal 
inviáveis. Se tivermos que interromper a execução do algoritmo dual simplex, todo o esforço 
será perdido pois não teremos uma solução viável para o problema até que o algoritmo 
termine. No algoritmo primal simplex todas as soluções básicas obtidas são primal viáveis. 
11 
 
Logo, se a execução do algoritmo for interrompida, poderemos não ter uma solução ótima, 
mas teremos, pelo menos, uma solução viável para o problema (Senne, 2014). 
O algoritmo dual simplex é muito útil para a Análise de Sensibilidade ou Análise de Pós-
otimalidade. Imagine que tenhamos uma base ótima para um PPL. Se após obter a base ótima 
for necessário alterar o vetor de constantes do lado direito (b), a base ótima pode deixar de 
ser primal viável, mas continuará dual viável, assumindo que o vetor de custos (c) mantenha-
se inalterado. A partir dessa base, o algoritmo dual simplex pode ser aplicado para o novo 
vetor b. Outra situação possível é precisar incluir uma nova restrição no modelo após ele ter 
sido resolvido. Neste caso, o algoritmo dual simplex poderá ser usado para encontrar uma 
solução ótima do novo modelo, partindo-se de uma solução ótima do modelo atual (Senne, 
2014). 
Análise de Sensibilidade em Programação Linear 
 
 Segundo autores FÁVERO e BELFIORE (2013) afirmam que resolver problemas de PL, 
assume-se que todos os parâmetros do modelo (coeficientes da função objetivo, coeficientes 
das variáveis das restrições e os termos independentes) são constantes e conhecidos com 
certeza. Porém, a aplicação da solução no mundo real pode gerar alterações em alguns 
parâmetros, causando incerteza sobre a qualidade da solução ótima (Lopes, 2019). 
Segundo Colin (2013), essas alterações podem ser: (1) propositais, ou seja, dentro de controle 
da empresa, como uma variação na sua capacidade de produção; e (2) relacionadas à 
incerteza, tendo relação a fatores externos e fora de controle da empresa, como a quantidade 
exata de venda no próximo mês (Lopes, 2019). 
Dessa forma, para minimizar a imprecisão a respeito dessas mudanças, realiza-se uma análise 
para verificar as possíveis variações, para cima e para baixo, dos valores dos parâmetros do 
modelo que não provocam alteração na solução ótima (LACHTERMACHER, 2006). Tal 
estudo é denominado de análise de sensibilidade (Lopes, 2019). 
De acordo com (FÁVERO, BELFIORE, 2013, p. 174), “a análise de sensibilidade é 
fundamental no estudo de problemas de programação linear, já que tem como objetivo 
12 
 
investigar os efeitos que determinadas alterações nos parâmetros do modelo causariam na 
solução ótima” (Lopes, 2019). 
 Os principais objetivos da análise de sensibilidade são: (1) identificar os parâmetros 
sensíveis, aqueles que se alterados modificam a solução ótima; e (2) determinar os intervalos 
de valores possíveis para os parâmetros não sensíveis, aqueles ao longo do qual a solução 
ótima permanecerá inalterada (HILLIER, LIEBERMAN, 2013). Para Lachtermacher (2006), 
a análise de sensibilidade auxilia o tomador de decisão avaliar como mudanças no modelo e 
no mundo real podem afetar a solução (COLIN, 2013), além de identificar quanto a solução 
está dependente de uma determinada constante ou coeficiente (Lopes, 2019). 
Tipos de Análise de Sensibilidade em Programação Linear 
Segundo Lachtermacher (2006), Fávero e Belfiore (2013), a análise de sensibilidade pode ser 
empregada em dois casos distintos. O primeiro caracteriza-se pelo fato de avaliar as 
possibilidades de variações e influências na solução ótima de um problema quando ocorre 
apenas uma alteração por vez; enquanto o segundo avalia quando ocorre mais de uma 
alteração de forma simultânea (Lopes, 2019). 
No primeiro caso, chamado de análise de sensibilidade, “estuda-se a variação que os 
coeficientes da função objetivo e as constantes do lado direito de cada restrição podem 
assumir (limites inferiores e superiores), sem alterar a solução ótima do modelo inicial ou 
sem alterar a região de factibilidade”, respectivamente (FÁVERO, BELFIORE, 2013, p. 
174). Essa análise pode ser feita com gráficos, com cálculos algébricos ou diretamente pelo 
Solver do Excel ou outros softwares como o LINGO (Lopes, 2019). 
O segundo caso, chamado de análise de sensibilidade pós-otimização ou análise pós-
otimização, “é empregado quando, após mudanças nos parâmetros do modelo, a solução 
ótima do modelo é afetada (a solução passa a ser subótima ou infactível), sendo necessário 
recalcular a nova solução ótima do modelo” (FÁVERO, BELFIORE, 2013, p. 174). A análise 
desse caso pode ser feita com gráficos, caso o problema tenha até duas variáveis, e a partir 
da forma tabular do método Simplex. Dessa forma, os conceitos da teoria da dualidade são 
utilizados diretamente na análise pós-otimização (Lopes, 2019). 
13 
 
Conclusão 
No presente trabalho conclui que todo problema de PL pode ser expresso de duas formas O 
problema original da programação linear é chamado de "Primal", enquanto o problema linear 
derivado é chamado de "Dual”. É um facto que quando o problema primal é de maximização, 
o seu problema dual será de minimização. O mesmo vale para o inverso, ou seja, se o primal 
for de minimização, seu dual será de maximização. Nota-se que Quando o primal possui 
muitas restrições é mais fácil resolver o problema pelo seu dual, pois a quantidade de 
restrições será igual ao número de variáveis da função objetivo do primal. Portanto, 
provavelmente será um número menor de restrições, o que facilita para encontrar a solução 
ótima. Sobre o método dual – simplex Ele lida com um problema exatamente como se o 
método simplex estivesse sendo, simultaneamente, aplicado ao seu problema dual. O 
algoritmo dual simplex pode ser executado usando a tabela canônica ou usando a tabela 
inversa (método dual simplex revisado). 
 
14 
 
Bibliografia 
Business Jargons. (16 de Setembro de 2016). Business Jargons. Obtido em 11 de Fevereiro 
de 2021, de businessjargons.com: https://businessjargons.com/duality-in-linear-
programming.html 
Lopes, T. F. (09 de Julho de 2019). ANÁLISE DE SENSIBILIDADE EM MODELOS DE 
PROGRAMAÇÃO LINEAR COM SOLUÇÃO DEGENERADA. Brasília. Obtido em 
12 de Fevereiro de 2021, de 
https://www.bdm.unb.br/bitstream/10483/25820/1/2019_ThaisFerreiraLopes_tcc.pd
f 
Senne, E. L. (19 de Fevereiro de 2014). O Método Dual Simplex. Obtido em 12 de 
Fevereiro de 2021, de feg.unesp.br: 
https://www.feg.unesp.br/Home/PaginasPessoais/profedsonluizfrancasenne/9-o-
metodo-dual-simplex.pdf 
Taha, H. A. (2008). Pesquisa Operacional (Vol. VIII). São Paulo: Pearson Education. 
Obtido em 12 de Fevereiro de 2021, de https://drive.google.com/file/d/1oCPC-
1RxBTEMD1pyVHJ5fGcGoY-yP9ai/view