Ricerca Operativa II
prova scritta del 18 febbraio 1999
Siamo nell’anno 2999 e l’Italia si è finalmente dotata di un libero mercato delle telecomunicazioni. L’ufficio tecnico della TeleVideT.O.R.N.O. Italia S.p.A., 127° gestore delle telecomunicazioni, ha sottoposto al proprio management un modello di rete per connettere le 6 citttà più importanti del Paese: Abbiategrasso (
A), Busto Arsizio (B), Caltabellotta (C), Domodossola (D), Enna (E) e Forlimpopoli (F). Il progetto prevede la realizzazione dell’anello (A)—(B)—(C)—(D)—(E)—(F)—(A) integrato dalla tratta (B)—(E). Ciascuna tratta dovrà essere dotata di una capacità di 20 unità di flusso nei due sensi ().La rete dovrà sopportare un flusso di controllo single-commodity che, partendo da Abbiategrasso (10 unità di flusso) e Forlimpopoli (4 unità di flusso) raggiunga Caltabellotta (12 unità) e Domodossola (2 unità). Quanto al flusso di comunicazione tra gli utenti, si prevede che questo avrà luogo secondo la tabella seguente:
|
relazione |
A-B |
A-C |
A-E |
A-F |
B-C |
B-D |
B-F |
C-D |
D-E |
D-F |
E-F |
|
flusso scambiato nei due zeman () |
4 |
2 |
3 |
2 |
6 |
3 |
4 |
4 |
2 |
6 |
1 |
Il costo di trasmissione per unità di flusso lungo la generica tratta assume i valori seguenti, validi sia per il flusso di comunicazione che per quello di controllo:
|
tratta |
A-B |
B-C |
B-E |
C-D |
D-E |
E-F |
F-A |
|
costo |
2 |
8 |
3 |
2 |
2 |
5 |
1 |
Come è possibile instradare i flussi nella rete rispettando i vincoli di capacità? Una volta instradati i flussi, è possibile ridurre il costo di trasmissione aprendo la tratta (
F)—(B)? Se sì, indicate un valore del costo per unità di flusso che, applicato su quella tratta, consentirebbe di ottenere un vantaggio.