7.0 Problemas de Programação Linear (PPL)

Prévia do material em texto

Pesquisa Operacional Aplicada a 
Engenharia
Problemas de Programação Linear (PPL)
• 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
• A Reage Brasil é uma indústria de reatores para usinas de 
energia nuclear 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 esta disponível para a Reage Brasil em apenas 20 
unidades. Cada 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
• 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)
• 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+ 
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)
• 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 esta fosse omitida a 
solução viável não se 
alteraria. 
• Esta restrição é 
chamada de 
redundante
Programação Linear 
Restrições Redundantes
• 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
• 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 brinco é 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
• 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)
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
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)
• Os problemas analisados até agora apresentaram 
sempre uma solução ótima, e única.
• Isto é, sempre houve uma única solução viável 
levava a função-objetivo ao 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 estes casos.
Sobre a solução ótima
• 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, e deseja saber 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
• 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
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
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)
• 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
• 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
= +
− + 

+ 
+ 

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 indefinidamente
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 indefinidamente
• 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 quandopelo 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
• 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
+
+ 
+ 

Programação Linear 
Solução Inviável – análise gráfica
122 21 + xx
152 21 + xx
• 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
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
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.)
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
• 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
• 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
• 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
• 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
• ... 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
• 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