Ricerca operativa II - 27/03/2008

Università degli studi di Napoli Federico II

Corso di ricerca operativa II

Prova di esame del 27.03.2008

Quesito 1

Si consideri un problema di albero a costo minimo con vincoli di capacità, assumendo la matrice dei costi indicata, il nodo 1 come nodo radice, una domanda pari a 2 per ogni nodo, e una capacità massima pari a 8.

• (a) Si individui una soluzione del problema utilizzando un algoritmo migliorativo;
• (b) A partire dalla soluzione individuata al punto (a) si sviluppino due iterazioni di un algoritmo di Tabu Search per la sua risoluzione.

Quesito 2

Si consideri un problema di scheduling a macchina singola con riferimento alla lista di operazioni indicata. Indicando con Tj la tardiness associata all'operazione j,

• (a) Si individui e si applichi una procedura costruttiva che minimizzi la funzione ∑f(Tj), assumendo f(Tj) = 1 se Tj≤3 e f(Tj) = T² se Tj≥3;
• (b) Si proponga un algoritmo di Simulated Annealing per la risoluzione del problema e si effettui una iterazione.

8 1 2 3 4 5 7 6

Operazione j 4 2 4 7 5 8 6 5

Tempo di processamento Pi 12 15 10 18 15 7 10 13

Scadenza dj

Quesito 3

Si illustri il concetto di soluzione di Pareto e si illustri il metodo dei pesi per la individuazione di tali soluzioni. Sulla base della definizione fornita

• (a) Si individuino le soluzioni di Pareto all'interno dell'insieme di soluzioni caratterizzate dai valori di funzioni obiettivo indicate in tabella nell'ipotesi di assumere gli obiettivi 1 e 2 a massimizzare e l'obiettivo 3 a minimizzare;
• (b) Si indichi in un problema con n soluzioni e p obiettivi (con n>p) quale è il numero minimo e il numero massimo di soluzioni di Pareto individuabili.

Ob.2

Ob.1 Ob. 3

Soluzione 6

1 8 7 4

10 8

2 5 9 6

3 4 10 7

7 4 25

Il 6 7 8 5

7 9 4 7

Per la simulazione di eventi casuali, si ipotizzi che un generatore di numeri casuali da 0 a 1 produca nell'ordine i valori: 0,30; 0,45; 0,12; 0,89; 0,58; 0,75; 0,55; 0,27; 0,05; 0,60, 0,97, 0,83, 0,11, 0,07.