Risoluzione Problema di PL con metodo simplesso
Se ho questo problema
maz z = X1 + 3X2
con i vincoli
X1 - X2 >=-3
-X1 + 2X2 >= -4
con x>=0
e risolvo i vincoli e lo riscrivo così
$X1+3X2+0X3+0X4=0$
$X1-X2-X3 = -3$
$ -X1 +2X2 -X4=-4$
alle due equazioni dei vincoli si deve per caso cambiare di segno?
maz z = X1 + 3X2
con i vincoli
X1 - X2 >=-3
-X1 + 2X2 >= -4
con x>=0
e risolvo i vincoli e lo riscrivo così
$X1+3X2+0X3+0X4=0$
$X1-X2-X3 = -3$
$ -X1 +2X2 -X4=-4$
alle due equazioni dei vincoli si deve per caso cambiare di segno?
Risposte
Ciao,
quello che cerchi di fare è portare il tuo problema in forma standard e poi in forma slack? (procedura per applicare il metodo del simplesso)
Così capisco se posso aiutarti o meno...
PS: in altri post parli di "un libro", potresti dirmi di che libro si tratta...
quello che cerchi di fare è portare il tuo problema in forma standard e poi in forma slack? (procedura per applicare il metodo del simplesso)
Così capisco se posso aiutarti o meno...
PS: in altri post parli di "un libro", potresti dirmi di che libro si tratta...
allora il libro è introduzione alla programmazione lineare di de cesare- maddalena
In pratica spiega tutto passo per passo però poi utilizza come esempi solo esercizi dove fila tutto liscio.
Di forma standard non ne parla proprio e ti spiego come agisce il mio libro per risolvere col simplesso:
-aggiunge le variabili slack per risolvere i vincoli
-pone il sistema con funzione obbiettivo e vincoli che sarà in forma canonica
- costruisce la tavola del simplesso dove l'equazione della funz. obiettivo "z" viene moltiplicata per -1
- si vede la prima soluzione ammissibile e se non è ottima allora si cerca variabile entrante e uscente e si costruinsce la nuova tavola del simplesso e così si va avanti.
Ora nell'esercizio che ho scritto, risolvendo con le variabili slack
X1+3X2+0X3+0X4=0
X1-X2-X3=-3
-X1+2X2-X4=-4
in pratica non mi trovo con la risoluzione dell'esercizio perchè ci sono i meno davanti a x3 e x4 e usando quel programma che mi hai suggerito tu ho notato che all'equazione dei vincoli cambia il segno. L'ho fatto anche io è mi sono trovato!
Quindi in teoria avrei anche risolto però volevo una conferma perchè magari è solo un caso il mio.
Se dai un occhiata pure alle altre mie discussioni mi fai un piacere. Grazie
In pratica spiega tutto passo per passo però poi utilizza come esempi solo esercizi dove fila tutto liscio.
Di forma standard non ne parla proprio e ti spiego come agisce il mio libro per risolvere col simplesso:
-aggiunge le variabili slack per risolvere i vincoli
-pone il sistema con funzione obbiettivo e vincoli che sarà in forma canonica
- costruisce la tavola del simplesso dove l'equazione della funz. obiettivo "z" viene moltiplicata per -1
- si vede la prima soluzione ammissibile e se non è ottima allora si cerca variabile entrante e uscente e si costruinsce la nuova tavola del simplesso e così si va avanti.
Ora nell'esercizio che ho scritto, risolvendo con le variabili slack
X1+3X2+0X3+0X4=0
X1-X2-X3=-3
-X1+2X2-X4=-4
in pratica non mi trovo con la risoluzione dell'esercizio perchè ci sono i meno davanti a x3 e x4 e usando quel programma che mi hai suggerito tu ho notato che all'equazione dei vincoli cambia il segno. L'ho fatto anche io è mi sono trovato!
Quindi in teoria avrei anche risolto però volevo una conferma perchè magari è solo un caso il mio.
Se dai un occhiata pure alle altre mie discussioni mi fai un piacere. Grazie
Sì il tuo libro, fa un po' il contrario di ciò che si fa di solito...ma è equivalente penso (slack -> stanard-canonica), quello che si fa di solito è standard->slack.
però da quanto dici non sai il "perchè" si fanno certi passaggi...
Penso che manchi un $x_i>=0 | i=1,2$ per i vincoli di non negatività.
forma non-standard:
$max x_1 + 3x_2$
con le condizioni:
$x_1 - x_2 >=-3$
$-x_1 + 2x_2 >= -4$
$x_i>=0 | i=1,2$
forma standard:
$max x_1 + 3x_2$
con le condizioni:
$-x_1 + x_2 <=3$
$x_1 - 2x_2 <= 4$
$x_i>=0 | i=1,2$
se noti il $-1$ che dici è utilizzato per trasformare il $>=$ in $<=$ così cambiando di segno ai vincoli, si ottine una formulazione equivalente.
forma slack (a partire da quella standard):
$max z = x1 + 3x2$
con le condizioni:
$x_3 = 3 + x_1 - x_2$
$x_4 = 4 - x_1 + 2x_2$
$x_i>=0 | i=1,2,3,4$
La cosa principale che penso tu debba capire è come formulare bene la "forma slack", poi il calcolo è sempre quello...
però da quanto dici non sai il "perchè" si fanno certi passaggi...
Penso che manchi un $x_i>=0 | i=1,2$ per i vincoli di non negatività.
forma non-standard:
$max x_1 + 3x_2$
con le condizioni:
$x_1 - x_2 >=-3$
$-x_1 + 2x_2 >= -4$
$x_i>=0 | i=1,2$
forma standard:
$max x_1 + 3x_2$
con le condizioni:
$-x_1 + x_2 <=3$
$x_1 - 2x_2 <= 4$
$x_i>=0 | i=1,2$
se noti il $-1$ che dici è utilizzato per trasformare il $>=$ in $<=$ così cambiando di segno ai vincoli, si ottine una formulazione equivalente.
forma slack (a partire da quella standard):
$max z = x1 + 3x2$
con le condizioni:
$x_3 = 3 + x_1 - x_2$
$x_4 = 4 - x_1 + 2x_2$
$x_i>=0 | i=1,2,3,4$
La cosa principale che penso tu debba capire è come formulare bene la "forma slack", poi il calcolo è sempre quello...
diciamo che in questo esempio i vincoli li ho moltiplicati per -1, e così l'esercizio mi viene, però in altri casi, cioè quando i vincoli sono <=0 e quindi si aggingono variabili slack positive ( + x3, +x4 ... ) i vincoli li lascio stare col segno che hanno.
Per caso sai risolvere i problmei di PL anche col metodo grafico???
Per caso sai risolvere i problmei di PL anche col metodo grafico???
eh bhe ovvio che se la funzione obiettivo è "massimizzare" e i vincoli sono $<=$ è sbagliato che converti in $>=$ ti risulterà una regione non amissibile....
Da quanto dici è come suppungo, tu non sai il "perchè" si fanno certi passaggi....
la moltiplicazione con $-1$ e l'ovvio passaggio a $<=$ (come disequazione) è un modo per standardizzare la formulazione di problemi di PL per poi dare in pasto al metodo del simplesso problemi formulati in forma slack equivalente.
Leggi meglio il libro, mi sa molto strano che non dica cose del genere.
L'unico metodo grafico che conosco è quello del simplesso, ignoravo che ne esistesse un secondo...
Da quanto dici è come suppungo, tu non sai il "perchè" si fanno certi passaggi....
la moltiplicazione con $-1$ e l'ovvio passaggio a $<=$ (come disequazione) è un modo per standardizzare la formulazione di problemi di PL per poi dare in pasto al metodo del simplesso problemi formulati in forma slack equivalente.
Leggi meglio il libro, mi sa molto strano che non dica cose del genere.
L'unico metodo grafico che conosco è quello del simplesso, ignoravo che ne esistesse un secondo...
il mio libro fa una distinzione fra metodo grafico e metodo algebrico( cioè il metodo del simplesso) per risolveree i problemi di programmzione lineare
aaah tu le definisci in modo diverso, ma vanno sempre sotto il nome di Metodo del Simplesso.
Questo si suddivide in fomulazione slack (e risoluzione algebrica che è l'applicazione dell'algoritmo del Simplesso) e il metodo grafico (che è un'analisi matematica, cercando il gradiente, soluzione ottima se esiste, ecc...).
Perciò Sì so risolverlo anche con metodo grafico, è questione di terminlogia (come prima
), se avrò un po' di tempo stasera ti mostro qualcosa, ma te intanto se hai fatto qualcosa postalo
Questo si suddivide in fomulazione slack (e risoluzione algebrica che è l'applicazione dell'algoritmo del Simplesso) e il metodo grafico (che è un'analisi matematica, cercando il gradiente, soluzione ottima se esiste, ecc...).
Perciò Sì so risolverlo anche con metodo grafico, è questione di terminlogia (come prima
), se avrò un po' di tempo stasera ti mostro qualcosa, ma te intanto se hai fatto qualcosa postalo
Guarda se mi riesci a risolvere questo problema col metodo grafico ti sarei grato
$ Max z 2X1 - 3x2 $
vincoli
$ x1 - x2 <= 1 $
$ x1 <= 2$
$ -x1 +2x2 <= 4 $
con x>= 0
$ Max z 2X1 - 3x2 $
vincoli
$ x1 - x2 <= 1 $
$ x1 <= 2$
$ -x1 +2x2 <= 4 $
con x>= 0
Allora, ho fatto qualche disegno passaggio per passaggio, così ti è chiaro (ho fatto schizzi non avevo il software adatto):
$max 2x_1 - 3x_2$
vincoli
$x_1 - x_2 <=1$
$x_1 <= 2$
$-x_1 + 2x_2 <=4$
tutti i vincoli sono conformi allo stantard.
la prima cosa da fare è tracciare il grafico, con i vincoli:
$x_1 - x_2 <=1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 <= 2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -x_1 + 2x_2 <=4$
Dall'intersezione dei vincoli amissimbili otterrai una regione ammissibile, che è il simplesso.
Ti calcoli il gradiente dalla funzione obiettivo:
$Delta(x_1,x_2) = (2,-3)$
questa è (dai corsi di analisi) la massima crescita della funzione.
Questo ti darà una direzione, che percorri all'indietro con rette perpendicolari alla norma del gradiente (vedi disegno).
La prima retta che interseca il vertice del simplesso, sarà il valore ottimo e anche la soluzione ottima (da definizione).
Soluzione ottima $(1,0)$ il cui valore è $2$ (sostituito alla funzione obiettivo).
Semplice, ma solo da utilizzare con al massimo 2 variabili, poi meglio utilizzare la formulazione slack.
Se hai dubbi chiedi pure
EDIT: modificata immagine simplesso risultante, così è più chiara.
$max 2x_1 - 3x_2$
vincoli
$x_1 - x_2 <=1$
$x_1 <= 2$
$-x_1 + 2x_2 <=4$
tutti i vincoli sono conformi allo stantard.
la prima cosa da fare è tracciare il grafico, con i vincoli:
$x_1 - x_2 <=1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 <= 2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -x_1 + 2x_2 <=4$
Dall'intersezione dei vincoli amissimbili otterrai una regione ammissibile, che è il simplesso.
Ti calcoli il gradiente dalla funzione obiettivo:
$Delta(x_1,x_2) = (2,-3)$
questa è (dai corsi di analisi) la massima crescita della funzione.
Questo ti darà una direzione, che percorri all'indietro con rette perpendicolari alla norma del gradiente (vedi disegno).
La prima retta che interseca il vertice del simplesso, sarà il valore ottimo e anche la soluzione ottima (da definizione).
Soluzione ottima $(1,0)$ il cui valore è $2$ (sostituito alla funzione obiettivo).
Semplice, ma solo da utilizzare con al massimo 2 variabili, poi meglio utilizzare la formulazione slack.
Se hai dubbi chiedi pure
EDIT: modificata immagine simplesso risultante, così è più chiara.
"ham_burst":
Allora, ho fatto qualche disegno passaggio per passaggio, così ti è chiaro (ho fatto schizzi non avevo il software adatto):
$max 2x_1 - 3x_2$
vincoli
$x_1 - x_2 <=1$
$x_1 <= 2$
$-x_1 + 2x_2 <=4$
tutti i vincoli sono conformi allo stantard.
la prima cosa da fare è tracciare il grafico, con i vincoli:
$x_1 - x_2 <=1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 <= 2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -x_1 + 2x_2 <=4$
Dall'intersezione dei vincoli amissimbili otterrai una regione ammissibile, che è il simplesso.
Ti calcoli il gradiente dalla funzione obiettivo:
$Delta(x_1,x_2) = (2,-3)$
questa è (dai corsi di analisi) la massima crescita della funzione.
Questo ti darà una direzione, che percorri all'indietro con rette perpendicolari alla norma del gradiente (vedi disegno).
La prima retta che interseca il vertice del simplesso, sarà il valore ottimo e anche la soluzione ottima (da definizione).
Soluzione ottima $(1,0)$ il cui valore è $2$ (sostituito alla funzione obiettivo).
Semplice, ma solo da utilizzare con al massimo 2 variabili, poi meglio utilizzare la formulazione slack.
Se hai dubbi chiedi pure
ti ringrazio... in pratica io per calcolare il punto di ottimo mettevo a sistema $x_1 - x_2 <=1$ e $-x_1 + 2x_2 <=4$. I risulatati poi li sostituivo all'equazione della funzione obiettivo e mi calcolavo il valore di z. Ottenuto z, potevo anche calcolare i punti per i quali passa la funzione obiettivo.
Questo modo che ho descritto è come procede il mio libro. Quei pochi esempi che ci sono su libro riescono usando questo procedimento. Il probelma che ho postato invece lo diede il mio professore con una breve risoluzione e usando il metodo del libro non riesce. Invece tu l'hai risolta perfettamete come ha fatto lui. Solo che non riesco a capire una cosa:
per i vincoli ho capito tutto, però per capire quel' è il punto di ottimo non ho ancora capito come hai fatto a trovare 1;0, non ho capito il discorso della prima retta che si interseca con un vertice del simplesso
Ma si alla fine ci sono molti modi per risolvere problemi di PL. Ma il metodo grafico utilizzabile da noi mortali fino a 3 variabili, è questo (almeno io lo ho studiato in questo modo).
Sì i vincoli li trasformi in un sistema a funzioni di una variabile, $x_2=f(x_1)$.
Se studi la teoria del Simplesso, troverai che, essendo il simplesso convesso, il massimo locale è un massimo globale, cioè che la soluzione fattibile (rispetta i vincoli) è anche quella ottimale.
dato che le soluzioni ottimali sono sui vertici del simplesso, te devi guardare quale nella direzione che il gradiente di da, interseca con una retta immaginaria perpendicolare a questo, il massimo locale. Se gli altri punti del vertice non sono massimi migliori, il massimo locale trovato sarà anche globale, perciò ottimo globale (da un punto di vista algoritmico trovare l'ottimo globale non è cosa da poco)
Se hai dubbi
PS: piccolo nota che speto tu sappia: la distanza che separa "massimizzare" da "minimizzare" è un $-$.
Sì i vincoli li trasformi in un sistema a funzioni di una variabile, $x_2=f(x_1)$.
però per capire quel' è il punto di ottimo non ho ancora capito come hai fatto a trovare 1;0, non ho capito il discorso della prima retta che si interseca con un vertice del simplesso
Se studi la teoria del Simplesso, troverai che, essendo il simplesso convesso, il massimo locale è un massimo globale, cioè che la soluzione fattibile (rispetta i vincoli) è anche quella ottimale.
dato che le soluzioni ottimali sono sui vertici del simplesso, te devi guardare quale nella direzione che il gradiente di da, interseca con una retta immaginaria perpendicolare a questo, il massimo locale. Se gli altri punti del vertice non sono massimi migliori, il massimo locale trovato sarà anche globale, perciò ottimo globale (da un punto di vista algoritmico trovare l'ottimo globale non è cosa da poco
)Se hai dubbi
PS: piccolo nota che speto tu sappia: la distanza che separa "massimizzare" da "minimizzare" è un $-$.
ok ti ringrazio di tutto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo