Metodos Quantitativos - Secao 07 - EC 2016 1

Prévia do material em texto

Seção 7EC 2016 1 1
Métodos Quantitativos
Prof. Gerson Lachtermacher
Prof. Paulo Sérgio de Souza Coelho
Seção 7EC 2016 1 2
 Problemas de Programação Linear (PPL)
 Situações especiais:
• Restrições Redundantes
• Soluções Ótimas Múltiplas
• Solução Ótima Ilimitada
• Sem solução viável
 Hipóteses sobre o mundo real para que possa ser modelado por um 
PPL
 Método Simplex
 Teoremas Fundamentais
 Verificação Geométrica
 Aplicações de otimização em negócios 
Conteúdo da Seção
Seção 7EC 2016 1 3
 A Reage Brasil é uma indústria de reatores para usinas de energia
nuclear que produz reatores de dois tipos, um aspirado a água e
outro aspirado a ar.
 Há demanda para um total de 7 reatores neste ano, mas a Reage
Brasil sabe que, individualmente, há demanda para até 5 reatores
aspirados a água e para 4 reatores aspirados a ar.
 O processo de fabricação envolve um núcleo radioativo que está
disponível para a Reage Brasil em apenas 20 unidades. Cara reator
aspirado a água precisa de 2 núcleos, e o aspirado a ar precisa de 3
núcleos.
 Se a Reage Brasil tem uma expectativa de lucro de R$ 4 milhões
por reator aspirado a água e de R$2 milhões por reator aspirado a
ar, como ela deve planejar sua produção para este ano?
Produção Radioativa
Seção 7EC 2016 1 4
 Quem decide?
 O que o decisor deve decidir?
 Com que objetivo ele deve tomar a decisão?
 Com que restrições a decisão será tomada?
Produção Radioativa
– A Reage Brasil
– Quantas unidades de cada reator produzir neste ano
– Chamemos de x1 e x2 o total de unidades de reator aspirado a água e a ar,
respectivamente, que serão produzidas neste ano
–Maximizar o Lucro Total
–Demanda total
–Demanda do reator aspirado a água
–Demanda do reator aspirado a ar
–Quantidade disponível de matéria-prima (núcleos radioativos)
Seção 7EC 2016 1 5
 Função-objetivo
 Maximizar o lucro total
 Restrições
 Demanda total
 Demanda do aspirado a água
 Demanda do aspirado a ar
 Núcleos radioativos
 Não Negatividade
O Modelo para a Produção Radioativa
1 0x 2 0x 
e
1 24 2Max Z x x 
1 5x 2 4x 
1 2 7x x 
1 22 3 20x x 
Seção 7EC 2016 1 6
Programação Linear 
Solução Gráfica
1 22 3 20x x 
1 2 7x x 
Z = 24Z = 20Z = 8
A opção mais lucrativa é 
produzir 5 reatores 
aspirados a água e 
somente 2 a ar.
O lucro total será de
R$24 milhões
(5 ; 2)
Seção 7EC 2016 1 7
 Examinando a região 
viável, percebemos que 
uma restrição não faz 
parte do conjunto de 
arestas que delimitam a 
região viável.
 Se essa fosse omitida, a 
solução viável não se 
alteraria. 
 Essa restrição é chamada 
de redundante.
Programação Linear 
Restrições Redundantes
Seção 7EC 2016 1 8
 Uma restrição é dita redundante quando a sua exclusão do
problema não altera o conjunto de soluções viáveis deste.
 É uma restrição que não participa formando nenhuma aresta do
conjunto de soluções viáveis.
 Existe um outro problema sem essa restrição que tem o mesmo
conjunto de soluções viáveis e, principalmente, a mesma solução
ótima.
Programação Linear 
Restrições Redundantes
Seção 7EC 2016 1 9
 Um artesão faz colares e brincos para vender num bazar que
acontece todos os dias. Ele os vende por R$10,00 e R$5,00,
respectivamente. Ele nunca conseguiu vender mais de 10
colares e 8 brincos por dia. Um colar é feito em 20 minutos,
enquanto um anel é feito em 40 minutos. O artesão trabalha
4 horas por dia antes de ir para o bazar. Quantos colares e
quantos brincos ele deve produzir para maximizar a sua
receita diária?
O Problema do Artesão
Seção 7EC 2016 1 10
 Quem decide?
 O que o decisor deve decidir?
 Com que objetivo ele deve tomar a decisão?
 Com que restrições a decisão será tomada?
O Problema do Artesão
– O artesão
– Quantos colares e brincos deve produzir por dia
– Chamemos de x1 e x2 as quantidades de colares e brincos que ele faz
por dia, respectivamente
– Maximizar sua receita
– Tempo para produção
– Demanda dos consumidores (colares/brincos)
Seção 7EC 2016 1 11
O Modelo para a 
Decisão do Artesão
• Função-objetivo
– Maximizar a receita
• Restrições
– Demanda de Colares
– Demanda de Brincos
– Tempo Padrão
– Não Negatividade
1 210 5Max Z x x 
1 10x 
2 8x 
1 220 40 240x x 
1 0x 2 0x 
e
Seção 7EC 2016 1 12
1 10x 
2 8x 
1 220 40 240x x 
A análise gráfica para o
Problema do Artesão
Z = 105Z = 30Z = 0
A opção com maior receita 
total é produzir 10 colares 
e 1 brinco.
A receita total será de
R$105.
(10 ; 1)
Seção 7EC 2016 1 13
 Os problemas analisados até agora apresentaram sempre uma
solução ótima, e única.
 Isto é, sempre houve uma única solução viável que levava a
função-objetivo a seu valor ótimo.
 Entretanto, existem problemas nos quais observamos:
 Múltiplas Soluções Ótimas;
 Solução Ótima Ilimitada (infinita);
 Não haver solução viável, portanto sem solução ótima.
 Vamos examinar esses casos.
Sobre a solução ótima
Seção 7EC 2016 1 14
 Um cozinheiro faz dois tipos de quentinha para os
funcionários de uma empresa. O custo total de produção é
de R$4,00, para os dois tipos de quentinha.
 Ele tem um contrato de entregar diariamente pelo menos 15
quentinhas, de qualquer tipo, por dia.
 A quentinha de lasanha é feita em dois minutos e a
quentinha de frango em 4 minutos. O cozinheiro dispõe de
apenas 48 minutos para embalar as quentinhas.
 Hoje o cozinheiro está sem caixa para comprar a matéria-
prima, quantas quentinhas do tipo 1 e do tipo 2 ele deve
produzir para cumprir o contrato com o menor custo
possível?
O Problema das quentinhas
Seção 7EC 2016 1 15
 Quem deve tomar a decisão?
 O cozinheiro
 O que o decisor deve decidir?
 Quantas quentinhas do tipo 1 e do tipo 2 deve produzir hoje
 Chamemos de x1 e x2 as quantidades de quentinhas do tipo 1 e 2 que 
ele fará hoje, respectivamente.
 Com que objetivo ele deve tomar a decisão?
 Obter o custo mínimo
 Com que restrições a decisão será tomada?
 Tempo para produção
 Contrato de entrega
O Problema das quentinhas
Seção 7EC 2016 1 16
O Modelo para a 
Decisão do Cozinheiro
• Função-objetivo
– Minimizar o custo
• Restrições
– Contrato
– Tempo Padrão
– Não Negatividade
1 24 4Min Z x x 
1 2 15x x 
1 22 4 48x x 
1 0x 2 0x 
e
Seção 7EC 2016 1 17
Problema das quentinhas
Solução Gráfica
1 2
20
4 4 20
Z
x x

 1 2
60
4 4 60
Z
x x

 
Múltiplas Soluções 
Ótimas
1 2 15x x 1 22 4 48x x 
(6;9)
Seção 7EC 2016 1 18
 Um problema é dito como de Soluções Múltiplas quando mais de 
uma solução viável levam a função objetivo ao mesmo valor 
ótimo, isto é, existem soluções múltiplas;
 Esta situação ficará melhor formalizada, mas é possível garantir 
que se mais de uma solução viável é ótima, então existem infinitas 
soluções ótimas
 Correspondem ao segmento de reta destacado no gráfico anterior.
 Soluções Múltiplas ocorrem com alguma frequência. É comum que 
softwares apresentem uma das soluções ótimas e não explicite o 
fato.
Soluções Múltiplas
Seção 7EC 2016 1 19
 Encontrar a solução ótima:
Programação Linear 
Solução Ilimitada
1 2
1 2
2
1 2
1 2
1 2
6 10
. . 2
 6
 3 5 15
 5 4 20
 , 0
Max Z x x
s r x x
x
x x
x x
x x
 
  

 
 

Seção 7EC 2016 1 20
Programação Linear 
Solução Ilimitada – análise gráfica
x1108642
62 x
221  xx
10
14
12
x2
8
6
4
-2
2
-2
1553 21  xx
2045 21  xx
02 x
01 x
Cresce indefinidamentex1108642
62 x
221  xx
10
14
12
x2
8
6
4
-2
2
-2
1553 21  xx
2045 21  xx
02 x
01 x
Cresce indefinidamente
Seção 7EC 2016 1 21
 Um problema de programação linear apresenta solução ilimitada 
quando:
 a região viável é ilimitada 
 O valor ótimo da função-objetivo se projeta da direção em que a 
região é ilimitada.
 A região viável é ilimitada quando pelo menos uma das variáveis 
não tem nenhuma restrição de crescimento ou decrescimento.
 Graficamente, vemos que o polígono da região não está fechado.
 Uma solução ilimitada está geralmente relacionada a um problema 
que foi mal modelado.
Solução Ilimitada
Seção 7EC 2016 1 22
 Encontrar a solução ótima:
Programação Linear 
Solução Inviável
1 2
1 2
1 2
1 2
 
. . 2 12
 2 15
 , 0
Max x x
s r x x
x x
x x

 
 

Seção 7EC 2016 1 23
Programação Linear 
Solução Inviável – análise gráfica
122 21  xx
152 21  xx
Seção 7EC 2016 1 24
 Um problema de programação linear é dito inviável quando o 
conjunto de soluções viáveis é vazio
 Na ausência de soluções viáveis, não há também soluções ótimas.
 A solução inviável significa que as restrições são rigorosas demais.
 Em problemas práticos pode ser:
 Erro de modelagem
 Impossibilidade de atuação.
Programação Linear 
Solução Inviável
Seção 7EC 2016 1 25
São 3 hipóteses sobre o mundo real para que o mesmo possa ser 
modelado como um PPL:
1. Hipótese de Aditividade: 
 As atividades (variáveis de decisão) do modelo são totalmente 
independentes, ou seja, não há interdependência entre as mesmas
• Não existem no modelo termos cruzados das variáveis, ou seja, 
não há 𝑥1 × 𝑥2 ou 
𝑥1
𝑥2
2. Hipótese de Proporcionalidade: 
 O valor da função-objetivo é proporcional ao nível de atividade de 
cada variável de decisão
• O valor da função-objetivo se altera em um valor constante dada 
uma variação constante da variável de decisão – em qualquer 
nível
Programação Linear
Hipóteses
Seção 7EC 2016 1 26
3. Hipótese de Divisibilidade:
 Todas as unidades de atividade podem ser divididas em qualquer 
nível de fracionamento
 Qualquer variável de decisão pode assumir qualquer valor fracionário
 Esta hipótese pode ser quebrada, dando origem a um problema 
especial de programação linear, chamado de problema inteiro.
• Problemas inteiros serão estudados neste curso.
Programação Linear
Hipóteses (cont.)
Seção 7EC 2016 1 27
O Procedimento de busca da solução ótima é baseado em 3 
teoremas fundamentais:
 Teorema I
 O conjunto de todas as soluções viáveis de um modelo de 
Programação Linear formam um conjunto convexo.
 Teorema II
 Se a função-objetivo possui um único ótimo finito, então esta 
solução ótima é um ponto extremo do conjunto convexo de 
soluções viáveis.
 Teorema III
 Se a função-objetivo assume o ótimo em mais de um ponto 
extremo do conjunto de soluções viáveis, então ela toma o 
mesmo valor para qualquer ponto do segmento da reta que 
une esses pontos extremos.
Método Simplex
Teoremas Fundamentais
Seção 7EC 2016 1 28
 Conjunto Convexo em ℝ2
 Para quaisquer dois pontos do conjunto, todos os pontos que 
formam o segmento de reta que os unem fazem parte do conjunto. 
Programação Linear 
e Convexidade
Conjunto
Convexo
Conjunto não
Convexo
Seção 7EC 2016 1 29
 Considere o problema e sua solução gráfica: 
Teoremas Fundamentais
interpretação geométrica
1 2
1
2
1 2
1
2
5 2
. .
3
4
2 9
0
0
Max Z x x
s r
x
x
x x
x
x
 


 


x2
x1
(0,4)
(1,4)
(0,0) (3,0)
(3,3)
21=5x1+2x2
Solução
Viável
Seção 7EC 2016 1 30
 Nos pontos extremos temos os seguintes valores para Z
Teoremas Fundamentais
interpretação geométrica
x2
x1
(0,4)
(1,4)
(0,0) (3,0)
(3,3)
z
pontos
extremosA B C D E
21
15
13
8
A B
C
D
E
Seção 7EC 2016 1 31
 O valor da função-objetivo varia quando esta se desloca;
 O valor ótimo (mínimo ou máximo) será obtido deslocando-se o
máximo ou o mínimo a função-objetivo;
 Ela necessariamente esbarrará em um vértice...
Teoremas Fundamentais
interpretação geométrica – Teorema II
x2
x1
(0,4)
(1,4)
(0,0) (3,0)
(3,3)
Mínimo =A
B
C = máximo
D
E
Seção 7EC 2016 1 32
 ... ou numa aresta
 quando a função-objetivo tiver uma inclinação tal que no ponto 
ótimo ela coincida com a inclinação de alguma restrição.
Teoremas Fundamentais
interpretação geométrica – Teorema III
x2
x1
(0,4)
(1,4)
(0,0)
(3,0)
(3,3)
B
D
E
Soluções
Múltiplas
Em todos os pontos do 
segmento de reta CD, o 
valor da função-objetivo 
é o mesmoA
C
x2
Seção 7EC 2016 1 33
 Gestão da Produção
 Escolha de opções de roteamento
 Localização de rede de distribuição
 Planejamento de tempo, agendamento e escalas;
 Alocação de recursos limitados para produção, venda ou consumo
 Gestão Financeira
 Escolha de opções de financiamento 
 Estudo sobre capacidade de endividamento, pagamento;
 Gestão Comercial
 Planejamento regional
 Alocação de recursos em Marketing em diferentes mídias
 Gestão de Pessoas
 Alocação de recursos
 Planejamento salarial
Aplicações de Otimização Matemática
em Negócios