[Ricerca Operativa] Problema metodo del simplesso

[Escher]

Ciao a tutti, il problema sta nel risolvere questo esercizio col metodo del simplesso.

Traccia:

\(\displaystyle \begin{cases}min -x_{1}-3x_{2}-2x_{4}+2x_{5} \\ x_{1}+2x_{2}+x_{3}-x_{5} = 1 \\ x_{2}+x_{4} = 2 \\ 2x_{1}+x_{2}+x_{3}-x_{4} = 6 \\ x\geq 0 \end{cases} \)

Questa è la mia soluzione, usando il metodo dei dizionari. Quello che mi hanno insegnato è che la variabile che entra è quella variabile positiva con coefficiente più piccolo. A parità di coefficiente entra quella con indice minore.
Visto che sono abituato a risolvere i problemi con la massimizzazione, allora lo porto in forma standard (cambiando di segno la funzione obiettivo):

\(\displaystyle \begin{cases}max \ x_{1}+3x_{2}+2x_{4}-2x_{5} \\ x_{1}+2x_{2}+x_{3}-x_{5} = 1 \\ x_{2}+x_{4} = 2 \\ 2x_{1}+x_{2}+x_{3}-x_{4} = 6 \\ x\geq 0 \end{cases} \)

Ora aggiungo le variabili di slack:

\(\displaystyle \begin{cases}max \ x_{1}+3x_{2}+2x_{4}-2x_{5} \\ x_{1}+2x_{2}+x_{3}-x_{5}+x_{6} = 1 \\ x_{2}+x_{4}+x_{7}= 2 \\ 2x_{1}+x_{2}+x_{3}-x_{4}+x_{8} = 6 \\ x\geq 0 \end{cases} \)

Esplicito le variabili di slack:
\(\displaystyle x_{6} = 1 - x_{1}-2x_{2}-x_{3}+x_{5}\)
\(\displaystyle x_{7} = 2 -x_{2}-x_{4} \)
\(\displaystyle x_{8} = 6- 2x_{1}-x_{2}-x_{3}+x_{4} \)
\(\displaystyle z = x_{1}+3x_{2}+2x_{4}-2x_{5} \)

Una prima soluzione è data da: \(\displaystyle (x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}) = (0,0,0,0,0,1,2,6) \) e \(\displaystyle z = 0 \)

In accordo con quello detto all'inizio faccio entrare \(\displaystyle x_{1} \):
\(\displaystyle x_{1} \) può crescere fino a 1 sul vincolo \(\displaystyle x_{6} \) finchè \(\displaystyle x_{6} \) non diventi zero.
\(\displaystyle x_{1} \) non c'è sul vincolo \(\displaystyle x_{7} \)
\(\displaystyle x_{1} \) può crescere fino a 3 sul vincolo \(\displaystyle x_{8} \) finchè \(\displaystyle x_{8} \) non diventi zero.

Il valore più piccolo tra 1 e 3 è 1, quindi esce \(\displaystyle x_{6} \).
Ricavo \(\displaystyle x_{1} \) da \(\displaystyle x_{6} \): \(\displaystyle x_{1} = 1-2x_{2}-x_{3}+x_{5}-x_{6} \)
Sostituendo \(\displaystyle x_{1} \) a tutti i vincoli compreso \(\displaystyle z \), ottengo:
\(\displaystyle x_{1} = 1-2x_{2}-x_{3}+x_{5}-x_{6} \)
\(\displaystyle x_{7} = 2 -x_{2}-x_{4} \)
\(\displaystyle x_{8} = 4+3x_{2}+x_{3}+x_{4}-2x_{5}+2x_{6} \)
\(\displaystyle z = 1+x_{2}-x_{3}+2x_{4}-x_{5}-x_{6} \)

Che ha soluzione: \(\displaystyle (x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}) = (1,0,0,0,0,0,2,4) \) e \(\displaystyle z = 1 \)

Adesso entra \(\displaystyle x_{2} \):
\(\displaystyle x_{2} \) può crescere fino a \(\displaystyle \frac{1}{2} \) sul vincolo \(\displaystyle x_{1} \) finchè \(\displaystyle x_{1} \) non diventi zero.
\(\displaystyle x_{2} \) può crescere fino a 2 sul vincolo \(\displaystyle x_{7} \) finchè \(\displaystyle x_{7} \) non diventi zero.
\(\displaystyle x_{2} \) può crescere indefinitivamente sul vincolo \(\displaystyle x_{8} \).

Il più piccolo tra \(\displaystyle \frac{1}{2} \) e \(\displaystyle 2 \) è \(\displaystyle \frac{1}{2} \). Quindi esce \(\displaystyle x_{2} \). Ricavo \(\displaystyle x_{2} \) da \(\displaystyle x_{1} \): \(\displaystyle x_{2} = \frac{1}{2}-\frac{1}{2}x_{1}-\frac{1}{2}x_{3}+\frac{1}{2}x_{5}-\frac{1}{2}x_{6} \). Sostituisco \(\displaystyle x_{2} \) a tutti i vincoli compreso \(\displaystyle z \) e ottengo:
\(\displaystyle x_{2} = \frac{1}{2}-\frac{1}{2}x_{1}-\frac{1}{2}x_{3}+\frac{1}{2}x_{5}-\frac{1}{2}x_{6} \)
\(\displaystyle x_{7} = \frac{3}{2}+ \frac{1}{2}x_{1}+ \frac{1}{2}x_{3}-x_{4}- \frac{1}{2}x_{5}+ \frac{1}{2}x_{6} \)
\(\displaystyle x_{8} = \frac{11}{2}- \frac{3}{2}x_{1}- \frac{1}{2}x_{3}+x_{4}- \frac{1}{2}x_{5}+ \frac{1}{2}x_{6} \)
\(\displaystyle z = \frac{3}{2}- \frac{1}{2}x_{1}- \frac{3}{2}x_{3}+2x_{4}- \frac{1}{2}x_{5}- \frac{3}{2}x_{6} \)

La cui soluzione è: \(\displaystyle (x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}) = (0,\frac{1}{2},0,0,0,0,\frac{3}{2},\frac{11}{2}) \) e \(\displaystyle z = \frac{3}{2} \)

Evitando un ulteriore allungamento del post, scrivo a parole cosa ho fatto dopo:
Operando come prima ho fatto entrare \(\displaystyle x_{4} \) e uscire \(\displaystyle x_{7} \) ottenendo questa soluzione:
\(\displaystyle (x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}) = (0,\frac{1}{2},0,\frac{3}{2},0,0,0,7) \) e \(\displaystyle z = \frac{9}{2} \)

Nell'ultimo passaggio ho fatto entrare \(\displaystyle x_{1} \) e uscire \(\displaystyle x_{2} \) ottenendo la soluzione:
Riporto anche la \(\displaystyle z = 5-x_{2}-x_{3}-x_{5}-x_{6}-2x_{7} \)
\(\displaystyle (x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}) = (1,0,0,2,0,0,0,6) \) e \(\displaystyle z = 5 \)
Ora visto che la \(\displaystyle z \) ha tutti termini negativi, la soluzione trovata è ottima. Visto che ho cambiato il problema originale massimizzandolo allora \(\displaystyle z = (-z) \) quindi \(\displaystyle z = -5 \).

Ovviamente il risultato non è corretto, la soluzione è:
\(\displaystyle (x_{1},x_{2},x_{4},x_{5}) = (4,0,2,3) \)

Non credo aver fatto errori di calcolo , forse sono errori concettuali.
Grazie per le eventuali risposte e scusate la lunghezza del post.