Home

Federica EU

1/8

1 e il Problema dello Zaino Frazionario.

Il Problema dello Zaino 0/1,

I Problemi dello Zaino si collocano fra i classici problemi di ottimizzazione.

In quanto segue studieremo il Problema dello Zaino 0/1 ed il Problema dello Zaino Frazionario, descrivendone
la formulazione matematica e discutendo dei metodi per risolverli.

Il Problema dello Zaino 0/1, 1

Siano dati uno zaino di capacità limitata pari a $W$ ed un insieme di $n$ oggetti $O=\{o_1,o_2,\ldots,o_n\}$ .

A ciascun oggetto $o_j\in O$ è associato un peso $w_j$ ed un profitto $p_j$ .
Senza perdita di generalità, possiamo assumere che $w_j,\ p_j\in {\mathbb Z},\ \forall\ o_j\in O$ .

Il Problema dello Zaino 0/1 consiste nell’individuare un sottoinsieme di oggetti da inserire nello zaino tale da massimizzare il profitto totale senza eccedere la capacità $W$ dello zaino.

E’ banale ipotizzare che

$\displaystyle{\sum_{j=1}^n w_j>W}$ ;

$w_j\leq W,\ j=1,2,\ldots,n$ .

Il Problema dello Zaino 0/1, 2

Introducendo $n$ variabili di decisione $x_1,x_2,\ldots,x_n$ , dove per ogni $j=1,2,\ldots,n$

$x_j=\left\{\begin{array}{ll} 1, &\mbox{se l'oggetto$j$\`e inserito nello zaino};\\0,&\mbox{altrimenti,}\end{array}\right.$

si ottiene il seguente problema di PLI

$\begin{array}{lllll} \mbox{{\rm (Z$_{0/1}$)}} & \mbox{{\rm max}}&\displaystyle{\sum_{j=1}^n p_jx_j} \\& \mbox{{\rm s.a}} \\&&amp\displaystyle{\sum_{j=1}^n w_jx_j}\leq W \\ & & x\in \{0,1\}^n.\end{array}$

Il Problema dello Zaino Frazionario, 1

Il rilassamento continuo di $\mbox{Z}_{0/1}$ ha la seguente formulazione matematica
$\begin{array}{lllll} \mbox{{\rm (Z-c$_{0/1}$)}} & \mbox{{\rm max}} & \displaystyle{\sum_{j=1}^n p_jx_j} \\ & \mbox{{\rm s.a}} \\ & & \displaystyle{\sum_{j=1}^n w_jx_j}\leq W \\ & & 0\leq x_j\leq 1,\ j=1,2,\ldots,n. \end{array}$

Il problema $\mbox{Z-c}_{0/1}$ , noto come il Problema dello Zaino Frazionario, in quanto è lecito selezionare anche percentuali, frazioni di oggetti, ammette sempre una soluzione massimale, cioè il peso totale della combinazione di oggetti selezionati è sempre pari a $W$ .

A differenza di $\mbox{Z}_{0/1}$ che è un problema difficile dal punto di vista computazionale, $\mbox{Z-c}_{0/1}$ è un problema risolvibile in tempo polinomiale mediante l’applicazione di un semplice algoritmo greedy descritto in quanto segue.

Il Problema dello Zaino Frazionario, 2

Prima di descrivere l’algoritmo greedy per trovare una soluzione ottima al Problema dello Zaino Frazionario, è opportuno richiamare le caratteristiche principali di una qualunque tecnica di tipo greedy.

Una qualunque tecnica di tipo greedy (goloso) procede iterativamente.
A partire da una soluzione vuota, ad ogni iterazione viene aggiunto un elemento e alla soluzione parziale in costruzione.
Fra tutti i possibili candidati ad essere aggiunti, l’elemento e è quello più promettente, ossia quello che, se scelto, porta ad un maggiore miglioramento della funzione obiettivo.

E’ chiaro che non tutti i problemi possono essere risolti all’ottimo con questa strategia, ma solo quelli per i quali è possibile dimostrare che effettuare la scelta migliore al momento conduce ad una soluzione ottima globalmente.
Ed è appunto questo il caso del Problema dello Zaino Frazionario e del Problema del Minimum Spanning Tree di un grafo, come vedremo fra qualche lezione.