Marzo 07 Compitoa

Metodi e modelli per il supporto alle decisioni – Prof Caprara Marzo 2007 Compito A

Un’azienda vuole confezionare regali natalizi per i suoi clienti partendo da un insieme di oggetti {1,…,n}. Ogni oggetto j ha un valore vj, ed ogni regalo deve contenere oggetti per un valore complessivo non inferiore a V. Inoltre, l’insieme degli oggetti è partizionato nei sottoinsiemi S1,…,Sp (cioè S1 U…U Sp = {1,…,n}, e Sh ∩ Sk = Ø per h≠k) ciascuno contenente oggetti simili, ed ogni regalo non può contenere due (o più) oggetti appartenenti allo stesso sottoinsieme. Infine ogni oggetto può essere inserito al massimo in un regalo. L’obiettivo è confezionare il massimo numero di regali che soddisfino i vincoli sopra. 1) Si scriva un modello ILP descrittivo, discutendo eventualmente il numero e la “forza” o “debolezza” dei vincoli relativi ai sottoinsiemi S1,…,Sp 2) Algoritmo euristico guidato dal rilassamento continuo 3) Modello ILP con una variabile associata ad ogni sottoinsieme di oggetti inseribili in un regalo, discutendo eventualmente la possibilità di ridurre questo numero di variabili 4) Modello ILP per la generazione di colonne del punto 3 5) Si discutano variazioni dei punti 1 e 3 per la variante in cui il numero dei regali da confezionare sia fissato pari ad m, i vincoli relativi a S1,…,Sp invariati, i vincoli sul valore minimo V eliminati, e si voglia massimizzare il minimo valore di un regalo (cioè si voglia massimizzare min {V1,…,Vm} dove Vi indica il valore complessivo degli oggetti contenuti in Vi).