Metodi per le decisioni Ricerca operativa II - Esercizi

Università degli studi di Napoli Federico II

Corso di metodi per le decisioni - Ricerca operativa II

Prova di esame del 06.02.2012

Quesito 1

Si consideri un problema di routing definito dalla matrice dei costi indicata in tabella con il nodo come deposito e si supponga di avere a disposizione una flotta di tre veicoli.

12345678910891215910147280741186108397078131181141247010714101551511810012129106981371209111271061114129081081410810911809978111510121090

• Si risolva un problema di 3-TSP assumendo come funzione obiettivo la minimizzazione della somma delle lunghezze dei circuiti.
• Dopo aver introdotto una misura dello sbilanciamento tra le lunghezze dei circuiti assegnati ai veicoli, si sviluppi un algoritmo costruttivo che punti a minimizzare tale misura.
• A partire dalla soluzione individuata al punto b), si effettui una iterazione di un algoritmo di Simulated Annealing assumendo una temperatura pari ad un terzo del valore della funzione obiettivo.

Quesito 2

Si consideri il seguente problema di scheduling caratterizzato dal routing indicato per ogni job.

Job12345678910

p_1i2-3-5--64-7

p_2i-6-8-----2-

p_3i-4-4-32--3

Routing3-123-121-333-1121-3

• Si individui una soluzione del problema con obiettivo Cmax.
• Facendo riferimento alla soluzione individuata, apportando delle modifiche, si mostri un esempio di soluzione attiva e soluzione senza ritardo del problema.

Quesito 3

Si consideri un problema di lot sizing caratterizzato dalla domanda riportata in tabella considerando il prezzo di acquisto del prodotto pari a 50, il costo di mantenimento unitario pari al 24% all’anno mese e il costo di ordinazione pari a 100.

• Si risolva il problema utilizzando uno dei metodi scelto a piacere;
• Si illustri il modello del lot sizing e lo si particolarizzi per il caso in esame;
• Si mostri come la soluzione individuata al punto a) risulti ammissibile.

Mese12345

Domanda2010401020

Dove occorre, si utilizzino, nell’ordine, i numeri casuali: 0,12, 0,78, 0,56, 0,28, 0,44, 0,02, 0,88, 0,21, 0,63, 0,71, 0,13, 0,60, 0,53, 0,96, 0,23; 0,78; 0,61; 0,69; 0,54; 0,43; 0,18.