programação linear 2

Prévia do material em texto

Universidade Federal de Juiz de Fora
Instituto de Ciências Exatas
Departamento de Ciência da Computação
Programação Linear
Programação Linear 
Análise de sensibilidade
Alunos:
Ricardo da Silva Werneck - 200335037
Thiago Amaral Guarnieri - 200335021
1) Objetivo do laboratório:
O objetivo do presente laboratório é utilizar a análise de sensibilidade do programa 
LINDO para que se possa melhorar a solução pela adoção de variações nas restrições. 
No caso podemos aperfeiçoar a solução manipulando as restrições do problema de 
forma que se possa, por exemplo, reduzir o custo de produção diminuindo a quantidade 
de um material ou obter mais lucro aumentando o número de horas.
1.1) Enunciado do problema:
Bolos e pães é uma fábrica de processamento de alimentos que produz salsichas e pães 
para cachorro-quente. A empresa moe sua própria farinha para fazer pães em uma taxa 
de 200 libras por semana. Cada pãozinho para cachorro-quente requer 0,1 libra de 
farinha. Atualmente, possui um contato com a Pigland, Inc, que especifica que uma 
entrega de 800 libras de carne suína é entregue toda segunda-feira. Cada salsicha precisa 
de 1/4 de libra de carne suína. Todos os demais ingredientes para fabricação de 
salsichas e pães se encontram em estoque pleno. Finalmente, a força de trabalho da 
empresa é formada por cinco empregados em período integral (40h/semana). Cada 
salsicha gera um lucro de US$ 0,20 e cada pãozinho, US$ 0,10.
A empresa gostaria de saber quantas salsichas e quantos pães deve produzir para obter o 
maior lucro possível.
(a) Formule um modelo de programação linear para esse problema;
(b) Use o método gráfico para solucionar esse modelo.
2) Modelagem do problema:
Função Objetivo:
Temos que a função objetivo é tal que obtenhamos o maior lucro possível:
 Max (z) = 0,1p + 0,2s
O que no caso representa o custo unitário de cada material, 10 centavos para o pão e 20 
centavos para a salsicha.
Restrições:
As restrições são como a seguir:
• O número de horas semanais da produção não pode ultrapassar o número de 
horas semanais acumuladas dos cinco empregados
o 2p + 3s <= 12000
• O número de pães não pode ultrapassar as 2000 unidades
o p <= 2000
• O número de salsichas não pode ultrapassar as 3200 unidades
o s <= 3200
• A produção não poderá ser negativa
o p, s >= 0
3) Desenvolvimento do problema:
A seguir serão mostradas algumas telas do programa, que procuram demonstrar sua 
análise de sensibilidade.
Figura 1: Modelagem original do problema
Figura 2: após a resolução do problema, nos é oferecida a opção de fazer a análise de 
sensibilidade.
Figura 3: A análise de sensibilidade 
De acordo com a figura 3, a análise de sensibilidade nos mostra como podemos reduzir 
os coeficientes da função objetivo além de mostrar a variação que as restrições podem 
tomar tanto para acréscimo quanto para decréscimo no seu valor direito da inequação.
3.1) Primeira análise: restrição de P
De acordo com o programa temos que a restrição p<=2000 (linha três) pode ter o 
acréscimo infinito e o decréscimo de até 800 unidades, sem que tenhamos alteração no 
valor da função objetivo.
Figura 4: Valores permissíveis para a restrição p<=2000 (linha três)
Portanto temos que p pode variar de 1200 até infinito:
 p’–800 <=p <=p’+ ∞
1200 <= p <= ∞
Temos na figura 5 os resultados da aplicação do intervalo obtido acima. Primeiro P foi 
submetido ao seu valor mínimo permitido – 1200 – e depois à um valor maior, aleatório, 
acima de 2000 e depois a um valor abaixo do limite inferior. Observar que o resultado 
não varia quando colocamos as restrições dentro do limite permitido, mas varia quando 
o limite foi extrapolado.
Figura 5: resultado da aplicação dos limites obtidos pela análise
p<=1200 à 760
p<=100000 à 760
p<=1199 à 759,9
Podemos reduzir a produção de pão para 1200 unidades e manteremos o mesmo lucro.
3.2) 2ª Análise: restrição de S
De acordo com o programa temos que a restrição s<=3200 (linha quatro) pode ter o 
acréscimo de até 800 unidades e o decréscimo de até 533 unidades. 
Figura 6: Valores permissíveis para a restrição s <= 3200 (linha quatro).
Observar também que, neste caso, temos que a função objetivo terá uma variação de 
acréscimo e decréscimo em seus coeficientes, que é representada pela coluna DUAL 
PRICES.
Figura 7: Valores de acréscimo para cada unidade retirada/removida
Figura 8: Valores obtidos para as variações impostas 
Observar que cada vez que adicionamos ou removemos uma salsicha, estaremos 
aumentando/diminuindo o lucro pelo fator indicado em DUAL PRICES. Para os 
exemplos resolvidos temos que:
s<=3199 à 759.95
s<=3210 à 760.5
O lucro aumenta por um fator de 0,05
3.3) 3ª Análise: restrição de P e S
De acordo com o programa temos que a restrição 2p + 3s <= 12000 (linha dois) pode ter 
o acréscimo de até 1600 e o decréscimo de até 2400 unidades, sem que tenhamos 
alteração no valor da função objetivo.
Figura 9: Valores permissíveis para a restrição 2p + 3s <= 12000 (linha dois).
Também temos, neste caso, que levar em consideração o fator DUAL PRICES, que é 
semelhante ao da linha quatro:
Figura 10: Valores de acréscimo para cada unidade retirada/removida
Aumento de Horas
Para:
2p + 3s <=13600 à840
2p + 3s <=13650 à840
A diferença nos dois casos 
é a sobra de horas de 
trabalho no segundo caso, 
50h, que não interferem na 
função objetivo.
Redução de Horas
Para:
2p + 3s <=9600 à640
2p + 3s <=9550 à636.67
Nestes casos nos chama a 
atenção o fato de não 
produzir pães, o número de 
horas foi destinado à 
produção de salsichas.
4) Conclusão:
1. Pode manter o lucro e reduzir a produção de pães para 1200 unidades.
2. Pode manter a taxa de produção de pães e salsichas e aumentar número de horas 
de trabalho, aumentado o lucro.
*Nos dois casos não há “sobras”, de horas ou produtos.
Figura 13: melhores soluções