Spiegazione svolgimento problema dello zaino
Salve a tutti, avrei bisogno di capire lo svolgimento di questo esercizio...purtroppo non ho fatto nulla di ricerca operativa alla triennale ed ora alla magistrale mi ritrovo a fare della programmazione lineare con un bel po' di buchi 
L'esercizio è il seguente : " si consideri il seguente problema dello zaino
$ max z = 10 x_{1}+4x_{2}+14x_{3} , 3x_{1}+x_{2}+4x_{3} <= 4, x_{1}, x_{2}, x_{3} \in {0,1} $
calcolare la soluzione ottima del rilassamento lineare del problema dato e il valore ottimo corrispondente.
E' stato risolto così: sono stati calcolati i rapporti beneficio/ingombro $\frac{10}{3}, \frac{4}{1}, \frac{14}{4} $ ed è stato osservato che $x_{2}>x_{3}>x_{1} $ (*), la soluzione ottima (SO) del rilassamento risluta essere $x=(0,1,\frac{3}{4})$.
Ora le mie domande sono : perché si calcolano quei rapporti ? Come si ricava la soluzione ottima di un rilassamento lineare ?? inoltre, le componenti della SO sono in ordine, cioè x1,x2,x3 oppure come è stato ricavato da (*) ??
GRAZIE MILLE A CHIUNQUE ME LO SPIEGHERA', E' MOLTO IMPORTANTE. GRAZIE ANCORA.
L'esercizio è il seguente : " si consideri il seguente problema dello zaino
$ max z = 10 x_{1}+4x_{2}+14x_{3} , 3x_{1}+x_{2}+4x_{3} <= 4, x_{1}, x_{2}, x_{3} \in {0,1} $
calcolare la soluzione ottima del rilassamento lineare del problema dato e il valore ottimo corrispondente.
E' stato risolto così: sono stati calcolati i rapporti beneficio/ingombro $\frac{10}{3}, \frac{4}{1}, \frac{14}{4} $ ed è stato osservato che $x_{2}>x_{3}>x_{1} $ (*), la soluzione ottima (SO) del rilassamento risluta essere $x=(0,1,\frac{3}{4})$.
Ora le mie domande sono : perché si calcolano quei rapporti ? Come si ricava la soluzione ottima di un rilassamento lineare ?? inoltre, le componenti della SO sono in ordine, cioè x1,x2,x3 oppure come è stato ricavato da (*) ??
GRAZIE MILLE A CHIUNQUE ME LO SPIEGHERA', E' MOLTO IMPORTANTE. GRAZIE ANCORA.
Risposte
Posso aiutarti solo per la prima parte, riprendiamo la definizione del problema dello zaino:
Dall'equazione $max z$ ricavi i valori degli oggetti, mentre dalla disuguaglianza ricavi i corrispondenti pesi e anche la capacità dello zaino.
Si capisce quindi che la capacità dello zaino è 4 (il termine noto della disuguaglianza).
Essendo il problema binario (le variabili possono assumere solo i valori 0 oppure 1) si avrà un solo oggetto per ogni variabile, quindi 3 oggetti in totale: il primo con peso 3 e valore 10, il secondo con peso 1 e valore 4, il terzo con peso 4 e valore 14. Calcolare i rapporti valore/peso ti da un'idea di quali oggetti sia meglio preferire: se un oggetto ha un alto valore ma anche un alto peso (rapporto vicino a 1) allora è meglio preferire ad esso altri oggetti in quanto lo zaino ha capacità limitata.
I rapporti sono: per $x_1$ 3.33, per $x_2$ 4, per $x_3$ 3.5, dunque il migliore oggetto è x2, seguito da x3 e infine x1, da qui si ha l'equazione $x_{2}>x_{3}>x_{1}$
Sia dato uno zaino che possa sopportare un determinato peso e siano dati inoltre N oggetti, ognuno dei quali caratterizzato da un peso e un valore. Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere il maggiore valore senza eccedere il peso sostenibile dallo zaino stesso
Dall'equazione $max z$ ricavi i valori degli oggetti, mentre dalla disuguaglianza ricavi i corrispondenti pesi e anche la capacità dello zaino.
Si capisce quindi che la capacità dello zaino è 4 (il termine noto della disuguaglianza).
Essendo il problema binario (le variabili possono assumere solo i valori 0 oppure 1) si avrà un solo oggetto per ogni variabile, quindi 3 oggetti in totale: il primo con peso 3 e valore 10, il secondo con peso 1 e valore 4, il terzo con peso 4 e valore 14. Calcolare i rapporti valore/peso ti da un'idea di quali oggetti sia meglio preferire: se un oggetto ha un alto valore ma anche un alto peso (rapporto vicino a 1) allora è meglio preferire ad esso altri oggetti in quanto lo zaino ha capacità limitata.
I rapporti sono: per $x_1$ 3.33, per $x_2$ 4, per $x_3$ 3.5, dunque il migliore oggetto è x2, seguito da x3 e infine x1, da qui si ha l'equazione $x_{2}>x_{3}>x_{1}$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo