Esercizio di programmazione lineare intera

[matths87]

Supponiamo che al termine della risoluzione del rilassamento lineare di un problema di ILP tramite il metodo del simplesso la base, l'inversa della matrice di base e le componenti in base della soluzione ottima siano \( \displaystyle \beta={\left\lbrace{1},{2},{3}\right\rbrace} \), \( \displaystyle {{B}}^{{-{1}}}={\left(\matrix{{1}&{4}&{0}\\-{1}&{2}&\frac{{1}}{{2}}\\{0}&-{3}&-{2}}\right)} \), \( \displaystyle {{B}}^{{-{{1}}}}{b}={\left(\matrix{\frac{{1}}{{3}}\\\frac{{11}}{{2}}\\{4}}\right)} \).
Sappiamo inoltre che la matrice delle colonne fuori base (ordinate per indici crescenti delle variabili) sia \( \displaystyle {N}={\left(\matrix{{4}&{1}&{7}&{5}\\{2}&{2}&{1}&{3}\\{4}&{0}&-{3}&{0}}\right)} \). Determinare uno o più tagli di Gomory che eliminino la soluzione ottima corrente.

Io ragionerei così: considero la prima variabile in base della soluzione ottima che è frazionaria: pongo allora \( \displaystyle {u}={{\left({1},{4},{0}\right)}}^{{T}} \). Ricavo la matrice \( \displaystyle {B} \) invertendo \( \displaystyle {{B}}^{{-{{1}}}} \) e costruisco la matrice \( \displaystyle {A}={\left({{B}}^{{1}},{{B}}^{{2}},{{B}}^{{3}},{{N}}^{{1}},{{N}}^{{2}},{{N}}^{{3}},{{N}}^{{4}}\right)} \), ove con \( \displaystyle {{B}}^{{i}} \) ho indicato la \( \displaystyle {i} \)-ma colonna di \( \displaystyle {B} \) (similmente per \( \displaystyle {N} \)). Ricavo inoltre \( \displaystyle {b} \): allora la disuguglianza ricercata è data da \( \displaystyle {{u}}^{{T}}\cdot{A}\cdot{{\left({x}_{{1}},\ldots,{x}_{{7}}\right)}}^{{T}}\le{{u}}^{{T}}\cdot{b} \), applicando ai coefficienti la parte intera inferiore.
È corretto questo ragionamento? Esistono strade meno dispendiose dal punto di vista dei conti (che devo fare necessariamente a mano )? Preciso che ovviamente dovrei effettuare lo stesso ragionamento per la seconda variabile in base, essendo essa frazionaria nella soluzione ottima.

[Kiliz]

Ciao, ti vengono forniti i valori delle variabili in base \( \displaystyle {{B}}^{{-{{1}}}}{b} \) , l'inversa della matrice di base \( \displaystyle {{B}}^{{-{{1}}}} \) e la matrice delle variabili fuori base \( \displaystyle {N} \). Per determinare il tableau finale dal simplesso ti basterà comporlo dai dati da te posseduti. Il tableau finale con variabili in base 1 2 3 sarà così fatto: \( \displaystyle {\left[{I},{{B}}^{{-{{1}}}}{N}{\mid}{{B}}^{{-{{1}}}}{b}\right]} \).
Per la determinazione dei tagli di gomory ti basterà prendere la riga del tableau con soluzione non intera, (nel tuo caso o 1/3 o 11/4 e arrotondare per difetto tutti i coefficenti della matrice e anche il valore della variabile in base) (Es: la riga associata alla soluzione di base \( \displaystyle \frac{{11}}{{2}} \) presenta \( \displaystyle {a}_{{21}}=\frac{{1}}{{3}}{a}_{{22}}={2} \), il taglio di gomory sarà dato da \( \displaystyle {2}{x}_{{2}}\lt{5} \) ; Questo esempio non è quello dell'esercizio in questione, è di carattere generale) . Molto meno dispendioso no ? Manda pm se ti servono delucidazioni ulteriori.