1.75 Esercizio. Nel problema del knapsack continuo si effettui la trasformazione di varia- bile y

1.75 Esercizio. Nel problema del knapsack continuo si effettui la trasformazione di varia- bile y

= b

x

, in modo da risolvere il seguente problema:

max



a

b

y



y

≤ c 0 ≤ y

≤ b

∀i

(1)

Si deduca la struttura della soluzione ottima.

Soluzione. Si immagini di costruire la soluzione a partire da y

= 0, ∀i. Siccome c’`e simmetria fra le variabili per il vincolo 

i=1

y

≤ c, conviene assegnare valore positivo alla componente corrispondente al massimo rapporto a

/b

. Si saturi allora tale variabile (cio`e fino a y

= b

)oppure si saturi il vincolo 

i=1

y

≤ c. Si prosegua allora assegnando il massimo valore positivo alla variabile corrispondente al secondo rapporto a

/b

e cos`ı di seguito fino alla saturazione del vincolo 

i=1

y

≤ c. La soluzione cos`ı ottenuta `e un massimo. Infatti ogni altra soluzione si pu` o ottenere diminuendo i valori di componenti con rapporto a

/b

pi` u alto e aumentando quelli di componenti con rapporto a

/b

pi` u basso.

1