Esercizio 5.2.6

0 passi visti su 5

Consegna

Si supponga di voler caricare uno zaino di capacità massima di 17 kg avendo a disposizione 4 oggetti diversi con peso e profitto riportati nella seguente tabella: Oggetto Peso (in kg) Profitto (in euro) 184026243515448 Si descriva il modello matematico del problema dello zaino frazionario con riferimento al problema descritto e lo si risolva trovandone una soluzione ottima; 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.

0Modelloapri

x_j

1Zaino frazionarioapri

x_3 = \frac{3}{5}

2Programmazione dinamicaapri

m

$m$ \ $\hat W$	4	5	6	7	8	9	10	11	12	13	14	15	16	17
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	40	40	40	40	40	40	40	40	40	40
2	0	0	24	24	40	40	40	40	40	40	64	64	64	64
3	0	15	24	24	40	40	40	40	40	55	64	64	64	64
4	8	15	24	24	40	40	40	40	48	55	64	64	64	64

3Branch & Boundapri

x_j = 0

Nodo	Variabili fissate	Bound	Esito
$Z_1$	nessuna	73	si ramifica su $x_3$
$Z_2$	$x_3 = 0$	70	si ramifica su $x_4$
$Z_4$	$x_3 = 0$ , $x_4 = 0$	64	intero: $z_{\mathrm{opt}} = 64$
$Z_5$	$x_3 = 0$ , $x_4 = 1$	68	si ramifica su $x_2$
$Z_6$	$x_2 = 0$ , $x_3 = 0$ , $x_4 = 1$	48	chiuso, $48 \le 64$
$Z_7$	$x_2 = 1$ , $x_3 = 0$ , $x_4 = 1$	67	si ramifica su $x_1$
$Z_8$	$x_1 = 0$ , $x_2 = 1$ , $x_3 = 0$ , $x_4 = 1$	32	chiuso
$Z_9$	$x_1 = 1$ , $x_2 = 1$ , $x_3 = 0$ , $x_4 = 1$		inammissibile (18 kg)
$Z_3$	$x_3 = 1$	71	si ramifica su $x_2$
$Z_{10}$	$x_2 = 0$ , $x_3 = 1$	63	chiuso
$Z_{11}$	$x_2 = 1$ , $x_3 = 1$	69	si ramifica su $x_1$
$Z_{12}$	$x_1 = 0$ , $x_2 = 1$ , $x_3 = 1$	47	chiuso
$Z_{13}$	$x_1 = 1$ , $x_2 = 1$ , $x_3 = 1$		inammissibile (19 kg)

4Soluzioneapri

x = (1, 1, 0, 0)

$m$ \ $\hat W$	4	5	6	7	8	9	10	11	12	13	14	15	16	17
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	40	40	40	40	40	40	40	40	40	40
2	0	0	24	24	40	40	40	40	40	40	64	64	64	64
3	0	15	24	24	40	40	40	40	40	55	64	64	64	64
4	8	15	24	24	40	40	40	40	48	55	64	64	64	64

$m$ \ $\hat W$	4	5	6	7	8	9	10	11	12	13	14	15	16	17
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	40	40	40	40	40	40	40	40	40	40
2	0	0	24	24	40	40	40	40	40	40	64	64	64	64
3	0	15	24	24	40	40	40	40	40	55	64	64	64	64
4	8	15	24	24	40	40	40	40	48	55	64	64	64	64

$m$ \ $\hat W$	4	5	6	7	8	9	10	11	12	13	14	15	16	17
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	40	40	40	40	40	40	40	40	40	40
2	0	0	24	24	40	40	40	40	40	40	64	64	64	64
3	0	15	24	24	40	40	40	40	40	55	64	64	64	64
4	8	15	24	24	40	40	40	40	48	55	64	64	64	64