Esercizi_base

Esercizio di base (modello) con metodo del Simplesso

Risolvere il seguente problema di PL :

$$\begin{array}{r}\max 3x_1+x_2+3x_3\\ s.t2x_1+x_2+x_3\le 2\\ x_1+2x_2+3x_3\le 5\\ 2x_1+2x_2+x_3\le 6\\ x_1,x_2,x_3,\ge 0\end{array}$$

Lo scriviamo in forma standard :

• siccome è $\max$ dobbiamo moltiplicare per $-1$ la funzione obiettivo :

$$\min -3x_1-x_2-3x_3$$

• aggiungiamo i vari “surplus” ai vincoli per farli diventare uguaglianze :

$$\begin{array}{r}2x_1+x_2+x_3+x_4=2\\ x_1+2x_2+3x_3+x_5=5\\ 2x_1+2x_2+x_3+x_6=6\end{array}$$

e quindi avremo :

La nostra base ammissibile sono le nostre variabili di slack aggiunte (che sono gratis “soluzioni” ammissibili, basta porre le $x_1,x_2,x_3=0$).

Facciamo il tableau :

$$\begin{array}{cccccccc}& b& x_1& x_2& x_3& x_4& x_5& x_6\\ -z& 0& -3& -1& -3& 0& 0& 0\\ x_4& 2& 2& 1& 1& 1& 0& 0\\ x_5& 5& 1& 2& 3& 0& 1& 0\\ x_6& 6& 2& 2& 1& 0& 0& 1\end{array}$$

e quindi la situazione e la seguente (in figura le rappresentazioni con i rispettivi colori - blu e rosso) :

$$x_B=\left[\begin{array}{c}{x}_4\\ x_5\\ x_6\end{array}\right]x_F=\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]$$

e :

$$B=\left[\begin{array}{c}{A}_4,A_5,A_6\end{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$$

(conosciuta anche come Matrice Identità in giallo nella figura sotto).

Siccome la prima riga di $-z$ non ha tutti i numeri $\ge 0$, la soluzione di base attuale NON è OTTIMALE. Quindi procediamo con l’operazione di cambio base :

• prendere il minimo della riga $-z$, che risulta essere : $-3$ $⟹$ la colonna che entra in base è $x_1$
• calcoliamo il quoziente minimo :

$$\begin{array}{r}\theta =\min \left\{\frac{b_i}{x_{1,i}}\right\}i=1,2,3\\ ⟹\min \left\{\frac{2}{2},\frac{5}{1},\frac{6}{2}\right\}=\min \{1,5,3\}=1\end{array}$$

quindi siccome $i=1$ prendiamo la prima riga, ovvero $x_4$ che esce. - quindi la nuova base risulta essere : $B=\{x_1,x_5,x_6\}$ (siccome è “entrato” $x_1$ ed uscito $x_4$)

• eseguiamo l’operazione di pivot (intersezione tra riga che esce e colonna che entra), e quindi otteniamo che il pivot sarà $2$
• calcoliamoci la nostra nuova riga $x_1$ che sarà

$$\begin{array}{r}{x}_1=\left(\frac{b_1}{2}\Vert \frac{x_4}{2}\right)i=1,2,3,4,5,6\\ ⟹x_1=\left(\frac{2}{2}\Vert \frac{2}{2},\frac{1}{2},\frac{1}{2},\frac{0}{2},\frac{0}{2}\right)=\\ =\left(1\Vert 1,\frac{1}{2},\frac{1}{2},\frac{1}{2},0,0\right)\end{array}$$

• le nuove righe ($-z,x_5,x_6$) verranno create secondo il seguente “algoritmo”, prendiamo per esempio la costruzione della riga $x_5$:
  • prendo come riferimento la vecchia riga $x_5=(5||1,2,3,0,1,0)$
  • prendiamo il numero di questa riga in posizione $k$, dove $k$ è l’indica della nostra colonna che entrava ($x_1$), quindi $k=1$ e quindi il nostro numero della riga è $1$ (il secondo dopo $5$)
  • ora dobbiamo capire quante volte dobbiamo sottrarre il nostro numero ($1$) per avere $0$. (dobbiamo risolvere $1-j=0⟹j=1$)
    • quindi il nostro numero “jolly” sarà $j=1$
  • ora gli altri numeri della riga del nuovo $x_5$
  • seguiranno questo pattern :

$$x_{5,i}=x_{5,i}-j\times x_{1,i}$$

	- quindi avremo che :

$$\begin{array}{rl}& x_{5,1}=x_{5,1}-j\times x_{1,1}=5-(1)\times 1=4\\ & x_{5,2}=1-(1)\times 1=0\\ & x_{5,3}=2-\frac{1}{2}=\frac{3}{2}\\ & x_{5,4}=3-\frac{1}{2}=\frac{6-1}{2}=\frac{5}{2}\\ & x_{5,5}=0-\frac{1}{2}=-\frac{1}{2}\\ & x_{5,6}=1-0=1\\ & x_{5,7}=0-0=0\end{array}$$

Quindi applicando lo stesso algoritmo per costruire la riga $x_6$ avremo il nuovo tableau :

$$\begin{array}{cccccccc}& b& x_1& x_2& x_3& x_4& x_5& x_6\\ -z& 3& 0& 1/2& -3/2& 3/2& 0& 0\\ x_1& 1& 1& 1/2& 1/2& 1/2& 0& 0\\ x_5& 4& 0& 3/2& 5/2& -1/2& 1& 0\\ x_6& 4& 0& 1& 0& -1& 0& 1\end{array}$$

con la seguente situazione :

$$x_B=\left[\begin{array}{c}{x}_1\\ x_5\\ x_6\end{array}\right]x_F=\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]$$

e :

$$B=\left[\begin{array}{c}{A}_1,A_5,A_6\end{array}\right]=\left[\begin{array}{ccc}2& 0& 0\\ 1& 1& 0\\ 2& 0& 1\end{array}\right]$$

e quindi con $x=(x_1,x_2,x_3,x_4,x_5,x_6)=(1,0,0,0,4,4)$ avremo che $z=-3$.

N.B. : il “nuovo” $B$ si costruisce sempre secondo il problema originale, quindi in questo caso abbiamo sostituito $A_4$ con $A_1$ e quindi andiamo a prendere i coefficienti degli $x_1$ originali del problema

Siccome la riga $-z$ ha ancora numeri NON positivi si ripete il metodo!

• il minimo della riga $-z$ è $-3$ $⟹$ $x_3$ colonna che entra
• calcoliamo il minimo :

$$\min \left\{\frac{1}{1/2},\frac{4}{5/2},\cancel{\frac{4}{0}}\right\}=\left\{2,\frac{8}{5}\right\}=\frac{8}{5}$$

- quindi $x_{5}$ esce

• il nostro pivot è $5/2$
• calcoliamo la nuova $x_3$

$$x_3=\left(\frac{4}{5/2}||0,\frac{3}{5},1,-\frac{1}{5},\frac{2}{5},0\right)$$

Riconsideriamo il tableau solo con i valori nuovi :

$$\begin{array}{cccccccc}& b& x_1& x_2& x_3& x_4& x_5& x_6\\ -z& & & & & & & \\ x_1& & & & & & & \\ x_3& 4& 0& 3/2& 5/2& -1/2& 1& 0\\ x_6& & & & & & & \end{array}$$