Il knapsack in pratica

Risolviamo il seguente problema:

max	4x1	+2x2	+3x3	-5x4	-x5	+x6
	3x1	-3x2	+x3	+x4	-x5		≤1/2

x∈{0,1}⁶

La prima riga è il problema, ed è rappresentato dalla formula

$\sum _{j=1}^n{c}_j{x}_j$

per j = 1, c_j = 4
per j = 2, c_j = 2
eccetera

La seconda riga è il vincolo, ed è rappresentato dalla formula

$\sum _{j=1}^n{a}_j{x}_j\le b$

per j = 1, a_j = 3
per j = 2, a_j = 3
per j = 3, a_j = 1
eccetera
infine, b = 1/2

Riepiloghiamo le prime semplificazioni possibili in questo prospetto:

	c < 0	c = 0	c > 0
a < 0	xj = 1 - yj	1	1
a = 0	0	0	1
a > 0	0	0	xj

Nell'esempio:

1. c>0, a>0
2. c>0, a<0 => x₂ = 1
3. c>0, a>0
4. c<0, a>0 => x₄ = 0
5. c<0, a<0 => x₅ = 1-y₅
6. c>0, a=0 => x₆ = 1

Sostituendo nel problema i valori noti e la sostituzione di x₅, otteniamo

max	4x1	+2*1	+3x3	-5*0	-(1-y5)	+1
	3x1	-3	+x3		-(1-y5)		≤1/2

con 0 ≤ x₁, x₃, y₅ ≤ 1

il problema si può riscrivere come

max	4x1	+3x3	+y5	+2
	3x1	+x3	+y5	≤9/2

A questo punto, bisogna ordinare le variabili in base al rapporto tra c e a: 4/3, 3/1, 1/1.

$\frac{3}{1}\ge \frac{4}{3}\ge \frac{1}{1}$

e bisogna verificare quanti di questi numeri ∈ℚ, sommati tra loro nell'ordine, sono minori o uguali di 4,5.

3 < 4,5

3 + 4/3 < 4,5

3 + 4/3 + 2 > 4,5

quindi il nostro indice è 2.

x₁, a cui corrisponde la frazione 4/3, vale 1

x₃, a cui corrisponde 3, vale 1

y₅, a cui corrisponde l'ultimo 1, vale

$\frac{b-\sum _{k=1}^h{a}_k}{a_{h+1}}$

quindi

$\frac{4.5-\left(1+3\right)}{1}=0.5$

Se y₅ = 0,5 allora x₅ = 1-0,5 = 0,5

La soluzione è quindi x₁ = 1; x₂ = 1; x₃ = 1; x₄ = 0; x₅ = 0.5; x₆ = 1;