Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 14.Il Problema dello Zaino 0/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.

Il Problema dello Zaino Frazionario: un algoritmo greedy

Gli oggetti \{o_1,o_2,\ldots,o_n\} vengono ordinati e rienumerati in ordine non crescente di profitto per unità di peso:

\[ \frac{p_1}{w_1}\geq\frac{p_1}{w_2}\geq\cdots\geq\frac{p_n}{w_n}. \]

Ciò fatto, si individua l’oggetto critico s\in\{1,2,\ldots,n\} , cioè l’oggetto tale che

\[ \displaystyle{\sum_{j=1}^{s-1} w_j<W\leq \sum_{j=1}^{s} w_j}. \]

Il Problema dello Zaino Frazionario: un algoritmo greedy, 2

La soluzione ottima x^* di \mbox{Z-c}_{0/1} è data da

x^*_1=x^*_2=\cdots=x^*_{s-1}=1 ;

x^*_s=\frac{W-\displaystyle{\sum_{j=1}^{s-1}w_j}}{w_s} ;

x^*_{s+1}=x^*_{s+2}=\cdots=x^*_n=0 .

Il Problema dello Zaino Frazionario: un algoritmo greedy, 3

L’ordinamento degli oggetti (ordine non crescente di profitto per unità di peso) richiede

\[O(n\log n).\]

La costruzione della soluzione ottima x^* di \mbox{Z-c}_{0/1} richiede O(n) .

Ne consegue che la complessità dell’algoritmo greedy per il Problema dello Zaino Frazionario è
\[ O(n\log n). \]

I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion