Esercizio 5.2.1

0 passi visti su 5

Consegna

Si supponga di voler caricare uno zaino di capacità massima di 9 kg avendo a disposizione 4 oggetti diversi con peso e profitto riportati nella seguente tabella:

OggettoPeso (in kg)Profitto (in euro)
134
212
323
471
  1. Si descriva il modello matematico del problema dello zaino frazionario con riferimento al problema descritto e lo si risolva trovandone una soluzione ottima;
  2. Si descriva il modello matematico del problema dello zaino 0/1 con riferimento al problema descritto e lo si risolva trovandone una soluzione ottima tramite applicazione di (a) un algoritmo di Programmazione Dinamica; (b) un algoritmo Branch & Bound.
Apri nello zaino
0Modelloapri

Con xjx_j la parte dell'oggetto jj che si carica:

max⁡ 4x1+2x2+3x3+1x4s.a. 3x1+x2+2x3+7x4≤9\begin{aligned} \max\ & 4x_1 + 2x_2 + 3x_3 + 1x_4 \\ \text{s.a.}\ & 3x_1 + x_2 + 2x_3 + 7x_4 \le 9 \end{aligned}

Nel frazionario 0≤xj≤10 \le x_j \le 1; nello zaino 0/1 xj∈{0,1}x_j \in \{0, 1\}.

1Zaino frazionarioapri

I rapporti pj/wjp_j / w_j valgono 43\frac{4}{3}, 2, 32\frac{3}{2} e 17\frac{1}{7}, quindi l'ordine è 2, 3, 1, 4. Gli oggetti 2, 3 e 1 entrano interi (6 kg) e restano 3 kg; l'oggetto 4 pesa 7 ed è critico: x4=37x_4 = \frac{3}{7}.

Soluzione x=(1,1,1,37)x = (1, 1, 1, \frac{3}{7}) con z=9+37=667z = 9 + \frac{3}{7} = \frac{66}{7}.

2Programmazione dinamicaapri

fm,W^=max⁡{fm−1,W^, fm−1,W^−wm+pm}f_{m,\hat W} = \max\{f_{m-1,\hat W},\ f_{m-1,\hat W - w_m} + p_m\}, con f0,W^=0f_{0,\hat W} = 0.

mm \ W^\hat W0123456789
00000000000
10004444444
20224666666
30235679999
40235679999

Per esempio f3,6=max⁡{f2,6, f2,4+3}=max⁡{6,9}=9f_{3,6} = \max\{f_{2,6},\ f_{2,4} + 3\} = \max\{6, 9\} = 9. Si risale da f4,9=9f_{4,9} = 9: f4,9=f3,9f_{4,9} = f_{3,9} dà x4=0x_4 = 0; f3,9≠f2,9f_{3,9} \ne f_{2,9}, f2,7≠f1,7f_{2,7} \ne f_{1,7} e f1,6≠f0,6f_{1,6} \ne f_{0,6} danno x3=x2=x1=1x_3 = x_2 = x_1 = 1.

3Branch & Boundapri

Il bound di un nodo è lo zaino frazionario con le variabili già fissate.

  • Z1Z_1, nessuna variabile fissata: è il frazionario, con z=667z = \frac{66}{7} e x4x_4 frazionaria. Si ramifica su x4x_4.
  • Z2Z_2, con x4=0x_4 = 0: soluzione (1,1,1,0)(1, 1, 1, 0), intera, con z=9z = 9. Diventa l'ottimo corrente, zopt=9z_{\mathrm{opt}} = 9.
  • Z3Z_3, con x4=1x_4 = 1: restano 2 kg, che prendono l'oggetto 2 e metà del 3, quindi il bound è 1+2+32=921 + 2 + \frac{3}{2} = \frac{9}{2}. Siccome 92≤9\frac{9}{2} \le 9, il nodo si chiude.
4Soluzioneapri

Lo zaino 0/1 ha ottimo x=(1,1,1,0)x = (1, 1, 1, 0), cioè gli oggetti 1, 2 e 3, con z=9z = 9 e peso 6 kg. Il bound del frazionario, 667\frac{66}{7}, è più grande, come deve essere.