Aula 7 Pesquisa Operacional

Prévia do material em texto

EAD 350EAD 350
Pesquisa OperacionalPesquisa Operacional
Aula 07Aula 07
Prof. Hiroo Takaoka
takaoka@usp.br
FEA/USP
Aviso! Aviso! -- Dia 27/04/15 Dia 27/04/15 -- ProvaProvaAviso! Aviso! -- Dia 27/04/15 Dia 27/04/15 -- ProvaProva
• Cai: elaboração do modelo matemático, resolução 
gráfica, análise de sensibilidade, preço sombra e 
elaboração e análise dos resultados no Solver do 
Excel, incluindo relatório de análise de 
sensibilidade
• Prova em sala de Aula, Individual e sem consulta
• Está disponível no Erudito uma lista de exercícios 
para estudo (com respostas)
Contabilização das AtividadesContabilização das AtividadesContabilização das AtividadesContabilização das Atividades
• Hoje completaremos 7 atividades, colocarei mais uma 
(atividade 8) para realização opcional.
• Quem realizou pelo menos 6 atividades completas terá 
nota 3,0 nos exercícios
• Para quem realizou menos de 6, haverá um “desconto 
progressivo”
– 6 ou 7 atividades – 3,0 / 5 atividades – 2,0
– 4 atividades – 1,5 / 3 atividades – 1,0
– 2 atividades – 0,5 / 1 ou 0 atividades – 0,0
• As notas serão reajustadas se as atividades realizadas 
estiverem incompletas.
Programação Binária Programação Binária -- ConceitoConceitoProgramação Binária Programação Binária -- ConceitoConceito
• De n possibilidades selecionar não mais do que k alternativas. Suponha xi = 0 ou 1 p/ 
i=1,...,n. A restrição x1 + x2 + ... + xn < k significa que, no máximo, k alternativas 
de n possibilidades podem ser escolhidas.
• De n possibilidades selecionar pelo menos k alternativas. Suponha xi = 0 ou 1 p/ 
i=1,...,n. A restrição x1 + x2 + ... + xn > k significa que, no mínimo, k alternativas 
de n possibilidades devem ser escolhidas.
• De n possibilidades selecionar k alternativas. Suponha xi = 0 ou 1 p/ i=1,...,n. A 
restrição x1 + x2 + ... + xn = k significa que k alternativas de n possibilidades 
devem ser escolhidas.
• Decisões dependentes A alternativa k só pode ser selecionada se antes a alternativa 
m tiver sido selecionada. A restrição xk < xm ou xk - xm < 0 impõe esta condição.
• Decisões obrigatórias Deve selecionar a alternativa k se antes a alternativa m tiver 
sido selecionada. A restrição xm < xk ou xm- xk < 0 impõe esta condição.
• Negação. A negação de xk é representada como: (1 – xk).
Programação Programação BináriaBinária
Exemplo : Seleção Exemplo : Seleção de de InvestimentoInvestimento
Programação Programação BináriaBinária
Exemplo : Seleção Exemplo : Seleção de de InvestimentoInvestimento
Opções Retorno(VPL)
A
Capital Necessário por Ano
1 2 3 4 5
400 100 50 200 100 0
B 700 300 200 100 100 100
C 800 100 200 270 200 100
D 1000 200 100 400 200 200
Capital
Disponível
por Ano
500 450 700 400 300
Deseja-se selecionar projetos de investimentos que maximizem o retorno. Os 
retornos e as limitações de capital por ano para o investimento são dados no 
quadro abaixo: 
A diretoria decidiu que a opção D deve ser selecionada se a opção A for selecionada.
Programação Binária Programação Binária 
Exemplo: Exemplo: Seleção Seleção de Investimentode Investimento
Programação Binária Programação Binária 
Exemplo: Exemplo: Seleção Seleção de Investimentode Investimento
Max Z = 400xA + 700xB + 800xC + 1000xD
Sujeito a
100xA + 300xB + 100xC + 200xD < 500
50xA + 200xB + 200xC + 100xD < 450
200xA + 100xB + 270xC + 400xD < 700
100xA + 100xB + 200xC + 200xD < 400
0xA + 100xB + 100xC + 200xD < 300
xi = 0 ou 1; i=A, B, C, D 
Variáveis de decisão
xi = 1 se for selecionado o investimento i, xi = 0 se não
for selecionado o investimento i. (i = A, B, C, D)
Programação Programação MistaMista
Exemplo: Localização Exemplo: Localização de Depósitode Depósito
Programação Programação MistaMista
Exemplo: Localização Exemplo: Localização de Depósitode Depósito
Depósito
Local Capacidade
(em número
de caminhões)
Aluguel
mensal1 2 43
170 40 16070
150 195 10100
100 240 60140
100 90 60110
A
B
C
Demanda
(em número
de caminhões)
200 7750
250 4000
300 5500
Programação Programação MistaMista
Exemplo: Localização Exemplo: Localização de Depósitode Depósito
Programação Programação MistaMista
Exemplo: Localização Exemplo: Localização de Depósitode Depósito
yi = 1 se alugar o depósito i, yi = 0 se não alugar o 
depósito i. (i = A, B, C)
xij = número de caminhões de depósito i para
local j. (i = A, B, C; j = 1, 2, 3, 4)
Custo de transporte
170xA1 + 40xA2 + 70xA3 + ... + 60xC4
Aluguel 
7750yA + 4000yB + 5500yC 
Custo Total = Custo de transporte + Aluguel
Programação Programação MistaMista
Localização Localização de Depósitode Depósito
Programação Programação MistaMista
Localização Localização de Depósitode Depósito
Min Z = 170xA1 + 40xA2 + 70xA3 + ... + 60xC4 +
7750yA + 4000yB + 5500yC
Sujeito a
xA1 + xB1 + xC1 = 100
xA2 + xB2 + xC2 = 90
xA3 + xB3 + xC3 =110
xA4 + xB4 + xC4 = 60
xA1 + xA2 + xA3 + xA4 < 200yA xA1 + xA2 + xA3 + xA4 - 200yA < 0
xB1 + xB2 + xB3 + xB4 < 250yB xB1 + xB2 + xB3 + xB4 - 250yB < 0
xC1 + xC2 + xC3 + xC4 < 300yC xC1 + xC2 + xC3 + xC4 - 300yC < 0
yi = 0 ou 1 (binário); i = A, B, C
xij > 0; i = A, B, C; j = 1 ... 4
Como o depósito A será alugado se yA = 1, a sua capacidade será de 200. 
Caso contrário, será 0. 
Programação Programação MistaMista-- SolverSolver
Localização Localização de Depósitode Depósito
Programação Programação MistaMista-- SolverSolver
Localização Localização de Depósitode Depósito
Todas as variáveis
Programação Programação MistaMista-- SolverSolver
Localização Localização de Depósitode Depósito
Programação Programação MistaMista-- SolverSolver
Localização Localização de Depósitode Depósito
Uma companhia distribuidora quer minimizar o custo de transporte de bens de 
seus depósitos A, B e C para as lojas de varejo 1, 2 e 3. Os custos para 
transportar uma unidade de um depósito para uma loja de varejo são dados 
na tabela abaixo:
Os custos fixos de operar os depósitos A, B e C são 5.000, 750 e 600 
respectivamente. Pelo menos dois deles devem operar. Os depósitos podem ser 
considerados como tendo capacidade ilimitada de armazenamento (usar qualquer 
valor maior do que 525). Formule um modelo de programação binária para 
decidir quais depósitos devem operar e a quantidade a ser transportada de cada 
depósito para cada loja de varejo.
Lojas de varejo
Depósito 1 2 3
A 15 32 21
B 9 7 6
C 11 18 5
Demanda 200 150 175
AtivAtiv. 7a. 7a–– Resolver em Excel HOJE em AULA Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
AtivAtiv. 7a. 7a–– Resolver em Excel HOJE em AULA Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
AtivAtiv. 7b. 7b–– Resolver em Excel HOJE em AULA Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
AtivAtiv. 7b. 7b–– Resolver em Excel HOJE em AULA Resolver em Excel HOJE em AULA ––
Entregar pelo Erudito Entregar pelo Erudito –– Duplas ou Trios Duplas ou Trios 
Investimentos
4158426Investimento
3209220515Retorno
7654321Projeto
Uma empresa está considerando um conjunto de projetos mostrado no 
quadro que segue. Deseja maximizar o retorno, investindo no máximo 25. 
Cada projeto está sujeito a seguintes condições
Projeto Condição
1 Nenhuma
2 Pode somente se 1 for escolhido
3 Pode somente se 2 for escolhido
4 Deve se 2 for escolhido
5 Pode somente se 1 não for escolhido
6 Pode somente se 2 e 3 não forem escolhidos
7 Pode somente se 1 for escolhido e 2 não for escolhido