Ricerca operativa II - 22/02/2011

Università degli Studi di Napoli Federico II

Corso di ricerca operativa

Prova di esame del 22.02.2011

Quesito 1

Si consideri un problema di TSP considerando la matrice dei costi indicata nel seguito.

• Si determini una prima soluzione casuale del problema, effettui una iterazione di un algoritmo di tipo migliorativo basato su una mossa di 2-opt.
• Effettui una seconda iterazione individuando necessariamente un nodo diverso da quello prescelto altrimenti.

Quesito 2

Si consideri un problema di Flow Shop su quattro macchine (secondo la successione 1, 2, 3, 4) desumibile dalla seguente matrice dei tempi di processamento.

• Si risolva il problema applicando un algoritmo greedy.
• Si illustri, in corrispondenza di una delle soluzioni individuate, come varia nel tempo il numero dell'job in coda all'ingresso delle macchine 2 o 3.

Quesito 3

Si illustri il problema dello zero ad zero e si spieghi la sua complessità.

Si ipotizzi che un generatore di numeri casuali da 0 a 1 produca l'elenco che seguono valori: 0.93, 0.45, 0.12, 0.98, 0.58, 0.75, 0.35, 0.27, 0.65, 0.60, 0.97, 0.83, 0.11, 0.07.