Brench & bound: risolvere rilassato

[mistergks]

Sto studiando l'algoritmo brench e bound ma ho un problema.
Non capisco come si trova la parte frazionaria di un punto.
Qualcuno che mi aiuta a capire?

[mistergks]

Cioè... Non so come si risolve il rilassato continuo ...
Poi so andare avanti avendo i due punti

[Intermat]

Non credo di poterti essere troppo di aiuto, ti dico ciò che mi ricordo. Solitamente usi il branch and bound per risolvere un problema di PLI attraverso la risoluzione di problemi di PL. Quindi in ogni nodo del B&B andrai a fare un taglio in modo tale da eliminare la sola parte non intera, una volta fatto ciò avrai due nuovi vincoli e risolvi nuovamente il problema come fatto in precedenza. Il metodo di risoluzione solitamente è il simplesso.
La prima cosa che dovresti specificare è se stai usando il B&B per risolvere un problema di PLI o per altro. Non è che il B&B venga usato solo per quello!

[mistergks]

"Intermat":Non credo di poterti essere troppo di aiuto, ti dico ciò che mi ricordo. Solitamente usi il branch and bound per risolvere un problema di PLI attraverso la risoluzione di problemi di PL. Quindi in ogni nodo del B&B andrai a fare un taglio in modo tale da eliminare la sola parte non intera, una volta fatto ciò avrai due nuovi vincoli e risolvi nuovamente il problema come fatto in precedenza. Il metodo di risoluzione solitamente è il simplesso.
La prima cosa che dovresti specificare è se stai usando il B&B per risolvere un problema di PLI o per altro. Non è che il B&B venga usato solo per quello!

Si! Sto usando l'algoritmo B&B per risolvere un problema di PLI.
Quello che non capisco è come si risolve graficamente il rilassato continuo...
Per poi continuare l'algoritmo!
Allego un esempio
X*pl=[-3, 5/2] dove lo prendo??

[Intermat]

Continui a non saper risolvere i problemi attraverso la risoluzione grafica. Ti consiglierei di soffermarti su questo piuttosto che andare avanti cercando di capire più cose insieme. Ad ogni modo si risolve come ti avevo fatto vedere l'altra volta. Disegni la regione ammissibile, disegni la funzione obiettivo fissando arbitrariamente un valore di $z$ e poi vedi "in che verso" si massimizza. In questo caso è chiaro che viene massimizzata per $x_1 -> -oo$ e per $x_2 -> +oo$.
A questo punto, avendo disegnato sia i vincoli sia la funzione obiettivo, trascini la funzione nella direzione di massimizzazione e vedrai che uscirà proprio il punto in questione.

[mistergks]

"Intermat":Continui a non saper risolvere i problemi attraverso la risoluzione grafica. Ti consiglierei di soffermarti su questo piuttosto che andare avanti cercando di capire più cose insieme. Ad ogni modo si risolve come ti avevo fatto vedere l'altra volta. Disegni la regione ammissibile, disegni la funzione obiettivo fissando arbitrariamente un valore di $z$ e poi vedi "in che verso" si massimizza. In questo caso è chiaro che viene massimizzata per $x_1 -> -oo$ e per $x_2 -> +oo$.
A questo punto, avendo disegnato sia i vincoli sia la funzione obiettivo, trascini la funzione nella direzione di massimizzazione e vedrai che uscirà proprio il punto in questione.

Esatto! Avevo pensato anch'io che ho lacune sul metodo grafico.
Il problema è che sto cercando materiale "terra terra" che mi spieghi come si risolve graficamente... Fino ai minimi calcoli senza lasciare nulla per scontato.

Quindi il punto lo ricavo dai vincoli isolando x1 e dando valore a x2?

Edit: Sul metodo grafico ho trovato questo ma non capisco cosa si intenda per intersecare le due rette

[Intermat]

Intersecare due rette vuol dire sempre la stessa cosa ovvero trovare il punto di intersezione. In pratica devi risolvere un sistema di equazioni.
Per il resto una volta disegnati i vincoli disegni la funzione obiettivo fissando un valore arbitrario di $z$ e quindi scrivendo la f.o. nella forma $y=mx+c$. Una volta fatto ciò vedi in che direzione tale f.o. viene minimizzata e, una volta disegnata, la trasli lungo tale direzione. Il primo punto che incontrerai (e in questo caso è esattamente quello riportato) è il punto di minimo.

[mistergks]

Ma il punto 28/17, 12/17 come lo trovo sull'asse???
Corrisponde a [1,0]?
Potresti mostrarmi proprio i calcoli? Con le parole mi perdo

[Intermat]

"mistergks":Ma il punto 28/17, 12/17 come lo trovo sull'asse???
Corrisponde a [1,0]?
Potresti mostrarmi proprio i calcoli? Con le parole mi perdo

Scusa, ieri avevo letto da telefono ma poi mi sono dimenticato di rispondere da pc!

I calcoli sono di una banalità estrema, una volta che hai capito come funziona la minimizzazione della f.o.. In pratica si riduce a trovare l'intersezione dei due vincoli. Infatti se risolvi:

$\{(2x + y = 4),(3x+ 10y = 12):}$

Ottieni, facendo tutti i passaggi:


$\{(y = 4-2x),(3x+ (40-20x) = 12):}$


$\{(y = 4-2x),(17x= 28):}$


$\{(y = 4-2(28/17)=12/17),(x= 28/17):}$

[mistergks]

"Intermat":[quote="mistergks"]Ma il punto 28/17, 12/17 come lo trovo sull'asse???
Corrisponde a [1,0]?
Potresti mostrarmi proprio i calcoli? Con le parole mi perdo

Scusa, ieri avevo letto da telefono ma poi mi sono dimenticato di rispondere da pc!

I calcoli sono di una banalità estrema, una volta che hai capito come funziona la minimizzazione della f.o.. In pratica si riduce a trovare l'intersezione dei due vincoli. Infatti se risolvi:

$\{(2x + y = 4),(3x+ 10y = 12):}$

Ottieni, facendo tutti i passaggi:


$\{(y = 4-2x),(3x+ (40-20x) = 12):}$


$\{(y = 4-2x),(17x= 28):}$


$\{(y = 4-2(28/17)=12/17),(x= 28/17):}$[/quote]

Ah tutto qui?
Credo di aver capito ora!
Cosi risolvo il rilassato continuo e poi vado avanti con l algoritmo di b&b

Non va quindi fatta l enumerazione totale di tutti i punti all'inizio vero?

[Intermat]

Il B&B vuole proprio evitare di andare a visualizzare tutte le possibili soluzioni.