Programação Linear - Conceitos e Exemplos

Prévia do material em texto

PESQUISA OPERACIONAL
AULA 2 – PROGRAMAÇÃO LINEAR
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
Conteúdo Programático
1. Definição 
2. Modelos de Programação Linear
3. Formulações do PPL
4. Formulações equivalentes
5. Características do PPL
6. Teoremas importantes
7. Resolução gráfica do PPL
8. Exemplos 
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
DEFINIÇÃO
A Programação Linear trata de modelos de programação 
matemática onde as restrições e a função objetivo são lineares
Modelagem matemática
Função-objetivo
Condição de não-negatividade
Conjunto de restrições
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
FORMULAÇÃO DO PROBLEMA DE PROGRAMAÇÃO LINEAR
(PPL)
0
0
;0
,
,,1
2
1
2211
33232131
22222121
11212111
2211








n
mnmnmm
nn
nn
nn
nn
x
x
x
bxaxaxa
bxaxaxa
bxaxaxa
bxaxaxa
asujeito
njxcxcxcZOtimizar






 O termo otimizar 
representa 
a possibilidade de 
maximizar
ou minimizar a 
função objetivo.
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
EXEMPLO DO PROBLEMA DE PROGRAMAÇÃO LINEAR
(PPL)
Certa empresa fabrica dois produtos P1 e P2. O lucro unitário 
do produto P1 é de 1000 unidades monetárias e o lucro 
unitário de P2 é de 1800 unidades monetárias. A empresa 
precisa de 20 horas para fabricar uma unidade de P1 e de 30 
horas para fabricar uma unidade de P2. O tempo anual de 
produção disponível para isso é de 1200 horas. A demanda 
esperada para cada produto é de 40 unidades anuais para P1 
e 30 unidades anuais para P2. 
Qual é o plano de produção para que a empresa maximize seu 
lucro nesses itens? Construa o modelo de programação linear 
para esse caso.
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
Max Z = 1000x1 + 1800x2
Sujeito a: 
20x1 + 30x2 1200
x1 40
x2 30
x1 0
x2 0





MODELO DO PPL
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
EXEMPLO DO PROBLEMA DE PROGRAMAÇÃO LINEAR
Um gerente de um SPA chamado Só é Magro Quem Quer 
contrata você para ajudá-lo com o problema da dieta para os 
hóspedes. (Observe que ele paga bem: 40% do que você 
precisa!) Mais especificamente, ele precisa de você para 
decidir como preparar o lanche das 17:00h. Existem dois 
alimentos que podem ser fornecidos: cheeseburguers e pizza. 
São unidades especiais de cheeseburguers e pizza, grandes, 
com muito molho e queijo, e custam, cada, R$10,00 e 
R$16,00, respectivamente. Entretanto, o lanche tem que 
suprir requisitos mínimos de carboidratos e lipídios: 40 u.n. e 
50 u.n., respectivamente (u.n. significa unidade nutricional). 
Sabe-se, ainda, que cada cheeseburguers fornece 1 u.n. de 
carboidrato e 2 u.n. de lipídios, e cada pizza fornece 2 u.n. 
de carboidratos e 5 u.n. de lipídios. O gerente pede 
inicialmente que você construa o modelo
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
MODELO DO PPL
Min Z = 10x1 + 16x2
Sujeito a: 
x1 + 2x2 40
2x1 + 5x2 50
x1 0
x2 0



PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
FORMA REDUZIDA DO PROBLEMA DE PROGRAMAÇÃO 
LINEAR (PPL)
 
0,,,
,,2,1:
21
1
1







n
ij
n
j
ij
n
j
jj
xxx
mibxaasujeito
xcZMaximizar


PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
FORMULAÇÕES EQUIVALENTES DO PPL
0
:



x
bAxoubAx
asujeito
cxZOtimizar
Forma Canônica Forma Padrão
dadobsendo
x
bAx
asujeito
cxZOtimizar
0
0
:




PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
a quantidade de recursos consumidos por uma dada 
atividade deve ser proporcional ao nível dessa 
atividade no final do problema.
o custo total é a soma 
das parcelas associadas 
a cada atividade
identifica-se de forma separada o custo 
específico das operações de cada atividade.
CARACTERÍSTICAS DO PPL
PPLNão negatividade
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
CARACTERÍSTICAS DO PPL
Proporcionalidade
PPL AditividadeNão negatividade
Separabilidade
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
OBSERVAÇÕES SOBRE O PPL
• Divisibilidade: Todas as unidades de atividade podem ser 
divididas em qualquer nível fracional.
• Certeza: Todos os parâmetros do modelo são constantes 
conhecidas. 
Análise de sensibilidade dos resultados
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
OBSERVAÇÕES SOBRE O PPL
• Solução viável: Uma solução que satisfaz todas as restrições
do modelo.
• Solução ótima: É a melhor solução viável que atende a função
objetivo.
Podemos encontrar essa solução através dos seguintes métodos:
 Resolução gráfica (quando o problema envolve duas variáveis de 
decisão.
 Resolução analítica.
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
TEOREMAS IMPORTANTES
 Teorema 1. Se o problema de programação linear tem 
solução ótima, então esta solução está em, pelo menos, um 
ponto extremo do polígono de soluções viáveis. 
 Teorema 2. Se a região de soluções viáveis de um problema 
de programação linear é não vazia, então existe uma solução 
ótima. 
 Teorema 3. O conjunto de soluções viáveis de um problema 
de programação linear é um conjunto convexo.
 Teorema 4. O conjunto de soluções viáveis de um problema 
de programação linear tem um número finito de pontos 
extremos (vértices).
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO GRÁFICA DO PPL
Algumas observações sobre a construção de gráficos
31 x
1x
2x
2x
1x
31 x
2x
1x
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
Algumas observações sobre a construção de gráficos
2x
2x
1x
1x
32 x
32 x
9032 21  xx
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
9032 21  xx
2x
1x
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO GRÁFICA DO PPL
Considere o seguinte problema de programação linear:
Uma mulher tem R$ 10.000,00 para investir e seu corretor 
sugere investir em dois títulos, A e B. O título A é bastante 
arriscado, com lucro anual de 10% e o título B é bastante 
seguro, com lucro anual de 7%. 
Depois de algumas considerações, ela resolve investir no 
máximo R$ 6.000,00 no título A e no mínimo R$ 2.000 no título 
B. 
Como ela deverá investir seus R$ 10.000,00 a fim de maximizar 
o rendimento anual?
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO GRÁFICA DO PPL
Considere o seguinte problema de programação linear:
Max Z = 0,10x1 + 0,07x2
Sujeito a:
x1 + x2 ≤ 10.000 (I)
x1 ≤ 6.000 (II)
x2 ≥ 2.000 (III)
x1 0
x2 0

PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO GRÁFICA DO PPL
1x
2x
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO GRÁFICA DO PPL
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO GRÁFICA DO PPL
Pontos viáveis:
A (0, 2.000)
B (6.000, 2.000)
C (6.000, 4.000)
D (0, 10.000)
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO GRÁFICA DO PPL
Pontos viáveis:
A (0, 2.000) =>
B (6.000, 2.000) =>
C (6.000, 4.000) =>
D (0, 10.000) =>
Max Z = 0,10x1 + 0,07x2
Z = 0,10. 0 + 0,07.2000 = 140
Z = 0,10.6000 + 0,07.2000 = 740
Z = 0,10.6000 + 0,07.4000 = 880 => ponto
ótimo
Z = 0,10.0 + 0,07.10000 = 700
Conclusão: A mulher deverá investir R$6000 no título A e R$4000
No título B para obter um rendimento máximo de 
R$ 880,00. 
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
EXEMPLO 1
Problema do alfaiate
Max Z = 300x1 + 500x2
Sujeito a:
2x1 + x2 ≤ 16 (I)
x1 + 2x2 ≤ 11 (II)
x1 + 3x2 ≤ 15 (III) 
x1 ≥ 0
x2 ≥ 0
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
Pontos Viáveis:
A (8,0)
B (7,2) retas I e II
C (3,4) retas II e III
D (0,5) 
E (0,0)
Max Z = 300x1 + 500x2
A (8,0) → 300 X 8 + 500 X 0 = 2.400
B (7,2) → 300 X 7 + 500 X 2 = 3.100 →
ponto ótimo
C (3,4) → 300 X 3 + 500 X 4 = 2.900
D (0,5) → 300 X 0 + 500 X 5 = 2.500
E (0,0) → 300 X 0 + 500 X 0 = 0
Resp. O alfaiate deverá confeccionar 7 
ternos e 2 vestidospara obter lucro 
máximo de R$3100,00.
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
EXEMPLO 2
Uma companhia de aluguel de caminhões possuía-os de dois 
tipos: o tipo A com 2 metros cúbicos de espaço refrigerado e 4 
metros cúbicos de espaço não refrigerado e o tipo B com 3 
metros cúbicos refrigerados e 3 não refrigerados. Uma fábrica 
precisou transportar 90 metros cúbicos de produto refrigerado 
e 120 metros cúbicos de produto não refrigerado. Quantos 
caminhões de cada tipo ela deve alugar, de modo a minimizar 
o custo, se o aluguel do caminhão A era R$ 0,30 por km e o do 
B R$ 0,40 por km. Determine a solução ótima do modelo.
Min Z = 0,30x1 + 0,40x2
Sujeito a: 
2x1 + 3x2 ≥ 90 (I)
4x1 + 3x2 ≥ 120 (II)
x1,x2 ≥ 0 
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
EXEMPLO 3
Problema da confeitaria que produz dois tipos de bolos de 
sorvete: chocolate e creme. 
Max Z = 3x1 + x2
Sujeito a:
x1 ≥ 10 (I)
x1 + x2 ≥ 20 (II)
x1 ≤ 60 (III)
x2 ≤ 40 (IV)
2x1 + 3x2 ≤ 180 (V)
x1,x2 ≥ 0 
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
Pontos Viáveis:
A (20, 0)
B (10, 10) retas I e II
C (10, 40) retas I e IV
D (30, 40) retas IV e V
E (60, 20) retas III e V
F (60, 0) 
Max Z = 3x1 + x2
Z = 3 x 20 + 0 = 60
Z = 3 x 10 + 10 = 40
Z = 3 x 10 + 40 = 70
Z = 3 x 30 + 40 = 130
Z = 3 x 60 + 20 = 200 PONTO ÓTIMO
Z = 3 x 60 + 0 = 180
Conclusão: A confeitaria para maximizar o lucro em 200 u.m 
deverá fazer 60 bolos de chocolates e 20 bolos de cremes.
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESUMINDO
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL