Otimizacao_uni2

Prévia do material em texto

47
2.1 Dualidade
É comum observarmos a correlação entre di-
versos tópicos estudados na área da matemática, 
que, em princípio, não parecem ter conexão, como 
o estudo de Integrais e Derivadas que, ao se rela-
cionarem, convergem para um dos teoremas mais 
populares e basais do cálculo, que é o Teorema 
Fundamental do Cálculo. E, ainda, de acordo com 
Thie (1938), essas relações não só tem aplicabilidade 
computacional, mas também munem uma teoria de 
coerência e unidade.
Conforme Lins (2006), estudar a dualidade tem 
diversas vantagens e permitem:
• A melhor compreensão estrutural dos proble-
mas de programação linear;
• A interpretação econômica de alguns parâme-
tros, como o preço-sombra (shadow-price) e o custo 
de oportunidade;
• O desenvolvimento de aplicações utilizadas 
em pós-otimização, como o algoritmo dual-simplex;
• Problemas de Teoria dos Jogos de duas pes-
soas podem ser formulados por programação linear. 
Neste caso, as formulações primal e dual correspon-
dem às óticas do primeiro e segundo jogador;
• A Análise Envoltória de Dados (Data En-
velopment Analysis), cujas formulações primal 
e dual fornecem informações complementares 
48
sobre a fronteira de produção: os trade-offs e os 
benchmarks.
Dualidade considera que para cada problema 
de programação original, denominado primal, existe 
um problema dual intimamente relacionado. Con-
forme Luenberger (1984), ambos possuem a mesma 
linha de custo e coeficientes de restrição. No que se 
refere ao objetivo, enquanto o problema primal mi-
nimiza a função, o dual a maximiza e vice versa. Os 
valores ótimos da função objetivo correspondente, 
caso forem finitos, são iguais.
As variáveis do problema dual podem ser in-
terpretadas como preços associados com as restri-
ções do problema primal, e através dessa associação 
é possível fornecer uma caracterização economica-
mente significativa ao problema dual, embora, não 
exista tal caracterização para o problema primal 
(LUENBERGER, 1984).
Para representar matematicamente um pro-
blema dual, Thie (1938) primeiramente expressa o 
problema em sua forma primal, como demonstrado 
pelas Equações 1 a 5.
Max z=c1 x1+ c2 x2+....+cn xn (1)
Sujeito a: a11 x1+a12 x2+....+a1n xn≤b1 (2) 
a21 x1+a22 x2+....+a2n xn≤b2 (3)
49
am1 x1+am2 x2+⋯+amn xn≤bm (4)
x1,x2,…,xn≥0 (5)
Assim, a forma primal de um problema de pro-
gramação linear é um problema de maximização 
com um sistema de restrições que consistem apenas 
em desigualdade do tipo menor-igual (≤). É possível 
observar que neste modelo não existem limitações 
nos sinais dos coeficientes aij, cj e nas constantes bi 
(THIE, 1938).
Dado o problema primal representado pelas 
Equações 1 a 5, segue demonstrado pelas Equações 
de 6 a 10 o problema dual associado.
Min v=b1 y1+ b2 y2+....+bm ym (6)
Sujeito a: a11 y1+a21 x2+....+am1 ym≤c1 (7) 
a12 x1+a22 x2+...+am2 ym≤c2 (8)
a1n y1+a2n y2+....+amn ym≤cm (9)
y1,y2,…,ym≥0 (10)
Thie (1938) resume os componentes do problema 
dual relacionados com o problema primal, como segue:
i.Função objetivo: os coeficientes da função 
objetivo do problema dual são os termos constantes 
das restrições do problema primal e; a função objeti-
vo do dual é minimizar, desde que a função objetivo 
do primal seja maximizar o problema.
50
ii. Variáveis: o número de variáveis não negati-
vas do problema dual é igual ao número de desigual-
dades do tipo menor-igual (≤) do problema primal.
iii. Restrição: o número de desigualdades do 
tipo maior-igual (≥) do problema dual é igual ao nu-
mero de variáveis não negativas do problema primal.
Tabela 3: Relações entre um problema 
primal e dual.
Primal Dual
Problema de maximização Problema de minimização
i-ésima desigualdade (≤) i-ésima variável não negativa
j-ésima variável não negativa j-ésima desigualdade (≥)
Coeficientes da função 
objetivo
Termos constantes das 
restrições
Termos constantes das 
restrições
Coeficientes da função 
objetivo
Ex:
A fim de ilustrar, considere o seguinte problema:
Encontre o problema dual do seguinte proble-
ma de programação linear primal:
Max 12x1+ 4x2+ x3
sujeito a: 5x1+ x2+ 2x3≤10
7x1+ 2x2+ 5x3≤30
x1,x2,x3≥0
51
Resposta. O dual do problema primal acima é:
Min 10y1+ 30y2
sujeito a 5y1+ 7y2≥12
y1+ 2y2≥4
2y1+ 5y2≥1
y1,y2≥0
A fim de ilustrar melhor a relação entre o pro-
blema primal e dual alguns autores a demonstram por 
meio de notação matricial. Considerando o problema 
representado pelas Equações de 1 a 5, temos a se-
guinte representação matricial, segundo Thie (1938):
A=
a11 a12 a1n
a21 a22 a2n
am1 am2 amn
....
....
....
....
A=
a11 a12 am1
a21 a22 am2
am1 am2 amn
....
....
....
....
x=
x1
x2
xn
....b=
b1
b2
bm
.... c=
c1
c2
cn
....
Admita que At seja a matriz transposta de A e 
c∙X seja o produto escalar dos vetores c e X. Dessa 
forma teremos:
c∙X=c1 x1+ c2 x2+....+cn xn=c
t
 X=X
t
 c=X∙c
e
52
O problema primal representado pelas equa-
ções 1 a 5, simplesmente objetiva:
Max z=c∙X
sujeito a AX ≤b
X≥0
onde AX ≤b significa que cada componente do 
vetor coluna AX é menor ou igual so componen-
te correspondente do vetor b; e X≥0 considera o 0, 
neste caso, sendo o vetor zero n-dimensional. 
Assuma, ainda, que Y seja o vetor coluna m-
-dimensional (y1,y2,… ,ym )t. Dessa forma, o proble-
ma dual representado pelas Equações de 6 a 10 tem 
o intuito de:
Min v=b∙Y
sujeito a At Y ≥c
Y≥0
A Tabela 4 resume e a Figura 9 ilustra a com-
paração matricial entre um problema primal e dual:
Tabela 4: Comparação matricial resumida 
entre um primal e dual
Problema primal: Maximize z=c∙X sujeito a AX ≤b, X≥0.
Problema dual: Minimize v=b∙Y sujeito a A^t Y ≥c, Y≥0.
53
Fonte: Elaboração própria
Ex:
Lins (2006) exemplifica um problema dual utili-
zando o exemplo do problema da dieta, como segue.
Problema da dieta
Este problema consiste em garantir a oferta de 
calorias e vitaminas através de determinada quan-
tidade de cinco alimentos.
i nutriente;
j alimento;
xj variável de decisão do alimento j;
Aij Quantidade do nutriente i por unidade do alimento j
bi Quantidade necessária de nutriente i
Formulando o problema de programação line-
ar temos:
Min. 20x1+ 25x2+ 31x3+11x4+12x5
sujeito a: x1+x_3+x4+2x5≥21 
x2+2x3+x4+x5≥12
x1,x2,x3,x4,x5≥0 
54
Este problema de programação linear está re-
presentado a seguir e possui solução ótima x*=[0 0 0 
3 9]T e custo de 141.
x1 x2 x3 x4 x5 b
Calorias 1 0 1 1 2 21
Vitaminas 0 1 2 1 1 12
Custo 
Unitário 20 25 31 11 12 Q(x)
Agora, imagine que determinada empresa 
tem o interesse me criar pílulas de calorias e vi-
taminas que contenham uma unidade de cada, a 
fim de substituir os alimentos de 1 a 5 (x1 a x5), 
sendo que o principal interesse da empresa é obter 
o maior lucro possível. Considere que as pílulas 
são para substituição integral da alimentação di-
ária dos indivíduos, e, dessa forma, o preço da 
pílula de calorias é y1 e o da pílula de vitaminas é 
y2. Assim, teremos a função objetivo do problema 
como segue:
Min 21y1+ 12y2.
Além de maximizar seu lucro, a empresa deve 
possuir competitividade para que se mantenha no 
mercado, e por isso, deve garantir que as pílulas cus-
tem menos e que sejam proporcionais à quantidade 
calórica e vitamínica de cada um dos alimentos. 
55
Dessa maneira, para o alimento 1, que contém ape-
nas uma unidade de caloria, a restrição é:
1y1≤20
A restrição do alimento 2 que contém apenas 
uma unidade de vitamina é:
1y2≤25
A restrição do alimento 3 que é composto por 
uma unidade de caloria e dias de vitamina é dada 
por:
1y1+2y2≤31
As demais restrições são descritas como segue:
1y1+1y2≤11: restrição relacionada à variável x4
2y1+1y2≤12: restrição relacionada à variável x5
Considerando que os preços não podem ser va-
riáveis negativas, logo teremos:
y1 ,y2≥0.
As demais restrições são descritas como segue:
1y1+1y2≤11: restrição relacionada à variável x4
2y1+1y2≤12: restrição relacionada à variável x5
56
Considerando que os preços não podem ser va-
riáveis negativas, logo teremos:y1,y2≥0.
Condensando a função objetivo e restrições, te-
mos o seguinte problema dual:
Min 21y1+ 12y2
sujeito a 1y1 ≤20
1y2 ≤25
1y1+2y2≤31
1y1+1y2≤11
2y1+1y2≤12
y1 ,y2≥0.
A tabela abaixo representa matricialmente o 
problema:
y1 y2 b
Alimento 1 1 0 20
Alimento 2 0 1 25
Alimento 3 1 2 31
Alimento 4 1 1 11
Alimento 5 2 1 12
Receita Uni-
tária 21 12 Q(y)
Colocando o problema na forma padrão temos:
57
y1 y2 w1 w2 w3 w4 w5 b
Alimento 1 1 0 1 0 0 0 0 20
Alimento 2 0 1 0 1 0 0 0 25
Alimento 3 1 2 0 0 1 0 0 31
Alimento 4 1 1 0 0 0 1 0 11
Alimento 5 2 1 0 0 0 0 1 12
Receita 
Unitária -21 -12 0 0 0 0 0 Q(y)
A solução ótima deste problema dual é 
y*=[1 10], e a receita unitária será de 141, exa-
tamente o mesmo valor encontrado no problema 
de programação linear primal.
2.1.1. MÉTODO DUAL-SIMPLEX
O método dual-simplex foi concebido 
como forma alternativa a alguns métodos de so-
lução para problemas de programação linear, por 
exemplo, o método das duas fases e Big-M (Lins, 
2006). Assim, este método é utilizado nos casos 
em que não exista uma base inicial viável para o 
problema primal, mas que exista uma base viável 
para o problema dual. É utilizado o tableux do 
modelo primal para a aplicação do método dual-
-simplex.
Pizzolato (2009) descreve o passo a passo do 
algoritmo dual-simplex, como segue:
58
Passo (0): o problema é de maximização
Passo (1): se bi ≥0,i=1,2,…,m então fim, o óti-
mo encontrado. Se existe algum bj <0 então vá 
para o passo (2);
Passo (2): escolha a variável a sair da base, ou 
linha pivô:
Br =mini {bi | bi<0}, onde r é a linha do pivô.
 Se arj≥0,j=1,2,…,n então o problema 
primal é infactível fim. Caso contrário, vá para o 
passo (3);
Passo (3): escolha a variável para entrar na 
base, para isso selecione:
CS CS 
ARS ARS
= MaxJ ARJ<0 Onde s é a coluna do pivô.
Passo (4): efetuar a atualização dos coeficien-
tes da tabela, realizar o pivoteamento em ars. Vá 
para o passo (2).
59
Ex:
Luenberger (1984) demonstra a aplicação do 
algoritmo dual-simplex através do exemplo:
A forma mais comum de um problema é 
quando se pretende minimizar uma combinação 
positiva de variáveis positivas, sujeitas a uma série 
de inequações do tipo “maior que” possuindo coe-
ficientes positivos. Problemas desse tipo são candi-
datos naturais para a aplicação do algoritmo dual 
simplex. Como segue:
Max 3x_1+4x_2+ 5x_3
sujeito a: x1+2x2+3x3 ≥5
2x1+2x2+x3≥6 
x1,x2,x3≥0
Introduzindo as variáveis de folga e modifican-
do os sinais das inequações é obtido o tableau inicial.
Primeiro tableau
-1 -2 -3 1 0 -5
-2 -2 -1 0 1 -6
3 4 5 0 0 0
60
A base corresponde à solução factível dual desde 
que todos cj- zj sejam não negativos. Então, é selecio-
nado qualquer xBi<0, por exemplo, x5 =-6 para re-
mover do conjunto de variáveis básicas.Para encon-
trar o elemento pivô apropriado na segunda linha 
, calcula-se a relação (zj- cj)/y2j e seleciona a menor 
relação positiva. Assim, os tableaus seguintes são:
Segundo tableau
0 -1 -5/2 1 -1/2 -2
1 1 1/2 0 -1/2 3
0 1 7/2 0 3/2 -9
Último tableau
0 1 5/2 -1 1/2 2
1 0 -2 1 -1 1
0 0 1 1 1 -11
O último tableau gera a solução factível do 
primal que deve ser ótima. Dessa forma, tem-se a 
solução: x1=1,x2 =2,x3 =0.
2.2. Teorema da Dualidade
Nesta seção serão apresentados os teoremas re-
ferentes à dualidade, que tiveram maior acuidade após 
o esforço de John Von Newmann em prová-los. Para 
isso, continuaremos a considerar a notação estabele-
cida na seção anterior, como demonstra a Tabela 5.
61
Primal Dual
Max z=c∙X Min v=b∙Y
sujeito a AX ≤b sujeito a At Y ≥c
X≥0 Y≥0
Tabela 5: Notação dos problemas primal e dual.
2.2.1. Teorema da Dualidade Fraca
Seja X_0 o conjunto de solução factível do pro-
blema primal e Y_0 o conjunto de solução factível 
do problema dual, logo ⋯c∙X⋯_0≥b∙Y_0.
Prova. Seja X0 a solução do problema primal im-
plica que AX0 ≤b, uma vez que, Y0≥0,Y0t AX0≤Y0t 
b. Analogamente, seja Y_0 a solução do problema 
dual e X0≥0 implica que At Y0≥c e X0t At Y0≥ X0t c. 
Agora, X0t At Y0 é apenas um número real, e então:
(X0t At Y0 )= (X0t At Y0 )t= Y0t AX0
Portanto:
c∙X0= X0t c ≤X0t At Y0=Y0t AX0≤Y0t=b∙Y0.
Ex:
Thie (1938) demonstra a aplicação deste teore-
ma de maneira elementar.
Problema P
62
Max 13x1-2x2+ 5x3
sujeito a: 2x1-6x2+ 7x3≤100
x1+9x2- 8x3≤150
x1,x2,x3≥0
Problema D
Min 100y_1+150y_2
sujeito a 2y_1+ y_2 ≥13 
-6y1+ 9y2≥-2
7y1- 8y2≥5 
y1,y2≥0
Considere que os problemas P e D sejam duais. 
Suponha agora que (x1,x2,x3) seja o conjunto de solu-
ção factível para as restrições do problema P, e que 
(y1,y2) seja o conjunto de solução factível para as res-
trições do problema D. Assim, desde que os compo-
nentes de (x1,x2,x3) sejam não negativos e satisfaçam 
as inequações do problema P e que os componentes 
de (y1,y2), também, sejam não negativos e satisfa-
çam as inequações do problema D, tem-se:
x1,x2,x3)= 13x1-2x2+ 5x3 
= 13x1+ (-2) x2+ 5x3
≤(2y1+y2 ) x1+ (-6y1+ 9y2 ) x2+ (7y1- 8y2)x3
 =2y1 x1+y2 x1 -6y1 x2+9y2 x2+7y1 x3-8y2 x3
=(2x1-6x2+ 7x3 ) y1+ (x1+9x2 -8x3)y2
63
≤100y1150y2
= y1,y2 
A prova do teorema da dualidade fraca é sim-
plesmente a generalização desses passos.
Corolário 1
Se X0 e Y0 forem soluções factíveis para os 
problemas primal e dual, respectivamente, e se 
c∙X0=b∙Y0 os valores ótimos das funções objetivos 
z e v são iguais, ou seja, maximizar z=c∙X é igual a 
minimizar v=b∙Y.
Corolário 2
Se a função objetivo z do problema primal for 
ilimitada acima, não haverá solução factível para o 
problema dual. De forma equivalente, se a função 
objetivo v do problema dual for ilimitada abaixo, 
não haverá solução factível para o problema primal.
2.2.2. Teorema da Dualidade Forte
Caso o problema primal tenha uma solução fi-
nita, então o problema dual também terá uma solu-
ção finita. Ademais, os valores ótimos das funções 
objetivos serão iguais (c∙X0=b∙Y0).
64
Você pode encontrar prova do teorema forte da dualidade em 
todos os livros referências, porém, é possível encontrar a expli-
cação de maneira simplificada em Thie (1938) e em Lins (2006)..
Corolário 3
Se ambos os problemas primal e dual possuem 
soluções factíveis, então, ambas as soluções-objeti-
vos possuem soluções-ótimas e maximizar z=c∙X é 
igual a minimizar v=b∙Y.
Thie (1938) resume que existem exatamente 
quatro diferentes categorias em que as soluções dos 
problemas primal e dual podem ocorrer, são elas:
Os dois problemas possuem soluções factíveis, 
assim, os conjuntos de valores possíveis para as fun-
ções objetivos z e v relacionados como segue apre-
sentado pela Figura 10.
Fonte: THIE (1938).
• A função objetivo z é ilimitada acima e o pro-
blema dual não possui solução factível.
65
• A função objetivo é ilimitada abaixo e o pro-
blema primal não possui solução factível.
• Ambos os problemas não possuem solução 
factível.
Ex:
O Teorema forte da dualidade é exemplificado 
como segue:
Problema Primal
Max -5x1+18x2+ 6x3-3x4
sujeito a 2x1 -x3+ 3x4 ≤20 
x2- 2x3- x4 ≤30 
-3x1+6x2+3x3+ 4x4≤24 
x1,x2,x3,x4≥0
Problema Dual
Min 20y1+30y2+24y3
sujeito a 2y1 - 3y ≥-5 
 y2+ 6y3≥18
-y1- 2y2+3y3≥6
3y1- y2+4y3≥-3 
y1,y2,y_≥0
Adicionando três variáveis de folga ao problema 
primal e resolvendo-o, nós teremos a tabela abaixo:
66
 x1 x2 x3 x4 x5 x6 x7 
x5 2 0 -1 3 1 0 0 20
x6 0 1 -2 -1 0 1 0 30
x7 -3 6 3 4 0 0 1 24
 5 -18 -6 3 0 0 0 0
x5 2 0 -1 3 1 0 0 20
x6 1/2 0 -5/2 -5/3 0 1 -1/6 26
x2 -1/2 1 1/2 2/3 0 0 1/6 4
 -4 0 3 15 0 0 3 72
x1 1 0 -1/2 3/2 1/2 0 0 10
x6 0 0 -9/4 -29/12 -1/4 1 -1/6 21
x2 0 1 1/4 17/12 1/4 0 1/6 9
 0 0 1 21 2 0 3 112
O máximo valor da função -5x1+18x2+ 6x3-3x4 
é 112 e obtém os pontos (10, 9, 0, 0). O mínimo valor 
da função objetivo do problema dual é, também, 112 
e, a partir da última linha na terceira tabela (variá-
veis de folga), os pontos obtidos foram (2,0,3).
2.3. ANÁLISE DE SENSIBILIDADE
Em algumas aplicações de programação linear 
pode haver a necessidade não apenas em otimizar 
uma função sob condições específicas, mas tambémavaliar os efeitos das mudanças realizadas nas condi-
ções do problema na solução ótima (THIE, 1938).
Santos (2007) complementa ainda que os mo-
delos de otimização não possuem precisão nos re-
sultados, por isso, tem-se um certo grau de incerteza 
67
e, devido a isso, o estudo de análise de sensibilidade 
se faz necessário. Lins (2006) exemplifica a aplicação 
da análise de sensibilidade em duas situações:
• No planejamento em longo prazo, por exem-
plo, pode ser interessante verificar o quanto determi-
nados parâmetros podem variar sem alterar a solu-
ção ótima encontrada;
• Novos requisitos, visando à melhor formula-
ção do PPL, podem implicar em acréscimo de uma 
nova restrição e/ou variável, assim como alteração 
em parâmetros.
No estudo de análise de sensibilidade, os parâ-
metros que são passíveis de variação são:
• Coeficientes da função objetivo;
• Coeficientes das restrições;
• Constantes do lado direito das restrições e;
• Inclusão de uma nova variável.
Ex:
1) Problema da dieta
Considere que um produtor deve produzir o 
estoque de uma dieta adequada a um custo mínimo 
de dois alimentos disponíveis. Seja x_1 e x_2 o peso 
dos alimentos 1 e 2 da dieta, assim, o problema de 
programação linear é:
Min 16x1+ 14x2
sujeito a 10x1+4x2≥124
68
3x1+5x2- 8x3≥60
x1,x2≥0
A Figura 11 apresenta, graficamente, o conjun-
to das soluções factíveis (área sombreada). O valor 
da função objetivo pode ser calculado nos três vérti-
ces e seu valor mínimo encontrado. É claro, a par-
tir do gráfico que o valor mínimo de 16x1+ 14x2, é 
obtido nos pontos (10, 6) e assim, obtendo valor 244.
Agora suponha que os custos desses dois alimen-
tos variam de acordo com as condições de mercado. 
Agora o produtor gostaria de saber se o ponto (10,6) 
ainda é o custo mínimo da dieta. É possível notar 
que, contanto que a inclinação das linhas determi-
69
nadas pela função objetivo esteja entre a inclinação 
das duas linhas que se cruzam em (10, 6), então este 
ponto pode fornecer um custo mínimo. 
Algebricamente, seja c1 e c2 denotar os custos 
dos alimentos 1 e 2, respectivamente. A inclinação 
da linha c1 x1+c2 x2=c, é (-c1) c2 onde c é uma cons-
tante. A inclinação dessas duas linhas que intersec-
tam em (10, 6) são (-5) (2 )e (-3) 5. Assim, a condição 
em c 1 e c2 é simplesmente que:
-5 -3-c1
c22 5≤
≤
3 5-c1
c25 2
≤ ≤
Ou
Dessa forma, desde que a relação dos custos do 
alimento 1 ao alimento 2 esteja entre 3/5 e 5/2, 
10kg do alimento 1 e 6kg do alimento 2 fornecem 
uma dieta de custo mínimo.
Suponha, ainda, que o produtor questione o 
efeito da variação dos requisitos nutricionais diá-
rios. Considere que foram estimadas 124 unidades 
do nutriente A e 60 unidades do nutriente B, e o 
produtor gostaria de saber o quanto ele economiza-
ria diminuindo essas quantidades. Ou pode ser que 
o produtor descobriu que incrementando as quanti-
dades de um desses nutrientes seu estoque terá maior 
valor de mercado.
70
Assuma que o custo dos dois alimentos são 16 e 14 
centavos / Kg. Para isso, considere o problema dual:
Max 124y1+ 60y2
sujeito a: 10y1+3y2≤16
4y1+5y2≤14
x1,x2≥0
A Figura 12 exibe que o máximo valor da fun-
ção objetivo 124y1+ 60y2 é alcançado no ponto (1, 
2) e é igual a 244, o mesmo valor encontrado na 
minimização do problema original, o que reflete o 
exposto pelo Teorema da Dualidade.
Este fato foi considerado para estimar o efeito 
de variar as quantidades requeridas de nutrientes. 
Seja, b1 e b2 denotar a mínima quantidade diária de 
elementos A e B respectivamente. Sob essas condições 
gerais a mais o único componente modificado no 
problema dual foi a função objetivo que se tornou b1 
y1+ b2 y2. Agora, como antes, desde que a inclinação 
das linhas determinadas pela função objetivo este-
ja entre a inclinação das duas linhas que se cruzam 
em (1, 2), então este ponto pode fornecer o máximo 
valor da função objetivo. Essa duas inclinações são 
-10/3 e -4/5. Assim, contanto que:
10 4b1
b23 5≤ ≤
71
Ou
4 10b1
b25 3
≤ ≤
O máximo valor da função objetivo dual, e 
também, o mínimo custo da dieta apropriada será 
b1+ 2b2. Dessa forma, desde que a relação do nú-
mero requerido de unidades entre o elemento A e B 
esteja entre 4/5 e 10/3, o mínimo custo em centavos 
para o produtor será a quantidade de unidades do 
nutriente A mais duas vezes a quantidade de unida-
des do nutriente B. Pode-se interpretar também, que 
cada unidade do nutriente A custa para o produtor 
1 centavo, e cada unidade do nutriente B custa para 
o produtor 2 centavos.
72
Na segunda parte do exemplo, fomos capazes 
de medir a consequência que as variações implicam 
no custo mínimo, ou seja, foi medido o efeito nas 
mudanças nos termos das restrições do problema no 
valor ótimo da função objetivo.
73
Exercícios 
1.A Dualidade considera que para cada proble-
ma de programação original, denominado primal, 
existe um problema dual. Cite o que o estudo da 
dualidade proporciona.
2.Resuma em forma de esquema, os compo-
nentes de um problema dual relacionando-os com 
o problema primal.
3.Dado o problema primal abaixo, formule seu 
dual.
Max 2x1+ 5x2+ 7x_3
sujeito a: 3x1+ 8x2+ 6x3≤10
4x1+ 2,5x2+ 3,2x3≤30
x1,x2,x3≥0
4.Descreva o passo a passo do método dual 
simplex.
5.Explique a função da análise de sensibilidade, 
indique quais os parâmetros que podem ser modifi-
cados e cite a importância de aplicação.