Esercizio Branch and bound
Ciao a tutti, avrei bisogno di una mano con un esercizio (di cui ho la soluzione ma che non mi è molto chiara) sul Branch and bound.
Si consideri il seguente problema di programmazione lineare intera:
$max\ 4x_1-x_2$
$4x_1+2x_2<=19$
$10x_1-4x_2<=25$
$x_2<=9/2$
$x_1,\ x_2inZZ^+$
Calcolare la soluzione ottima del problema applcando il metodo del branch and bound. Calcolare il
rilassamento continuo per via grafica ad ogni nodo. Si esegua prima il branch sulla variabile $x_1$.
La regione ammissibile:
La soluzione ottima del rilassamento continuo è data dal punto $x^0=(7/2,5/2)$.
La stima della soluzione ottima intera (cioè l'ottimo del rilassamento continuo) è $23/2=11.5$
Albero di branch and bound:
Ora $x_1$ inivizlmente vale 3.5 quindi col primo branch imposto $x_1<=3$ e $x_1>=4$ e fin qui ci sono.
Non riesco però a capire come faccia a saltare fuori 10.75 come $P_1$
Io mi sarei aspettato come $P_1$ 9.5, ovvero $4*3-5/2$
Una volta risolto questo dubbio posterò i successivi
Grazie mille per l'aiuto.
Saluti
Stefano
Si consideri il seguente problema di programmazione lineare intera:
$max\ 4x_1-x_2$
$4x_1+2x_2<=19$
$10x_1-4x_2<=25$
$x_2<=9/2$
$x_1,\ x_2inZZ^+$
Calcolare la soluzione ottima del problema applcando il metodo del branch and bound. Calcolare il
rilassamento continuo per via grafica ad ogni nodo. Si esegua prima il branch sulla variabile $x_1$.
La regione ammissibile:
La soluzione ottima del rilassamento continuo è data dal punto $x^0=(7/2,5/2)$.
La stima della soluzione ottima intera (cioè l'ottimo del rilassamento continuo) è $23/2=11.5$
Albero di branch and bound:
Ora $x_1$ inivizlmente vale 3.5 quindi col primo branch imposto $x_1<=3$ e $x_1>=4$ e fin qui ci sono.
Non riesco però a capire come faccia a saltare fuori 10.75 come $P_1$
Io mi sarei aspettato come $P_1$ 9.5, ovvero $4*3-5/2$
Una volta risolto questo dubbio posterò i successivi
Grazie mille per l'aiuto.
Saluti
Stefano
Risposte
anche io ho lo stesso dubbio.
per calcolare il punto p1 io intersecato la retta $x1 = 3$ con la retta del primo vincolo $4x1 + 2x2 = 19$ ottenendo quindi il punto di coordinate $(3,7/2)$ quindi la funzione obiettivo calcolata in quel punto dovrebbe essere secondo i miei calcoli $8,5$ non riesco proprio a capire nemmeno io come ottenere quel $10,75$
qualcuno può confermare il procedimento?
grazie
per calcolare il punto p1 io intersecato la retta $x1 = 3$ con la retta del primo vincolo $4x1 + 2x2 = 19$ ottenendo quindi il punto di coordinate $(3,7/2)$ quindi la funzione obiettivo calcolata in quel punto dovrebbe essere secondo i miei calcoli $8,5$ non riesco proprio a capire nemmeno io come ottenere quel $10,75$
qualcuno può confermare il procedimento?
grazie
Lo state risolvendo per via grafica quindi, poichè l'ottimo si trova sicuramente su uno spigolo della poligonale, avrete che esso (dopo il branching) si ha in corrispondenza di una delle seguenti intersezioni:
$\{(x_1=3),(4x_1 +2x_2 = 19) :}$ $=>$ $ {(x_1=3),(x_2 = 7/2) :}$
${(x_1=3),(10x_1 - 4x_2 = 25) :}$ $=>$ ${(x_1=3),(x_2 = 5/4) :}$
Calcolando le $z$ della massimizzazione si ha:
Se $x=(3,7/2)$ allora $z=4*3 - 7/2=17/2=8.5$
Se $x=(3, 5/4)$ allora $z=4*3-5/4=43/4=10.75$
Poichè stiamo massimizzando si ha che per $P_1$ $z*=10.75$
$\{(x_1=3),(4x_1 +2x_2 = 19) :}$ $=>$ $ {(x_1=3),(x_2 = 7/2) :}$
${(x_1=3),(10x_1 - 4x_2 = 25) :}$ $=>$ ${(x_1=3),(x_2 = 5/4) :}$
Calcolando le $z$ della massimizzazione si ha:
Se $x=(3,7/2)$ allora $z=4*3 - 7/2=17/2=8.5$
Se $x=(3, 5/4)$ allora $z=4*3-5/4=43/4=10.75$
Poichè stiamo massimizzando si ha che per $P_1$ $z*=10.75$
grazie mille, io avevo preso solo il primo punto $(3,7/2)$ perchè facendo "scorrere" la funzione obiettivo sulla regione ammissibile, questo risultava l'ultimo vertice ad essere preso.
quindi il metodo che ho utilizzato non è sufficiente per trovare vertici ottimi?
grazie mille
quindi il metodo che ho utilizzato non è sufficiente per trovare vertici ottimi?
grazie mille
Solitamente vedere "il verso" di massimizzazione aiuta. Infatti potevi notare che il vertice in basso è il migliore dal semplice fatto che, fissato $x_1$, facendo aumentare il solo $x_2$ il valore di $z$ peggiora! Ovvero la variabile $x_2$ penalizza il valore della f.o. Quindi, nel caso in particolare, fissato $x_1$, il valore di $x_2$ "più conveniente" è il più piccolo.
giusto, non ci avevo pensato.
grazie mille!
grazie mille!
"Intermat":
Solitamente vedere "il verso" di massimizzazione aiuta. Infatti potevi notare che il vertice in basso è il migliore dal semplice fatto che, fissato $x_1$, facendo aumentare il solo $x_2$ il valore di $z$ peggiora! Ovvero la variabile $x_2$ penalizza il valore della f.o. Quindi, nel caso in particolare, fissato $x_1$, il valore di $x_2$ "più conveniente" è il più piccolo.
io utilizzavo questo metodo per risolvere graficamente un problema a 2 variabili:
prendevo la F.O. ad esempio = 0 e disegnavo la retta, dopodichè mi posizionavo con un righello su questa retta e (se il problema è di max) spostavo da sinistra verso destra il righello e mi fermavo sull'ultimo vertice toccato.
analogamente per un problema di min, spostavo il righello dall'alto verso il basso (e da destra verso sinistra)
questo metodo quindi non è sempre efficace? è necessario che tutti i coefficienti della F.O. siano positivi (per esempio nel caso di max) per poterlo applicare?
grazie mille.
Il fatto è che secondo me è sbagliata la rappresentazione della f.o. In questo caso se ho $z=4x_1 -x_2=0$ deve valere $x_1=1 , x_2=4$ invece nel disegno non è così. Se la rappresenti con la pendenza giusta dovrebbe essere valido quello che tu dici!
"Intermat":
Il fatto è che secondo me è sbagliata la rappresentazione della f.o. In questo caso se ho $z=4x_1 -x_2=0$ deve valere $x_1=1 , x_2=4$ invece nel disegno non è così. Se la rappresenti con la pendenza giusta dovrebbe essere valido quello che tu dici!
no, infatti nemmeno io mi ritrovo con la retta che è disegnata nella figura.
l'ho calcolata nello stesso modo. $z=4x_1 -x_2=0$
quindi il metodo "del righello" può funzionare solo se ho funzioni di MAX con entrambi termini positivi oppure funzioni di MIN con entrambi i negativi?
perchè effettivamente mi sono reso conto che in quel caso il $-x2$ faceva sì che il metodo riportasse un vertice sbagliato (quello con x1 e x2 massimi) mentre avrei dovuto prendere x1 massimo e x2 minimo
Sei sicuro che ti porti ad un punto sbagliato? Se non mi sbaglio ha una pendenza positiva e tale che, facendola scorrere "lungo a $x_1$", passa prima sul punto in alto e solo successivamente su quello in basso.
allora riprovo a disegnare la retta, magari ho sbagliato qualcosa.
mi confermi che l'equzione della retta è : $y = 4x$ ?
grazie
mi confermi che l'equzione della retta è : $y = 4x$ ?
grazie
avevi ragione 
!!
ho rifatto il disegno e ho utilizzato il metodo "del righello" e il punto che ho trovato è l'intersezione tra $x1=3$ e $10x1 - 4x2 = 25 $ ed effettivamente il punto che ho calcolato è $(3,4/5)$ che sostituito nella funzione obiettivo dà proprio 10,75 !
grazie mille
!!ho rifatto il disegno e ho utilizzato il metodo "del righello" e il punto che ho trovato è l'intersezione tra $x1=3$ e $10x1 - 4x2 = 25 $ ed effettivamente il punto che ho calcolato è $(3,4/5)$ che sostituito nella funzione obiettivo dà proprio 10,75 !
grazie mille
scusami ho un altro domanda : dunque abbiamo riscontrato che il metodo "del righello" funziona, però il mio dubbio è sulla direzione dello spostamento della retta F.O.
dobbiamo spostarla da sinistra verso destra? dall'alto verso il basso? o dipende dalla funzione obiettivo?
con quale criterio spostiamo la retta per trovare il vertice ottimo?
grazie mile
dobbiamo spostarla da sinistra verso destra? dall'alto verso il basso? o dipende dalla funzione obiettivo?
con quale criterio spostiamo la retta per trovare il vertice ottimo?
grazie mile
La retta della f.o. la devi spostare a seconda del tipo di f.o. Vedi "in che verso" si massimizza (o minimizza) e verso tale verso la sposti. Detto questo, su domini così semplici (tanto da risolversi col metodo grafico) è facile vedere quali sono gli spigoli della regione ammissibile e calcolare, con la ricerca esaustiva, l'ottimo su cui poi fare branching.
ciao, stavo provando a risolvere un problema di massimo e il suo duale per verificare il teorema della dualità forte.
il problema primale è questo
$ MAX $ $2x1 - 2x2 +x3$
con i seguenti vincoli
$x1-x2-2x3<= 12$
$x1 + x2 +x3 <= 1$
$x1$ libera $x2 >= 0$ e $x3<=0$
ho calcolato la soluzione ottima con l'algoritmo del simplesso che risulta $(4.67 , 0 , -3.67)$ e quindi la funzione obiettivo vale $Z = 5,67$
a questo punto dato il teorema della dualità forte ho pensato che risolvendo il problema duale avrei ottenuto una soluzione ottima che avrebbe portato alla stessa $Z$.
il problema duale è il seguente:
MIN $12Y1 + Y2$
con i seguenti vincoli
$Y1 +Y2 = 2$
$Y1 + Y2 >= -2$
$-2Y1 + Y2 <= 1$
con $Y1,Y2 >= 0$
a questo punto, considerando che ho un problema in 2 variabili ho pensato di risolverlo graficamente.
essendo un problema di minimo ho pensato che potessi usare il metodo del "righello" così come ho fatto per il problema di massimo a 2 varibili nel branch e bound.
questa è la regione ammissibile
[img]http://www.mathe-fa.de/it.plot.png?uid=5284ce700a4e61.03574413[/img]
(quella in grigio è la FO)
il punto di ottimo sarà quello di coordinate $(0.33 , 1.67)$ con $Z = 5,67$ il problema è che non so come ottenere quel punto risolvendo graficamente con il metodo del "righello" visto che facendo "scorrere" la funzione obiettivo gli ultimi punti che vengono toccati sono $(0,0)$ se faccio scorrere la FO verso sinistra e $(-2,0)$ se faccio scorrere la FO verso destra.
mi sarei aspettato di trovare il punto di ottimo con questo metodo ma non ha funzionato.
come mai ?
grazie
il problema primale è questo
$ MAX $ $2x1 - 2x2 +x3$
con i seguenti vincoli
$x1-x2-2x3<= 12$
$x1 + x2 +x3 <= 1$
$x1$ libera $x2 >= 0$ e $x3<=0$
ho calcolato la soluzione ottima con l'algoritmo del simplesso che risulta $(4.67 , 0 , -3.67)$ e quindi la funzione obiettivo vale $Z = 5,67$
a questo punto dato il teorema della dualità forte ho pensato che risolvendo il problema duale avrei ottenuto una soluzione ottima che avrebbe portato alla stessa $Z$.
il problema duale è il seguente:
MIN $12Y1 + Y2$
con i seguenti vincoli
$Y1 +Y2 = 2$
$Y1 + Y2 >= -2$
$-2Y1 + Y2 <= 1$
con $Y1,Y2 >= 0$
a questo punto, considerando che ho un problema in 2 variabili ho pensato di risolverlo graficamente.
essendo un problema di minimo ho pensato che potessi usare il metodo del "righello" così come ho fatto per il problema di massimo a 2 varibili nel branch e bound.
questa è la regione ammissibile
[img]http://www.mathe-fa.de/it.plot.png?uid=5284ce700a4e61.03574413[/img]
(quella in grigio è la FO)
il punto di ottimo sarà quello di coordinate $(0.33 , 1.67)$ con $Z = 5,67$ il problema è che non so come ottenere quel punto risolvendo graficamente con il metodo del "righello" visto che facendo "scorrere" la funzione obiettivo gli ultimi punti che vengono toccati sono $(0,0)$ se faccio scorrere la FO verso sinistra e $(-2,0)$ se faccio scorrere la FO verso destra.
mi sarei aspettato di trovare il punto di ottimo con questo metodo ma non ha funzionato.
come mai ?
grazie
Possibile che tu nel problema hai come vincolo una equazione? Praticamente la regione ammissibile si restringe ad una retta delimitata dalle altre due disequazioni?
PS: $(0,0)$ non verificherebbe l'uguaglianza incriminata ovvero $y_1 + y_2=2$
PS: $(0,0)$ non verificherebbe l'uguaglianza incriminata ovvero $y_1 + y_2=2$
hai ragione! me ne sono accorto.
comunque la retta è dovuta alla variabile libera nel problema primale che mi porta ad avere quel vincolo di uguaglianza nel problema duale
comunque la retta è dovuta alla variabile libera nel problema primale che mi porta ad avere quel vincolo di uguaglianza nel problema duale
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo