Aula 5 Pesquisa Operacional

Prévia do material em texto

EAD 350EAD 350
Pesquisa OperacionalPesquisa Operacional
Aula 05Aula 05
Prof. Hiroo Takaoka
takaoka@usp.br
FEA/USP
Ativ4 Ativ4 -- Problema de Transporte Problema de Transporte -- Resolução Resolução Ativ4 Ativ4 -- Problema de Transporte Problema de Transporte -- Resolução Resolução 
Min Z = 17x1A + 20x1B + 13x1C + 12x1D
+ 15x2A + 21x2B + 26x2C + 25x2D
+ 15x3A + 14x3B + 15x3C + 17x3D
Sujeito a
Local 1 x1A + x1B + x1C + x1D = 70
Local 2 x2A + x2B + x2C + x2D = 80
Local 3 x3A + x3B + x3C + x3D = 115
Armazém A x1A + x2A + x3A < 50
Armazém B x1B + x2B + x3B < 60
Armazém C x1C + x2C + x3C < 70
Armazém D x1D + x2D + x3D < 95
xij > 0 (i = 1, 2, 3) e (j = A, B, C, D)
Função Objetivo
Ativ4 Ativ4 -- Problema de Transporte Problema de Transporte -- Resolução Resolução Ativ4 Ativ4 -- Problema de Transporte Problema de Transporte -- Resolução Resolução 
Ativ4 Ativ4 -- Problema de Transporte Problema de Transporte -- Resolução Resolução Ativ4 Ativ4 -- Problema de Transporte Problema de Transporte -- Resolução Resolução 
Ativ4 Ativ4 -- Problema de Transporte Problema de Transporte -- Resolução Resolução Ativ4 Ativ4 -- Problema de Transporte Problema de Transporte -- Resolução Resolução 
1
n
i
1
j
n
Agente Tarefa
x11
x1j
x1m
xi1
xij
xim
xn1
xnj
xnm
rn1
r11
rij
ri1
r1j
r1n
rin
rnn
rnj
Oferta Demanda
• Designar cada um dos n agentes indivisíveis para cada uma das n tarefas, de 
modo a maximizar o rendimento total dos agentes. 
• xij - agente i designado para tarefa j
• rij - rendimento do agente i na tarefa j
Problema de DesignaçãoProblema de DesignaçãoProblema de DesignaçãoProblema de Designação
Problema de Designação Problema de Designação –– Modelo de PLModelo de PLProblema de Designação Problema de Designação –– Modelo de PLModelo de PL

 
n
i
n
j
ijijxr
1 1
Max Z =
Sujeito a



n
i
ijx
1
1



n
j
ijx
1
1
j = 1 ... n
i = 1 ... n
0ijx i = 1 ... n; j = 1 ... n
Função Objetiva
Problema de Designação Problema de Designação –– ExemploExemploProblema de Designação Problema de Designação –– ExemploExemplo
Designar cada um dos n agentes indivisíveis para cada uma das n 
tarefas, de modo a maximizar o rendimento total dos agentes. O 
rendimento de cada um dos agentes em cada uma das tarefas é dado 
abaixo:
Agente 1 2 3 4
1 24 10 21 11
2 14 22 10 15
3 15 17 20 19
Total
1
1
1
4 11 19 14 14 1
Total 1 1 1 1
Tarefa
Problema de Designação Problema de Designação -- ExemploExemploProblema de Designação Problema de Designação -- ExemploExemplo
Agente 1 2 3 4
1 x11 x12 x13 x14
2 x21 x22 x23 x24
3 x31 x32 x33 x34
Total
1
1
1
4 x41 x42 x43 x44 1
Total 1 1 1 1
Tarefa
xij - agente i designado para tarefa j
Problema de Designação Problema de Designação -- ExemploExemploProblema de Designação Problema de Designação -- ExemploExemplo
Função Objetiva
Max Z = 24x11 + 10x12 + 21x13 + 11x14
+ 14x21 + 22x22 + 10x23 + 15x24
+ 15x31 + 17x32 + 20x33 + 19x34
+ 11x41 + 19x42 + 14x43 + 14x44
Sujeito a
x11 + x12 + x13 + x14 = 1
x21 + x22 + x23 + x24 = 1
x31 + x32 + x33 + x34 = 1
x41 + x42 + x43 + x44 = 1
x11 + x21 + x31 + x41 = 1
x12 + x22 + x32 + x42 = 1
x13 + x23 + x33 + x43 = 1
x14 + x24 + x34 + x44 = 1
xij > 0
Agente
Tarefa
Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 1 em Excel 1 Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 1 em Excel 1 
Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 1 em Excel 1 Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 1 em Excel 1 
Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 1 em Excel 1 Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 1 em Excel 1 
Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 1 em Excel 1 Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 1 em Excel 1 
Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 1 em Excel 1 Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 1 em Excel 1 
Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 2em Excel 2Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 2em Excel 2
Variáveis
decisórias
Valor ótimo
Rendimento
Restrições
Rendimentos do agente
Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 2em Excel 2Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 2em Excel 2
Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 2em Excel 2Problema de DesignaçãoProblema de Designação–– ModeloModelo em Excel 2em Excel 2
Ativ. 5a p/ Resolver em Excel HOJE em AULA Ativ. 5a p/ Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito -- Duplas ou Trios Duplas ou Trios 
Ativ. 5a p/ Resolver em Excel HOJE em AULA Ativ. 5a p/ Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito -- Duplas ou Trios Duplas ou Trios 
Fábrica 1 Fabrica 2 Fabrica 3 Fabrica 4
Local A 10 12 15 16
Local B 14 12 13 18
Local C 10 16 19 15
Local D 14 12 13 15
O quadro abaixo representa os custos de transporte de uma máquina dos 
locais de depósito para as fábricas onde deverão ser instaladas. Designar 
uma máquina para cada fábrica com o menor custo total possível. 
1. Elaborar o Modelo matemático na própria planilha Excel
2. Elaborar o Modelo na planilha Excel e resolver com o Solver
3. Gerar o Relatório de Sensibilidade
Ativ. 5b p/ Resolver em Excel HOJE em AULA Ativ. 5b p/ Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito -- Duplas ou Trios Duplas ou Trios 
Ativ. 5b p/ Resolver em Excel HOJE em AULA Ativ. 5b p/ Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito -- Duplas ou Trios Duplas ou Trios 
Incorp1 Incorp2 Incorp3 Incorp4 Incorp5
Terreno A 19 19 29 23 24
Terreno B 23 21 27 19 25
Terreno C 19 19 22 0 20
Terreno D 23 0 19 21 18
Um agente de compra e venda de terras pretende vender quatro terrenos 
e recebeu cinco ofertas individuais de cinco incorporadores. Devido ao 
capital necessário, essas ofertas foram feitas sabendo-se que nenhum 
incorporador compraria mais do que um terreno. As ofertas em milhares 
de R$ são mostradas na tabela a seguir. O agente deseja maximizar o 
ganho total dessas ofertas. 
1. Elaborar o Modelo matemático na própria planilha Excel
2. Elaborar o Modelo na planilha Excel e resolver com o Solver
3. Gerar o Relatório de Sensibilidade
Petróleo
Máxima
quantidade
disponível 
Custo
unitário
A 100 6
B 200 3
Gasolina
Mínima
% A
requerida 
Preço de
venda
unitária
1 60 8
2 30 5
Deseja-se saber a quantidade de cada gasolina que deve ser fabricada 
de tal maneira que o lucro seja máximo.
1. Elaborar o Modelo matemático na própria planilha Excel
2. Elaborar o Modelo na planilha Excel e resolver com o Solver
3. Gerar o Relatório de Sensibilidade
Uma refinaria fabrica dois tipos de gasolina (1 e 2) a partir de dois tipos de 
petróleo bruto (A e B).
Os custos, os preços de venda e matéria-prima para fabricar as gasolinas são:
Ativ. 5c p/ Resolver em Excel HOJE em AULA Ativ. 5c p/ Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito -- Duplas ou Trios Duplas ou Trios 
Ativ. 5c p/ Resolver em Excel HOJE em AULA Ativ. 5c p/ Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito -- Duplas ou Trios Duplas ou Trios 
Ativ. 5c p/ Resolver em Excel HOJE em AULA Ativ. 5c p/ Resolver em Excel HOJE em AULA ––
Entregarpelo Erudito Entregar pelo Erudito -- Duplas ou Trios Duplas ou Trios 
Ativ. 5c p/ Resolver em Excel HOJE em AULA Ativ. 5c p/ Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito -- Duplas ou Trios Duplas ou Trios 
PA
PB
G1
G2
xA1+xA2 < 100
xB1+xB2 < 200
xA1+xB1
xA2+xB2
> 60%
> 30%
XA1
XA2
XB1
XB2
(Preço: 8)
(Preço: 5)
(Custo: 6)
(Custo: 3)
xA1: quantidade de petróleo A p/ produzir gasolina 1
xA2: quantidade de petróleo A p/ produzir gasolina 2
xB1: quantidade de petróleo B p/ produzir gasolina 1
xB2: quantidade de petróleo B p/ produzir gasolina 2
Variáveis 
decisórias
Ativ. 5d p/ Resolver em Excel HOJE em AULA Ativ. 5d p/ Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
Ativ. 5d p/ Resolver em Excel HOJE em AULA Ativ. 5d p/ Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
O supervisor do centro de suporte da empresa Alpha precisa elaborar a escala de seu 
pessoal. O centro de suporte fica aberto das 8 da manhã até meia-noite. O supervisor 
monitorou as quantidades de chamados por período e determinou que o seguinte número de 
analistas seriam necessários por período.
Período do dia Número mínimo de analistas de plantão 
08h – 12h 4
12h – 16h 8
16h – 20h 10
20h – 24h 6
Podem ser contratados dois tipos de analistas: em tempo integral e em tempo parcial 
(estagiários). Os analistas em tempo integral trabalham por oito horas seguidas em três tipos 
de turno (8h às 16h, 12h às 20h ou 16h às 00h) e recebem $14 por hora. Os analistas 
estagiários em tempo parcial podem ser contratados para os períodos de 4 horas indicados na 
tabela anterior e recebem $12 por hora.
Durante qualquer período, deve haver pelo menos dois analistas tempo integral para cada 
analista estagiário em tempo parcial. Como atender a esses requisitos com o custo mínimo? 
• Elaborar e escrever o modelo matemático na própria planilha Excel
• Elaborar a o modelo na planilha Excel e resolver com o Solver
• Gerar o relatório de análise de sensibilidade
Ativ. 5d p/ Resolver em Excel HOJE em AULA Ativ. 5d p/ Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
Ativ. 5d p/ Resolver em Excel HOJE em AULA Ativ. 5d p/ Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
A tabela abaixo indica as variáveis de decisão e1, e2, e3 e e4 referentes ao número 
de estagiários (tempo parcial) em cada um dos turnos de 4 horas e as variáveis a1, 
a2 e a3 referentes ao número de analistas em cada um dos turnos de 8 horas, bem 
como as quantidades mínimas para cada turno de 4 horas
Período do 
dia Estagiário
Analista 
manhã
Analista 
tarde
Analista 
noite
Número 
mínimo de 
atendentes
8h – 12h e1
a1
--- --- 4
12h – 16h e2
a2
--- 8
16h – 20h e3 ---
a3
10
20h – 24h e4 --- --- 6
A função objetivo pode então ser assim descrita:
Minimizar o custo: ((e1+e2+e3+e4) *10 * 4) + ((a1+a2+a3) * 14 * 8)
Mínimo de 2 analistas para cada estagiário no turno.
a1/e1 > 2
(a1+a2) / e2 > 2
(a2+a3) / e3 > 2
a3 / e4 > 2