Enunciado_2011-1

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Página 1 de 2 
Projeto	
  –	
  Programação	
  Linear	
  –	
  2011.1	
  Dpto.	
  Engenharia	
  Elétrica,	
  PUC-­‐Rio.	
  Professor:	
  Alexandre	
  Street	
  (street@ele.puc-­‐rio.br)	
  As	
  notas	
  serão	
  divulgadas	
  no	
  grupo	
  (Internet):	
  http://groups.yahoo.com/group/po_puc-­‐rio	
  	
  Data	
  de	
  apresentação:	
  dia	
  16	
  de	
  junho	
  de	
  2011	
  para	
  a	
  graduação	
  e	
  17	
  de	
  junho	
  para	
  a	
  pós-­‐graduação.	
  
 
TAREFA	
   –	
   1	
   (7	
   pts)	
   Implementar	
   o	
   método	
   simplex	
   revisado	
   para	
   resolver	
   um	
   problema	
   de	
  programação	
  linear	
  (PL)	
  genérico,	
  expresso	
  na	
  seguinte	
  forma:	
  
	
   !"#$%$&"'  !!!	
   (1)	
  Sujeito	
  a:	
   	
  !" ≤ !	
   (2)	
  ! ≥ !.	
   (3)	
  
O	
  seu	
  algoritmo	
  deve	
  retornar	
  os	
  seguintes	
  objetos:	
  1. O	
  valor	
  ótimo	
  da	
  função	
  objetivo.	
  2. O	
  estado	
  do	
  algoritmo:	
  -­‐2	
  se	
  o	
  número	
  máximo	
  de	
  iterações	
  foi	
  alcançado,	
  -­‐1	
  se	
  o	
  problema	
  for	
  inviável,	
  0	
  se	
  ilimitado	
  e	
  1	
  se	
  existe	
  ponto	
  ótimo.	
  3. O	
  ponto	
  ótimo	
  (!∗)	
  que	
  resolve	
  o	
  problema,	
  caso	
  exista.	
  a. Caso	
   o	
   estado	
   seja	
  menor	
   que	
   0,	
   o	
   valor	
   de	
  !∗	
   deve	
   representar	
   a	
   ultima	
   solução	
  	
  obtida	
   e	
   caso	
   seja	
   igual	
   a	
   0,	
   deve	
   retornar	
   a	
   direção	
   extrema	
   encontrada	
   (!∗ =!!|!! !).	
  4. O	
  vetor	
  de	
  variáveis	
  de	
  folga	
  das	
  restrições	
  (2).	
  5. O	
  vetor	
  de	
  variáveis	
  duais	
  associadas	
  às	
  restrições	
  (2).	
  6. O	
  vetor	
  de	
  custos	
  reduzidos	
  de	
  todas	
  as	
  variáveis.	
  7. Os	
  vetores	
  de	
  índices	
  relativos	
  às	
  variáveis	
  básicas	
  e	
  não	
  básicas	
  finais.	
  	
  Resolver	
  as	
  seguintes	
  instâncias	
  de	
  teste:	
  a) Problema	
  da	
  página	
  39	
  do	
  livro	
  texto	
  (Chvátal),	
  utilizado	
  para	
  exemplificar	
  a	
  necessidade	
  da	
  fase	
   1.	
   O	
   seu	
   algoritmo	
   deve	
   identificar	
   a	
   necessidade	
   da	
   fase	
   1	
   e	
   emprega-­‐la	
   de	
  maneira	
  automatizada,	
  entregar	
  para	
  a	
  fase	
  2	
  a	
  primeira	
  base	
  viável	
  e	
  resolver	
  o	
  problema.	
  	
  b) Um	
  problema	
  que	
  seja	
  ilimitado	
  de	
  sua	
  escolha.	
  	
  Nos	
  dois	
  casos	
  de	
   teste	
   (a)	
  e	
   (b)	
  acima,	
   imprima	
  ou	
  escreva	
  em	
  um	
  arquivo	
  o	
  conjunto	
  de	
  variáveis	
  básicas	
  de	
  cada	
  iteração	
  e	
  compare	
  com	
  os	
  passos	
  do	
  livro.	
  	
  
TAREFA	
   –	
   2	
   (3	
   pts)	
   Escolher	
   um	
   problema	
   relevante	
   e	
   resolvê-­‐lo	
   para	
   diferentes	
   tamanhos	
   de	
  instância	
  que	
  variem	
  de	
  pequenas	
  a	
  grandes.	
  Tente	
  identificar	
  o	
  limite	
  (em	
  tamanho	
  do	
  problema)	
  do	
  seu	
  algoritmo	
  e	
  o	
  fator	
  limitante.	
  Os	
  resultados	
  de	
  cada	
  instância	
  devem	
  ser	
  exibidos	
  em	
  uma	
  tabela	
  com	
  as	
  seguintes	
  informações:	
  coluna	
  1,	
  número	
  de	
  variáveis	
  (n),	
  coluna	
  2,	
  número	
  de	
  restrições	
  (m),	
  coluna	
  3,	
  valor	
  da	
  função	
  objetivo,	
  coluna	
  4,	
  número	
  de	
  iterações	
  (trocas	
  de	
  base),	
  coluna	
  5,	
  tempo	
  de	
  execução	
   do	
   seu	
   algoritmo,	
   e	
   por	
   fim,	
   coluna	
   6,	
   tempo	
   computacional	
   que	
   o	
   linprog	
   levou	
   para	
  resolver	
   a	
  mesma	
   instância.	
   Faça	
   um	
   gráfico	
   exibindo	
   as	
   colunas	
   de	
   tempo	
   (5	
   e	
   6)	
   para	
   todas	
   as	
  instâncias,	
   colocando	
   no	
   eixo	
   horizontal	
   o	
   tamanho	
   da	
   instância	
   (!")	
   e	
   no	
   vertical	
   os	
   valores	
   em	
  segundos.	
  Faça	
  um	
  segundo	
  gráfico	
  mostrando	
  o	
  número	
  de	
  iterações	
  ao	
  longo	
  das	
  instâncias.	
  
 
Página 2 de 2 
	
  
Apresentação	
   Graduação	
   e	
   Pós-­‐graduação:	
   As	
   duas	
   tarefas	
   devem	
   ser	
   apresentadas	
   em	
   slides	
  (formato	
   PDF)	
   em	
   não	
   mais	
   que	
   15	
   minutos.	
   O	
   trabalho	
   é	
   individual	
   e	
   o	
   código	
   de	
   todos	
   os	
  programas	
   deve	
   ser	
   enviado	
   por	
   e-­‐mail	
   até	
   a	
   data	
   da	
   apresentação.	
   Os	
   programas	
   devem	
   estar	
  preparados	
   para	
   serem	
   chamados	
   na	
   linha	
   de	
   comando	
   do	
  MATLAB	
   e	
   executarem	
   as	
   respectivas	
  tarefas	
   de	
   maneira	
   automática,	
   sem	
   a	
   necessidade	
   de	
   se	
   passar	
   parâmetros.	
   Para	
   isso,	
   criem	
  
procedures	
  que	
  executem	
  as	
  tarefas	
  automaticamente.	
  
Artigo	
   Pós-­‐graduação:	
  Os	
   alunos	
   de	
   pós-­‐graduação	
   deverão	
   entregar	
   além	
   da	
   apresentação,	
   um	
  texto	
  em	
  formato	
  de	
  artigo	
  científico	
  (formato	
  IEEE	
  –	
  disponível	
  no	
  site	
  –	
  MATERIAIS	
  EXTRA).	
  Neste,	
  o	
   problema	
   selecionado	
   deve	
   ser	
   motivado	
   e	
   contextualizado	
   dentro	
   da	
   literatura,	
   na	
   seção	
  introdução,	
   e	
   apresentada	
   a	
   sua	
   formulação	
   em	
   uma	
   seção	
   seguinte	
   denominada	
   Formulação	
  matemática.	
   O	
   pseudocódigo	
   do	
   algoritmo	
   programado	
   deve	
   ser	
   apresentado	
   em	
   uma	
   seção	
  subsequente.	
  Os	
  resultados	
  devem	
  seguir	
  em	
  uma	
  próxima	
  seção	
  nomeada	
  estudo	
  de	
  caso.	
  A	
  seção	
  conclusões	
  devem	
   resumir	
   as	
  principais	
   constatações	
  do	
   seu	
   trabalho:	
   dificuldades,	
   peculiaridades	
  do	
  seu	
  algoritmo	
  e/ou	
  problema,	
  etc.