POI Uchoa 1

Prévia do material em texto

1
Pesquisa Operacional I
Apresentação Geral
Prof. Eduardo Uchoa
eduardo.uchoa@gmail.com
http://www.logis.uff.br/~uchoa/POI/
2
Pesquisa Operacional (PO) é o uso do métodos científicos para 
auxiliar a tomada de decisões. Caracteriza-se por: 
a) emprego de matemática “avançada”
b) aplicação em problemas reais
c) multidisciplinaridade, envolve conceitos vindos de várias 
áreas, incluindo:
Matemática Estatística
Engenharia Computação
Administração Economia
Definição
3
Outras Definições
� “Operations research is the application of advanced analytical 
methods to help make better decisions.”
Informs: http://www.informs.org/About-INFORMS/About-Operations-Research
� “A Pesquisa Operacional é uma ciência aplicada voltada para 
a resolução de problemas reais. Tendo como foco a tomada 
de decisões, aplica conceitos e métodos de várias áreas 
científicas na concepção, planejamento ou operação de 
sistemas. A Pesquisa Operacional é usada para avaliar linhas 
de ação alternativas e encontrar as soluções que melhor 
servem aos objetivos dos indivíduos ou organizações.”
SOBRAPO: http://www.sobrapo.org.br/o_que_e_po.php
4
A Pesquisa Operacional é o “cálculo da 
engenharia de produção”
A PO é uma disciplina básica, que oferece ferramentas aplicáveis 
na maioria das demais áreas da Produção, incluindo:
• Planejamento e Controle de Produção (PCP)
• Logística
• Arranjo Físico
A PO e a Engenharia de Produção
Graduação em Engenharia de Produção – Universidade Federal Fluminense
5
“Pré-História” da PO
A partir do século XVII, muitos matemáticos clássicos criaram 
ferramentas que podem ser aplicadas no auxílio à decisão:
� Newton, Leibniz, Taylor, Lagrange: Cálculo diferencial para 
achar mínimos/máximos de funções.
� Cardano, Pascal, Huygens, Bayes, Poisson: Cálculo de 
probabilidades.
� Euler, Kirchhoff, Hamilton: Teoria dos grafos, fluxos em 
redes, Otimização combinatória.
� Gauss, Fourier: Sistemas de equações lineares.
6
Estabelecimento da PO como disciplina 
autônoma militar
� 1936 criação da Bawdsey Manor Research Station em 
Suffolk, Inglaterra: estudo do uso de radares para interceptar 
aeronaves inimigas
� 1937 o termo Operational Research foi cunhado por A. P. 
Rowe na BMRS
� 1939 Leonid V. Kantorovich modelou e propôs métodos de 
solução para diversos problemas de planejamento na União 
Soviética
� 1940 (WWII) criado The Anti-Aircraft Research Group na 
força aérea britânica (3 fisiologistas, 1 físico geral, 2 físicos 
matemáticos, 2 matemáticos, 1 astrofísico, 1 oficial do 
exército e 1 topógrafo)
7
� 1941 primeira definição formal do Problema Clássico de 
Transporte por Frank L. Hitchcock
� 1942 formação da U.S. Navy Antisubmarine Warfare 
Operations Research Group (ASWORG)
� 1943-1945 diversos grupos apoiando o planejamento 
logístico (abastecimento) das tropas aliadas,estratégias de 
ataque e defesa aérea e marítima, etc.
� 1945 ao final da WWII é criado o projeto RAND para trabalhar 
no planejamento militar e em problemas do governo norte 
americano
� 1947 George B. Dantzig formalizou a Programação Linear e 
criou o método Simplex para solução de problemas deste tipo 
na USAF
Estabelecimento da PO como disciplina 
autônoma militar
8
� 1951 primeiro uso de um modelo de 
programação linear na indústria: problema 
da mistura (blend) ótima nas refinarias de 
petróleo.
� 1950-1960
� Estabelecimento das primeiras sociedades de 
profissionais de PO nos EUA e na Europa
� Começo do ensino de PO nas universidades 
A PO entra no mundo civil
9
� Usada rotineiramente por empresas e 
organizações nos mais diversos setores da 
indústria, serviços, finanças ou governo.
� A PO contribui significativamente para a eficiência 
da economia mundial
� Tradicionalmente a PO tem sido usada para minimizar 
custos e/ou maximizar lucros
� Atualmente também existem outras preocupações:
� minimizar impactos ecológicos e riscos de acidentes
� maximizar benefícios sociais
A PO hoje
Graduação em Engenharia de Produção – Universidade Federal Fluminense
10
� Entretanto, a PO ainda é muito menos usada do 
que poderia!
� Conflitos com outras culturas empresariais
� Disputas políticas (decisão = poder)
� Dificuldades em obter dados confiáveis
A PO hoje
11
� Entretanto, a PO ainda é muito menos usada do 
que poderia!
� Dificuldades em aplicar adequadamente as técnicas 
de PO aos problemas complexos do mundo real!
� O uso avançado de PO é uma técnica, mas também é uma 
arte.
� Existe escassez (no mundo, mas no Brasil isso é mais grave) 
de profissionais experientes com essa competência.
A PO hoje
12
� Toda a PO está baseada na construção de 
modelos matemáticos para representar de 
forma simplificada os sistemas reais.
Como funciona a PO?
13
Um modelo é uma representação 
simplificada de um sistema real
Modelo
Conclusões
do Modelo
Conclusões
sobre o
Sistema Real
Modelagem
Dedução
Interpretação
Sistema
Real
Graduação em Engenharia de Produção – Universidade Federal Fluminense
14
Para que serve um modelo?
Um modelo é útil quando permite que se 
chegue a conclusões adequadas sobre o 
sistema real, dentro de seu limite de 
aplicabilidade.
Como a PO trabalha com modelos 
matemáticos, a utilidade de um modelo 
também depende da existência de métodos 
matemático-computacionais capazes de 
resolver o modelo.
15
Principais Áreas da PO
� Otimização
� Programação Matemática
� Programação Linear
� Programação Inteira
� Programação Não-Linear
� Otimização Combinatória
� Heurísticas/Metaheurísticas
� Simulação
� Previsão
� Análise Multi-critério
16
Nosso curso de PO I
� Otimização
� Programação Matemática
� Programação Linear
� Programação Inteira
� Programação Não-Linear
� Otimização Combinatória
� Heurísticas/Metaheurísticas
� Simulação
� Previsão
� Análise Multi-critério
17
Um modelo de programação matemática é definido por 
um sistema de equações/inequações.
• As variáveis representam as decisões a serem 
tomadas.
• As equações/inequações representam as 
restrições que existem sobre essas decisões, 
refletindo as características do sistema real.
• Uma função objetivo indica qual dentre as 
possíveis decisões é a mais desejável (solução 
ótima).
Programação Matemática
Graduação em Engenharia de Produção – Universidade Federal Fluminense
18
Tipos de Modelos de Programação 
Matemática
� Programação Linear: todas as restrições e a FO 
são funções lineares
� Um número razoável de sistemas reais podem ser 
bem modelados como PLs
� Métodos de solução extremamente eficazes, 
problemas com milhões de variáveis e restrições 
podem ser resolvidos num laptop
19
Tipos de Modelos de Programação 
Matemática
� Programação Inteira: todas as restrições e a FO 
são funções lineares, mas algumas variáveis 
podem ser obrigadas a terem valores inteiros.
� Um número enorme de sistemas reais podem ser bem 
modelados como PIs
� Métodos de solução bem menos eficazes, problemas 
com alguns milhares de variáveis e restrições já
podem ser intratáveis
20
Tipos de Modelos de Programação 
Matemática
� Programação Não-Linear (será vista em PO II): 
as restrições e a FO podem ser funções não-
lineares.
� Um número enorme de sistemas reais podem ser bem 
modelados como PNLs.
� Métodos de solução eficazes apenas para alguns 
casos particulares (ex: funções quadráticas, funções 
convexas). Problemas envolvendo funções mais 
complicadas com algumas dezenas de variáveis e 
restrições já podem ser intratáveis
21
Nos anos 1940, a força aérea dos EUA usava a palavra 
“programa” como sinônimo de “planejamento”. O seu 
uso pioneiro de modelos matemáticas para auxiliarseus planejamentos disseminou o nome Programação 
Matemática.
• Esse nome histórico causa confusão entre os leigos, 
porque a partir dos anos 1950 a palavra “programação”
passou a ser universalmente associada com escrita de 
código para computadores. 
Um nome pouco feliz
22
Recentemente a Mathematical Programming Society
trocou o seu nome para Mathematical Optimization
Society. Na nova nomenclatura (ainda pouco usada) 
teríamos:
• Otimização Linear
• Otimização Inteira
• Otimização Não-Linear
Programação Matemática = 
Otimização Matemática
23
O nome histórico “Operations Research” não diz nada 
para um leigo. Alguns quase sinônimos que também 
são usados:
• Management Science
• Decision Science
• Analytics
O nome “Pesquisa Operacional”
também não é dos melhores ...
24
Exemplo de Modelo de PL: Problema 
do Mix Ótimo de Produção
Para maximizar seu lucro, uma fábrica de cadeiras precisa 
decidir quais modelos deve produzir.
Graduação em Engenharia de Produção – Universidade Federal Fluminense
25
Problema do Mix Ótimo de 
Produção
Entretanto, a produção é restrita pela disponibilidade 
de matéria-prima: madeira (50 lâminas/semana) e 
tecido (75 metros/semana).
26
Produção de Cadeiras: 
Lucro X Gasto de Matéria-prima
150 400 200
1 4 1
1 1 2
300
3
1
27
Modelo de Programação Linear
x1 x2 x4150 + 400 + 200
x1 x2 x41 + 4 + 1 ≤ 50
x1 x2 x41 + 1 + 2 ≤ 75
max x3+ 300
x3+ 3
x3+ 1
x1, x2, x3, x4 ≥ 0
S.a
Graduação em Engenharia de Produção – Universidade Federal Fluminense
28
Modelo de Programação Linear
x1 x2 x4150 + 400 + 200
x1 x2 x41 + 4 + 1 ≤ 50
x1 x2 x41 + 1 + 2 ≤ 75
max x3+ 300
x3+ 3
x3+ 1
x1, x2, x3, x4 ≥ 0
Solução ótima: x1=25, x2 = x3 = 0, x4=25; lucro = R$ 8750/semana 
S.a
29
Programação Inteira
Tipo de modelo matemático que difere da 
programação linear simplesmente porque algumas (ou 
todas as) variáveis podem ser definidas como inteiras.
Esse recurso adicional (a primeira vista banal) permite 
modelar um número muito maior de situações.
30
Exemplo: Problema da Mochila
Um viajante precisa decidir entre n possíveis objetos 
para colocar na sua mochila com capacidade de peso 
P. Cada objeto i oferece um ganho gi mas possui um 
peso pi. O problema é escolher um subconjunto dos 
objetos com peso ≤ P que maximize o ganho total.
31
Exemplo: Problema da Mochila
P=10 p1=1 p2=2 p3=4 p4=4 p5=5 p6=6 
. g1 =3 g2=3 g3=5 g4=5 g5= 6 g6=9 
1
2
3 4
5 6
32
Modelo de Programação Inteira
inteiros,,,,,
1,,,,,0
1065442.a.S
965533Max
654321
654321
654321
654321
xxxxxx
xxxxxx
xxxxxx
xxxxxx
≤≤
≤+++++
+++++
33
Modelo de Programação Inteira
inteiros,,,,,
1,,,,,0
1065442.a.S
965533Max
654321
654321
654321
654321
xxxxxx
xxxxxx
xxxxxx
xxxxxx
≤≤
≤+++++
+++++
Solução ótima: x1, x2 e x6 =1, ganho total 15
34
Solução Ótima
P=10 p1=1 p2=2 p3=4 p4=4 p5=5 p6=6 
. g1 =3 g2=3 g3=5 g4=5 g5= 6 g6=9 
1
2
3 4
5 6
1
2
6
Graduação em Engenharia de Produção – Universidade Federal Fluminense
35
Bibliografia do Curso
“Pesquisa Operacional”, Arenales, Armentano, 
Morabito, Yanasse. Ed. Campus, 2007
“Introdução à Pesquisa Operacional”, Hillier, 
Lieberman. McGraw-Hill, 2006.
“Técnicas de Otimização”, Pizzolato, Gandolpho. LTC, 
2009.
“Linear Programming”, Chvátal. Ed. Freeman, 1983 
(Caps. 1-5)
36
OBSERVAÇÃO
Este material refere-se às notas de aula do curso 
TEP117 (Pesquisa Operacional I) da Universidade 
Federal Fluminense (UFF) e não pode ser 
reproduzido sem autorização prévia do autor. 
Quando autorizado, seu uso é exclusivo para 
atividades de ensino e pesquisa em instituições 
sem fins lucrativos.