EAD350 Aula07 2014 2sem alunos

Prévia do material em texto

EAD 350
 Pesquisa Operacional
Aula 07
Prof. Cesar Alexandre de Souza
calesou@usp.br
FEA/USP
Aviso! - Dia 30/09/14 - Prova
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 Atividades
Hoje completaremos 7 atividades, colocarei mais uma (atividade 8) para realização opcional.
Quem realizou pelo menos 6 atividades 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
Quem tiver realizado as 8 atividades, receberá 0,5 ponto “extra”!
8 atividades – 3,5
Programação Binária - Conceito
A programação binária é um caso especial da programação inteira
Quando as variáveis de decisão em um problema só são permitidas a assumir valores 0 ou 1, tem-se o caso de programação binária.
O número de aplicações para este tipo de problema é muito grande: sempre que se deseja indicar como solução um conjunto de decisões do tipo sim/não interdependentes pode-se aplicar a programação binária
Uma decisão do tipo sim/não pode ser modelada por uma variável binária, fazendo-se 1=sim e 0=não
Programação Binária – Ativ. 6A
Para modelar esse problema com a programação binária utilizaremos 4 variáveis binárias representando a decisão (0=não faz o projeto; 1 = faz o projeto)
A partir daí, elabora-se o modelo matemático:
Função Objetivo: Max Z (VPL) = 9X1+5X2+6X3+4X4
Restrições:
Capital: 
 6X1+3X2+5X3+2X4 <= 10
Depósito somente onde há fábricas: 
X3 <= X1  -X1+X3 <=0
X4 <= X2  -X2+X4 <=0
Variáveis X1, X2, X3 e X4 Binárias	
Programação Binária – Ativ. 6B
Aplicação de Variáveis Binárias
De n possibilidades 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 
Decisões dependentes. Não selecionar a alternativa k a não ser que seja selecionada antes a alternativa m. A restrição xk < xm ou xk - xm < 0 impõe esta condição.
Rua F
Rua G
Rua H
Rua J
Rua K
Rua B
Rua C
Rua E
Rua D
Rua A
Rua I
c8
c7
c4
c5
c1
c2
c6
c3
Instalar, a custo mínimo, câmeras de segurança cobrindo todas as ruas
Ativ 7A – Entregar Pelo Erudito, Hoje
Rua F
Rua G
Rua H
Rua J
Rua K
Rua B
Rua C
Rua E
Rua D
Rua A
Rua I
c8
c7
c4
c5
c1
c2
c6
c3
O condomínio tem verba para instalar apenas 3 câmeras. Quais devemos instalar?
Ativ 7 B– Entregar Pelo Erudito, Hoje
As câmeras ainda são variáveis (Ci = 0 ou Ci = 1) , mas a quantidade que podemos adquirir é uma nova restrição (3 câmeras)
As Ruas passam a ser variáveis também! (Ri = 0 ou Ri = 1). 
A configuração (quais câmeras “enxergam” quais ruas) continua sendo representada por restrições. 
Qual a nova função objetivo Z? Como incorporar as variáveis Ri nas restrições de configuração? 
(Dica: Assim como na ativ. 6A, há uma precedência – decisão dependente - que deve ser respeitada)
Rua F
Rua G
Rua H
Rua J
Rua K
Rua B
Rua C
Rua E
Rua D
Rua A
Rua I
c8
c7
c4
c5
c1
c2
c6
c3
O condomínio tem verba para instalar apenas 3 câmeras. Na tabela temos quantas casas existem em cada rua. Quais devemos instalar?
Ativ 8 – Opcional – (Variação da 7B)
Rua
Qtd.Casas
A
10
B
11
C
13
D
9
E
6
F
18
G
20
H
5
I
6
J
8
K
8
Elabore o novo modelo matemático para essa variação do problema 7 A