Pesquisa  Operacional  

Modelagem  de  problemas  

Princípios  

•  Impossibilidade  de  lidar  com  a  complexidade  do  mundo  à  criação  de  metáforas  para  a  representação  e  solução  de  sua  relação  com  esse  mesmo  mundo.  

•  Modelo:  simulação  da  realidade.  •  Modelo  é  um  veículo  para  uma  visão  bem  estruturada  da  realidade.  

•  Representação  subsBtuBva  da  realidade.  Que  Bpo  de  modelos  nós  já  lidamos  no  coBdiano?  

Modelo  

•  Deve  ser  livre  de  detalhes  onerosos.  •  Representar  simplificadamente  a  realidade  preservando  uma  equivalência  adequada.  

•  Processo  de  verificação  da  representaBvidade    (validação  do  modelo)  é  indispensável  em  qualquer  procedimento  cienMfico.  

Eficiência  do  Modelo  

•  Habilidades  necessária  para  criar  modelos  eficientes:  – Foco  HolísBco  – Tratamento  EcléBco  da  Dimensão  da  Análise  – Tradução  Adequada.   HolísBco:  o  todo  não  é  

dado  apenas  pela  soma  de  suas  partes.    “O  inteiro  é  mais  que  a  simples  soma  de  

suas  partes.”  (Aristóteles)  

Métodos  devem  ser  mais  livremente  dispostos  para  

atuarem  nas  mais  diferentes  áreas  

Complexidade  

•  Modelo  simples:  – Pouco  influenciado  pelas  variações  do  ambiente  – Estável,  homogêneo  e  possui  poucas  variáveis  – Comportamento  previsível  

Conceito  de  Sistemas  

•  Unidade  conceitual  ou  [sica  composta  de  partes  inter-­‐relacionadas,  interatuantes  e  interdependentes.  

•  Propriedades  –  Simbiose  interna  –  Simbiose  externa  –  Sinergia  – Homeostase  –  Entropia  NegaBva  –  Recursividade  

ComparBlhar  funções  tornando  cada  parte  

indispensável  dentro  do  sistema  

Componente  parBcipante  e  

indispensável  ao  ambiente.  

Alcançar  patamares  de  desempenho  superior  ao  obBdo  pela  soma  do  desempenho  das  partes  

Conservar  estado  de  equilíbrio.  Ex:  

Homeostase  no  corpo  humano.    

Regulação  térmica  (músculos  tremem  para  

produzir  calor)  

Importar  energia  do  ambiente  para  compensar  a  

degradação.  Realizar  auto-­‐ajuste  

Parte  do  sistema  pode  ser  consideradas  

subsistemas  gozando  das  mesmas  propriedades  

Tipos  de  Problemas  

•  Decidíveis:  Apresentam  solução  algoritmica.  – Problemas  de  Decisão:  Existe  uma  solução  S...  – Problemas  de  Localização:  Encontre  uma  solução  S...  

– Problemas  de  OBmização:  Encontrar  a  melhor  solução  S...  

•  Não  Decidíveis:  Não  apresenta  solução  algoritmica.  

Classificação  quanto  a  natureza  do  modelo  

•  Concretos:    – Físicos  – Geométricos  

•  Abstratos  – MatemáBcos  – Lógicos  

Classificação  quanto  às  propriedades  dos  modelos  

•  Icônicos  

•  Analógicos  

•  Simbólicos  

Propriedades  relevantes  dos  objetos  reais  são  apresentadas.    

Ex:  fotografia,  mapa  

Conjunto  de  propriedades  do  modelo  representam  as  propriedades  reais.  

Ex:  Grafos  

Letras,  números  e  outros  símbolos  representam  variáveis  

e  suas  relações.  Ex:  equações,  fluxogramas  

Classificação  quanto  às  variáveis  controladas  

•  DescriBvos:  expressos  em  linguagem  corrente    •  Físicos:  miniaturas,  túneis  de  vento    •  Simbólicos:  desenhos    •  Procedimentais:  simulação  

Processo  de  Modelagem  

Modelagem  MatemáBca  

•  Pesquisa  Operacional:  apresenta  técnicas  de  modelagem  matemáBca.  

•  Modelos  de  Pesquisa  Operacional:  estruturados  de  forma  lógica  e  amparados  no  ferramental  matemáBco  de  representação.  

•  Programação  =  Planejamento  •  Processo  de  modelagem  pouco  varia,  mas  as  técnicas  de  solução  podem  ser  agrupadas  em:  Programação  Linear,  Programação  Não-­‐Linear  e  Programação  Inteira  

Técnicas  de  Solução  

•  Programação  Linear:  variáveis  conMnuas,  comportamento  linear.  

•  Programação  Não-­‐Linear  •  Programação  Inteira:  variáveis  não  são  conMnuas.  

Estrutura  de  Modelos  MatemáBcos  

1.  Variáveis  de  Decisão:  determinadas  pela  solução  do  modelo.  

2.  Parâmetros:  valores  fixos  no  problema.  3.  Restrições:  limitações  [sicas  do  sistema.  

Limitam  as  variáveis  de  decisão.  4.  Função  ObjeBvo:  Função  matemáBca  que  

define  a  qualidade  da  solução.  

Exemplo  Uma  empresa  de  ração  canina  produz:  –  Ração  A  e  Ração  B  As  rações  são  compostas  por  cereais  e  carne.  q A  ração  A  uBliza  5kg  de  cereais  e  1kg  de  carne.  q A  ração  B  uBliza  2kg  de  cereais  e  4kg  de  carne.  q O  pacote  da  ração  A  custa  R$20,00  e  o  pacote  da  ração  B  custa  R$30,00.  

q O  quilo  de  carne  custa  R$4,00  e  o  quilo  de  cereais  custa  R$1,00.  q Estão  disponíveis  por  mês  10.000kg  de  carne  e  30.000kg  de  cereais.  

v Qual  a  quanBdade  de  cada  ração  deve  ser  produzida  para  maximizar  o  lucro?  

Exercícios  

Para  os  problemas  a  seguir,  encontre:    1.  Variáveis  de  Decisão  2.  Parâmetros  3.  Restrições  4.  Função  ObjeBvo    

10/05/16   UFVJM          DECOM        Luciana  Assis    www.dcc.ufmg.br/~lpassis   16  

Problema  da  dieta  •  Um  nutricionista  precisa  estabelecer  uma  dieta  contendo,  pelo  

menos,  10  unidades  de  vitamina  A,  30  unidades  de  vitamina  B  e  18  unidades  de  vitamina  C.    Essas  vitaminas  estão  conBdas  em  quanBdades  variadas  em  cinco  alimentos  que  vamos  chamar  de  s1,  s2,  s3,  s4  e  s5.  O  quadro  seguinte  dá  o  número  de  unidades  das  vitaminas  A,  B  e  C  em  cada  unidade  desses  cinco  alimentos  bem  como  o  custo,  em  reais,  por  unidade.  Calcular  as  quanBdades  dos  5  alimentos  que  devem  ser  incluídas  na  dieta  diária,  a  fim  de  encontrarmos  esses  teores  de  vitaminas  com  o  menor  custo.  

10/05/16   UFVJM          DECOM        Luciana  Assis    www.dcc.ufmg.br/~lpassis   17  

Alimentos    >  Vitaminas    v  

s1   S2   S3   S4   s5  

A   0   1   5   4   3  B   2   1   0   3   2  C   3   1   0   9   0  

CUSTO   4   2   1   10   5  

Problema  das  Ligas  Metálicas  •  Uma  metalúrgica  deseja  maximizar  sua  receita  bruta.  A  tabela  ilustra  a  proporção  de  cada  material  na  mistura  para  obtenção  das  ligas  passíveis  de  fabricação.  O  preço  está  cotado  em  Reais  por  tonelada  da  liga  fabricada.  Também  em  toneladas  estão  expressas  as  retrições  de  disponibilidade  de  matéria-­‐prima.  

10/05/16   UFVJM          DECOM        Luciana  Assis    www.dcc.ufmg.br/~lpassis   18  

Liga  Baixa  Resistência  

Liga  Alta  Resistência  

Disponibilidade  

Cobre   0,5   0,2   16  Zinco   0,25   0,3   11  

Chumbo   0,25   0,5   15  Preço   3000   5000  

Problema  do  SíBo  •  Um  siBante  está  planejando  sua  estratégia  de  planBo  para  o  próximo  ano.  Por  informações  obBdas  nos  órgãos  governamentais,  sabe  que  as  culturas  de  trigo,  arroz  e  milho  serão  as  mais  rentáveis  na  próxima  safra.  Por  experiência,  sabe  que  a  produBvidade  de  sua  terra  para  as  culturas  é  dada  na  tabela  abaixo.  Por  falta  de  um  local  de  armazenamento  próprio,  a  produção  máxima,  em  toneladas,  está  limitada  a  60.  A  área  culBvável  do  síBo  é  de  200.000m2.  Para  atender  às  demandas  de  seu  próprio  síBo,  é  imperaBvo  que  se  plante  400m2  de  trigo,  800m2  de  arroz  e  10.000m2  de  milho.  

10/05/16   UFVJM          DECOM        Luciana  Assis    www.dcc.ufmg.br/~lpassis   19  

ProduCvidade  (kg  por  m2)   Lucro  (kg  de  produção)  

Trigo   0,2   10,8  Arroz   0,3   4,2  Milho   0,4   2,03  

EXERCÍCIOS  

•  Um  jovem  estava  saindo  com  duas  namoradas:  Maria  e  Luísa.  Sabe,  por  experiência,  que:      – Maria,  elegante,  gosta  de  frequentar  lugares  sofisBcados,  mais  caros,  de  modo  que  uma  saída  de  três  horas  custará  R$240,00.    

–   Luísa,  mais  simples,  prefere  um  diverBmento  mais  popular,  de  modo  que  uma  saída  de  três  horas  custará  R$160,00.    

–  Seu  orçamento  permite  dispor  de  R$960,00  mensais  para  diversão.    Seus  afazeres  escolares  lhe  dão  liberdade  de,  no  máximo,  18  horas  e  40.000  calorias  de  sua  energia  para  aBvidades  sociais.      

–  Cada  saída  com  Maria  consome  5.000  calorias,  mas  com  Luísa,  mais  alegre  e  extroverBda,  gasta  o  dobro.      

–  Ele  gosta  das  duas  com  a  mesma  intensidade.        •  Como  ele  deve  planejar  sua  vida  social  para  obter  o  número  máximo  de  saídas?  

•  Um   fazendeiro   tem   200   unidades   de   área   de   terra   ,  onde  planeja   culBvar   trigo,   arroz   e  milho.  A  produção  esperada  é  de  1800  kg  por  unidade  de  área  plantada  de  trigo,  2100  kg  por  unidade  de  área  plantada  de  arroz  e  2900   kg  por   unidade  de   área  plantada  de  milho.   Para  atender  ao  consumo  interno  de  sua  fazenda,  ele  deverá  plantar   pelo  menos   12   unidades   de   área   de   trigo,   16  unidades   de   área   de   arroz   e   20   unidades   de   área   de  milho.  Ele  tem  condições  de  armazenar  no  máximo  700  000  kg.  Sabendo  que  o  trigo  dá  um  lucro  de  $  1,20  por  kg,  o  arroz  $  0,6  por  kg  e  o  milho  $  0,28  por  kg,  quantas  unidades   de   área   de   cada   produto   ele   deve   plantar  para  que  o  seu  lucro  seja  o  maior  possível?