Come usare il simplesso in un caso come questo?

[AndreaNobili]

Ciao,
come posso usare il metodo del simplesso nel caso in cui NON TUTTE LE VARIABILI di decisione sono definite come maggiori o uguali a 0?

Vi faccio un esempio concreto che è sicuramente più chiaro, ho questo esercizio:

Facendo uso del simplesso, determinare, se esiste, la soluzione ottima del seguente PL

min {X1 + X2: X1 + X2 + X3 = 11; 2*x1 - X2 + X4 = 4; -3*X1 + 2*X2 + X5 = 2; X3,X4,X5 >= 0}

Spero sia comprensibile...in pratica devo minimizzare la FUNZIONE OBBIETTIVO che è: X1 + X2

Ho 3 vincoli espressi come equazioni che sono:
X1 + X2 + X3 = 11
2*x1 - X2 + X4 = 4
-3*X1 + 2*X2 + X5 = 2

Poi ho i vincoli di non negatività solo sulle variabili X3, X4 ed X5...ecco quà mi frego...se avessi i vincoli di non negatività su tutte le variabili sarebbe semplicissimo (faccio il tableau ed applico l'algoritmo del simplesso)...così invece non sò proprio cosa devo fare...come si fà in situazioni di questo tipo? qualche idea?

Grazie mille
Andrea

[gardos]

Ma il problema è che non hai x1 e x2 vincolate <=0?
Se si anch'io ho questo problema, spesso le trovo <=0 nei problemi forniti, penso che vadano trasformate in modo che se x1 dev'essere x1<=0 allora devo cercare -x1 nei vincoli così da trasformare il vincolo di non negabilità in x1>=0.
Comunque il dubbio rimane anche a me.

[hamming_burst]

I programmi di programmazione lineare hanno una forma canonica, penso lo sappiate, dette forma standard e forma slack, che ha dei vincoli.
Un programma non in forma standard si può trasformarlo in un programma equivalente, e poi adeguarlo in quello slack.

Rinscriviamo il programma nella forma consona:

\( \displaystyle \min:{x}_{{1}}+{x}_{{2}} \)

condizioni:

\( \displaystyle {x}_{{1}}+{x}_{{2}}+{x}_{{3}}={11} \)
\( \displaystyle {2}{x}_{{1}}-{x}_{{2}}+{x}_{{4}}={4} \)
\( \displaystyle -{3}{x}_{{1}}+{2}{x}_{{2}}+{x}_{{5}}={2} \)

\( \displaystyle {x}_{{3}},{x}_{{4}},{x}_{{5}}\ge{0} \)

A mio vedere il programma è già in forma slack, lo ritrasformo nella forma canonica slack così da far vedere meglio il passaggio:

\( \displaystyle \min:{x}_{{1}}+{x}_{{2}} \)

condizioni:

\( \displaystyle {x}_{{3}}={11}-{x}_{{1}}-{x}_{{2}} \)
\( \displaystyle {x}_{{4}}={4}-{2}{x}_{{1}}-{x}_{{2}} \)
\( \displaystyle {x}_{{5}}={2}+{3}{x}_{{1}}-{2}{x}_{{2}} \)

\( \displaystyle {x}_{{3}},{x}_{{4}},{x}_{{5}}\ge{0} \)

come si vede i valori non di base stanno a destra, quelli di base a sinistra. Per aggiungere i vincoli di non negatività di \( \displaystyle {x}_{{1}} \) e \( \displaystyle {x}_{{2}} \) li sostituiamo in questo modo:

\( \displaystyle {x}_{{1}}={x}_{{{1}'}}-{x}_{{{1}{''}}} \)
\( \displaystyle {x}_{{2}}={x}_{{{2}'}}-{x}_{{{2}{''}}} \)

perciò sostituendo nel programma diviene:

\( \displaystyle \min:{x}_{{{1}'}}-{x}_{{{1}{''}}}+{x}_{{{2}'}}-{x}_{{{2}{''}}} \)

condizioni:

\( \displaystyle {x}_{{3}}={11}-{x}_{{{1}'}}+{x}_{{{1}{''}}}-{x}_{{{2}'}}+{x}_{{{2}{''}}} \)
\( \displaystyle {x}_{{4}}={4}-{2}{x}_{{{1}'}}+{2}{x}_{{{1}{''}}}-{x}_{{2}}'+{x}_{{{2}{''}}} \)
\( \displaystyle {x}_{{5}}={2}+{3}{x}_{{{1}'}}-{3}{x}_{{{1}{''}}}-{2}{x}_{{{2}'}}+{2}{x}_{{{2}{''}}} \)

\( \displaystyle {x}_{{{1}'}},{x}_{{{1}'}},{x}_{{{2}'}},{x}_{{{2}{''}}},{x}_{{3}},{x}_{{4}},{x}_{{5}}\ge{0} \)

Ed ecco risolto il problema, le soluzioni obbittivo del programma originale ha lo stesso valore obbiettivo del programma trasformato.
Ora è facile risolverlo con il simplesso