Problema di PL col metodo del simplesso,che sucede quando...

[Ste868686]

non ci sono soluzioni?

cioè se non ammette soluzioni come me ne accorgo? cosa ne viene fuori usando il metodo del simplesso?

[hamming_burst]

definiscimi cosa è per te: "non ammette soluzioni"

[Ste868686]

definiscimi cosa è per te: "non ammette soluzioni"

allra questo problema ad esempio
max z = X1 +X2
vincoli
X1-X2 >=0
-3X1 +X2 >=3
con x>=0

non ammette soluzioni.

Sul libro lo risolve col metodo grafico e non ho ancora provato a risolverlo col metodo del simplesso. La domanda quindi si riferiva a cosa capita nel procedimento del simplesso, cioè tipo provo tutte le soluzioni possibili e nessuna sarà ottima?
oppure tipo trovo mi posso trovare in situzioni in cui non si può calcolare la soluzioni con una data variabile entrante? o altro?

[Deckard]

Se un problema non ammette soluzioni significa che non esiste nessuna soluzione ammissibile. Ovvero nessun vettore \( \displaystyle {x} \) t.c. \( \displaystyle {A}{x}={b} \). In sostanza hai un sistema lineare non risolvibile e ciò accade, ma questo dovresti saperlo, quando la matrice A non ha rango pieno. Di conseguenza se la tua matrice A è \( \displaystyle {m}{x}{n} \) per applicare il simplesso dovresti trovare m colonne di A linearmente indipendenti (per formare la base B), ma ciò non è possibile perchè A non ha rango pieno.
Te ne accorgi perché per applicare il simplesso dovresti fare entrare in base m variabili e ottenere la matrice identità nel tableaux, ma per fare ciò dovresti moltiplicare il tableaux per \( \displaystyle {{B}}^{{-{{1}}}} \), ma poiché B è formata da vettori linearmente dipendenti non è invertibile e quindi non riuscirai mai a trovare la forma canonica del tableaux.
EDIT:
Altrimenti può capitare che il sistema sia risolubile, ma le soluzioni siano non positive: in questo caso riesci a trovare una base e la sua inversa ma poi la soluzione di base \( \displaystyle {{B}}^{{-{{1}}}}{b} \) non rispetta il vincolo di non negatività.
In sostanza non puoi neanche applicare l'algoritmo del simplesso poiché per scrivere il tableux in forma canonica bisogna trovare una soluzione di base ammissibile (BFS); per trovare la BFS si usa solitamente il metodo due fasi ed è da lì che ti accorgi che il problema non ha soluzioni ammissibili.

[hamming_burst]

sì ho chiesto cosa intendevi, perchè nel metodo del simplesso "ammette soluzioni" ha significati diversi. Una varibile entrante/non entrante può avere soluzioni di base ammissibili o meno. E anche il problema se non rispetta i vincoli non ha regioni amissibili. alla fine è questione di terminologia.
Ma Deckard (grazie) ha espresso il mio pensiero molto meglio

[Ste868686]

Allora ad un certo punto viene questo( lo scrivo sotto forma di equazioni)

2x1 - x3 = z

-x1 +x2 +x3 = 0

2x1 +x3 +x4 = -3


A questo punto se trasferite queste equazioni sulla tavola del simplesso avete quello che ho io davanti (cambiando di segno a z). Arrivati a questo passaggio già mi posso accorgere che l'equazione non ha soluzioni????

[Deckard]

Ma per applicare il simplesso devi partire da una soluzione di base ammissibile (per avere l'identità su due colonne: qui ce l'hai ma hai b <= 0 quindi devi cambiare di segno la seconda eq., ma così facendo non hai più l'identità): per trovarla come ho scritto prima devi applicare la prima fase del metodo "due fasi".

[Ste868686]

Ma per applicare il simplesso devi partire da una soluzione di base ammissibile (per avere l'identità su due colonne: qui ce l'hai ma hai b <= 0 quindi devi cambiare di segno la seconda eq., ma così facendo non hai più l'identità): per trovarla come ho scritto prima devi applicare la prima fase del metodo "due fasi".

si ho fatto tutto è la soluzione che viene non è ottima, allora c'è quel passaggio che ho scritto nel post. Da li non riesco ad andare avanti perchè delle due variabili uscenti una è nulla e l'altra al crescere di quella entrante di incrementa (infatti se vedi il termine noto è negativo)

Da questo capisco che non ha soluzioni??