Ricerca operativa II - i metodi per le decisioni

Università degli studi di Napoli Federico II

Corso di ricerca operativa II

Prova di esame del 12.05.2008

Quesito 1

Si consideri un problema di Flow Shop su quattro macchine (secondo la successione 1-2-3-4) descritto dalla seguente matrice dei tempi di processamento e si generi una soluzione del problema utilizzando una procedura di tipo bottleneck.

Si effettui una iterazione di un algoritmo di Simulated Annealing assumendo una temperatura pari a 15.

Quesito 2

a) Si illustrino gli algoritmi di inserimento per il TSP.

b) Con riferimento alla matrice dei minimi percorsi indicata, a partire dalla soluzione parziale 1-3-4-1 si completi la soluzione utilizzando un algoritmo di inserimento nelle versioni (i) nearest insertion, (ii) cheapest insertion, (iii) random insertion.

c) A partire dalla soluzione individuata si effettui una iterazione di un algoritmo genetico per la sua risoluzione.

d) Rispetto ad una delle soluzioni individuate al punto b) si effettui una stima dell'errore della funzione obiettivo rispetto alla soluzione ottima.

Quesito 3

Si illustri il modello generale di progetto su rete e si descriva il problema dell'albero minimo con e senza vincoli di capacità evidenziandone le relazioni e le differenze.