Metodos Quantitativos - Secao 11 - EC 2016 1

Prévia do material em texto

Seção 11EC 2016 1 1
Métodos Quantitativos
Prof. Gerson Lachtermacher
Prof. Paulo Sérgio de Souza Coelho
Seção 11EC 2016 1 2
 Programação Inteira
 Solução Gráfica
 Solução Excel
 Caso GLP Tecnologia S.A.
 Variáveis Binárias 
 Condições Lógicas
 Custos Fixos
Conteúdos da Seção
Seção 11EC 2016 1 3
 São PPLs em que uma ou mais variáveis de decisão apresentam 
restrições especiais de domínio:
 Variável inteira: a variável só pode assumir valores do conjunto
ℤ = {… ,−3,−2,−1, 0, 1, 2, 3, … }
 Variável binária: a variável só pode assumir valores do conjunto 
𝔹 = {0,1}
 Quando usar?
 Variáveis racionais (sem restrição de domínio) servem para valores 
que são contados (pessoas, veículos, localidades, etc.)
 Variáveis inteiras servem para valores que são medidos (distância, 
volume, tamanho, etc.)
 Variáveis binárias servem para representar uma situação que só tem 
duas possibilidades (sim ou não, faz ou não faz, tem ou não tem, etc.)
Problemas de programação Inteira
Seção 11EC 2016 1 4
 Considere resolver o seguinte problema:
Programação Inteira
O Problema Relaxado
e inteiros
0, 
1123 
1332 ..
24 
21
21
21
21




xx
xx
xxrs
xxMax
Considere o Problema Relaxado:
• O problema com a mesma função-
objetivo e as mesmas restrições
• Mas sem a restrição de domínio (de
variáveis inteiras/binárias)
Seção 11EC 2016 1 5
Programação Inteira
Solução do Problema Relaxado
0, 
1123 
1332 ..
24 
21
21
21
21




xx
xx
xxrs
xxMax
Z=26
Solução Ótima
(6,5 ; 0)
Z=11,6
Z=14,33
Seção 11EC 2016 1 6
 Usando o arredondamento da solução relaxada
Programação Inteira
Solução do Problema Original
e inteiros
0, 
1123 
1332 ..
24 
21
21
21
21




xx
xx
xxrs
xxMax
A região viável 
são somente 
os pontos 
inteiros
Z=24
Solução Ótima para
Prog.Inteira
(6;0)
Seção 11EC 2016 1 7
 A estratégia usada (resolver o problema relaxado e arredondar os
valores ótimos encontrados para cada uma das variáveis) nem
sempre é efetiva
 Por exemplo:
 Nenhum ponto inteiro vizinho ao 
ponto ótimo do problema 
relaxado é viável!
 Às vezes um dos vizinhos é viável mas:
 Não é necessariamente o 
ponto ótimo inteiro.
Programação Inteira
A aproximação pode dar errado?
x2
x1
Solução 
Ótima para
Prog.Inteira
Solução 
Ótima para
LP Relaxado
Seção 11EC 2016 1 8
 Para problemas de grande porte a aproximação geralmente leva a 
uma solução aceitável (próxima do ótimo real)
 A violação das restrições é tolerável
 Quando quiser obter a solução inteira exata:
Programação Inteira
Resolvendo no Excel
Seção 11EC 2016 1 9
1. A Programação Inteira leva muito mais tempo para ser resolvida
 Isso porque diversos problemas relaxados são resolvidos 
sucessivamente para se obter a solução de um problema inteiro.
2. Ao resolver uma Programação Inteira o Excel não provê relatório 
de sensibilidade ou de limites
 Para fazer análises econômicas (preço de sombra e custo reduzido) é 
necessário alterar o problema, obter nova solução e comparar os 
resultados
 Algumas vezes a solução relaxada já oferece valores inteiros, então 
sempre tente resolver sem definir que o problema é inteiro
Programação Inteira
Pense bem antes de usar
Seção 11EC 2016 1 10
 Um representante comercial deseja definir sua força de vendas e 
deve alocar pessoas para trabalhar na sede da empresa ou no 
interior
 Ele sabe que as pessoas que trabalham na sede costumam realizar 
R$5 milhões de vendas mensais, e as pessoas no interior costumam 
realizar R$4 milhões de vendas mensais
 O salário mensal na sede é de R$2.000 e o salário mensal no interior 
é R$1.500
 Sabendo que há um total de 50 pessoas que pode ser alocada e 
um orçamento de R$80.000 para despesas com salários, como o 
representante deve alocar as pessoas?
Usando Solver do Excel
O Caso do Representante Comercial
Seção 11EC 2016 1 11
 Especificar a
restrição de domínio
(variáveis inteiras)
é desnecessário e
1. tornaria o problema 
mais complexo 
2. Não haveria todos
os relatórios
 Alternativamente, o que ocorreria se o orçamento para salário 
fosse de R$79.900?
Caso do Representante Comercial
Solução Relaxada já é inteira
Seção 11EC 2016 1 12
 Neste caso, a 
solução relaxada 
não é inteira e
 Aproximar a solução
não funciona:
 10 na sede e 40 no
interior não é
viável
 Quando a solução relaxada não é inteira é conveniente impor a 
restrição de domínio no Excel
Caso do Representante Comercial
Solução Relaxada que não é inteira
Seção 11EC 2016 1 13
 A solução inteira
correta foi obtida
através do Solver:
Caso do Representante Comercial
Solução Inteira
Seção 11EC 2016 1 14
 A GLP Tecnologia S/A tem que escolher quais investimentos fazer. 
 Foram pré-selecionados 3 projetos 
 O objetivo é maximizar o VPL (valor presente líquido)
 Os gastos em cada ano estão restritos ao orçamento
 Os dados relevantes encontram-se na tabela:
Caso GLP Tecnologia S/A
Investimento Líquido Requerido em milhões de R$
Proj. VPL Ano 1 Ano 2 Ano 3 Ano 4 Ano 5
1 104,01 70 15 0 20 20
2 123,81 80 30 15 10 10
3 170,35 130 20 0 30 20
Orçamento disponível 200 70 50 30 70
Seção 11EC 2016 1 15
 Variáveis de Decisão são binárias:
 Função Objetivo = Maximizar o somatório VPL
Caso GLP Tecnologia S/A
1 , se o projeto i for selecionado 
= 1, 2,3
0 , se o projeto i não for selecionado
ix i
 
 

1 2 3 104,01 123,81 170,35Max x x x 
Seção 11EC 2016 1 16
 Restrições Orçamentárias
Caso GLP Tecnologia S/A
1 2 3
1 2 3
2
1 2 3
1 2 3
70 80 130 200 - Ano 1
15 30 20 70 - Ano 2
15 50 - Ano 3
20 10 30 30 - Ano 4
20 10 20 70 - Ano 5
x x x
x x x
x
x x x
x x x
  
  

  
  
Seção 11EC 2016 1 17
Caso GLP Tecnologia S/A 
Modelo no Excel
Seção 11EC 2016 1 18
Caso GLP Tecnologia S/A 
Parâmetros do Solver
Seção 11EC 2016 1 19
Caso GLP Tecnologia S/A 
Solução no Excel
Seção 11EC 2016 1 20
 As variáveis binárias também se prestam a selecionar alternativas
que sejam condicionais.
 No exemplo anterior imagine que não mais de um dos projetos 1,
3 e 4 pudesse ser selecionado. Deveríamos então adicionar:
 Se apenas um dos projetos e apenas um dos projetos 1, 2 e 4
tivesse que ser escolhido obrigatoriamente, deveríamos incluir:
Variáveis Binárias e
Condições Lógicas
1 3 4 1x x x  
1 2 4 1x x x  
Seção 11EC 2016 1 21
 Imagine agora que o projeto 1 dependa de uma tecnologia que 
deve ser desenvolvida pelo projeto 2
 Isto é, o projeto 1 só pode ser aprovado se o projeto 2 também for 
 Deve-se então incluir a restrição:
Variáveis Binárias e
Condições Lógicas
1 2
1 2
1 2
1 2
1 2
0, 0 nenhum dos projetos aceitos
1, 1 ambos os projetos aceitos 
0
0, 1 apenas o projeto 2 foi aceito
1, 0 inviável 
x x
x x
x x
x x
x x
  
   
  
  
   
1 2
1 2
1 2
1 2
1 2
0, 0 nenhum dos projetos aceitos
1, 1 ambos os projetos aceitos 
0
0, 1 apenas o projeto 2 foi aceito
1, 0 inviável 
x x
x x
x x
x x
x x
  
   
  
  
   
Seção 11EC 2016 1 22
 Imagine a seguinte situação:
 Você pode produzir até 600 unidades de certo item, mas há o custo 
variável de R$50 por unidade e o custo fixo de R$5.000para 
configuração do equipamento de produção
 Se não for produzir não precisa pagar o custo fixo
 Modelagem:
 Se 𝑥1 é a quantidade produzida então 50𝑥1 é o custo de produção
 Se 𝑦1 = ቊ
1 se for produzir
0se não
, 5000𝑦1 é o custo fixo de configurar
 E como combinar que 𝑥1 > 0 somente quando 𝑦1 = 1?
 Usa-se uma restrição como 𝑥1 ≤ 600𝑦1
Variáveis Binárias e Custos Fixos
Seção 11EC 2016 1 23
 A fábrica produz três tipos de furadeiras.
 Para começar a fabricar cada tipo é necessário configurar a fábrica, 
e há um custo fixo.
 Todas as furadeiras do mesmo tipo serão produzidas de uma só vez 
(apenas uma preparação por tipo). 
 Os dados de tempo, lucro e custo são:
Caso LCL Furadeiras
Tipo 1 Tipo 2 Tipo 3 Total Disponível
Montagem 2h/unid 3h/unid 2,5h/unid 600h
Pintura 3h/unid 2h/unid 2,5h/unid 500h
Lucro Unitário R$50 R$60 R$65
Preparação R$5.000 R$4.000 R$3.000
Seção 11EC 2016 1 24
Caso LCL Furadeiras
Variáveis de Decisão e Função Objetivo
 Variáveis de Decisão
 Função-Objetivo
 1,2,3i 
0 se 0,
 0 se 1,
1,2,3)(i i produto do produzidaser a Quantidade








i
i
i
i
X
X
Y
X
321321 300040005000656050 YYYXXXMax 
Seção 11EC 2016 1 25
 Restrições de Produção
 Restrições de ligação de Variáveis
Caso LCL Furadeiras
Restrições
5005,223
6005,232
321
321


XXX
XXX
.suficiente o grande é que nº um é 600 :
600
600
600
33
22
11
Obs
YX
YX
YX



Não há limite de produção, entretanto:
• se fossem produzidas apenas furadeiras do 
tipo 1 a capacidade é de 
500
3
= 166 unidades;
• Para o tipo 2, a capacidade é de 200 unidades
• Para o tipo 3, 200 unidades
Foi usado 600 como um número grande o 
bastante para os 3 tipos de furadeira
Seção 11EC 2016 1 26
Caso LCL Furadeiras
Modelo no Excel
Seção 11EC 2016 1 27
Parâmetros do Solver
Seção 11EC 2016 1 28
Caso LCL Furadeiras
Solução Ótima