Prgramação Inteira Cassel

Prévia do material em texto

Introdução	
  à	
  Programação	
  
Inteira	
  
Pesquisa	
  Operacional	
  
1	
  Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  Daniel	
  Zini	
  
Tipos	
  de	
  programação	
  inteira	
  (PI)	
  
•  Problemas	
  puros:	
  todas	
  as	
  variáveis	
  são	
  
inteiras	
  
•  Problemas	
  mistos:	
  algumas	
  variáveis	
  de	
  
decisão	
  são	
  inteiras	
  
•  Problemas	
  boleanos:	
  variáveis	
  somente	
  
podem	
  assumir	
  os	
  valores	
  inteiros	
  no	
  
intervalo	
  [0,	
  1]	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   2	
  
Programação	
  inteira	
  
•  A	
  todo	
  o	
  problema	
  de	
  PI	
  existe	
  um	
  problema	
  
de	
  PL	
  correspondente	
  no	
  qual	
  as	
  restrições	
  de	
  
não-­‐fracionariedade	
  são	
  removidas	
  (ou	
  
relaxadas)	
  
•  Alguns	
  resultados	
  seguem:	
  
– Espaço	
  de	
  soluções	
  viáveis	
  do	
  PI	
  estão	
  conTdas	
  no	
  
espaço	
  de	
  soluções	
  viáveis	
  do	
  PI	
  relaxado	
  
– Valor	
  óTmo	
  de	
  z	
  do	
  PI	
  é	
  no	
  máximo	
  tão	
  bom	
  
quanto	
  o	
  valor	
  óTmo	
  do	
  PI	
  relaxado	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   3	
  
Abordagem	
  para	
  solução	
  de	
  PI	
  
•  Resolver	
  seus	
  problemas	
  correspondentes	
  PL	
  
“relaxados”	
  arredondando	
  as	
  variáveis	
  de	
  
decisão	
  para	
  o	
  maior	
  ou	
  menor	
  inteiro	
  mais	
  
próximo	
  
•  Dois	
  possíveis	
  efeitos	
  do	
  arredondamento:	
  
– Valores	
  arredondados	
  inviáveis	
  no	
  PI	
  
– Soluções	
  resultantes	
  altamente	
  sub	
  óTmas	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   4	
  
Método	
  Branch-­‐and-­‐Bound	
  para	
  
solução	
  de	
  problemas	
  PI	
  puros	
  
max	
  z	
  =	
  	
  8X1	
  	
  +	
  	
  5X2	
  
s.a	
  
(1) 	
  	
  X1	
  	
  +	
  	
  X2	
  	
  ≤	
  	
  6	
  
(2) 	
  	
  9X1	
  	
  +	
  	
  5X2	
  	
  ≤	
  	
  45	
  
(3) 	
  	
  X1,	
  	
  X2	
  	
  ≥	
  	
  0	
  
(4) 	
  	
  X1,	
  	
  X2	
  	
  inteiros	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   5	
  
Branch-­‐and-­‐Bound	
  é	
  operacionalizado	
  
em	
  5	
  passos	
  
•  Passo	
  1:	
  Comece	
  resolvendo	
  o	
  PI	
  relaxado	
  
– Se	
  a	
  solução	
  óTma	
  for	
  inteira,	
  esta	
  é	
  a	
  solução	
  
– Caso	
  contrário,	
  esta	
  solução	
  será	
  o	
  limite	
  superior	
  
da	
  solução	
  óTma	
  inteira	
  
•  A	
  solução	
  óTma	
  do	
  PIR	
  dado	
  anteriormente	
  é:	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   6	
  
X1	
  =	
  15/4	
  
X2	
  =	
  9/4	
  
Z1*	
  =	
  165/4	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   7	
  
X1	
  
X2	
  
max	
  z	
  =	
  	
  8X1	
  	
  +	
  	
  5X2	
  
s.a	
  
(1)  X1	
  	
  +	
  	
  X2	
  	
  ≤	
  	
  6	
  
(2)  9X1	
  	
  +	
  	
  5X2	
  	
  ≤	
  	
  45	
  
(3)  X1,	
  	
  X2	
  	
  ≥	
  	
  0	
  
(4)  X1,	
  	
  X2	
  	
  inteiros	
  
5	
  
5	
   10	
  
(1)	
  
(2)	
  
z	
  
SP1	
  
Pto	
  óTmo	
  
Passo	
  1:	
  resolver	
  PI	
  relaxado	
  
X1	
  =	
  15/4	
  
X2	
  =	
  9/4	
  
Z1*	
  =	
  165/4	
  
Passo	
  2	
  -­‐	
  Desdobramento	
  
•  Escolha	
  uma	
  variável	
  de	
  decisão	
  fracionária	
  
em	
  z*	
  do	
  PIR:	
  
– Por	
  exemplo,	
  X1	
  =	
  15/4	
  
•  PI	
  admite	
  valores	
  de	
  X1	
  ≤	
  3	
  ou	
  X1	
  ≥	
  4,	
  mas	
  não	
  
em	
  3	
  <	
  X1	
  <	
  4	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   8	
  
Crie	
  dois	
  subproblemas	
  a	
  parTr	
  de	
  X1	
  
•  SP2:	
  SP1	
  +	
  restrição	
  X1	
  ≥	
  4	
  
•  SP3:	
  SP1	
  +	
  restrição	
  X1	
  ≤	
  3	
  
•  SP	
  =	
  subproblema	
  
•  O	
  problema	
  designado	
  por	
  SP1	
  é	
  o	
  próprio	
  
problema	
  de	
  PI	
  em	
  estudo,	
  relaxado	
  das	
  
restrições	
  de	
  não-­‐fracionariedade	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   9	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   10	
  
X1	
  
X2	
  
5	
  
5	
   10	
  
(1)	
  
(2)	
  
z	
  
SP2	
  =	
  SP1	
  +	
  X1	
  ≥	
  4	
  
Passo	
  3	
  –	
  Dividir	
  o	
  espaço	
  de	
  soluções	
  
SP3	
  =	
  SP1	
  +	
  X1	
  ≤	
  3	
  
max	
  z	
  =	
  	
  8X1	
  	
  +	
  	
  5X2	
  
s.a	
  
(1)  X1	
  	
  +	
  	
  X2	
  	
  ≤	
  	
  6	
  
(2)  9X1	
  	
  +	
  	
  5X2	
  	
  ≤	
  	
  45	
  
(3)  X1,	
  	
  X2	
  	
  ≥	
  	
  0	
  
(4)  X1,	
  	
  X2	
  	
  inteiros	
  
X1	
  ≥	
  4	
  
X1	
  ≤	
  3	
  
Passo	
  3	
  
•  Escolha	
  qualquer	
  SP	
  listado	
  no	
  passo	
  anterior	
  
e	
  resolva	
  como	
  se	
  fosse	
  um	
  problema	
  de	
  PL:	
  
– Por	
  ex.,	
  SP2,	
  solução	
  óTma	
  z*=41,	
  X1=4	
  e	
  X2=9/5	
  
•  Resultados	
  obTdos	
  até	
  agora	
  podem	
  ser	
  
apresentados	
  na	
  forma	
  de	
  uma	
  árvore	
  
hierárquica	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   11	
  
Árvore	
  hierárquica	
  de	
  solução	
  do	
  
problema	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   12	
  
SP1	
  
X1	
  =	
  3,75	
  
X2	
  =	
  2,25	
  
Z1*	
  =	
  41,25	
  
	
  
SP2	
  
X1	
  =	
  4	
  
X2	
  =	
  9/5	
  
Z2*	
  =	
  41	
  
	
  
SP3	
  
X1	
  =	
  ?	
  
X2	
  =	
  ?	
  
Z3*	
  =	
  ?	
  
	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   13	
  
X1	
  
X2	
  
5	
  
5	
   10	
  
(1)	
  
(2)	
  
z	
  
Pto	
  óTmo	
  SP2	
  
Pto	
  óTmo	
  SP3	
  
X1	
  =	
  4	
  
X2	
  =	
  9/5	
  
Z2*	
  =	
  41	
  
X1	
  =	
  ?	
  
X2	
  =	
  ?	
  
Z3*	
  =	
  ?	
  
max	
  z	
  =	
  	
  8X1	
  	
  +	
  	
  5X2	
  
s.a	
  
(1)  X1	
  	
  +	
  	
  X2	
  	
  ≤	
  	
  6	
  
(2)  9X1	
  	
  +	
  	
  5X2	
  	
  ≤	
  	
  45	
  
(3)  X1,	
  	
  X2	
  	
  ≥	
  	
  0	
  
(4)  X1,	
  	
  X2	
  	
  inteiros	
  
Passo	
  4	
  –	
  Resolver	
  novo	
  PL	
  
Passo	
  4	
  
•  Repita	
  o	
  procedimento	
  no	
  Passo	
  3	
  usando	
  o	
  
SP2	
  com	
  a	
  variável	
  de	
  decisão	
  fracionária	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  
X2	
  =	
  9/5	
  
•  Subproblemas	
  resultantes:	
  
– SP4:	
  SP2	
  +	
  restrição	
  X2	
  ≥	
  2	
  
– SP5:	
  SP2	
  +	
  restrição	
  X2	
  ≤	
  1	
  
•  Tem-­‐se	
  dois	
  problemas	
  que	
  podem	
  ser	
  
resolvidos:	
  SP4	
  e	
  SP5	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   14	
  
Escolha	
  um	
  SP	
  para	
  resolução	
  
Por	
  exemplo:	
  SP4	
  
•  SP4	
  não	
  apresenta	
  soluções	
  viáveis,	
  não	
  
podendo,	
  assim,	
  gerar	
  uma	
  soluçãoóTma	
  
para	
  o	
  problema	
  de	
  PI:	
  
– Assim,	
  diz-­‐se	
  que	
  este	
  nodo	
  da	
  árvore	
  foi	
  
terminado	
  
•  Dentre	
  os	
  SPs	
  não	
  resolvidos,	
  escolhe-­‐se	
  o	
  
mais	
  recente,	
  SP5:	
  
– Solução	
  vem	
  apresentada	
  na	
  árvore	
  do	
  problema	
  
a	
  seguir	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   15	
  
Árvore	
  hierárquica	
  de	
  solução	
  do	
  
problema	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   16	
  
SP1	
  
X1	
  =	
  3,75	
  
X2	
  =	
  2,25	
  
Z1*	
  =	
  41,25	
  
	
  
SP2	
  
X1	
  =	
  4	
  
X2	
  =	
  9/5	
  
Z2*	
  =	
  41	
  
	
  
SP3	
  
X1	
  =	
  ?	
  
X2	
  =	
  ?	
  
Z3*	
  =	
  ?	
  
	
  
SP5	
  
X1	
  =	
  40/9	
  
X2	
  =	
  1	
  
Z5*	
  =	
  40,555	
  
	
  
SP4	
  
Inviável!	
  
Passo	
  3	
  -­‐	
  Novamente	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   17	
  
X1	
  
X2	
  
5	
  
5	
   10	
  
(1)	
  
(2)	
  
z	
  
Pto	
  óTmo	
  SP5	
  
SP4	
  
X1	
  =	
  40/9	
  
X2	
  =	
  1	
  
Z4*	
  =	
  40,555	
  
Não	
  apresenta	
  
soluções	
  viáveis	
  
(nodo	
  terminado)	
  
max	
  z	
  =	
  	
  8X1	
  	
  +	
  	
  5X2	
  
s.a	
  
(1)  X1	
  	
  +	
  	
  X2	
  	
  ≤	
  	
  6	
  
(2)  9X1	
  	
  +	
  	
  5X2	
  	
  ≤	
  	
  45	
  
(3)  X1,	
  	
  X2	
  	
  ≥	
  	
  0	
  
(4)  X1,	
  	
  X2	
  	
  inteiros	
  
Repita	
  procedimento	
  em	
  (3)	
  usando	
  
SP5	
  e	
  variável	
  fracionária	
  X1	
  
•  Subproblemas	
  restantes	
  são:	
  
–  SP6:	
  SP5	
  +	
  X1	
  ≥	
  5	
  
–  SP7:	
  SP5	
  +	
  X1	
  ≤	
  4	
  
•  Três	
  SPs	
  podem	
  ser	
  resolvidos:	
  SP3,	
  SP6	
  e	
  SP7	
  
•  Escolhe-­‐se	
  aleatoriamente,	
  um	
  dos	
  mais	
  
recentes:	
  
–  SP7,	
  por	
  exemplo	
  
•  Solução	
  óTma	
  para	
  SP7	
  vem	
  dada	
  na	
  árvore	
  a	
  
seguir	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   18	
  
Passo	
  3	
  -­‐	
  Novamente	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   19	
  
X1	
  
X2	
  
5	
  
5	
   10	
  
(1)	
  
(2)	
  
z	
  
Pto	
  óTmo	
  SP6	
  
Pto	
  óTmo	
  SP7	
  
X1	
  =	
  ?	
  
X2	
  =	
  ?	
  
Z6*	
  =	
  ?	
  
max	
  z	
  =	
  	
  8X1	
  	
  +	
  	
  5X2	
  
s.a	
  
(1)  X1	
  	
  +	
  	
  X2	
  	
  ≤	
  	
  6	
  
(2)  9X1	
  	
  +	
  	
  5X2	
  	
  ≤	
  	
  45	
  
(3)  X1,	
  	
  X2	
  	
  ≥	
  	
  0	
  
(4)  X1,	
  	
  X2	
  	
  inteiros	
  
X1	
  =	
  4	
  	
  inteiro	
  
X2	
  =	
  1	
  	
  	
  inteiro	
  
Z7*	
  =	
  37	
  
1ª	
  Solução	
  
candidata!	
  
SP7	
  gera	
  a	
  primeira	
  solução	
  candidata	
  
para	
  PI	
  
•  A	
  solução	
  só	
  possui	
  valores	
  inteiros	
  para	
  a	
  
variável	
  de	
  decisão	
  
– Pode	
  ser	
  interpretada	
  como	
  solução	
  candidata	
  
ou	
  um	
  limite	
  inferior	
  no	
  valor	
  óTmo	
  do	
  
problema	
  de	
  PI	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   20	
  
Problemas	
  SP3	
  e	
  SP6	
  ainda	
  não	
  foram	
  
resolvidos	
  
•  Escolhe-­‐se	
  SP6	
  (+recente),	
  com	
  solução	
  dada	
  
na	
  árvore	
  a	
  seguir:	
  
– Solução	
  de	
  SP6	
  é	
  inteira	
  e	
  melhor	
  do	
  que	
  aquela	
  
obTda	
  para	
  SP7	
  
– Assim	
  termina-­‐se	
  nodo	
  da	
  árvore	
  em	
  SP7	
  
(idenTfica-­‐se	
  o	
  nodo	
  terminado	
  por	
  um	
  x	
  ou	
  
escrevendo	
  solução	
  excluída)	
  e	
  atualiza-­‐se	
  o	
  limite	
  
inferior	
  da	
  árvore;	
  novo	
  LI	
  =	
  40)	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   21	
  
Passo	
  3	
  -­‐	
  Novamente	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   22	
  
X1	
  
X2	
  
5	
  
5	
   10	
  
(1)	
  
(2)	
  
z	
  
Pto	
  óTmo	
  SP6	
  
Pto	
  óTmo	
  SP7	
  
X1	
  =	
  5	
  
X2	
  =	
  0	
  
Z6*	
  =	
  40	
  
max	
  z	
  =	
  	
  8X1	
  	
  +	
  	
  5X2	
  
s.a	
  
(1)  X1	
  	
  +	
  	
  X2	
  	
  ≤	
  	
  6	
  
(2)  9X1	
  	
  +	
  	
  5X2	
  	
  ≤	
  	
  45	
  
(3)  X1,	
  	
  X2	
  	
  ≥	
  	
  0	
  
(4)  X1,	
  	
  X2	
  	
  inteiros	
  
X1	
  =	
  4	
  
X2	
  =	
  1	
  
Z7*	
  =	
  37	
  
ÚlTmo	
  SP	
  a	
  ser	
  resolvido	
  é	
  SP3	
  
•  Solução	
  de	
  SP3	
  é	
  z*=	
  39,	
  onde	
  X1=X2=3:	
  
– Trata-­‐se	
  de	
  uma	
  solução	
  candidata	
  com	
  z*<	
  LI	
  
•  Assim,	
  o	
  nodo	
  SP3	
  é	
  terminado	
  e	
  SP6	
  é	
  
idenTficado	
  como	
  a	
  solução	
  óTma	
  para	
  o	
  
problema	
  de	
  PI	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   23	
  
Árvore	
  hierárquica	
  de	
  solução	
  do	
  
problema	
  (final)	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   24	
  
SP1	
  
X1	
  =	
  3,75	
  
X2	
  =	
  2,25	
  
Z1*	
  =	
  41,25	
  
	
  
SP2	
  
X1	
  =	
  4	
  
X2	
  =	
  9/5	
  
Z2*	
  =	
  41	
  
	
  
SP3	
  
X1	
  =	
  3	
  
X2	
  =	
  3	
  
Z3*	
  =	
  39	
  
	
  
SP5	
  
X1	
  =	
  40/9	
  
X2	
  =	
  1	
  
Z5*	
  =	
  40,555	
  
	
  
SP4	
  
Inviável!	
  
SP7	
  
X1	
  =	
  4	
  
X2	
  =	
  1	
  
Z7*	
  =	
  37	
  
	
  
SP6	
  
X1	
  =	
  5	
  
X2	
  =	
  0	
  
Z6*	
  =	
  40	
  	
  
	
  
Z3*	
  >	
  LI	
  =	
  Z5*	
  
(solução	
  excluída)	
  
Z7*	
  >	
  LI	
  =	
  Z5*	
  Solução	
  óTma	
  do	
  PLI	
  
X	
  
X	
  
X	
  
Aspectos	
  importantes	
  do	
  Branch-­‐and-­‐
bound	
  para	
  PIs	
  puros	
  
•  Sempre	
  que	
  não	
  for	
  necessário	
  desdobrar	
  um	
  
subproblema,	
  ele	
  deve	
  ser	
  terminado	
  
•  Critérios	
  uTlizados	
  para	
  terminação	
  são:	
  
– SP	
  não	
  possui	
  soluções	
  viáveis	
  
– SP	
  gera	
  uma	
  solução	
  óTma	
  contendo	
  somente	
  
valores	
  inteiros	
  
– SP	
  apresenta	
  um	
  valor	
  de	
  z*	
  menor	
  (em	
  
problemas	
  de	
  PI	
  do	
  Tpo	
  Maximização)	
  que	
  o	
  
limite	
  inferior	
  atual	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   25	
  
Mais	
  aspectos	
  
•  A	
  regra	
  “úlTmo	
  a	
  entrar,	
  primeiro	
  a	
  sair”,	
  que	
  
indica	
  qual	
  SP	
  deve	
  ser	
  trabalhado	
  dentre	
  
vários	
  candidatos	
  força	
  o	
  analista	
  a	
  trabalhar	
  
um	
  mesmo	
  ramo	
  da	
  árvore	
  até	
  o	
  final:	
  
– Existem	
  outras	
  regras	
  possíveis	
  
•  Quando	
  um	
  SP	
  apresenta	
  solução	
  óTma	
  com	
  
duas	
  ou	
  mais	
  variáveis	
  de	
  decisão	
  fracionárias,	
  
trabalhe	
  com	
  aquela	
  representar	
  maior	
  ganho	
  
na	
  função	
  obje3vo	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini26	
  
Método	
  Branch-­‐and-­‐bound	
  para	
  
solução	
  de	
  PIs	
  mistos	
  
•  Modifique	
  o	
  algoritmo	
  anterior	
  da	
  seguinte	
  
maneira:	
  
– Desdobre	
  somente	
  variáveis	
  de	
  decisão	
  restritas	
  à	
  
não-­‐fracionariedade	
  
– Considere	
  a	
  solução	
  óTma	
  de	
  um	
  SP	
  como	
  sendo	
  
candidata	
  à	
  solução	
  óTma	
  do	
  problema	
  de	
  PI	
  
quando	
  esta	
  atender	
  às	
  restrições	
  de	
  não-­‐
fracionariedade	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   27	
  
Exercício	
  1	
  –	
  PI	
  misto	
  
•  Min	
  z	
  =	
  4X1	
  +	
  5X2	
  
	
  	
  	
  	
  s.a:	
  
	
   	
   	
  X1	
  	
  +	
  	
  4X2	
  ≥	
  	
  5	
  
	
   	
   	
  3X1	
  	
  +	
  	
  2X2	
  ≥	
  	
  7	
  
	
   	
   	
  X1,	
  	
  X2	
  	
  ≥	
  	
  0	
  
	
   	
   	
  X1	
  inteiro	
  
	
  
	
  
	
  
	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   28	
  
Exercício	
  2	
  –	
  PI	
  misto	
  
•  Max	
  z	
  =	
  2X1	
  +	
  X2	
  
	
  	
  	
  	
  s.a:	
  
	
   	
   	
  5X1	
  	
  +	
  	
  2X2	
  	
  ≤	
  	
  8	
  
	
   	
   	
  X1	
  	
  +	
  	
  X2	
  	
  ≤	
  	
  3	
  
	
   	
   	
  X1,	
  	
  X2	
  	
  ≥	
  	
  0	
  
	
   	
   	
  X1	
  inteiro	
  
	
  
	
  
	
  
	
  
Dep	
  Engenharia	
  de	
  Produção	
  -­‐	
  UFRGS	
  -­‐	
  
Daniel	
  Zini	
   29