Algoritmo del simplesso
svolgendo un esercizio mi sono accorto di avere un piccolo dubbio in un passaggio.
la situazione attuale è questa:
$\{(max z = x_1 - 2x_2 - x_3),(x_4 = 2 - 4x_1 - x_2 +x_3),(x_5 = -1 +3x_1 - x_2 + 2x_3):}$
la variabile entrante è $\x_1$, il dubbio viene ora nella scelta della variabile uscente:
nel secondo vincolo il termine noto è negativo, mentre la variabile entrante è positiva. è corretto considerare questo vincolo o devo considerare solo il primo vincolo che ha termine noto positivo e variabile entrante negativa?
in parole povere: basta che termine noto e variabile entrante siano di segno opposto o il termine noto deve essere necessariamente positivo?
a me sembrava di aver capito che basta che siano discordanti affinche il problema non abbia soluzione illimitata.
cosi facendo, applicando il test del minimo rapporto, $\min(2/4, 1/3)$, la variabile uscente è $\x_5$
PS: cercando in rete ho notato che in questo caso bisognerebbe introdurre una variabile positiva per impostare il problema di prima fase (però nel mio corso non c'è stato un minimo accenno ai problemi di prima fase).
la situazione attuale è questa:
$\{(max z = x_1 - 2x_2 - x_3),(x_4 = 2 - 4x_1 - x_2 +x_3),(x_5 = -1 +3x_1 - x_2 + 2x_3):}$
la variabile entrante è $\x_1$, il dubbio viene ora nella scelta della variabile uscente:
nel secondo vincolo il termine noto è negativo, mentre la variabile entrante è positiva. è corretto considerare questo vincolo o devo considerare solo il primo vincolo che ha termine noto positivo e variabile entrante negativa?
in parole povere: basta che termine noto e variabile entrante siano di segno opposto o il termine noto deve essere necessariamente positivo?
a me sembrava di aver capito che basta che siano discordanti affinche il problema non abbia soluzione illimitata.
cosi facendo, applicando il test del minimo rapporto, $\min(2/4, 1/3)$, la variabile uscente è $\x_5$
PS: cercando in rete ho notato che in questo caso bisognerebbe introdurre una variabile positiva per impostare il problema di prima fase (però nel mio corso non c'è stato un minimo accenno ai problemi di prima fase).
Risposte
"mathix":
svolgendo un esercizio mi sono accorto di avere un piccolo dubbio in un passaggio.
la situazione attuale è questa:
$\{(max z = x_1 - 2x_2 - x_3),(x_4 = 2 - 4x_1 - x_2 +x_3),(x_5 = -1 +3x_1 - x_2 + 2x_3):}$
la variabile entrante è $\x_1$, il dubbio viene ora nella scelta della variabile uscente:
....
a me sembrava di aver capito che basta che siano discordanti affinche il problema non abbia soluzione illimitata.
cosi facendo, applicando il test del minimo rapporto, $\min(2/4, 1/3)$, la variabile uscente è $\x_5$
attenzione, la scelta non è arbitraria, esisono delle regole fissate e deterministiche. Una di queste, che ricordo in ogni post, è la regola di Bland perchè è la più facile per evitare soluzioni illimitate... (v. basi-ammissibili-t91257-10.html).
cmq per rimanere con il tuo metodo che di solito si applica in casi con carta&penna.
- scelta della variabile entrante (se si massimizza): scelgiere quella con coefficiente positivo più alto
- scelta della variabile uscente: sciegliere quealla che mimimizza lo scarto tra quelle con coefficiente della della v.e. negative, nel tuo caso con $x_1$.
$x_4 = 2 - 4x_1\ |\ 1/2$
$x_5 = -1 + 3x_1\ |\ oo$ semplicemente non si può scegliere perchè il coefficiente è positivo e questo preclude la scelta, provocando possibili soluzioni illimitate.
perciò la variabile uscente sarà $x_4$.
PS: cercando in rete ho notato che in questo caso bisognerebbe introdurre una variabile positiva per impostare il problema di prima fase (però nel mio corso non c'è stato un minimo accenno ai problemi di prima fase).
questo si introduce in un altra tipologia di metodo del simplesso, ne esistono molti, tipo a due fasi, duale-primale, ecc...
ti ringrazio per la risposta, è tutto chiaro. dato che il prof non ha proprio spiegato il simplesso a due fasi è inutile che mi ci addentro.
quindi quando nei vincoli la variabile entrante è positiva, scarto il vincolo a priori e considero solo quello con la variabile entrante negativa (che il termine noto sia negativo non fa differenza). giusto?
quindi quando nei vincoli la variabile entrante è positiva, scarto il vincolo a priori e considero solo quello con la variabile entrante negativa (che il termine noto sia negativo non fa differenza). giusto?
quindi quando nei vincoli la variabile entrante è positiva, scarto il vincolo a priori e considero solo quello con la variabile entrante negativa (che il termine noto sia negativo non fa differenza). giusto?
attento, rileggi bene ciò che ho scritto. Io parlo di regole di scelta.
Consideriamo che abbiamo un problema di massimo:
- tra le variabili entranti scegli qualla positiva con coefficienti PIU' ALTO
- tra le variabili uscenti (in relazione alla variabile entrante scelta) scegli quella negativa che minimizza lo scarto.
- il termine noto se negativo porta a delle complicazioni, non è da scartare. In alcuni casi si introduce un problema lineare ausiliario prima di valutare con il metodo del simplesso, che valuta se i vincoli sono ammissibili e portano ad una soluzione se valutati con il metodo del simplesso. Se il problema non degenera in casi particolari e puoi scegliere una variabile uscente senza troppi problemi, i vincoli con termine noto negativo scartali.
Comunque come ti ho consigliato leggiti almeno questo. Dove dico che bisogna differenziare il metodo quando si massimizza e minimizza perciò le regole di scelta, ma considera che $max f(x) = - min -f(x)$.
tutto chiaro, grazie mille per l'aiuto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo