sd 03 Programação Linear

Prévia do material em texto

Pesquisa Operacional
Programação Linear
Módulo 3
Programação Linear
Considere que você está saindo 
com duas mulheres:
Natalie Portman Scarlett Johansson
Caso Portman - Johansson
• Restrições :
- Uma não pode saber da outra. Para isso , você 
tem que levá-las a lugares diferentes em dias 
diferentes. (restrição operacional)
- O dinheiro é limitado, portanto você não pode 
sair todos os dias. (restrição logística/ 
matemática)
- O tempo é limitado, portanto deve haver um 
planejamento do tempo gasto com cada uma. 
(restrição logística/matemática)
-É chique, só gosta de restaurantes caros 
(de La Brasa pra cima), em um encontro 
com ela você vai gastar R$180,00.
-Ela é calma, sossegada, um encontro 
com ela dura 2 horas.
x1
-Ela é mais simples, gosta de lugares mais 
baratos (como o Cantina), em um 
encontro com ela você vai gastar 
R$100,00.
-Ela é agitada, gosta de fazer muitas 
coisas na noite, um encontro com ela 
dura 4horas.
x2
Quantas vezes você vai poder sair com Natalie 
numa semana? E com Scarlett?
Você pode gastar R$ 800,00 por semana com elas.
Você tem 20 horas livres para sair com elas na 
semana.
Caso Portman - Johansson
Caso Portman - Johansson
Chamemos assim:
x1 a quantidade de vezes que você sai com Natalie Portman.
x2 a quantidade de vezes que você sai com Scarlett Johansson.
Portanto teremos:
Resumindo:
- Se você sai x1 vezes com Natalie por semana e 
cada noite com ela custa R$180,00, então sair com Natalie 
custará 180 x1. Com Scarlett será 100 x2. A mesma lógica 
se aplica ao tempo.
{
800100180 21  xx 2042 21  xx
Caso Portman - Johansson
{
800100180 21  xx 2042 21  xx
Esse sistema de equação elaborado no slide passado são as 
restrições do modelo.
Como iremos resolver esse problema? Existem vários 
métodos para resolver problemas de programação linear 
(gráficos, solver, lindo, etc) porém iremos simplificar 
elaborando três alternativas de solução:
ALTERNATIVA 1: x1 = 2 e x2 = 4;
ALTERNATIVA 2: x1 = 3 e x2 = 3;
ALTERNATIVA 3: x1 = 3 e x2 = 2.
Caso Portman - Johansson
Vamos testar as alternativas!
Lembre-se que o limite é R$ 800,00 e 20horas.
Alternativa 3 - x1 = 3 e x2 = 2:
180 x 3 + 100 x 2 = R$740,00
2 x 3 + 4 x 2 = 14horas
Alternativa 2 - x1 = 3 e x2 = 3:
180 x 3 + 100 x 3 = R$840,00
2 x 3 + 4 x 3 = 18 horas
Alternativa 1 - x1 = 2 e x2 = 4:
180 x 2 + 100 x 4 = R$760,00
2 x 2 + 4 x 4 = 20 horas
OK!
OK!
Errado!
Caso Portman - Johansson
Caso Portman - Johansson
• Qual é o seu objetivo? Segue abaixo dois 
objetivos diferentes:
1. Sair o máximo de vezes com as duas. 
Matematicamente teremos: MAX( x1 + x2 ).
2. Sair o máximo de vezes com as duas mas 
com notável preferência por Natalie 
Portman. Matematicamente teremos: 
MAX( 3x1 + x2 ).
Seguindo o Objetivo 1, analisamos as duas alternativas válidas:
Alternativa 1 : x1 = 2 e x2 = 4:
x1 + x2 = 6
Alternativa 3 : x1 = 3 e x2 = 2:
x1 + x2 = 5
Portanto, se o objetivo for sair o máximo possível com as duas, sem 
preferências, você deve sair duas vezes com Natalie Portman e quatro
vezes com Scarlett Johansson em uma semana.
Objetivo 1: MAX( x1 + x2 )
Caso Portman - Johansson
Seguindo o Objetivo 2, analisamos as duas alternativas válidas:
Alternativa 1 : x1 = 2 e x2 = 4:
3x1 + x2 = 10
Alternativa 3 : x1 = 3 e x2 = 2:
3x1 + x2 = 11
Portanto, se o objetivo for sair o máximo possível com as duas, mas 
com uma clara preferência por Portman, você deve sair três vezes com 
Natalie Portman e duas vezes com Scarlett Johansson em uma 
semana.
Objetivo 2: MAX( 3x1 + x2 )
Caso Portman - Johansson
Modelo com o 1º objetivo:
Função objetivo: 
MAX( x1 + x2 )
Restrições:
Condições de não-negatividade:
x1, x2 ≥ 0
800100180 21  xx
2042 21  xx
Modelo com o 2º objetivo:
Função objetivo: 
MAX( 3x1 + x2 )
Restrições:
Condições de não-negatividade:
x1, x2 ≥ 0
800100180 21  xx
2042 21  xx
LACHTERMACHER, G. Pesquisa Operacional na Tomada de
Decisões: modelagem em Excel. São Paulo: Campus, 2006.
(Adaptado)
Caso Portman - Johansson
Exercícios
Módulo 4
Exemplos Práticos
O Problema do SAMU-SP
• O tempo médio de atendimento das ambulâncias 
no município de SP está muito elevado!
– Quase 30 minutos
• O que fazer para melhorar o serviço?
Alguns dados do problema...
• Serviço que funciona initerruptamente 
– 24h por dia, 7 dias por semana
• 9000 chamadas recebidas por dia.
• 1200 despachos de ambulância por dia.
• 140 veículos.
• 77 bases.
Premio IFORS for OR in 
Development
Como melhorar o serviço?
• Adicionando mais ambulâncias?
– Quantas?
– Onde? (ao longo do tempo)
• Novas bases? Relocar atuais?
– Quantas?
– Onde?
• Dificuldade de abrir novas 
bases
– Demora devido à burocracia
– Baixa disponibilidade de imóveis
– Custo elevado para adequação de 
prédios
– Preços dos imóveis
Bases móveis podem ser uma 
solução?
Afim de superar as dificuldades para 
aumentar o número de bases!
Ou para relocar bases existentes que 
ficaram mal localizadas ou muito 
pequenas!
Podem ser instaladas em espaços público 
e serem facilmente relocadas a fim de 
assegurar boa cobertura em todos os 
momentos.
Resultados
Redução dos tempos de atendimento 27min → 10min
Melhor localização para bases e ambulâncias 
Demonstrou eficácia das bases móveis
Modelo para outros SAMUs
"Nesse comportamento surge uma inteligência coletiva. Não existe 
uma abelha planejadora dizendo para onde ir. A mesma coisa é o 
sistema de atendimento móvel. Ele se auto adapta para o que o 
município precisa"
Modelo matemático
• Variáveis de decisão 
– Onde localizar bases
– Quantas ambulâncias de cada tipo alocar em cada um 
dos 21 períodos (7 dias x 3 turnos)
• Função Objetivo 
– Minimizar tempo de resposta total
• Restrições 
– Cada ponto de demanda coberto pelo número mínimo 
de ambulâncias de cada tipo
– Ambulâncias só podem ser alocadas a bases 
selecionadas
– Conectividade do plano de realocação das ambulâncias 
entre bases
– Capacidades das bases 
Módulo 4
Caso West Shipping
Caso West Shipping
• Um navio cargueiro pode ser carregado com 
duas cargas disponíveis para transporte 
entre dois portos: 
– castanha-do-Pará (em sacos) 
– fios elétricos (rolos) 
• O navio possui uma capacidade de 5.000 t 
úteis e 9.600 m3
• Deseja-se determinar quanto transportar
de cada uma das duas cargas, de modo a 
maximizar a receita total obtida.
Caso West Shipping
Variáveis de Decisão
• Quantas toneladas de cada carga 
transportar?
– x1= quantidade da carga 1 (castanha) a 
transportar, em toneladas.
– x2= quantidade da carga 2 (fios) a 
transportar, em toneladas.
Função Objetivo
• Maximizar 80x1+ 100x2
Restrições
• Peso máximo (t)
▪ x1+ x2 ≤ 5000
• Volume útil (m³)
▪ 2,4x1+ 0,8x2 ≤ 9600
• Quantidades máximas
▪ X1 ≤ 6000
▪ X2 ≤ 3500
Peso máximo (t)
▪x1+ x2 ≤ 5000
Volume útil (m³)
▪2,4x1+ 0,8x2 ≤ 9600
Quantidades máximas
▪X1 ≤ 6000
▪X2 ≤ 3500
Restrições
Exercícios