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

INVESTIGAÇÃO OPERACIONAL I

Folha de Exercícios 3

1. Uma empresa pode produzir três produtos (P1, P2 e P3) que vende ao preço de 3000, 2000 e 4000 u.m. a tonelada, respectivamente. Para a sua produção são necessárias três matérias-primas (mp1, mp2 e mp3). As quantidades disponíveis para o próximo ano e os preços a que foram compradas são os seguintes:

	mp1	mp2	mp3	
Quantidade (ton.)	40	60	120	
Preço (u.m. / ton)	500	300	200	

O plano produtivo que maximiza a receita obtida com a venda dos três produtos foi determinado como segue:

	V. B.	x1	x2	x3	x4	x5	x6	valores		
	Z	-3	-2	-4	0	0	0	0		
	x4	2	1	1	1	0	0	40		
	x5	0	2	2	0	1	0	60		
	x6	1	0	3	0	0	1	120	QUADRO INICIAL	
				(…)						
	V. B.	x1	x2	x3	x4	x5	x6	valores		
	Z	0	2	0	3/2	5/4	0	135		
	x1	1	0	0	1/2	-1/4	0	5		
	x3	0	1	1	0	1/2	0	30		
	x6	0	3	0	-1/2	-5/4	1	25	QUADRO FINAL	

									

Considere todas as alíneas relativas ao problema apresentado acima.

a) Comente o plano de aprovisionamento das matérias-primas da empresa.
b) Determine o lucro unitário de cada produto e mostre que este é também o plano que maximiza o lucro da empresa.
c) Admita que devido ao mau ano agrícola se prevê uma quebra importante na produção de mp1, que poderá obrigar a uma redução de aprovisionamento para o próximo ano. Faça um estudo que permita à empresa estar preparada para essa eventual redução.
d) Admita que as previsões indicam que os preços das matérias-primas sofrerão no próximo ano acréscimos de 20%, 12% e 8%, respectivamente e que o orçamento da empresa para a compra de matérias-primas terá um acréscimo de apenas 10%.
Formalize um problema de PL cuja solução indique o plano óptimo de aprovisionamento de matérias-primas, supondo que é mantido o objectivo de maximização da receita com as vendas de P1, P2 e P3.
e) Escreva o dual do problema de PL associado ao quadro inicial apresentado e a respectiva solução óptima. 

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 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 (103 euros)	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ê?

4. Suponha que uma empresa pode produzir 2 produtos, P1 e P2, dispondo de duas tecnologias distintas para produzir cada um deles, de acordo com: 

	Produto P1	Produto P2		
	Tecnologia 1 	Tecnologia 2	Tecnologia 1	Tecnologia 2	Disponibilidades	
m.o.  (semanas)	1	1	1	1	15	
m. p. 1 (ton)	2	10	3	2	120	
m. p. 2 (ton)	3	5	5	5	100	
Lucro(103euros/ton)	4	15	9	11		
Produção (ton)	x1	x2	x3	x4		

O plano produtivo que maximiza o lucro total foi obtido com o seguinte quadro de simplex:

Var. básicas	x1	x2	x3	x4	x5	x6	x7	valores	
Z	7	0	5/2	0	10	1/2	0	210	
x4	1	0	7/8	1	5/4	-1/8	0	15/4	
x2	0	1	1/8	0	-1/4	1/8	0	45/4	
x7	-2	0	0	0	-5	0	1	25	

Considere todas as alíneas independentes.

a) Elabore um relatório para enviar à direcção da empresa. 
b) Até que valor pode a empresa reduzir o lucro unitário do seu produto mais lucrativo sem ter de alterar a estrutura do plano produtivo? 
Se o reduzir para além desse limite como deverá proceder para obter o lucro máximo?
c) Admita que a totalidade da produção de P2 é vendida a outra empresa que faz o empacotamento e que o transporte entre as duas empresas é da responsabilidade do fabricante. Se no período em estudo a capacidade de transporte for apenas de 3 toneladas como deve a empresa proceder? 
d) Escreva o dual, e a respectiva solução óptima, do problema que deu origem ao quadro de simplex apresentado acima. 
e) Mostre que a condição dos desvios complementares é verificada pelo par de soluções primal e dual retirado do quadro de simplex.
5. Uma empresa produz dois produtos com margens unitárias de 2 e 1 u.m. respectivamente. A produção é feita com recurso às matérias-primas A, B e C. Para determinar o plano que maximiza a margem total foi formalizado e resolvido o seguinte problema de PL:

MAX   Z = 
s. a	

	
cujo quadro óptimo é:

V. B.	x1	x2	x3	x4	x5	valores	
Z	0	1	1	0	0	10	
x1	1	1	0.5	0	0	5	
x4	0	1	-2	1	0	0	
x5	0	2	0	0	1	8	

a) Escreva o problema dual. Apresente o par de soluções óptimas complementares e a respectiva interpretação económica.
b) Determine o intervalo de sensibilidade para a margem unitária do produto 1.
c) Estude a vantagem de dispor de mais 10 unidades de matéria prima B. Justifique.
d) Um concorrente pediu à empresa a cedência de 2 unidades de matéria prima A pelo valor de 2 u.m.. Que resposta deve ser dada? Justifique.

6. 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.

7. 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.

8. 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 ton 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).
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 ton cada. Com base no trabalho já efectuado pelo técnico (ver anexo) faça um estudo detalhado que habilite a direcção da empresa a responder a essa eventualidade.

ANEXO
!
!    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		 -.8000000
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