risoluzione Problema di PL con metodo simplesso

[Ste868686]

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ì

\( \displaystyle {X}{1}+{3}{X}{2}+{0}{X}{3}+{0}{X}{4}={0} \)
\( \displaystyle {X}{1}-{X}{2}-{X}{3}=-{3} \)
\( \displaystyle -{X}{1}+{2}{X}{2}-{X}{4}=-{4} \)

alle due equazioni dei vincoli si deve per caso cambiare di segno?

[hamming_burst]

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...

[Ste868686]

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

[hamming_burst]

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 \( \displaystyle {x}_{{i}}\ge{0}{\mid}{i}={1},{2} \) per i vincoli di non negatività.

forma non-standard:

\( \displaystyle \max{x}_{{1}}+{3}{x}_{{2}} \)

con le condizioni:

\( \displaystyle {x}_{{1}}-{x}_{{2}}\ge-{3} \)
\( \displaystyle -{x}_{{1}}+{2}{x}_{{2}}\ge-{4} \)
\( \displaystyle {x}_{{i}}\ge{0}{\mid}{i}={1},{2} \)

forma standard:

\( \displaystyle \max{x}_{{1}}+{3}{x}_{{2}} \)

con le condizioni:
\( \displaystyle -{x}_{{1}}+{x}_{{2}}\le{3} \)
\( \displaystyle {x}_{{1}}-{2}{x}_{{2}}\le{4} \)
\( \displaystyle {x}_{{i}}\ge{0}{\mid}{i}={1},{2} \)

se noti il \( \displaystyle -{1} \) che dici è utilizzato per trasformare il \( \displaystyle \ge \) in \( \displaystyle \le \) così cambiando di segno ai vincoli, si ottine una formulazione equivalente.

forma slack (a partire da quella standard):

\( \displaystyle \max{z}={x}{1}+{3}{x}{2} \)

con le condizioni:
\( \displaystyle {x}_{{3}}={3}+{x}_{{1}}-{x}_{{2}} \)
\( \displaystyle {x}_{{4}}={4}-{x}_{{1}}+{2}{x}_{{2}} \)
\( \displaystyle {x}_{{i}}\ge{0}{\mid}{i}={1},{2},{3},{4} \)

La cosa principale che penso tu debba capire è come formulare bene la "forma slack", poi il calcolo è sempre quello...

[Ste868686]

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???

[hamming_burst]

eh bhe ovvio che se la funzione obiettivo è "massimizzare" e i vincoli sono \( \displaystyle \le \) è sbagliato che converti in \( \displaystyle \ge \) ti risulterà una regione non amissibile....
Da quanto dici è come suppungo, tu non sai il "perchè" si fanno certi passaggi....

la moltiplicazione con \( \displaystyle -{1} \) e l'ovvio passaggio a \( \displaystyle \le \) (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...

[Ste868686]

il mio libro fa una distinzione fra metodo grafico e metodo algebrico( cioè il metodo del simplesso) per risolveree i problemi di programmzione lineare

[hamming_burst]

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

[Ste868686]

Guarda se mi riesci a risolvere questo problema col metodo grafico ti sarei grato

\( \displaystyle {M}{a}{x}{z}{2}{X}{1}-{3}{x}{2} \)

vincoli
\( \displaystyle {x}{1}-{x}{2}\le{1} \)
\( \displaystyle {x}{1}\le{2} \)
\( \displaystyle -{x}{1}+{2}{x}{2}\le{4} \)

con x>= 0

[hamming_burst]

Allora, ho fatto qualche disegno passaggio per passaggio, così ti è chiaro (ho fatto schizzi non avevo il software adatto):

\( \displaystyle \max{2}{x}_{{1}}-{3}{x}_{{2}} \)

vincoli
\( \displaystyle {x}_{{1}}-{x}_{{2}}\le{1} \)
\( \displaystyle {x}_{{1}}\le{2} \)
\( \displaystyle -{x}_{{1}}+{2}{x}_{{2}}\le{4} \)

tutti i vincoli sono conformi allo stantard.

la prima cosa da fare è tracciare il grafico, con i vincoli:

\( \displaystyle {x}_{{1}}-{x}_{{2}}\le{1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {x}_{{1}}\le{2}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -{x}_{{1}}+{2}{x}_{{2}}\le{4} \)


Dall'intersezione dei vincoli amissimbili otterrai una regione ammissibile, che è il simplesso.

Ti calcoli il gradiente dalla funzione obiettivo:

\( \displaystyle \Delta{\left({x}_{{1}},{x}_{{2}}\right)}={\left({2},-{3}\right)} \)

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 \( \displaystyle {\left({1},{0}\right)} \) il cui valore è \( \displaystyle {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.