tecnicas de PO

Prévia do material em texto

INTRODUÇÃO À 
PESQUISA OPERACIONAL
O problema das pontes de Kaliningrado 
Problema Geral
(formulado por Leonhard Euler em 1736)
Qualquer que seja a disposição e divisão do rio,
onde que quer as pontes estejam, alguém pode
descobrir se é ou não possível atravessar cada
ponte exatamente uma vez?".
Cada região: Nó
Cada ponte: Aresta
Representação através de grafo
Teorema da existência de solução para um percurso
abrangente em relação às arestas de um grafo não orientado,
utilizando cada aresta uma única vez.
O grafo deve ser conexo (uma região precisa ser acessada todas as
outras através de pontes) e cada nó deve ter grau par (o número de
pontes em cada região precisa ser par). Claramente, este não é o caso
das pontes de Königsberg.
Seja n é o número de vértices de grau ímpar
Se n=0, o grafo contém pelo menos um circuito euleriano.
Se n=2 , o grafo possui pelo menos um caminho euleriano , 
mas não um circuito euleriano.
Se n>2. não há nem caminho e nem circuito.
Caminho euleriano: visita todos os nós passando uma vez por todas
as arestas
Circuito euleriano: caminho euleriano em que se retorna ao mesmo 
ponto de partida. 
Caminho Euleriano: visita todos os nós passando uma vez por todas
as arestas
Circuito Euleriano : Caminho euleriano em que se retorna ao ponto de partida.
Caminho Hamiltoniano : passa por todos os vértices exatamente uma vez. 
Circuito Hamiltoniano : Caminho hamiltoniano em que se retorna ao ponto de partida.
Problema do cavalo - Euler - 1759 Circuito Hamiltoniano
O Problema do Carteiro Chinês
(Caminho mínimo em grafos não-orientados)
Em 1962, 226 anos após a descoberta de Euler em Königsberg, o
matemático chinês Kwan Mei-Ko levantou uma importante questão
acerca do problema da travessia das pontes: "Dado que é
impossível atravessar cada ponte exatamente uma vez e retornar
para o ponto de partida, qual é o número mínimo de travessias
redundantes que é preciso fazer?"
Eulerização do grafo
Uma solução é: a → b → c → b → e → f → g → d → d
O Problema do Varredor de Ruas
(Caminho mínimo em grafos orientados)
Muitos anos depois do problema proposto por Kwan, uma
variação do problema do carteiro chinês procurava pelo caminho
mínimo se as arestas só pudessem ser percorridas em uma
direção. Como este é o problema encontrado por varredores de
rua nas avenidas de mão única de Nova York, este problema
ficou conhecido como " O problema do varredor de ruas de Nova
York ”
Balanceamento do grafo: o numero de arcos que chegam em cada nó 
tem que ser igual ao número de arcos que saem.
Arco é uma aresta que pode ser percorrida em uma só direção
Arco que chega em um nó: +1
Arco que sai de um nó: -1
Solução: a → b → c → b → f → e → g→ d → e → g
Programação Linear
Problema de Otmização em que tanto a função
objetivo quanto as funções que representam as
restrições são lineares, ou seja, são funçòes do
primeiro grau
Programação Linear
Problema da mistura de minérios
Sem Programação por Metas
Com Programação de Metas
Programação Inteira
Todas as variáveis de decisão são inteiras
Programação Mista
As variáveis de decisão são inteiras e contínuas
Programação Não Linear
A função objetivo e ou ao menos uma das restrições não é linear.
ESTUDO DE CASO DE UM PROBLEMA PROGRAMAÇÃO DE 
HORÁRIOS: timetabling problem na Escola de Minas – UFOP
Autor :Eron Martins Xavier 
Monografia TCC Curso de Engenharia de Produção 
Exemplo de Problema de Programação Inteira
Parâmetros do Modelo
Função Objetivo
PROGRAMAÇÃO NÃO LINEAR
Dimensionamento ótimo de painéis, câmaras e pilares 
com programação
não-linear
R.P. de Figueiredo & A. Curi
Departamento de Engenharia de Minas, Escola de Minas, Universidade Federal de 
Ouro Preto, Ouro Preto,
MG, Brasil
I SIAEM (I Simpósio Ibero Americano de Engenharia de Minas)
Para uma espessura constante e igual a altura dos pilares tem-se?
Recuperação = 1 – Área dos Pilares / Área Total
Configuração (a)
Configuração (c)
Configuração (b)
Configuração (d)
Problema geral de maximização da Recuperação de minério na lavra
por câmaras, painéis e pilares
s.a.
HEURÍSTICA E METAHEURÍSTICA
As heurísticas ou algoritmos heurísticos foram desenvolvidos
com a finalidade de se resolver problemas de elevado nível de
complexidade em tempo computacional razoável.
As heurísticas procuram encontrar soluções próximas da
otimalidade em um tempo computacional razoável, sem, no entanto,
conseguir definir se esta é a solução ótima, nem quão próxima ela está
da solução ótima.
Metaheurísticas são procedimentos destinados a encontrar
uma boa solução, eventualmente a ótima, consistindo na aplicação,
em cada passo, de uma heurística subordinada, a qual tem que ser
modelada para cada problema específico. A principal característica das
metaheurísticas é a capacidade que estas possuem de escapar de
ótimos locais.
Texto extraído da monografia MODELAGENS EXATA E HEURÍSTICA PARA RESOLUÇÃO DO PROBLEMA DO
CAIXEIRO VIAJANTE COM COLETA DE PRÊMIOS de Antônio Augusto Chaves
TEORIA DAS FILAS
Em uma pedreira, caminhões chegam para descarregar em um
britador, provenientes de 2 minas diferentes. O tempo médio para
descarregar um caminhão é de 2 minutos. Os caminhões chegam
da mina 1 a intervalos médios de 3 minutos e da mina 2 a
intervalos médios de 12 minutos. Supondo que os processos de
chegada e atendimento sejam marcovianos (modelo M/M/1),
determinar qual espaço deverá ser disponibilizado na praça do
britador (quantos caminhões a praça deve comportar) para que
as operações sejam realizadas satisfatoriamente.
Programação Dinâmica
Aplicada a problemas que consistem de alguns estágios interligados
uns aos outros de uma forma que decisões tomadas em um estágio
influencia outros estágios.
Estes estágios podem ser uma sequência tecnológica ou uma sequência
de tempos, ou ambos.
Um exemplo de aplicação é o algoritmo de Lerchs e Grossmann usado 
na otimização de cava.
Redes PERT e COM ou PERT-CPM
São duas técnicas usadas para o planejamento, programação 
e controle de projetos.
PERT – Técnica de Avaliação e Revisão de Projetos
COM – Método do Caminho Crítico
Com essas técnicas pode-se responder perguntas como:
• Pode a data para a conclusão do projeto ser atingida? Se não existe
tal data, quando o projeto poderá ser concluído?
• Quais atividades ou trabalhos a serem feitos são críticos? Quais devem
ser finalizados na programação afim de não afetar o projeto todo?
• Qual a probabilidade de se seguir a programação?
Na rede CPM a duração da atividade é conhecida, determinada, enquanto
que na rede PERT ela é uma variável aleatória.
Sequenciamento de operações para se realizar uma tarefa:
• Projeto de manutenção de uma escavadeira elétrica;
• Construção de uma britagem subterrânea;
• Projeto de desenvolvimento de uma mina subterrânea
Construção de uma Britagem Subterrânea
** Exemplo extraído de: CRITICAL PATH PLANNING AND SCHEDULING APPLIED TO MINING OPERATIONS 
By Adrian J. Mathias and Donald E. Redmon
Desenvolvimento de uma mina 
subterrânea
Técnicas de análise de decisão
São um conjunto de técnicas para analise de problemas associados
a probabilidade ou incerteza e riscos.
Árvore de decisão é uma técnica de análise de risco.
Uma petrolífera oferece a um dono de terra $60 000,00 pelos direitos de exploração de 
gás natural e a opção por um futuro desenvolvimento que se ocorrer, acrescentará mais 
600 000,00 ao proprietário do terreno. Devido a esse interesse, o proprietário pensa em 
talvez ele mesmo desenvolver o campo. Para isso ele deverá contratar alguma empresa 
especializada em exploração e desenvolvimento. Para isso, ele terá que realizar um 
investimento inicial de 100.000,00. Se gás for descoberto, o proprietário estima um 
lucro líquido de 2 000 000,00.As decisões para o proprietário são D1 (aceitar a oferta da petrolífera) e D2 (ele mesmo 
fazer a exploração e desenvolvimento). Dois eventos podem ocorrer: S1 (não existir gás 
no terreno) e S2 (existir gás no terreno).
Os ganhos ou perdas do proprietário em milhares para a combinação entre eventos e 
decisões estão na tabela:
Para P(S1) = 0,4 e P(S2) =0,6 , os ganhos médios esperados são:
A um custo de 30 000,00 o proprietário tem acesso a informações de teste que foram
feitos na região onde o gás natural é suposto de estar presente. Os testes indicam
que o gás não está presente, mas o teste não é perfeito. A companhia que fez os
testes informa que em 30% das vezes em que o teste indica que o gás não está
presente, de fato ele está, e em 90 % das vezes o teste indica que não existe gás
quando realmente ele não está presente.
Seja 𝜃1 o evento em que o teste indica que não há gás.
Os ganhos esperados são:
Suponha que o resultado do teste indique a presença de gás.
Seja 𝜃2 o evento em que o teste indica que existe gás.
Suponha agora que o teste não tenha sido realizado e que a sua realização 
esteja apenas sendo considerada de ser feito.
O processo apresenta agora uma decisão em dois estágios:
O proprietário deve decidir se vai realizar testes e depois deve decidir se 
aceita a oferta da petrolífera. 
𝐷𝐼 decisão de realizar o teste
𝐷𝐼𝐼 decisão de não realizar o teste
𝜃1 o teste não indica gás 
𝜃2 o teste indica gás
O ganho esperado no nó I será igual a:
Exemplo extraído de Schaum's Outline of Operations Research-McGraw-Hill (1997)