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

INVESTIGAÇÃO OPERACIONAL I

Folha de Exercícios 4

1. Considere um problema de transportes com 3 origens e 3 destinos. As quantidades disponíveis nas origens (ai, i =1,2,3), as procuras nos destinos (bj, j =1,2,3) e os custos unitários de transporte (cij, i =1,2,3, j =1,2,3), são os seguintes: 

,	,	

a) Determine uma solução admissível pelo método do canto superior esquerdo.
b) Determine uma solução admissível pelo método do mínimo da matriz dos custos.
c) Determine a solução óptima partindo da solução admissível obtida pelo método do mínimo da matriz dos custos.

2. Considere o problema de transporte cuja matriz de custos unitários de transporte, C, vector de ofertas, a, e vector de procuras, b, são os seguintes:

C = 		a = 		b = 

a) Construa o quadro correspondente à solução:
x11 = x24 = x33 = 4;    x12 = 14;    x31 = 2;    x43 = 11;    x44 =1;
                  xij = 0  todos os outros
e mostre que ela é admissível.
b) A partir da solução apresentada em a) calcule a solução óptima e o respectivo custo.
c) Escreva o dual do problema de transporte apresentado e o respectivo valor óptimo.

3. Um importador vai receber três remessas de um novo modelo de telemóveis: uma de 300 unidades proveniente de Hong-Kong, uma de 200 unidades proveniente da Índia e uma de 100 unidades proveniente das Filipinas, pelas quais pagou 4500 u.m., 3600 u.m. e 1300 u.m., respectivamente. 
O importador tem três clientes para os telemóveis: um (C1) que pretende comprar-lhe 200 unidades e dois (C2 e C3) que pretendem comprar-lhe 250 unidades cada um. Dada a insuficiência da importação face à procura, os clientes C2 e C3 admitem comprar menos unidades ao importador desde que ele garanta pelo menos 150 unidades a cada um.
Os custos unitários de transporte até às lojas dos clientes apresentados no quadro (em u.m.) são suportados pelo importador. 
O importador pretende negociar as entregas a fazer aos clientes de forma a minimizar o montante total que tem de desembolsar até entregar os telemóveis aos seus clientes.

	C1	C2	C3	
Hong-Kong	1.25	1.30	1.20	
Índia 	1.00	0.95	0.95	
Filipinas	0.90	1.10	1.05	

 a) Formalize o problema como um problema de transportes.
b) Obtenha uma solução básica admissível para o problema formalizado em a).
c) Faça uma iteração do método de Dantzig para a resolução do problema formalizado em a). 

4. Um serviço de inspecção pública dispõe de 4 técnicos para realizar 5 possíveis acções inspectivas a outras tantas empresas. As acções são individuais e cada técnico apenas inspecciona uma empresa. Pediu-se a cada técnico que indicasse o número de dias de calendário em que se comprometia a realizar o trabalho, os quais são apresentados no quadro seguinte:
				Acção			
		A1	A2	A3	A4	A5	
	T1	20	28	26	22	27	
Técnico	T2	28	24	27	20	27	
	T3	39	27	27	22	26	
	T4	25	31	29	27	28	

A acção A4 tem prioridade dado que existe uma denúncia de irregularidades em relação à empresa correspondente.
a) Proponha um programa de trabalhos imediatos a desenvolver pelos técnicos de forma a minimizar o tempo total de trabalho dos mesmos, desenvolvendo o maior número de acções possível. Justifique a metodologia adoptada.
b) Suponha que faltam exactamente 26 dias para o fim do prazo para a conclusão das inspecções. Verifique se é possível arranjar um programa de trabalhos de forma a que cada técnico complete uma acção dentro do prazo.

5. Um departamento da UE abriu as seguintes vagas para tradutores:
Vaga 1: Português – Francês; Vaga 2: Português – Alemão; Vaga 3: Português – Grego
Concorreram 4 candidatos que nas provas de selecção obtiveram as seguintes classificações (numa escala de 0 a 10):

Candidato 1		Vaga 1: 7	Vaga 2: 6	 Vaga 3: 2
Candidato 2		Vaga 1: 8	Vaga 2: 8	 Vaga 3: 4
Candidato 3		Vaga 1: 8	Vaga 2: 5	 Vaga 3: 4
Candidato 4		Vaga 1: 9	Vaga 2: 7	 Vaga 3: 6

Determine como deve ser feita a contratação para obter a melhor qualidade global nos serviços de tradução do departamento.

6. Considere o problema de afectação de 4 tarefas a 4 máquinas cuja matriz dos custos (em u.m.) é a seguinte:
            Máquinas
Tarefas 

a) Determine a afectação óptima e o respectivo custo.
b) Admita que pode ser usada uma outra máquina para realizar as tarefas 1 e 3 com custos 4 u.m. e 7 u.m. respectivamente. Recomenda a sua utilização? Porquê?

7. Para concorrer a um concurso de tangos, 3 raparigas e 4 rapazes duma escola de dança ensaiaram e dançaram aos pares perante os professores. As classificações dadas pelos professores foram as seguintes:

	David	Eduardo	Filipe	Gil	
Ana	15	18	12	19	
Beatriz	11	17	13	14	
Carla	14	12	16	15	

Sabendo que no concurso vão concorrer todos, formando 4 pares fixos, determine como devem ser constituídos esses pares em função das classificações atribuídas nos ensaios, de modo a obter a melhor classificação global para a escola.