Si consideri il seguente problema di programmazione lineare intera:
\( \displaystyle \max\ {4}{x}_{{1}}-{x}_{{2}} \)
\( \displaystyle {4}{x}_{{1}}+{2}{x}_{{2}}\le{19} \)
\( \displaystyle {10}{x}_{{1}}-{4}{x}_{{2}}\le{25} \)
\( \displaystyle {x}_{{2}}\le\frac{{9}}{{2}} \)
\( \displaystyle {x}_{{1}},\ {x}_{{2}}\in{\mathbb{Z}}^{+} \)
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 \( \displaystyle {x}_{{1}} \).
La regione ammissibile:
La soluzione ottima del rilassamento continuo è data dal punto \( \displaystyle {{x}}^{{0}}={\left(\frac{{7}}{{2}},\frac{{5}}{{2}}\right)} \).
La stima della soluzione ottima intera (cioè l'ottimo del rilassamento continuo) è \( \displaystyle \frac{{23}}{{2}}={11.5} \)
Albero di branch and bound:
Ora \( \displaystyle {x}_{{1}} \) inivizlmente vale 3.5 quindi col primo branch imposto \( \displaystyle {x}_{{1}}\le{3} \) e \( \displaystyle {x}_{{1}}\ge{4} \) e fin qui ci sono.
Non riesco però a capire come faccia a saltare fuori 10.75 come \( \displaystyle {P}_{{1}} \)
Io mi sarei aspettato come \( \displaystyle {P}_{{1}} \) 9.5, ovvero \( \displaystyle {4}\cdot{3}-\frac{{5}}{{2}} \)
Una volta risolto questo dubbio posterò i successivi
Grazie mille per l'aiuto.
Saluti
Stefano
