Ricerca operativa II - Metodi per le decisioni

Università degli Studi di Napoli Federico II

Corso di ricerca operativa II

Prova di esame del 14.10.2009

Quesito 1

Con riferimento alla matrice dei minimi percorsi indicata:

• a) Si individui una prima soluzione del TSP attraverso una procedura casuale;
• b) A partire dalla soluzione così ottenuta si effettui una iterazione di una procedura migliorativa basata su una mossa di 2-opt;
• c) Sempre a partire dalla soluzione individuata al punto a) si effettui una iterazione di un algoritmo di Simulated Annealing utilizzando una mossa 3-opt, assumendo una temperatura pari a 5.

Quesito 2

Si consideri un problema F2||C_max con riferimento alla lista di operazioni indicata (sequenza 1-2).

• a) Si individui una soluzione del problema utilizzando diverse procedure euristiche.
• b) Si risolva il problema attraverso una procedura euristica nell'ipotesi che la seconda macchina risulti inattiva nell'intervallo [5, 12].
• c)* Si risolva il problema F2|r_j|C_max attraverso una procedura euristica.

Quesito 3

• a) Si illustri il problema del lot sizing per singolo prodotto, evidenziandone le proprietà e, quindi, la complessità.
• b) Si consideri un problema di lot sizing caratterizzato dalla domanda indicata in tabella assumendo un costo di mantenimento per periodo per unità di prodotto pari a 2. Fissato il valore f₀=1000, si individui la soluzione con le tecniche del costo minimo per unità di prodotto e per unità di tempo.

Per le operazioni casuali si ipotizzi che un generatore di numeri casuali da 0 a 1 produca i seguenti 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.