v.s.f.f.

Dep. Econ. Gestão e Engª IndustrialDep. Econ. Gestão e Engª IndustrialDep. Econ. Gestão e Engª IndustrialDep. Econ. Gestão e Engª Industrial

DISCIPLINA: Investigação Operacional

ANO LECTIVO 2009/2010

Exame de Recurso

14 de Julho de 2010 duração: 2h30

1. Considere o modelo seguinte, de Programação Linear (PL), referente a um plano de distribuição

de menus a comissários de uma prova desportiva e que tem como objectivo a minimização do custo

de fornecimento de alimentação e bebidas a cada um dos comissários:

min Z(x) = 12x1 + 11,5x2 + 15x3 + 14x4 (€/comissário) s.a: x1 + x2 + x3 + x4 = 15 (menus a distribuir a cada comissário)

x1 ≤ 4 (menus tipo 1) (P) x2 ≤ 4 (menus tipo 2)

x1 + x2 ≤ 7 (menus tipo 1 e 2) 3,5x1 + 3x2 + 2,5x3 + 3,5x4 ≥ 40 (litros de água)

x1, x2, x3, x4 ≥ 0

em que para o horizonte temporal considerado, as variáveis principais representam:

xj: número de vezes que o menu j vai ser distribuído, durante a prova, a cada comissário; j=1,2,3,4

A utilização do método SIMPLEX fornece o seguinte quadro óptimo:

cj 12 11,5 15 14 0 0 0 0 M

cB V.B. x1 x2 x3 x4 s2 s3 s4 s5 w1 sol.

0 s5 0 0 1 0 0 - 0,5 0 1 3,5 10,5

12 x1 1 0 0 0 0 - 1 1 0 0 3

0 s2 0 0 0 0 1 1 - 1 0 0 1

11,5 x2 0 1 0 0 0 1 0 0 0 4

14 x4 0 0 1 1 0 0 - 1 0 1 8

zj 12 11,5 14 14 0 - 0,5 - 2 0 14 194

zj – cj 0 0 -1 0 0 - 0,5 - 2 0 14 - M

em que s2, s3, s4 e s5 são as variáveis de folga introduzidas na 2ª, 3ª, 4ª e 5ª restrição, respectivamente; w1

representa a variável artificial utilizada na 1ª restrição.

Nota: considere as alíneas independentes.

a) Formule o problema dual (D) do modelo de P.L. apresentado (P). Tendo em conta o conhecimento

da solução do modelo (P) e com base na teoria da dualidade resolva o problema dual (D). Justifique

a sua resposta apresentando todo o processo de resolução.

(80)

v.s.f.f.

b) Suponha que a Direcção da prova pretende obter informações que lhe permitam alguma

flexibilidade na gestão deste plano de distribuição de menus. Assim, apresente os intervalos de

variação, que não envolvam alteração da estrutura da solução óptima já encontrada, para os seguintes

parâmetros:

i) custos unitários do menu 1 e do menu 3;

ii) limitação de distribuição de 4 menus tipo 2 e de pelo menos 40 litros de água;

iii) imposição de distribuição de 15 menus a cada comissário.

Justifique a sua resposta apresentando todo o processo de resolução.

c) Suponha que a empresa de catering, que fornece os menus, decidiu diminuir o custo unitário dos

menus 3 de 15 € para 13,5 €. Nestas condições qual será o novo plano óptimo de distribuição e o

respectivo custo? Justifique a sua resposta apresentando todo o processo de resolução.

d) Relativamente ao problema original, suponha que agora foi entendido que a quantidade de água

distribuída, aos comissários, durante a prova devia ser pelo menos de 45 litros. Analise e descreva

as consequências que decorrem desta alteração. Justifique a sua resposta apresentando todo o

processo de resolução.

2. Uma empresa industrial tem seis fábricas (F1, F2, F3, F4, F5 e F6) a produzir um produto que deverá

ser enviado para cinco clientes (C1, C2, C3, C4 e C5). Suponha que o produto é transportado das

fábricas para os clientes, implicando um custo unitário de transporte proporcional à distância

percorrida. Admita que no dia 14 de Julho de 2010, o coordenador dos transportes dispunha das

informações que se apresentam na tabela seguinte, referentes à disponibilidade e procura diária bem

como ao custo unitário (em €/tonelada) de transporte entre os seis pontos de oferta e os cinco pontos de

procura. Por exemplo, o transporte de uma tonelada do produto entre F2 e C3 custa 8 €. Note que não

existe transporte directo entre os seguintes pares de Fábrica-Cliente: F2-C2, F3-C5, F5-C2 e F6-C4.

Clientes

C1 C2 C3 C4 C5 Oferta (toneladas)

F1 14 7 7 11 8 60

F2 9 --- 8 13 6 70

F3 10 7 11 10 --- 90

F4 11 4 10 12 7 40

F5 12 --- 9 10 9 40

Fábricas

F6 13 5 8 --- 6 50

Procura (toneladas) 60 40 80 70 50

a) Suponha que o coordenador de transportes tinha planeado, para o dia 14 de Julho de 2010, o

seguinte plano de transporte directo do produto (em toneladas) entre as fábricas e os clientes:

(60)

v.s.f.f.

Enviar: 60 ton. da fábrica F1 para o cliente C3; 20 ton. da fábrica F2 para o cliente C3;

50 ton. da fábrica F2 para o cliente C5; 60 ton. da fábrica F3 para o cliente C1;

30 ton. da fábrica F3 para o cliente C4; 40 ton. da fábrica F4 para o cliente C2;

40 ton. da fábrica F5 para o cliente C4;

Com este plano, a fábrica F6 não envia 50 ton. de produto (i.e. no modelo do PT, x66=50).

Adicionalmente, do ponto de vista da IO, este plano corresponde a uma solução degenerada: x36=0,

x46=0 e x63=0. O custo total deste plano é de 2340 €.

Mostre, justificando, que este plano de transporte não é óptimo.

b) Utilizando um algoritmo de P.L. apresente o plano óptimo de transporte directo do produto entre as

fábricas e os clientes, de custo total mínimo. Justifique a solução apresentando todo o processo de

resolução.

c) Suponha que o coordenador de transportes pretende obter informações que lhe permitam alguma

flexibilidade na gestão deste plano de transporte directo do produto entre as fábricas e os clientes.

Assim, apresente os intervalos de variação, que não envolvam alteração da estrutura da solução

óptima já encontrada, para os seguintes custos unitários:

i) custo unitário entre F1 e C1 (c11=14 €); ii) custo unitário entre F3 e C1 (c31=10 €);

iii) custo unitário entre F4 e C5 (c45=7 €); iv) custo unitário entre F6 e C2 (c62=5 €).

Justifique a sua resposta apresentando todo o processo de resolução.

3. Considere uma rede orientada de 10 vértices, cuja disposição se representa, de forma aproximada, na

figura seguinte. A tabela apresenta a capacidade máxima do arco que une cada par de vértices:

Arco (i,j) Capacidade Arco (i,j) Capacidade

(A,B) 20 (E,G) 10

(A,C) 80 (E,H) 10

(A,D) 15 (F,G) 30

(B,E) 20 (F,I) 30

(C,E) 10 (G,H) 50

(C,F) 20 (G,I) 20

(C,G) 50 (H,J) 60

(D,F) 15 (I,J) 50

(E,F) 20

(60)

v.s.f.f.

a) Utilizando a informação da tabela e a representação da localização dos vértices represente

graficamente a rede (i.e. desenhe as ligações entre os vértices, incluindo o valor da capacidade

máxima de cada arco).

b) Suponha que se pretende determinar o fluxo máximo entre o vértice A e o vértice J.

i) Formule o problema em Programação Linear Inteira.

ii) Utilizando o algoritmo de Ford-Fulkerson determine o fluxo máximo que se pode enviar do

vértice A para o vértice J. Justifique a sua resposta, apresentando todo o processo de

resolução

Fim do Exame

Relações Primal – Dual

Problema de Maximização passagem

ao dual

Problema de minimização

i-ésima restrição

≤ ≥ =

≥ 0 ≤ 0 livre

i-ésima variável

j-ésima variável

≥ 0 ≤ 0 livre

≥ ≤ =

j-ésima restrição

matriz dos coef. técnicos A matriz dos coef. técnicos AT

coeficientes da f.o. termos independentes

termos independentes coeficientes da f.o.

D

A

C

F

G

I

J

B

E

H