Ricerca Operativa II
prova scritta del 2 giugno 1998
Internet
Come è forse noto, Internet è costituita da un insieme di reti "proprietarie", vale a dire autonomamente gestite, tra di loro collegate e chiamate domini. Vi sono domini immensi e piccoli domini locali, e tutti offrono servizi di interconnessione e trasmissione dati. Tuttavia, la gestione di questi servizi presenta una fondamentale differenza rispetto alla gestione di servizi analoghi in una rete locale: infatti le esigenze di autonomia e riservatezza del dominio fanno sì che le caratteristiche di quest’ultimo in termini di capacità dei link e dei nodi (semplificando, in termini di numero di bit/secondo che il dominio è in grado di trasmettere da un’origine a una destinazione) siano difficilmente quantificabili in modo esatto.
Immaginiamo allora la nostra rete come un grafo in cui, per semplificare, ogni dominio possa essere rappresentato come un arco uv che offre un servizio di comunicazione a due terminali u e v, e ipotizziamo che il dominio stesso sia tenuto periodicamente a notificare all’utente un parametro puv(w) che, per valori di w in {w0, w1, …, wq}, rappresenti la probabilità che la capacità disponibile tra u e v valga proprio w.
Consideriamo allora il problema di stabilire un collegamento tra un nodo s e un nodo t della rete. Tale collegamento comporterà l’attraversamento di un certo insieme di domini (e quindi di archi), il primo dei quali contenente s e l’ultimo contenente t. Ora, per poter istituire il collegamento si avrebbe bisogno di un insieme di domini che consenta di trasmettere almeno wk bit al secondo. Come si fa a trovare un insieme per il quale risulti massima la probabilità di rispettare questo requisito? (si supponga il flusso di comunicazione tra s e t non frazionabile, e si descrivano le capacità disponibili nei generici archi come variabili aleatorie indipendenti).
Formulare il problema in termini di programmazione lineare intera nell’ipotesi che il collegamento non possa essere istituito se i domini attraversati sono più di h.
Tutto sta a organizzarsi
Una società utilizza due operai specializzati per eseguire lavori che richiedono attrezzature di diverso tipo e di costo particolarmente elevato, disponibili perciò in un unico esemplare per ciascun tipo. Dovendo eseguire una commessa piuttosto importante, la società ha approntato un breakdown individuando sette operazioni distinte, indicate nel seguito con le prime lettere dell’alfabeto. La durata delle operazioni è di uno (A, B, C, E, F) o due (D, G) giornate. Non vi sono vincoli di precedenza tra le operazioni; alcune di esse richiedono però l’uso contemporaneo di certe attrezzature, e non possono pertanto essere eseguite se non in periodi di tempo disgiunti. Il diagramma di compatibilità delle operazioni è rappresentato dalla matrice 0-1 sotto riportata: se l’elemento ij vale 1, allora le due operazioni possono essere eseguite in parallelo, se vale 0 invece no.
|
A |
B |
C |
D |
E |
F |
G |
|
|
A |
- |
1 |
0 |
1 |
1 |
0 |
0 |
|
B |
1 |
- |
1 |
0 |
1 |
1 |
0 |
|
C |
0 |
1 |
- |
1 |
1 |
1 |
0 |
|
D |
1 |
0 |
1 |
- |
0 |
0 |
0 |
|
E |
1 |
1 |
1 |
0 |
- |
1 |
1 |
|
F |
0 |
1 |
1 |
0 |
1 |
- |
1 |
|
G |
0 |
0 |
0 |
0 |
1 |
1 |
- |
Il responsabile della società ha pensato di affidare al primo operaio le operazioni A, B, D, e F e le rimanenti al secondo operaio. Operando in questo modo, il completamento della commessa richiederà 6 giornate; è possibile far di meglio? Illustrare una metodologia generale per conseguire un eventuale miglioramento a partire da una generica assegnazione di operazioni e applicarla al caso in esame partendo dalla soluzione proposta dal responsabile.