Metodo del Simplesso
Ciao a tutti! Sto studiando il metodo del simplesso ma sono arrivato a un punto morto. Non riesco a capire come funziona la creazione di un problema artificiale nella fase 1.
Potreste farmi qualche esempio?
Potreste farmi qualche esempio?
Risposte
In pratica devi aggiungere delle variabili "artificiali" al problema iniziale, in modo da ottenere una base ammissibile individuabile per ispezione per un problema associato.
Per esempio se hai il problema \(\displaystyle max \{z = cx\colon Ax=b, x\geq0\} \) e devi trovare una base ammissibile con il programma di prima fase, devi creare un problema associato (che è diverso dall'originale) introducendo delle variabili artificiali \(\displaystyle s \) e cambiando la funzione obiettivo in \(\displaystyle max \space \zeta = -\sum s \)
Poi al posto di \(\displaystyle Ax=b,x\geq0 \) devi semplicemente aggiungere queste variabili artificiali che hai creato apposta: \(\displaystyle Ax + s = b, x\geq0, s\geq0 \)
Quindi il programma di prima fase associato al programma lineare è \(\displaystyle max \{ \zeta = -\sum s\colon Ax+s=b, x\geq0,s\geq0\} \)
Adesso questo programma ha sempre soluzioni ammissibili, perchè basta che \(\displaystyle x=0 \) e \(\displaystyle s=b \) e hai già una soluzione. Questa infatti sarebbe la soluzione individuabile per ispezione che ti crei "ad hoc"
Inoltre il nuovo programma ha sempre soluzioni ottime! Infatti la funzione obiettivo è sempre \(\displaystyle \leq0 \) perchè le variabili sono tutte positive, quindi (essendo un problema di massimo) non può essere illimitata superiormente.
A questo punto ci sono due possibilità: il massimo è un valore minore di 0, e allora in questo caso il problema originale non ammette soluzioni ammissibili; oppure il massimo è proprio uguale a 0, e allora la base ottima di questo problema è anche una base ammissibile per quello originale. Per non farla troppo lunga, una volta che hai risolto il problema di prima fase trovando come ottimo 0, basta che alla base del problema associato togli brutalmente le variabili \(\displaystyle s \) e hai immediatamente una base ammissibile per il programma originale.
Funziona perchè intuitivamente se hai trovato massimo uguale a 0 per il programma associato, vuol dire che le variabili artificiali sono tutte ugali a 0, e quindi di fatto \(\displaystyle Ax + s = b, x\geq0, s\geq0 \) diventa \(\displaystyle Ax=b,x\geq0 \)
Spero di esserti stato d'aiuto, sono una frana a spiegare.
Per esempio se hai il problema \(\displaystyle max \{z = cx\colon Ax=b, x\geq0\} \) e devi trovare una base ammissibile con il programma di prima fase, devi creare un problema associato (che è diverso dall'originale) introducendo delle variabili artificiali \(\displaystyle s \) e cambiando la funzione obiettivo in \(\displaystyle max \space \zeta = -\sum s \)
Poi al posto di \(\displaystyle Ax=b,x\geq0 \) devi semplicemente aggiungere queste variabili artificiali che hai creato apposta: \(\displaystyle Ax + s = b, x\geq0, s\geq0 \)
Quindi il programma di prima fase associato al programma lineare è \(\displaystyle max \{ \zeta = -\sum s\colon Ax+s=b, x\geq0,s\geq0\} \)
Adesso questo programma ha sempre soluzioni ammissibili, perchè basta che \(\displaystyle x=0 \) e \(\displaystyle s=b \) e hai già una soluzione. Questa infatti sarebbe la soluzione individuabile per ispezione che ti crei "ad hoc"
Inoltre il nuovo programma ha sempre soluzioni ottime! Infatti la funzione obiettivo è sempre \(\displaystyle \leq0 \) perchè le variabili sono tutte positive, quindi (essendo un problema di massimo) non può essere illimitata superiormente.
A questo punto ci sono due possibilità: il massimo è un valore minore di 0, e allora in questo caso il problema originale non ammette soluzioni ammissibili; oppure il massimo è proprio uguale a 0, e allora la base ottima di questo problema è anche una base ammissibile per quello originale. Per non farla troppo lunga, una volta che hai risolto il problema di prima fase trovando come ottimo 0, basta che alla base del problema associato togli brutalmente le variabili \(\displaystyle s \) e hai immediatamente una base ammissibile per il programma originale.
Funziona perchè intuitivamente se hai trovato massimo uguale a 0 per il programma associato, vuol dire che le variabili artificiali sono tutte ugali a 0, e quindi di fatto \(\displaystyle Ax + s = b, x\geq0, s\geq0 \) diventa \(\displaystyle Ax=b,x\geq0 \)
Spero di esserti stato d'aiuto, sono una frana a spiegare.
Grazie mille per la risposta tempestiva e ampia. Sei stato chiaro, l'unico problema è che io a differenza di quanto hai scritto, studio su un problema artificiale in forma di minimizzazione, e quindi devo "tradurre" quello che hai scritto xD. Grazie mille davvero!
Semmai una domanda.. mi viene chiesto di costruire il "tableau" di un problema artificiale, normalmente con un problema non artificiale mi riesce ma così no.
Come lo costruiresti te con questo problema dato?
$min 4x_1 + x_2 +x_3$
$ 2x_1+x_2+2x_3 =4$
$ 3x_1+3x_2+x_3 =3$
$ -x_1+x_2-3x_3 =4-5$
$x_1 , x_2 ,x_3 >= 0$
Come lo costruiresti te con questo problema dato?
$min 4x_1 + x_2 +x_3$
$ 2x_1+x_2+2x_3 =4$
$ 3x_1+3x_2+x_3 =3$
$ -x_1+x_2-3x_3 =4-5$
$x_1 , x_2 ,x_3 >= 0$
Io passerei alla forma standard per un problema di massimo, perchè mi è più familiare. Tanto in questo caso basta moltiplicare la funzione obiettivo per -1.
Però per un problema di minimo il concetto è lo stesso, bisogna fare l'opposto di quanto detto sopra. Cioè: aggingi le variabili artificiali che ti servono, poi usando l'algoritmo del simplesso sul nuovo problema arrivi ad ottenere un ottimo. Siccome è un problema di minimo la nuova funzione obiettivo invece di \(\displaystyle -\sum_i s_i \) sarà semplicemente \(\displaystyle \sum_i s_i \) senza il meno davanti. Le condizioni per l'ammissibilità del problema originale invece sono sempre due: se l'ottimo del problema artificiale è uguale a 0, allora il problema originale ha una soluzione di base ammissibile; se invece l'ottimo trovato è maggiore di 0 (questa volta maggiore invece di minore) allora il problema originale non ammette soluzioni.
Per il tuo problema devi aggiungere tre variabili, una per ogni riga del problema. Chiamiamole ad esempio \(\displaystyle s_1,s_2,s_3 \)
Allora il tuo problema artificiale sarà:
\(\displaystyle min \space s_1+s_2+s_3 \)
\(\displaystyle 2x_1+x_2+2x_3+s_1=4\)
\(\displaystyle 3x_1+3x_2+x_3+s_2=3 \)
\(\displaystyle -x_1+x_2-3x_3+s_3=?? \)
\(\displaystyle x_1,x_2,x_3,s_1,s_2,s_3\geq0 \)
Adesso in buona sostanza bisogna ricavare le \(\displaystyle s \) dalle equazioni e sostituirle nella funzione obiettivo (non capisco quell'ultimo termine noto 4-5). La nuova funzione obiettivo la chiamo f.o. per semplicità nel tableau
e il tableau dovrebbe essere:
2 1 2 1 0 0| 4
3 3 1 0 1 0| 3
-11-30 0 1|??
----------------
f.o.
Nel tableau sopra le colonne ci sarebbero scritte le sei variabili e infine b (sulla colonna dei termini noti)
accanto alle tre righe invece ci sono nominate solo le nuove variabili.
Così almeno è come l'ho visto io. Però non ti garantisco che sia giusto perchè come già detto sono abituato a risolvere i problemi portandoli in forma standard di massimo
Però per un problema di minimo il concetto è lo stesso, bisogna fare l'opposto di quanto detto sopra. Cioè: aggingi le variabili artificiali che ti servono, poi usando l'algoritmo del simplesso sul nuovo problema arrivi ad ottenere un ottimo. Siccome è un problema di minimo la nuova funzione obiettivo invece di \(\displaystyle -\sum_i s_i \) sarà semplicemente \(\displaystyle \sum_i s_i \) senza il meno davanti. Le condizioni per l'ammissibilità del problema originale invece sono sempre due: se l'ottimo del problema artificiale è uguale a 0, allora il problema originale ha una soluzione di base ammissibile; se invece l'ottimo trovato è maggiore di 0 (questa volta maggiore invece di minore) allora il problema originale non ammette soluzioni.
Per il tuo problema devi aggiungere tre variabili, una per ogni riga del problema. Chiamiamole ad esempio \(\displaystyle s_1,s_2,s_3 \)
Allora il tuo problema artificiale sarà:
\(\displaystyle min \space s_1+s_2+s_3 \)
\(\displaystyle 2x_1+x_2+2x_3+s_1=4\)
\(\displaystyle 3x_1+3x_2+x_3+s_2=3 \)
\(\displaystyle -x_1+x_2-3x_3+s_3=?? \)
\(\displaystyle x_1,x_2,x_3,s_1,s_2,s_3\geq0 \)
Adesso in buona sostanza bisogna ricavare le \(\displaystyle s \) dalle equazioni e sostituirle nella funzione obiettivo (non capisco quell'ultimo termine noto 4-5). La nuova funzione obiettivo la chiamo f.o. per semplicità nel tableau
e il tableau dovrebbe essere:
2 1 2 1 0 0| 4
3 3 1 0 1 0| 3
-11-30 0 1|??
----------------
f.o.
Nel tableau sopra le colonne ci sarebbero scritte le sei variabili e infine b (sulla colonna dei termini noti)
accanto alle tre righe invece ci sono nominate solo le nuove variabili.
Così almeno è come l'ho visto io. Però non ti garantisco che sia giusto perchè come già detto sono abituato a risolvere i problemi portandoli in forma standard di massimo
Scusa ho sbagliato a scrivere... probabilmente era -5 xD
Ok, comunque ho capito quello che hai fatto e guardando sugli appunti mi torna anche. Ma adesso cosa devo fare? cioè io sono abituato a risolvere dei Tableau di problemi normali e so come si risolvono, ma ora non vedo cosa devo fare... Sugli appunti parla di una matrice identità, che nel tableau vedo, ma non capisco cosa devo farci...
Ok, comunque ho capito quello che hai fatto e guardando sugli appunti mi torna anche. Ma adesso cosa devo fare? cioè io sono abituato a risolvere dei Tableau di problemi normali e so come si risolvono, ma ora non vedo cosa devo fare... Sugli appunti parla di una matrice identità, che nel tableau vedo, ma non capisco cosa devo farci...
scusate ma il il problema artificiale è costruibile in ogni caso? e quando non mi conviene utilizzarlo?
nessuno?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo