Metodi per le decisioni Ricerca operativa II - Esercizi

Università degli Studi di Napoli Federico II

Corso di Ricerca Operativa II

Prova di esame del 19.06.2008

Quesito 1

Si consideri un problema di localizzazione definito dalla matrice dei costi di afferenza e dal vettore dei costi di localizzazione indicati.

12345678192575910821464791210335273811134562869101255568157966759726878910101052581010111211743

Matrice dei costi di afferenza

Nodi 12345678

Costi di localizzazione 12915107131010

a) Volendo individuare la soluzione che minimizzi il costo totale di localizzazione assicurando che il costo di afferenza totale risulti non superiore a 38, a partire da una soluzione ammissibile individuata casualmente, si imposti e si effettui una iterazione di un algoritmo di Tabu Search basato su una mossa a piacere.

b) Assumendo come obiettivi separati il costo di localizzazione ed il costo di afferenza, si indichino le soluzioni di Pareto tra quelle appartenenti all’intorno generato al punto a).

Quesito 2

Si consideri un problema di routing la cui matrice dei minimi percorsi coincida con la matrice dei costi di afferenza relativa al quesito 1.1. Assumendo il nodo 1 come nodo deposito.

a) Si risolva un problema di 2-TSP utilizzando un algoritmo a piacere assumendo come obiettivo la somma della lunghezza dei circuiti;

b)** Si illustri e si applichi un algoritmo costruttivo orientato alla soluzione di un 2-TSP nel caso in cui ciascun nodo possa essere visitato a partire dall’istante indicato in tabella, assumendo come obiettivo la minimizzazione della durata massima di un circuito.

Nodi 2345678

Istante minimo di visita 2118918231215

Quesito 3

Si consideri il problema F2||Cmax in cui i job seguano la sequenza A-B, assumendo i tempi di processamento indicati.

Job 123456

Macchina A 545642

Macchina B 211514

a) Si individui la soluzione ottima del problema;

b)* Si risolva un problema di scheduling, con obiettivo Cmax, in cui, oltre ai 6 job indicati siano presenti altri 3 job caratterizzati dalla matrice di routing e dei tempi di processamento di seguito indicate.

Job/operazioni 123152623123811

Matrice tempi di processamento

Job/operazioni 1231BA2BA3ABA

Matrice routing