Aula 02 (1)

Prévia do material em texto

PESQUISA OPERACIONAL
AULA 2 – PROGRAMAÇÃO LINEAR
Tema da Apresentação
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 
Tema da Apresentação
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
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
FORMULAÇÃO DO PROBLEMA DE PROGRAMAÇÃO LINEAR
(PPL)
O termo otimizar representa 
a possibilidade de maximizar
ou minimizar a 
função objetivo.
Tema da Apresentação
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.
Tema da Apresentação
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
Tema da Apresentação
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
Tema da Apresentação
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
 
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
FORMA REDUZIDA DO PROBLEMA DE PROGRAMAÇÃO LINEAR (PPL)
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
FORMULAÇÕES EQUIVALENTES DO PPL
Forma Canônica
Forma Padrão
Tema da Apresentação
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
PPL
Não negatividade
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
CARACTERÍSTICAS DO PPL
Proporcionalidade
PPL
Aditividade
Não negatividade
Separabilidade
Tema da Apresentação
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
Tema da Apresentação
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.
Tema da Apresentação
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).
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO GRÁFICA DO PPL
Algumas observações sobre a construção de gráficos
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
Algumas observações sobre a construção de gráficos
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
Tema da Apresentação
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?
Tema da Apresentação
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
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO GRÁFICA DO PPL
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO GRÁFICA DO PPL
Tema da Apresentação
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)
Tema da Apresentação
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. 
Tema da Apresentação
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
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
Tema da Apresentação
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 vestidos para obter lucro máximo de R$3100,00.
Tema da Apresentação
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 
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO
Tema da Apresentaçã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 
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESOLUÇÃO
Tema da Apresentaçã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.
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
RESUMINDO
Tema da Apresentação
PROGRAMAÇÃO LINEAR – AULA 2
PESQUISA OPERACIONAL
Tema da Apresentação
FUNÇÃO LOGARÍTMICA - AULA 6
FUNÇÃO LOGARÍTMICA - AULA 6