:: Ricerca Operativa - PLI - 15 giugno 2004 ::
Testo
Nel problema di Knapsack (KP) si ha un insieme di oggetti dati, ciascuno con un valore ed un volume noti. Si ha uno zaino di capacità nota e si vuole scegliere un sottinsieme di oggetti tali che il volume complessivo degli oggetti scelti non ecceda la capacità dello zaino ed il valore complessivo degli oggetti scelti sia massimo.
Si consideri la seguente variante del problema, denominata “Penalized KP”, cioè problema di zaino con penalità: ad ogni oggetto è associata anche una penalità ed il valore della funzione obiettivo da massimizzare è i lvalore totale degli oggetti scelti meno la massima penalità tra quelle associate agli oggetti scelti.
Formulare il problema, classificarlo e risolverlo con i dati contenuti nel file PENALIZED KP.TXT. Discutere unicità e ottimalità della soluzione ottenuta.
Gli oggetti sono 30.
Oggetto 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Valore 27 41 23 32 39 8 50 2 30 54 85 2 23 18 73 41 78 32 18 23 34 58 12 31 63 14 13 87 56 32
Volume 10 58 97 23 19 5 71 94 81 92 74 3 41 57 12 47 10 25 61 23 74 28 62 35 63 49 13 95 87 23
Penalty 34 59 87 34 40 29 84 67 53 48 53 85 37 49 85 37 90 57 62 34 75 88 43 75 93 75 39 58 37 6
La capacità disponibile è pari a 1000 unità di volume.
Soluzione
Dati
I dati che abbiamo sono:
- oggetti
- N = 30 : numero di oggetti
- valorei, i = 1..N : valore dell'i-esimo oggetto
- volumei, i = 1..N : volume dell'i-esimo oggetto
- penalitai, i = 1..N : penalità dell'i-esimo oggetto
- maxvol = 1000 : massima capacità del sacco
Variabili
Quello che dobbiamo decidere è quali oggetti mettere nel sacco e quali no. Per modellare ciò, usiamo una variabile binaria indicizzata con N elementi, i quali ci dicono se l'elemento è stato messo nel sacco, oppure no:
xi, i=1..N: variabile binaria: 1 = l'oggetto è stato scelto, 0 no
Funzione obiettivo
Come spiegato nel testo, voglio avere sì il massimo valore degli oggetti nel sacco, senza eccedere nel volume, ma a questo valore devo sottrarre la massima penalità tra quelle degli oggetti scelti.
Per fare un esempio, se ho scelto 10 oggetti e il valore complessivo è 503, e la penalità massima di questi oggetti è quella dell'oggetto 7, la quale vale 32, allora il mio massimo è 503 - 32 = 471.
max (SOMMAi xi * valorei) - maxPenalità
Per definire bene la penalità, aggiungeremo dei vincoli.
Vincoli
Il primo vincolo è quello sulla capacità: il volume di tutti gli oggetti selezionati non deve eccedere maxvol:
SOMMA(xi * pesoi) <= maxvol, i = 1..N
La variabile xi è binaria, quindi l'oggetto non selezionato avrà la sua xi = 0, e siamo felici.
Poi, occorre vincolare la maxPenalità:
maxPenalita >= xi * penalitai, i = 1..N
In questo modo, la maxPenalita sarà maggiore alla più alta penalità tra gli oggetti selezionati. Come sopra, la variabile xi ci assicura che solo gli oggetti selezionati verranno presi in considerazione (avranno xi = 1).
Codice Lingo
model:
sets:
oggetto /1..30/: volume, valore, penalita, x;
endsets
data:
valore = 27 41 23 32 39 8 50 2 30 54 85 2 23 18 73
41 78 32 18 23 34 58 12 31 63 14 13 87 56 32;
volume = 10 58 97 23 19 5 71 94 81 92 74 3 41 57 12
47 10 25 61 23 74 28 62 35 63 49 13 95 87 23;
penalita = 34 59 87 34 40 29 84 67 53 48 53 85 37 49 85
37 90 57 62 34 75 88 43 75 93 75 39 58 37 6;
maxvol = 1000;
enddata
!Funzione obiettivo;
max = @sum(oggetto(i): x(i) * valore(i)) - maxpenalita;
!Vincoli per definire maxpenalita;
@for(oggetto(i): maxpenalita >= x(i) * penalita(i));
!Vincolo sulla capacità;
@sum(oggetto(i): x(i) * volume(i)) <= maxvol;
! Binarietà di x;
@for(oggetto(i): @bin(x));
end
Discussione su unicità e ottimalità
Risolvendo il problema, Lingo ci dice che è arrivato al Global Optimum. Ne siamo felici. Per quanto riguarda l'unicità, Lingo non ci dice nulla, e la soluzione del professore dice che non si sa niente dell'unicità, e pertanto dichiariamo che non è necessariamente unica.
Torna alla pagina di Ricerca Operativa
