MOQ – 43

PESQUISA
OPERACIONAL

Professor: Rodrigo A. Scarpel

[email protected]
www.mec.ita.br/~rodrigo
Pesquisa Operacional

Durante a Segunda Guerra Mundial, os líderes militares solicitaram que

cientistas estudassem problemas como posicionamento de radares,
armazenamento de munições e transporte de tropa, etc...

A aplicação do método científico e de ferramentas matemáticas em

operações militares passou a ser chamado de Pesquisa Operacional.

Hoje em dia, Pesquisa Operacional é enfoque científico para Problemas

de Decisão.
APO: Advanced Planning Optimizer
 Pesquisa Operacional

A Pesquisa Operacional é uma ciência aplicada voltada

para a resolução de problemas reais, tendo como foco a
tomada de decisões.

Programação Matemática
Estatística / Séries Temporais / Modelos de Previsão
Fluxo em Redes / Grafos / Otimização Combinatória
Metaheurística
Redes Neurais / Sistemas Especialistas / IA
Análise Multicritério
Simulação / Filas / Processos Estocásticos
Teoria da decisão
 Pesquisa Operacional
MB-207 - Econometria Aplicada
Modelos de regressão linear. Previsão. Séries temporais.

CC-238 - Grafos e Otimização Combinatória

CT-215 - Inteligência Artificial

Sistemas especialistas. Aplicações de inteligência artificial.

CC-236 - Modelagem de Simulação por Computadores

EE-214 - Inteligência Artificial em Controle e Automação

Sistemas especialistas. Redes neurais, lógica fuzzy.

IT-207 - Pesquisa Operacional Aplicada a Problemas de Transporte Aéreo

Programação linear. Problemas do transporte, do transbordo e da
designação. Grafos.

MB-217 – Análise da decisão sob incerteza

 Programação Matemática

Um problema de programação matemática tem por

objetivo encontrar os valores para as variáveis de
decisão que otimizam (maximizam ou minimizam) uma
função objetivo respeitando um conjunto de restrições.
Tipos de modelos de programação matemática:
- Programação linear
- Programação inteira
- Programação não-linear
- Programação dinâmica
-Outros
Fases de um estudo com PM:

Definição do problema:
1. Quais são as alternativas para Implementação da solução
a decisão?
2. Sob quais restrições a decisão
é tomada?
Validação do modelo:
3. Qual seria um critério objetivo
para avaliar as alternativas? 1. Formulação está adequada?
2. Resolve o problema?

Construção do modelo:
Solução do modelo:
1. Utilização de algoritmos ou
métodos de resolução
2. Análise de sensibilidade
Programa do curso:
Semana Conteúdo

1 Apresentação da disciplina. Introdução à Programação Linear. Formulação em programação linear.

2 Resolução de problemas de PL pelo Método Gráfico. Introdução ao método simplex para resolução de PPL

3 Resolução de problemas de PL pelo Método Simplex. A matemática do método simplex.

Problemas com soluções iniciais (Método das 2 fases e o Big-M). Degeneração, ciclagem e convergência do
4
método simplex.
5 SBPO (Simpósio Brasileiro de Pesquisa Operacional)
6 Análise de Sensibilidade.
7 Prova
8 Correção da prova. Princípios de programação multiobjetivo. Resolução computacional.
O problema dual. Formulação e Interpretação econômica do problema dual. Teoremas da dualidade. Algoritmos
9
simplex adicionais. Análise pós-otimização.
10 O Problema do Transporte.
11 O problema da Designação. O problema do Transbordo.
12 Programação Linear Inteira: Formulação, Método de Branch and Bound de resolução.
13 O problema do caixeiro viajante e do carteiro chinês. Problemas de otimização combinatória.
Otimização em Redes: Definições. Os problemas do caminho mínimo e do fluxo máximo. O problema da
14
cobertura.
15 Prova
Correção da prova. Introdução à programação não-linear e aos métodos não exatos para resolução de problemas de
16
programação matemática.
Avaliação:
• 2 Provas (1 por bimestre)
• Exame:
1 Trabalho (individual)
• Formulação
• Resolução por computador
• Análise de sensibilidade
• Interpretação dos resultados

1. O TRABALHO FOI ENTREGUE DENTRO DO PRAZO? (20%)

2. A FORMULAÇÃO E RESOLUÇÃO ESTÃO CORRETAS? (40%)
3. A INTERPRETAÇÃO DOS RESULTADOS E A ANÁLISE DE
SENSIBILIDADE ESTÃO CORRETAS? (30%)
4. O RELATÓRIO ESTÁ BEM FEITO? (10%)
Bibliografia:

Taha, H. A., Pesquisa Operacional, 8a edição. Pearson

(Prentice-Hall), 2008.

Taha, H. A. Operations Research – An Introduction,

8th.edition. Pearson (Prentice Hall), 2007.

Winston, W.L., Operations Research, 4th.edition. Brooks/Cole

(Thomson), 2004.

Wagner, H.M., Pesquisa Operacional, 2a edição. Prentice-Hall

do Brasil, 1986.

Hillier, F.S. and Lieberman, G.J., Introduction to Operations

Research, McGraw Hill, 2000.
Para casa:

• Texto: OR Executive Guide (http://www.scienceofbetter.org/)

• Leitura Taha: Capítulo 1

MOQ – 43
INTRODUÇÃO À
PROGRAMAÇÃO
LINEAR

Professor: Rodrigo A. Scarpel

[email protected]
www.mec.ita.br/~rodrigo
Programação Linear:

• Técnica que se propõe otimizar (maximizar ou minimizar) o valor

de uma função linear, respeitando um conjunto de restrições
(equações ou inequações) lineares.

• George B. Dantzig (1947): planejamento logístico (suprimentos)

• Objetivo: tratar problemas de alocação de recursos - determinar

o modo mais eficiente de utilizar os recursos limitados;

• Linear: implica que todas as funções do problema são lineares.

Um modelo de programação linear (PL) reduz um sistema real a

um conjunto de equações ou inequações em que pretendemos
otimizar uma função objetivo.
Exemplos de Problemas de Decisão resolvidos por PL

• Se tanto a Matéria Prima quanto a Mão de Obra são limitados, qual

a quantidade produtos que maximiza o lucro da empresa?

• Se um dado combustível é obtido de uma mistura de produto de preços

variados, qual a composição de menor custo com poder calorífico
suficiente?

• Se existem vários caminhos que ligam duas cidades, qual é a que

propicia o mínimo de gasto de combustível?

• Se existem vários ativos financeiros, qual a combinação que melhor

reflete o compromisso entre o risco e o retorno?
Problema de programação linear:
Considere o seguinte problema:
( Minimizar / Maximizar ) Z = a1 x1 + a 2 x 2 + ... + a n x n
Sujeito a : b11 x1 + b12 x 2 + ... + b1n x n ≥ c1
b 21 x1 + b22 x 2 + ... + b2 n x n ≥ c 2
M M M M
b k1 x1 + bk 2 x 2 + ... + bkn x n ≥ c k
x1 , x 2 , .... , xn ≥ 0
Z: função objetivo (função critério)
ai: coeficientes da função objetivo (custo / lucro), i = 1,…,n
xi: variáveis de decisão, i = 1,…,n
bji: coeficientes tecnológicos, i = 1,…,n e j = 1,…,k
cj: constantes do lado direito (right-hand-side), j = 1,…,k
Exemplo de problema de PL (mix de produção):
Uma empresa fabrica 2 tipos de porta – de madeira e de alumínio.
Cada porta passa por 3 operações: corte, montagem e
acabamento. O tempo gasto em cada uma dessas etapas por
cada tipo de porta é:
Corte Montagem Acabamento
Madeira 1,5 h/porta 3,0 h/porta 1 h/porta
Alumínio 4,0 h/porta 1,5 h/porta 1 h/porta
Disponibilidade 24 h 21 h h h
8,75

Determine a quantidade de portas (de madeira e de alumínio) a

serem fabricadas para maximizar o lucro da empresa, respeitando
os recursos disponíveis (horizonte do planejamento: 1 dia).
Lucro unitário: porta de madeira: R$4,00
porta de alumínio: R$6,00
Exemplo de problema de PL (mix de produção):
Variável de decisão:
xi → quantidade do produto i (i = madeira, alumínio) que serão fabricados

Função Objetivo:
Maximizar Lucro = Z = 4,0*xmadeira + 6,0*xalumínio

Restrições: capacidade produtiva

corte → 1,5*xmadeira + 4,0*xalumínio ≤ 24
montagem → 3,0*xmadeira + 1,5*xalumínio ≤ 21
acabamento → 1,0*xmadeira + 1,0*xalumínio ≤ 8

Restrições: não negatividade

xmadeira, xalumínio ≥ 0
Hipóteses em Programação Linear:

Proporcionalidade: todos os retornos / custos e recursos

utilizados variam proporcionalmente a variável de decisão (não há
economia de escala);

Aditividade: o efeito total de quaisquer duas variáveis é a soma

dos efeitos individuais (não há sinergia ou efeito de substituição).
Exemplo: o custo total é a soma dos custos individuais;

Divisibilidade: as variáveis de decisão podem assumir valores

fracionados. Se essas variáveis só puderem assimir valores
inteiros o problema é de programação inteira (PI);

Certeza (Determinístico): todos os parâmetros do modelo são

constantes conhecidas (não são variáveis aleatórias);
Manipulação do problema:

Inequações e Equações:
n
n
∑a ij x j ≥ bi
∑ a ij x j = bi j =1
j =1 n

∑a ij x j ≤ bi
j =1
n n

∑a ij x j ≥ bi → ∑a ij x j − x n +1 = bi xn+1: variável de excesso

j =1 j =1
n n

∑a ij x j ≤ bi → ∑a ij x j + x n +1 = bi xn+1: variável de folga

j =1 j =1
n

Maximização e Minimização: Z = ∑ c j x j
j =1

Maximizar Z = Minimizar − Z

Não-negatividade: x j (irrestrito) → x j = x ′j − x ′j′ x ′j , x ′′j ≥ 0
Formas de Representação:

Formato padão: todas as restrições são igualdades e todas as
variáveis são não-negativas.

Formato canônico: (problema de minimização) todas as

variáveis são não-negativas e todas as restrições são do tipo ≥ .
MOQ – 43
FORMULAÇÃO EM PL

Professor: Rodrigo A. Scarpel

[email protected]
www.mec.ita.br/~rodrigo
Problema de programação linear:

( Minimizar / Maximizar ) Z = a1 x1 + a 2 x 2 + ... + a n x n

Sujeito a : b11 x1 + b12 x 2 + ... + b1n x n ≥ c1
b 21 x1 + b22 x 2 + ... + b2 n x n ≥ c 2
M M M M
b k1 x1 + bk 2 x 2 + ... + bkn x n ≥ c k
x1 , x 2 , .... , xn ≥ 0

Z: função objetivo (função critério)

ai: coeficientes da função objetivo (custo / lucro), i = 1,…,n
xi: variáveis de decisão, i = 1,…,n
bji: coeficientes tecnológicos, i = 1,…,n e j = 1,…,k
cj: constantes do lado direito (right-hand-side), j = 1,…,k
ETAPAS NA FORMULAÇÃO DO MODELO MATEMÁTICO:

 Identificar as variáveis de decisão do problema

 Construir sua função objetivo

 Definir suas restrições

Construção do modelo:
PROBLEMAS CLÁSSICOS:

Os problemas clássicos de PL podem ser

enquadrados em três categorias:

 Problema da mistura

 Problemas de planejamento

 Problemas de alocação de recursos

 Problemas de corte e empacotamento

PROBLEMAS CLÁSSICOS: o problema da mistura

• Estão entre os primeiros problemas de programação

linear implementados com sucesso na prática.

• Essa classe de problemas consiste em combinar

materiais com o objetivo de gerar produtos com
características convenientes (respeitando as
restrições) minimizando seu custo de produção.

• Exemplos:

• Formulação de rações / dietas

• Formulação de produtos na indústria química

• Formulação de ligas metálicas

Problema 1: Problema da Mistura

 Quanto comprar de cada insumo?

 Quanto fabricar de cada produto?

MP1: Gasolina Pura P1: Gasolina Verde

MP2: Octanas P2: Gasolina Azul
MP
MP3: Aditivos P3: Gasolina Amarela

Gasolina Octanas Aditivos Lucro

Pura
Gasolina Verde 22% 50% 28% R$ 0,48/l
Gasolina Azul 55% 32% 13% R$ 0,40/l
Gasolina Amarela 72% 20% 8% R$ 0,29/l
Disponibilidade (l) 3.200.000 2.400.000 1.100.000
PROBLEMAS CLÁSSICOS: problemas de planejamento

• Esta é uma classe de problemas bastante ampla sendo

aplicável a problemas de planejamento da produção e
financeiro.

• Essa classe de problemas (produção) consiste em decidir

quais produtos e quanto fabricar em um período
respeitando as restrições (máquinas, insumos, demanda,
capacidade de armazenagem,…) maximizando o lucro
obtido.

• Exemplos:

• Mix de produção (planejamento estático)

• Planejamento em multiplos períodos

Problema 2: Mix de Produção (planejamento estático)

MADEIRA ALUMÍNIO

CORTE Corte Montagem Acabamento

Madeira 1,5 h/porta 3,0 h/porta 1 h/porta
Alumínio 4,0 h/porta 1,5 h/porta 1 h/porta
Disponibilidade 24 h 21 h 8 h
MONTAGEM

ACABAMENTO

PORTA PORTA DE
DE ALUMÍNIO
MADEIRA
L=$6,00
L=$4,00
Problema 2: Mix de Produção

Curto prazo: planejamento da produção

 Quanto comprar de cada insumo?

 Quanto fabricar de cada produto?

Médio prazo: expansão da produção

 Quais etapas do processo são gargalo?

Problema 3: Problema do Planejamento da Produção

Um fabricante de barcos deve decidir quantas unidades serão

fabricadas nos próximos 4 trimestres.
Em sua carteira de pedidos há 40 barcos a serem entregues no
primeiro trimestre, 60 no segundo trimestre, 75 no terceiro trimestre
e 25 no quarto trimestre.
No início do primeiro trimestre o fabricante terá 10 barcos em
estoque e tem capacidade de produzir 40 barcos por trimestre
(nesse caso cada barcos custa $40.000).
Há a possibilidade de produzir unidades adicionais, porém o custo
unitário vai para $45.000.
O custo de carregamento (manter um barco estocado) é de $2.000.
Faça o planejamento da produção objetivando minimizar o custo
total nos próximos 4 trimestres.
PROBLEMAS CLÁSSICOS: probl. alocação de recursos

• Esta é uma classe de problemas aplicável aos

problemas operacionais das empresas (programação
das atividades).

• Essa classe de problemas consiste em decidir como os

recursos existentes (recursos humanos, aeronaves,
equipamentos,…) serão alocados de forma a atender o
planejamento, minimizando a quantidade de recursos
necessários.

• Exemplos:

• Alocação dos funcionários

• Alocação de aeronaves e tripulantes.

Problema 4: Programação de ônibus
Uma empresa de transporte urbano de passageiros quer determinar
a quantidade mínima de ônibus necessários para atender sua
programação. Dados:
1.Devido à mautenção diária obrigatória, cada ônibus só pode
circular apenas 8 horas sucessivas por dia
2. Necessidade:
PROBLEMAS CLÁSSICOS: probl. corte e empacotamento

Problema 5: Corte de rolos de papel

Uma empresa fabrica rolos de papel com 20 pés de comprimento
(diâmetro padrão). Em uma certa semana recebeu 3 pedidos:

Como fazer as entregas de forma a minimizar a perda devido ao

corte dos rolos?
Problema 5: Corte de rolos de papel
Para casa:

• Leitura Taha: 1, 2.3 e 2.4

Winston: 1, 3.1,

3.4 a 3.12

• OR Executive Guide

• Lista de Exercícios 1
OBSERVAÇÃO

Este material refere-se às notas de aula do curso

MOQ-43 (Pesquisa Operacional) do Instituto
Tecnológico de Aeronáutica (ITA). Não substitui o
livro texto, as referências recomendadas e nem as
aulas expositivas. Este material 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.