INSTITUTO SUPERIOR DE ECONOMIA E GESTÃO
UNIVERSIDADE TÉCNICA DE LISBOA

INVESTIGAÇÃO OPERACIONAL I

Folha de Exercícios 3

1. Um fabricante de calçado está a planear a colecção do próximo ano. Essa colecção inclui três tipos de botas, denominadas “Walker”, Hicker” e “Backpacker”. Entre os recursos usados na sua produção há três particularmente dispendiosos: NOwater (um revestimento que torna as botas impermeáveis), Fabrínsula (um isolante para manter o calor) e Lugster (solas). Actualmente estão disponíveis 10,000 sq.ft. de NOwater a $20 por sq.ft. Analogamente, o fabricante pode comprar até 5,000 oz. de Fabrínsula a $15 por oz. e 7,000 pares de solas Lugster a $10 o par. Na tabela seguinte são apresentadas as condições de produção dos vários tipos de botas.

	Produtos		
	Walker	Hiker	Backpacker		
NOwater	1 / 2	1	5/2	[sq.ft. por par]	
Fabrínsula	1 / 2	2 / 3	4 / 3	[oz. por par]	
Lugster	1	1	1	[ par de solas]	

O fabricante já aceitou encomendas para pelo menos 3,000 pares de botas “Walker”, pelo menos 2,000 pares de botas “Hicker” e pelo menos 1,000 pares de botas “Backpacker”. Se forem produzidos mais pares de botas, os compradores estão interessados em comprá-los. Os preços contratados com os clientes foram $40, $65 e $110 por par de botas, respectivamente.

Para obter o plano produtivo o analista desenhou o seguinte modelo de PL:

		Max z = 

Os resultados obtidos com a resolução deste modelo estão no anexo 1. 
O gerente da empresa fez as seguintes perguntas ao analista:

P1. Quantos pares de botas devemos produzir? Qual é o lucro?

P2. Sabe que NOwater, Fabrínsula e Lugster são recursos críticos. Quanto vamos usar nesse plano e quanto sobra?

P3. O responsável do marketing disse-me que as botas “Hicker” têm muita procura e que poderíamos subir o preço $10 por par. Essa subida alteraria o plano?

P4. Estamos a produzir 3,000 pares de botas “Walkers”, para satisfazer a encomenda que temos. Interrogo-me se seria vantajoso descermos o preço. Aumentaríamos as vendas?

P5. Outro dia um fornecedor ofereceu-me 100 oz. de Fabrínsula a $8.50 por oz. Acha que devemos aceitar? E se eu fizesse uma contra-proposta de $5? Ganharíamos alguma coisa com isso?

P6. Um dia destes vi um anúncio de um fornecedor que vende solas Lugster a $19 o par. Acha que vale a pena contactá-lo?

Apresente as respostas que o analista deve dar às perguntas do gerente (*).
_____________
(*)in Operations Research: a model-based approach, H.A. Eiselt and C.-L. Sandblom, Springer, 2010

ANEXO 1

SUMMARY OF RESULTS

VALUE OF THE OBJECTIVE FUNCTION         143,749.60		
				
DECISION 	VALUE AT	OPPORTUNITY		
VARIABLE	OPTIMUM	COST		
				
WALKER	3,000.0000	0.0000		
HIKER	2,750.0750	0.0000		
BACKPACKER	1,249.9249	0.0000		
				
SLACK / EXCESS 	CONSTRAINT	OPTIMAL 	SHADOW 	
VARIABLE	TYPE	VALUE	PRICE	
				
NOWATER	LE	2,625.1125	0.0000	
FABRINSULA	LE	0.0000	    7.5008	
LUGSTER	LE	0.0000	  19.9993	
WALKER	GE	0.0000	-11.2496	
HIKER	GE	  750.0750	0.0000	
BACKPACKER	GE	  249.9250	0.0000

				
	SENSIVITY ANALYSES		
				
COEFFICIENTS OF THE OBJECTIVE FUNCTION	
VARIABLE	LOWEST	ORIGINAL	HIGHEST	
	ALLOWABLE	VALUE	ALLOWABLE	
	VALUE		VALUE	
WALKER	-INFINITY	12.50	23.75	
HIKER	16.00	25.00	30.00	
BACKPACK	25.00	30.00	50.00	
				
	RIGHT-HAND SIDE VALUES		
CONSTRAINT	LOWEST	ORIGINAL	HIGHEST	
	ALLOWABLE	VALUE	ALLOWABLE	
	VALUE		VALUE	
NOWATER	7,374.89	10,000.00	INFINITY	
FABRINSULA	4,833.40	  5,000.00	5,500.00	
LUGSTER	6,625.00	  7,000.00	7,249.89	
WALKER	2,001.60	  3,000.00	3,600.02	
HIKER	-INFINITY	  2,000.00	2,750.08	
BACKPACKER	-INFINITY	  1,000.00	1,249.93	

2. Considere o problema de PL:

	MAX	
s. a 	

a) Mostre que x = [0, 2, 0, 7, 0, 0, 1, 0] T  é solução básica admissível do problema.
b) Use o teorema dos desvios complementares para provar que a solução apresentada na alínea anterior não é óptima.
c) Construa o quadro de simplex correspondente à solução apresentada na alínea a). Indique a base associada a uma solução que dê melhor valor à função objectivo e calcule a correspondente melhoria.

3. Uma empresa celebrou um acordo com um departamento do Estado pelo qual se comprometeu a reduzir a emissão de gases tóxicos para a atmosfera e a não diminuir o actual nível de emprego. Em contrapartida recebe dois tipos de incentivos: duas encomendas de 250 toneladas cada para dois dos seus produtos e um subsídio de carácter monetário por tonelada produzida para quatro dos seus produtos.
O técnico da empresa formalizou e resolveu o problema da determinação do plano óptimo de produção (ver anexo 2).
a) Elabore uma nota para enviar ao responsável pelo sector produtivo contendo a informação sobre o plano de produção que considere importante.
b) Elabore uma nota para enviar à direcção da empresa com uma apreciação crítica, baseada nos valores obtidos pelo técnico, sobre o acordo celebrado.
c) Admita que a direcção da empresa contesta o facto de o produto que maior subsídio proporciona por tonelada não ser produzido. Apresente uma resposta fundamentada a essa contestação.
d) Admita que correm rumores que o departamento de Estado vai propor uma renegociação do contrato, reduzindo as encomendas para 200 toneladas cada. Com base no trabalho já efectuado pelo técnico (ver anexo 2) faça um estudo detalhado que habilite a direcção da empresa a responder a essa eventualidade.

ANEXO 2
!    PRODi = quantidade (ton) a produzir do produto i     (i=1,...,4)
!    Objectivo  :  maximização do subsídio (u.m.)
!
MAX  60 PROD1 + 24 PROD2 + 36 PROD3 + 28 PROD4
ST
POLUICAO)     5 PROD1 + PROD2 +  4 PROD3 +  PROD4 < 2000
EMPREGO)    8 PROD1 + 14 PROD2 + 12 PROD3 + 9 PROD4 > 15000
ENCOMEN2)   PROD2 > 250
ENCOMEN3)   PROD3 > 250
END

LP OPTIMUM FOUND AT STEP         3
	OBJECTIVE FUNCTION VALUE
    SUBS)     	34600.000
VARIABLE			VALUE				REDUCED COST
    PROD1		  	        .000000	       		109.600000
    PROD2	         		 600.000000                       	 	       .000000
    PROD3	         		 250.000000                       		       .000000
    PROD4                   		 400.000000                       		       .000000

          ROW	     	SLACK OR SURPLUS			DUAL PRICES
POLUICAO)			 .000000				35.200000
 EMPREGO)			.000000				   -.800000
ENCOMEN2)	       	         350.000000				    .000000
ENCOMEN3)		               .000000			             - 95.200000

NO. ITERATIONS =		3

RANGES IN WHICH THE BASIS IS UNCHANGED:

					OBJ COEFFICIENT RANGES
VARIABLE	  CURRENT			ALLOWABLE		ALLOWABLE
		 COEF				  INCREASE		  DECREASE
   PROD1		60.000000	              		 109.600000		   INFINITY
   PROD2		24.000000		   	     4.000000		   INFINITY
   PROD3		36.000000		  	  95.200000		   INFINITY
   PROD4		28.000000		  	  INFINITY		  4.000000

					RIGHTHAND SIDE RANGES
        ROW	  	 CURRENT		ALLOWABLE		ALLOWABLE
			     RHS			  INCREASE		  DECREASE
 POLUICAO		  2000.000000		  194.444400		  142.857100
 EMPREGO		15000.000000		2000.000000		1750.000000
ENCOMEN2		    250.000000		  350.000000		      INFINITY
ENCOMEN3		    250.000000		    45.454540		    72.916660

4. Uma empresa pode produzir 3 produtos de acordo com as condições apresentadas no quadro:

	P1	P2	P3	Disponibilidade	
m. p. 1 (ton)	4	6	2	50	
m. p. 2 (ton)	3	5	1	80	
Margem (103euros)	5	6	4		

Um cliente encomendou 12 toneladas de P1 e a empresa decidiu satisfazer essa encomenda. Para determinar o plano óptimo de produção foi formalizado e resolvido o seguinte problema de PL:

Max	
s. a		[m.p. 1]
		[m.p. 2]
		[encomenda]

Var. básicas	x1	x2	x3	x4	x5	x6	R	valores	
Z	0	6	0	2	0	3	-3	64	
x3	0	3	1	1/2	0	2	-2	1	
x5	0	2	0	-1/2	1	1	-1	43	
x1	1	0	0	0	0	-1	1	12	

Considere todas as alíneas relativas à solução dada no quadro acima.

a) Elabore um relatório para enviar à direcção da empresa.
b) Estude a possibilidade de comprar mais matéria-prima 1 e elabore um relatório com as conclusões do estudo.
c) Se for possível aumentar em 10% a margem do produto de menor margem, a empresa deverá alterar o seu plano de produção? 
d) Se a empresa tiver capacidade para melhorar o processo de produção de P2 de forma a reduzir para metade o seu consumo unitário de mp1 e de mp2 tem vantagem em passar a produzir P2? Porquê?
e) Se o cliente cancelar a encomenda como deve a empresa proceder? Porquê?

5. Uma empresa industrial do sector público pretende fixar a produção mensal de 3 dos principais produtos da sua gama. Os produtos são fortemente poluentes e têm provocado bastante contestação por parte das populações residentes próximo do sector produtivo da empresa. Tendo em conta a sua responsabilidade social, a administração aceitou como correcto o seguinte modelo de PL:

min   Z = 
			s.a	

cujo quadro óptimo é:
V. B.	x1	x2	x3	x4	x5	R1	valores	
Z	0	0	-1/2	-1	-2	2	120	
x2	0	1	3/4	2	1	-1	60	
x1	1	0	1/4	-1	-1	1	20	

Trata-se de um modelo que pretende minimizar o nível de poluição provocado pelos produtos, satisfazendo duas limitações essenciais: um volume total de produção de 80 mil toneladas, no máximo, e uma margem bruta total de 100 mil euros, no mínimo, a fim de cobrir os custos fixos mensais que são de 95 mil euros. O nível de poluição é medido em toneladas de gás expelido para a atmosfera por cada mil toneladas de produção.

a) Escreva os valores óptimos das variáveis de decisão e auxiliares do primal e do dual e interprete o seu significado económico.
b) O responsável pelo sector produtivo defendeu perante a administração que o aumento da capacidade produtiva global permitiria reduzir significativamente a poluição. Por sua vez, o responsável financeiro estimou que o aumento da capacidade em 30% implicaria um aumento dos custos fixos mensais de 10 mil euros. A administração aceita a proposta desde que o lucro mensal se mantenha. Determine a melhor solução para a empresa.
c) Os protestos dos grupos ambientalistas têm crescido de intensidade, de nada servindo os argumentos da administração de que o objectivo da empresa tem sido o de minimizar o volume de poluição. Dado que o produto 1 tem sido muito criticado por ser fortemente poluente, a administração decidiu reduzir a sua produção em, pelo menos, 50%. Estude as consequências desta decisão e avalie se se trata ou não de uma decisão acertada.

6. Considere o seguinte problema de PL relativo à determinação do plano produtivo que maximiza o lucro de uma empresa:
Max   Z = 
s.a	

					
a) Resolva-o utilizando o algoritmo de simplex.
b) Formalize o problema dual, apresente a respectiva solução e interprete os seus valores.
c) Qual o lucro unitário mínimo para viabilizar a produção do produto 2? Justifique.

7. Considere o problema:
	(P)	MAX	
s. a 	

a) Use o método do M grande para determinar uma solução admissível de (P).
b) Determine a solução óptima de (P).
c) Escreva o problema dual de (P).
d) Apresente a solução óptima do dual de (P).
e) Faça a análise de sensibilidade do terceiro elemento do vector dos segundos membros das restrições.
f) Admita que é necessário verificar também a condição . Qual é o valor máximo de Z? Porquê?