Esercizio di programmazione lineare intera
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 $beta={1,2,3}$, $B^{-1}=((1,4,0),(-1,2,1/2),(0,-3,-2))$, $B^-1b=((1/3),(11/2),(4))$.
Sappiamo inoltre che la matrice delle colonne fuori base (ordinate per indici crescenti delle variabili) sia $N=((4,1,7,5),(2,2,1,3),(4,0,-3,0))$. 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 $u=(1,4,0)^T$. Ricavo la matrice $B$ invertendo $B^-1$ e costruisco la matrice $A=(B^1,B^2,B^3,N^1,N^2,N^3,N^4)$, ove con $B^i$ ho indicato la $i$-ma colonna di $B$ (similmente per $N$). Ricavo inoltre $b$: allora la disuguglianza ricercata è data da $u^T*A*(x_1,...,x_7)^T<=u^T*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.
Sappiamo inoltre che la matrice delle colonne fuori base (ordinate per indici crescenti delle variabili) sia $N=((4,1,7,5),(2,2,1,3),(4,0,-3,0))$. 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 $u=(1,4,0)^T$. Ricavo la matrice $B$ invertendo $B^-1$ e costruisco la matrice $A=(B^1,B^2,B^3,N^1,N^2,N^3,N^4)$, ove con $B^i$ ho indicato la $i$-ma colonna di $B$ (similmente per $N$). Ricavo inoltre $b$: allora la disuguglianza ricercata è data da $u^T*A*(x_1,...,x_7)^T<=u^T*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.
Risposte
Ciao, ti vengono forniti i valori delle variabili in base $ B^-1b $ , l'inversa della matrice di base $B^-1$ e la matrice delle variabili fuori base $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: $[ I , B^-1N | B^-1b]$.
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 $ 11/2 $ presenta $ a_21=1/3 a_22=2 $, il taglio di gomory sarà dato da $2x_2 < 5$ ; Questo esempio non è quello dell'esercizio in questione, è di carattere generale) . Molto meno dispendioso no ?
Manda pm se ti servono delucidazioni ulteriori.
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 $ 11/2 $ presenta $ a_21=1/3 a_22=2 $, il taglio di gomory sarà dato da $2x_2 < 5$ ; Questo esempio non è quello dell'esercizio in questione, è di carattere generale) . Molto meno dispendioso no ?
Manda pm se ti servono delucidazioni ulteriori.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo