Programação Linear - Abordagem Gráfica

Prévia do material em texto

28/10/12 
1 
PROGRAMAÇÃO LINEAR: UMA 
ABORDAGEM GRÁFICA 
¨  Exemplo(Mathur e Solow): Chemicals Company(CC) produz 
2 solventes(CS1 e CS2) em sua planta de Cleveland. A 
planta opera 40 horas pode semana e emprega 5 
trabalhadores em tempo integral e 2 em tempo parcial
(15h/semana) para fazer funcionar suas 7 máquinas que 
misturam certos produtos químicos para fabricar solvente. 
Esta força de trabalho fornece 230 horas no depto de 
mistura. Os produtos, uma vez misturados, são refinados no 
depto de purificação o qual, atualmente, tem 7 
purificadores e empregam 6 trabalhadores em tempo 
integral e um em tempo parcial(10 horas/semana). A força 
de trabalho neste depto é, portanto, de 250 horas por 
semana. 
28/10/12 
2 
¨  As horas requeridas nos referidos deptos são descritas abaixo. 
CC tem fornecimento ilimitado de matéria prima e pode 
vender qq quantia de CS1 mas a demanda de CS2 está 
limitada a 120 galões/semana. A contabilidade estima uma 
margem de lucro de $0,30/galão de CS1 e $0,50/galão de 
CS2. Determine o plano de produção semana da CC. 
 
Tabela 1 – requerimentos de mobra(h/1000gal) 
 
CS1 CS2 
Mistura 2 1 
Purificação 1 2 
¨  Maximize 3x1 + 5x2 
¨  s.t. 
¨  Mistura) 2x1 + x2 <= 230 (1) 
¨  Embal) x1 + 2x2 <= 250 (2) 
¨  DemP2) x2 <= 120 (3) 
¨  x1 >= 0 (4) 
¨  x2 >= 0 (5) 
28/10/12 
3 
O que se deseja? 
¨  Valores para as variáveis de decisão que 
obedeçam a todas as restrições 
Valores Viáveis 
¨  Conjunto de valores para as varáveis de decisão 
em um programa linear que satisfaz todas as 
restrições 
Região Viável 
28/10/12 
4 
¨  Uma solução na qual as variáveis de decisão são 
viáveis 
Solução Viável 
¨  Aquela solução que além de satisfazer todas as 
restrições (solução viável) conduz ao melhor valor 
da função objetivo 
Solução Ótima 
28/10/12 
5 
-250 
-150 
-50 
50 
150 
250 
350 
-300 -200 -100 0 100 200 300 
x1 
x2 
(1) 2x1+x2<=230 
(2) x1+2x2<=250 
(3) x2<=120 
(4) x1>=0 
(5) x2>=0 
FO) 3x1+5x2=660 
Ótima: x1 = 70; x2 = 90 (FO= 660) 
FO) 3x1+5x2=210 
FO) 3x1+5x2=400 
Solução Ótima 
Ponto
Extremo
X1 X2 F.O.
A 0 0 0
B 115 0 345
C 70 90 660
D 10 120 630
E 0 120 600
28/10/12 
6 
-250 
-150 
-50 
50 
150 
250 
350 
-300 -200 -100 0 100 200 300 
x1 
x2 
(1) 2x1+x2<=230 
(2) x1+2x2<=250 
(3) x2<=120 
(4) x1>=0 
(5) x2>=0 
FO) 3x1+5x2=660 
Ótima: x1 = 70; x2 = 90 (FO= 660) 
(4) x1>=150 
(2) x1+2x2>=250 
-250 
-150 
-50 
50 
150 
250 
350 
-300 -200 -100 0 100 200 300 
x1 
x2 
(1) 2x1+x2>=230 
(3) x2<=120 
(5) x2>=0 
(4) x1>=0 
28/10/12 
7 
-250 
-150 
-50 
50 
150 
250 
350 
-300 -200 -100 0 100 200 300 
x1 
x2 
(1) 2x1+x2<=230 
(2) x1+2x2<=250 
(3) x2<=120 
(4) x1>=0 
(5) x2>=0 
FO) 3x1+5x2=660 
Ótima: x1 = 70; x2 = 90 (FO= 660) 
(6) x1+x2<=300 
(2) x1+2x2<=250 
-250 
-150 
-50 
50 
150 
250 
350 
-300 -200 -100 0 100 200 300 
x1 
x2 
(1) 2x1+ x2<=230 
(3) x2<=120 
(4) x1>=0 
(5) x2>=0 
FO) 2x1+4x2=500 
Ótima: x1 = 70; x2 = 90 (FO= 500) 
Ótima: x1 = 10; x2 = 120 (FO= 500) 
FO) 3x1+5x2 FO) 2x1+4x2 
28/10/12 
8 
 DUALIDADE E ANÁLISE DE SENSIBILIDADE 
 
2a. Aula – 16/08/2011 
Análise de Sensibilidade 
Investigar os efeitos sobre a solução ótima de 
realizar-se mudanças nos parâmetros do modelo 
aij, bi e cj. 
 
Ex.: sempre que yi* >0 então a solução ótima muda 
caso bi seja modificado 
28/10/12 
9 
¨  Problemas empresariais devem considerar as 
incertezas 
¤  Oque aconteceria se o custo do produto aumentasse 
7%? 
¤  O que aconteceria se a redução do tempo de 
configuração de uma máquina permitisse capacidade 
adicional a essa máquina? 
¤  Oque aconteceria se o tempo de mão-obra para a 
produção de um produto precisasse de duas horas e 
não três? 
¨  Maximize 3x1 + 5x2 
¨  s.t. 
¨  Mistura) 2x1 + x2 <= 230 (1) 
¨  Embal) x1 + 2x2 <= 250 (2) 
¨  DemP2) x2 <= 120 (3) 
¨  x1 >= 0 (4) 
¨  x2 >= 0 (5) 
28/10/12 
10 
Microso'	
  Excel	
  14.0	
  Sensi3vity	
  Report	
  
Worksheet:	
  [Workbook1]Sheet1	
  
Report	
  Created:	
  15/08/2011	
  23:21:00	
  
	
  Variable	
  Cells	
  	
  
	
  	
   	
  	
   Final	
   Reduced	
   Objec3ve	
   Allowable	
   Allowable	
  
Cell	
   Name	
   Value	
   Cost	
   Coefficient	
   Increase	
   Decrease	
  
$B$2	
   x1	
   70	
   0	
   3	
   7	
   0,5	
  
$C$2	
   x2	
   90	
   0	
   5	
   1	
   3,5	
  
Constraints	
  
	
  	
   	
  	
   Final	
   Shadow	
   Constraint	
   Allowable	
   Allowable	
  
Cell	
   Name	
   Value	
   Price	
   R.H.	
  Side	
   Increase	
   Decrease	
  
$D$4	
   Mistura)	
   230	
   0,333333333	
   230	
   270	
   90	
  
$D$5	
   Embalagem)	
   250	
   2,333333333	
   250	
   45	
   135	
  
$D$6	
   DemP2)	
   90	
   0	
   120	
   1E+30	
   30	
  
Microso'	
  Excel	
  14.0	
  Answer	
  Report	
  
Worksheet:	
  [Workbook1]Sheet1	
  
Report	
  Created:	
  15/08/2011	
  23:20:59	
  
	
  Result:	
  	
  Solver	
  found	
  a	
  solu3on.	
  	
  All	
  constraints	
  and	
  op3mality	
  condi3ons	
  are	
  sa3sfied.	
  
	
  Solver	
  Engine	
  	
  
	
  Engine:	
  	
  	
  Simplex	
  LP	
  	
  
	
  SoluHon	
  Time:	
  	
  0,690193	
  	
  Seconds.	
  	
  
	
  IteraHons:	
  	
  3	
  	
  Subproblems:	
  	
  0	
  
	
  Solver	
  Op3ons	
  	
  
	
  Max	
  Time	
  	
  	
  Unlimited	
  ,	
  	
  IteraHons	
  	
  	
  Unlimited	
  ,	
  	
  Precision	
  	
  1e-­‐06	
  
	
  Max	
  Subproblems	
  	
  	
  Unlimited	
  ,	
  	
  Max	
  Integer	
  Sols	
  	
  	
  Unlimited	
  ,	
  	
  Integer	
  Tolerance	
  	
  1%,	
  	
  Assume	
  NonNegaHve	
  	
  
	
  ObjecHve	
  Cell	
  	
  (Max)	
  
Cell	
   Name	
   Original	
  Value	
   Final	
  Value	
  
$D$3	
   Max	
   0	
   660	
  
	
  Variable	
  Cells	
  	
  
Cell	
   Name	
   Original	
  Value	
   Final	
  Value	
   	
  Integer	
  	
  
$B$2	
   x1	
   0	
   70	
  	
  ConHn	
  	
  
$C$2	
   x2	
   0	
   90	
  	
  ConHn	
  	
  
Constraints	
  
Cell	
   Name	
   Cell	
  Value	
   Formula	
   Status	
   Slack	
  
$D$4	
   Mistura)	
   230	
  $D$4<=$F$4	
   Binding	
   0	
  
$D$5	
   Embalagem)	
   250	
  $D$5<=$F$5	
   Binding	
   0	
  
$D$6	
   DemP2)	
   90	
  $D$6<=$F$6	
   Not	
  Binding	
   30	
  
28/10/12 
11 
Dualidade 
“TODO O PROBLEMA DE PROGRAMAÇÃO LINEAR TEM ASSOCIADO A ELE 
UM OUTRO PROBLEMA DE PROGRAMAÇÃO LINEAR QUE FORNECE A 
MESMA SOLUÇÃO ÓTIMA” 
PRIMAL à DUAL 
Relações Primal-Dual 
PRIMAL DUAL 
Maximizar z=c1x1+c2x2+...+cnxn 
 
s.a. 
 
a11x1 + a12x2 +...+ a1nxn<=b1 (y1) 
a21x1 + a22x2 +...+ a2nxn<=b2 (y2) 
... 
am1x1 + am2x2 +...+ amnxn<=bm (yn) 
 
 
xj >=0,(j=1,2,...,n) 
 
 
Minimizar D=b1y1+b2y2+...+bmym 
 
s.a. 
 
a11y1 + a21y2 +...+ am1ym>=c1 (x1) 
a12y1 + a22x2 +...+ a2nym>=c2 (x2) 
... 
a1ny1 + a2nx2 +...+ a1nym>=cn (xn) 
 
yi >=0,(i=1,2,...,m) 
 
28/10/12 
12 
Relações Primal-Dual 
¨  1º.) se o problema primal é de maximização, o 
problema dual é de minimização e vice-versa; 
¨  2º.) lados direitos das restrições do problema primal se 
transformam nos coeficientes da função objetivo do 
dual; 
¨  3º.) os coeficientes da função-objetivo do primal se 
transformam nos lados direitos das restrições do 
problema dual; 
¨  4º.) a matriz dos coeficientes das restrições do dual 
corresponde à transposta da matriz tecnológica do 
primal. 
Relações Primal-Dual 
¨  5º) o número de restrições do primal corresponde 
ao número de variáveis do dual 
¨  6º.) os resultados do primal e do dual são iguais; 
¨  7º) o dual do problema dual é o próprio primal. 
Se W=b1y1+b2y2+...+bmym 
então yi pode ser interpretada como a contribuição 
atual ao lucro por unidade de recurso i 
28/10/12 
13 
¨  Teorema I : o dual do dual é o primal 
¨  Teorema II: se a k-ésima restrição do primal é uma 
igualdade, então a k-ésima variável do dual(yk) é sem 
restrição de sinal, isto é, pode ter valor positivo, zero ou 
negativo 
¨  Teorema III: se a p-ésima variável do primal é sem restrição 
de sinal, então a p-ésima restrição do dual é uma 
igualdade. 
¨  Teorema IV: se tanto o primal quanto o dual tem soluções 
viáveis finitas, então existe uma solução ótima finita para 
cada um dos problemas tal que Z*=D*. (propriedade forte 
da dualidade; Hillier e Libermann, 1995) 
Exemplos: 
¨  Max Z = 2y1 + y2 
¨  s.a. 
n  -y1 + y2 <= 1 
n  y1 + y2 <=3 
n  y1 – 2y2 <=4 
n  y1>=0, y2 >=0 
28/10/12 
14 
¨  Max Z = y1 + 2y2 
¨  s.a. 
n  3y1 + y2 <= 6 
n  2y1 + y2 = 3 
n  Y1 >=0, y2>=0 
n  COLIN PG. 70, exercs. 1,2,3 
DEA CCR orientado a insumos 
28/10/12 
15 
¨  Max Ef = 2u1 
¨  s.a. 
¨  4v1 + 3v2 = 1 ( ) 
¨  2u1 – 4v1 -3v2 <=0 
¨  5u1 – v1 – 6v2 <=0 
¨  4u1 – 2v1 -3v2 <=0 
¨  u1 – v1 -2v2 <=0 
¨  8u1 – 10v1 -5v2 <=0 
¨  u1, v1, v2 >=0 
1!
2!
3!
4!
5!
!
28/10/12 
16 
DEA CCR orientado a insumos 
Modelo do Envelopamento 
28/10/12 
17 
28/10/12 
18 
Interpretação econômica do problema dual 
¨  As variáveis originais(yi) são, normalmente, 
chamadas de preço-sombra ou preço dual e 
representam economicamente o valor marginal do 
recurso da restrição i em relação ao valor da 
função objetivo, isto é, o valor pelo qual a função 
objetivo seria alterada caso a quantidade do 
recurso i(representada pela constante da restrição 
bi) fosse aumentada em uma unidade. 
28/10/12 
19 
¨  PROBLEMA NA FORMA PADRÃO 
Maximizar z=c1x1+c2x2+...+cnxn 
s.a. 
a11x1 + a12x2 +...+ a1nxn + s1=b1 (y1) 
a21x1 + a22x2 +...+ a2nxn +s2=b2 (y2) 
... 
am1x1 + am2x2 +...+ amnxn + sn = bm (yn) 
xj >=0,(j=1,2,...,n) 
¨  Forma Padrão 
¤  A funçao objetivo é do tipo de maximização 
¤  Todos os lados direitos das equações são não negativos 
¤  Todas as restrições são do tipo igualdade; 
¤  Todas as variáveis de decisão são não-negtivas 
28/10/12 
20 
 
PREÇO SOMBRA OU PREÇO DUAL 
 
•  Preço sombra para o recurso i(yi*) mede o 
valor marginal desse recurso, i.e., a taxa 
na qual Z poderia ser aumentado, 
elevando-se ligeiramente a quantidade 
deste recurso(bi) que está sendo 
disponibilizado. 
•  É fornecido pela solução ótima para o 
problema dual. 
O valor deste preço sombra só é 
válido dentro do intervalo de 
sensibilidade.