Problema dello zaino multidimensionale (MDKP)

Catalogo dei problemi di ottimizzazione combinatoria · Problemi di zaino · Catalogo (PDF)

Definizione 1: Problema dello zaino multidimensionale

Dati:

1. uno zaino \(k\)-dimensionale,

2. per ogni dimensione \(d \in \underbrace{\{1,2,\dots,k\}}_{=\mathscr{D}}\), una capacità \(c_d \in \Z_{\ge 1}\),

3. un insieme \(\mathscr{I} = \{1,2,\dots,n\}\) di \(n\) oggetti,

4. per ogni oggetto \(j \in \mathscr{I}\), un profitto \(p_j \in \Z_{\ge 1}\),

5. per ogni dimensione \(d \in \mathscr{D}\) e ogni oggetto \(j \in \mathscr{I}\), un peso \(w_{dj} \in \Z_{\ge 1}\),

il problema dello zaino multidimensionale (MDKP) chiede di decidere quali oggetti inserire nello zaino, in modo che per ogni dimensione il peso totale degli oggetti selezionati non superi la capacità corrispondente e il profitto totale degli oggetti selezionati sia massimo.

Ipotesi

• Facciamo le seguenti ipotesi:

  1. L'insieme di tutti gli oggetti non entra nello zaino (altrimenti selezionare tutti gli oggetti è ammissibile e ottimo). Formalmente,

     \[ \exists\, d\in \mathscr{D} \ \text{tale che}\ \sum_{j\in \mathscr{I}} w_{dj} \;>\; c_d . \]

  2. Ogni oggetto, da solo, entra nello zaino in ogni dimensione (altrimenti non può mai essere selezionato). Formalmente,

     \[ w_{dj} \le c_d, \qquad \forall\, d\in \mathscr{D},\ \forall\, j\in \mathscr{I}. \]

Che cosa fa il corso su questo problema

Tecnica	Dove
Definizione	Cap. 2 «Problemi di zaino»
Formulazioni	Cap. 9 «Formulazioni dei problemi di zaino»
Programmazione dinamica	Cap. 16 «Principi della programmazione dinamica»; Cap. 22 «PD per il problema dello zaino multidimensionale»
Esercizi	Esercizio 9.9; Cap. 22 (5 esercizi)