Programação Linear: Solução Gráfica

Prévia do material em texto

Pesquisa Operacional – Aula 4
Profª. M.Sc. Júlia S. Humberto
Plano de aula
• Objetivo
─ Entendimento do aluno acerca de Modelagem de Problemas Gerenciais.
• Conteúdos
Programação linear: solução gráfica
• Metodologia de Ensino
– Aula expositiva
• Atividades
– Resolução de exercícios
• Leitura Obrigatória
– Nenhuma
• Leitura Recomendada
Revisão
PROGRAMAÇÃO LINEAR
A programação linear usa um modelo matemático para descrever
o problema em questão. O adjetivo linear significa que todas as
funções matemáticas nesse modelo são necessariamente funções
lineares. A palavra programação, nesse caso, não se refere à
programação e computador; ela é, essencialmente, um sinônimo
para planejamento.
Portanto, a programação linear envolve o planejamento de
atividades para obter um resultado ótimo, isto é, um resultado
que atinja o melhor objetivo especificado (de acordo como
modelo matemático) entre todas as alternativas viáveis.
Modelo de PL com 
duas variáveis
Obter os dados básicos do problema
• Estruturar o problema:
– Variáveis de decisão
– Função objetivo
– Restrições técnicas
– Resolução gráfica
Passo a passo
1. Interpretar o problema de programação linear;
2. Identificar as variáveis de decisão
3. Estruturar a função objetivo para a geração do máximo lucro
4. Estipular as restrições técnicas do sistema em inequações
5. Resolver analiticamente as equações
6. Criar e plotar pares ordenados no plano cartesiano
7. Construir graficamente o problema
8. Localizar a área de solução no plano cartesiano
9. Determinar o máximo lucro de forma gráfica
Exemplo: Companhia Reddy Mikks
A Reddy Mikks produz tintas para interiores e exteriores com base em duas
matérias-primas, M1 e M2. A tabela abaixo apresenta os dados básicos do
problema:
Produção de tintas da Reddy Mikks
Toneladas de matéria-prima
por tonelada de Disponibilidade 
máxima diária (ton)
Tinta para 
exteriores
Tinta para 
interiores
Matéria prima, M1 6 4 24
Matéria prima, M2 1 2 6
Lucro por tonelada (R$ 1000) 5 4
Uma pesquisa de mercado indica que a demanda diária de
tinta para interiores não pode ultrapassar a de tintas para
exteriores por mais de 1 tonelada. Além disso, a demanda
máxima diária de tinta para interiores é 2t.
 A Reddy Mikks quer determinar o mix ótimo (o melhor)
de produtos de tintas para interiores e exteriores que
maximize o lucro total diário.
Exemplo
1ª etapa: Dados do problema
2ª etapa: Estruturar o problema
a) Identificar as variáveis de decisão:
X1 = toneladas de tinta para exteriores produzidas diariamente
X2 = toneladas de tinta para interiores produzidas diariamente
b) Definir a função objetivo:
Maximizar Z = 5 𝑋1+ 4 𝑋2
c) Estipular as restrições técnicas:
Restrição de disponibilidade diárias:
– Matéria-prima M1: 6𝑋1 + 4𝑋2 ≤ 24
– Matéria-prima M2: 𝑋1 + 2𝑋2 ≤ 6
Restrição de demanda:
- Limite de mercado: 𝑋2 − 𝑋1≤ 1
- Limite de demanda: 𝑋2 ≤ 2
Restrição de não negatividade: 𝑋1≥ 0 e 𝑋2 ≥ 0
Exemplo
Modelo completo da Reddy Mikks:
Maximizar Z = 5 𝑋1+ 4 𝑋2
Sujeito a:
6𝑋1 + 4𝑋2 ≤ 24
𝑋1 + 2𝑋2 ≤ 6
−𝑋1 − 𝑋2 ≤ 1
𝑋2 ≤ 2
𝑋1, 𝑋2 ≥ 0
(1)
(2)
(3)
(4)
(5)
Exemplo
3ª etapa: Transformar inequações em equações:
(1): 6𝑋1 + 4𝑋2 ≤ 24
6𝑋1 + 4𝑋2 = 24
(2): 𝑋1 + 2𝑋2 ≤ 6
𝑋1 + 2𝑋2 = 6
(3): −𝑋1 + 𝑋2 ≤ 1
−𝑋1 + 𝑋2 = 1
(4): 𝑋2 ≤ 2
𝑋2 = 2 
Como 𝑋1 = 0 : 6 . (0) + 4𝑋2 = 24
Então: 𝑋2 = 24/4 = 6
Como 𝑋2 = 0 : 𝑋1 + 2 . (0) = 6
Então: 𝑋1 = 6
Mesmo raciocínio para os demais pontos.
A (0, 6)
B (4, 0)
C (0, 3)
D (6, 0)
E (0, 1)
F (2,5, 3,5)
G (0,2)
H (4,2)
𝑋_1
Exemplo
4ª etapa: Construir de forma gráfica
1 2 3 4 5
1
2
3
4
5
A (0, 6)
B (4, 0)
𝑋1
𝑋2
C (0, 3)
E (0, 1)
𝟏
𝟐
𝟑
D (6, 0)
F (2,5 , 3,5)
G (0, 2)
H (4 , 2) 𝟒
6 7
6
W (0,0 )
𝑋_1
Exemplo
5ª etapa: Testando o ponto “W” e determinando a região de solução
6𝑋1 + 4𝑋2 ≤ 24
6 . (0) + 4 . (0) ≤ 24
0 ≤ 24
VERDADEIRO
A região que contém o
Ponto “W” pertence a
região de solução no gráfico
W (0, 0)
𝑋1 + 2𝑋2 ≤ 6
0 ≤ 6
VERDADEIRO
A região que contém o
Ponto “W” pertence a
região de solução no
gráfico
W (0, 0)
𝑋2 - 𝑋1 ≤ 1 
0 ≤ 1
VERDADEIRO
A região que contém o
Ponto “W” pertence a
região de solução no
gráfico
W (0, 0)
𝑋2 ≤ 2 
0 ≤ 2
VERDADEIRO
A região que contém o
Ponto “W” pertence a
região de solução no
gráfico
W (0, 0)
𝑋_1
Exemplo
6ª etapa: Determinar a região solução
1 2 3 4 5
1
2
3
4
5
A (0, 6)
B (4, 0)
𝑋1
𝑋2
C (0, 3)
E (0, 1)
𝟏
𝟐
𝟑
D (6, 0)
F (2,5 , 3,5)
G (0, 2)
H (4 , 2) 𝟒
6 7
6
W (0,0 )
𝑋_1
Exemplo
7ª etapa: Identificar os pontos máximos da região solução
K (?, ?)
1 2 3 4 5
1
2
3
4
5
𝑋1
𝑋2
6 7
6
E (0, 1)
𝟒
𝟐
B (4, 0)W (0,0 )
𝟏
Y (?, ?) V (?, ?)
𝟑
Exemplo
8ª etapa: Achar os pontos “K, Y e V” do gráfico
 
𝑋2 − 𝑋1 = 1
𝑋2 = 2
 
𝑋1 + 2𝑋2 = 6
𝑋2 = 2
 
6𝑋1 + 4𝑋2 = 24
𝑋1 + 2𝑋2 = 6
K 
2 − 𝑋1 = 1
𝑋1 = 1
K (1,2)
Y 
𝑋1 + 2.2 = 6
𝑋1 = 2
Y (2,2)
V 
6𝑋1 + 4𝑋2 = 24
𝑋1 = 6 − 2𝑋2
6(6 − 2𝑋2) + 4𝑋2 = 24
36 − 12𝑋2 + 4𝑋2 = 24
-8𝑋2 = 24 − 36
𝑋2 = 12/8 = 1,5
V (3, 1,5)
𝑋1 + 2 . 1,5 = 6 𝑋1 =3
Exemplo
9ª etapa: Substituir os pontos extremos da região de solução na
função objetivo e encontrar o ponto de máximo lucro.
PONTO FUNÇÃO OBJETIVO LUCRO (Z)
(R$ 1000)
W (0, 0) Max Z = 5(0)+4(0)= 0
E (0, 1) Max Z = 5(0)+4(1)= 4
K (1,2) Max Z = 5(1)+4(2)= 13
Y (2, 2) Max Z = 5(2)+4(2)= 18
V (3, 1,5) Max Z = 5(3)+4(1,5)= 21
B (4, 0) Max Z = 5(4)+4(0)= 20
Conclusão: Isso representa um mix de 
produto diário de 3 t de tina para 
exteriores e 1,5 t de tinta para 
interiores. O lucro unitário é $21.000.
Exemplo
O modelo completo da Reddy Mikkes é:
Maximizar Z = 5𝑋1 + 4𝑋2
Sujeito a:
6𝑋1 + 4𝑋2≤ 24
𝑋1 + 2𝑋2≤ 6
−𝑋1 + 𝑋2≤ 1
𝑋2≤ 2
𝑋1, 𝑋2≥ 0
Por exemplo: a solução 𝑋1= 3t/d e 𝑋2 = 1 t/d é viável?
Sim! Não viola nenhum das restrições.
E a solução 𝑋1= 4t/d e 𝑋2 = 1 t/d é viável?
Não! Não satisfaz a restrição 1.
(1)
(2)
(3)
(4)
(5)
Atividade
1. Construa para o modelo Reddy Mikks, cada uma das
seguintes restrições e as expresse com o lado esquerdo linear
e o lado direto constante.
Atividade
2. Determine a melhor solução viável entre as seguintes soluções
(viáveis e inviáveis) do modelo da Reddy Mikks:
3. Para a solução viável X1 = 2, X2 = 2 do modelo da Reddy Mikks
determine as quantidades não utilizadas das matérias–primas M1
e M2.
ATIVIDADE
Uma empresa que funciona 10 horas por dia fabrica dois produtos
em três processos sequenciais. A tabela resume os dados do
problema.
Determine o mix ótimo dos dois produtos. Resolva o problema
graficamente.
Minutos por unidade Lucro por
unidade ($)Produto Processo 1 Processo 2 Processo 3
1 10 6 8 2
2 5 20 10 3
ATIVIDADE
A Burroughs Garment Company fabrica camisas masculinas e blusas
femininas para a Walmark Discount Stores. A Walmark aceitará toda a
produção fornecidas pela Burroughs. O processo de produção inclui cortar,
costurar e embalar. A Burroughs emprega 25 trabalhadores no
departamento de corte, 35 no departamento de costura e 5 no
departamento de embalagem. A empresa trabalha em turno de 8 horas por
dia, 5 dias por semana. A tabela dá os requisitos de tempo e os lucros por
unidade para as duas peças de vestuário.
Determine a programação semanal ótima de produção para a Burroughs.
Minutos por unidade Lucro por
unidade ($)Peça Corte Costura Embalagem
Camisas 20 70 12 8
Blusas 60 60 4 12