Ricerca operativa II - metodi per le decisioni

UNIVERSITA' DEGLI STUDI DI NAPOLI FEDERICO II CORSO DI RICERCA OPERATIVA II Prova di esame del 18.11.2009

Quesito 1

Si consideri un problema di 2.mediana definito dalla matrice dei minimi percorsi indicata.

1 2 3 4 5 6 7 1 0 2 6 4 6 9 6 2 0 3 5 7 8 7 10 3 9 4 3 5 8 4 6 4 7 5 8 10 15 15 13 5 5 6 7 8 15 10 8 6 6 9 7 8 9 8 13 7 10 6 11 13 8 8 0

• a) Si illustri il modello matematico rappresentativo del problema specificando il significato dei vincoli e delle variabili
• b) Si determini una prima soluzione casualmente
• c) Si effettuino due iterazioni di un algoritmo di Trab Search per la risoluzione del problema;
• d\*) Si proponga un algoritmo costruttivo per il problema del 2-centro in cui bisogna minimizzare la distanza dall'utente nelle condizioni più sfavorevole

Quesito 2

• a) Si illustri il modello matematico del problema del commesso viaggiatore multiplo
• b) Con riferimento alla stessa matrice dei minimi percorsi indicata al punto 1, si consideri un problema di 2-TSP e lo si risolva applicando opportunamente una procedura Route First- Cluster Second.

Quesito 3

• a) Utilizzando una metodologia a piacere, si risolva il problema di scheduling la cui matrice di routing è indicata in figura.
• b) Si illustri la metodologia proposta, illustrando i motivi della scelta.

J2, J3, J4

Macchina 1

J2, J3, J4

J2, J3, J4

Macchina 3

Macchina 2

J1, J5

Macchina 4

J1, J5

1 2 3 Job 1 6 3 Job 2 8 6 4 Job 3 5 7 3 Job 4 2 5 3 Job 5 4 6