Calcolo della soluzione ottima

[fiore051]

Salve a tutti ragazzi, vi scrivo perché non riesco a capire in alcun modo come si trova la soluzione ottima del seguente problema dello zaino....vi spiego la mia difficoltà !
L'esercizio che ho provato a risolvere è il seguente :

$ max z= 35x_{1}+26x_{2}+49x_{3}+71x_{4}+53x_{5} $

$12x_{1}+10x_{2}+14x_{3}+25x_{4}+20x_{5}<=69 $

$ x_1, x_2, x_3, x_4, x_5 >=0 $ interi.

Mi chiede di calcolare la soluzione ottima del rilassamento lineare del problema dato e il valore ottimo corrispondente !
Allora:
il rilassamento lineare del problema dato non è altro che lo stesso problema senza il vincolo di interezza sulle cinque variabili. Ho calcolato il rapporto benefici/ingombro delle variabili e ordinandole mi viene fuori che $x_3 > x_1 > x_4 >x_5>x_2 $.
La soluzione ottima da me calcolata è $(1,1,1,1,\frac{2}{5} )$ che mi dà come valore ottimo $202,5$, ma nella soluzione dell'esercizio la soluzione ottima è $(0,0,\frac{69}{14},0,0)$ con valore ottimo corrispondente $241,5$ che ovviamente è più grande del valore che ho ottenuto io.
Come si fa a determinare questa soluzione ?
GRAZIE MILLE A CHIUNQUE ME LO RIUSCIRA' A SPIEGARE.

[TigranMetz]

Il tuo problema di partenza è una variazione del problema dello zaino. In un problema dello zaino classico, avresti che le tue variabili $x_i$ sono binarie, mentre nel tuo problema sono dei numeri interi, ovvero puoi prendere ogni oggetto con qualsiasi numero di ripetizioni tu voglia. Per questo motivo, il rilassamento continuo vuole soltanto che $x_i \geq 0$, mentre nel rilassamento continuo del problema classico avresti $0 \leq x_i \leq 1$.

Per ottenere la tua soluzione, hai usato l'algoritmo di Dantzig, che lavora sotto l'ipotesi che $0 \leq x_i \leq 1$, ma tu non hai questa limitazione. Quindi, l'algoritmo "stupido" ma efficace da usare in questo caso è:

[*:7qr3z742] Trovo l'elemento con rapporto profitto / peso maggiore;
[/*:m:7qr3z742][*:7qr3z742] Prendo solo quell'elemento fino a saturare la capacità.[/*:m:7qr3z742][/list:u:7qr3z742]

Tale elemento è $x_3$ e ne posso prendere $x_3 = 69 /14$, che mi da un profitto di $49 * 69 / 14 = 241.5$.