Ricerca operativa II - Esercizi

Quesito 1

Si consideri un problema di localizzazione per il quale sono indicati i costi di afferenza.

a) Si illustri il modello matematico del problema di p-mediana;

b) Si generi casualmente una prima soluzione ammissibile del problema di 2-mediana.

c) A partire dalla soluzione ottenuta si sviluppino due iterazioni di un algoritmo di Tabu search.

Si consideri, poi, un problema di localizzazione in cui esiste una domanda associata a ciascun nodo e per il quale si intende individuare la posizione di due servizi con l'obiettivo di bilanciare al massimo la domanda afferente a ciascun servizio (si assuma che la domanda afferisca tutta al servizio più vicino).

d) Si estenda il modello descritto al punto a) specificando una forma possibile per la funzione obiettivo del problema (si consideri il caso generale di p-mediana e il caso p = 2).

e) Si proponga, a partire dalla stessa soluzione generata per il punto b), un algoritmo migliorativo per tale problema e se ne implementi una iterazione.

12345671101013789210101289113912104910413104368588667868987106791112657

Costi di afferenza

Nodi 1234567

Domanda 5141012658

Quesito 2

Si consideri un problema di Flow Shop F4||Cmax considerando per i job da processare la matrice dei tempi di processamento indicata.

a) Si risolva il problema con le regole di Gupta e di Parker;

b) Si punti a migliorare la soluzione con l'approccio bottleneck.

Job/macchina 123413632211442341521441025551233691664

Quesito 3

Si illustri la classificazione dei problemi (trattabili, intrattabili, P, NP, Np-hard) in funzione della loro complessità computazionale.