Esercizi_base

<#### Metodo del Simplesso (esercizio modello) 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.

Ricordiamo che nel calcolo di $\theta$ si ignora un eventuale negativo.

• 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/2$ $⟹$ $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& 8/5& 0& 3/5& 1& -1/5& 2/5& 0\\ x_6& & & & & & & \end{array}$$

Calcoliamo ora le varie righe :

• $-z$ :
  • $-\frac{3}{2}-j=0⟹j=-\frac{3}{2}$
  • $-z_b=3-\left(-\frac{3}{2}\times \frac{8}{5}\right)=3+\frac{12}{5}=\frac{27}{5}$
  • $-z_{x_1}=0$
  • $-z_{x_2}=\frac{1}{2}+\frac{9}{10}=\frac{5+9}{10}=\frac{7}{5}$
  • $-z_{x_3}=0$
  • $-z_{x_4}=\frac{3}{2}-\left(\frac{3}{2}\times \frac{1}{5}\right)=\frac{3}{2}-\frac{3}{10}=\frac{15-3}{10}=\frac{6}{5}$
  • $-z_{x_5}=\frac{3}{5}$
  • $-z_{x_6}=0$
• $x_1$ :
  • $\frac{1}{2}-j=0⟹j=\frac{1}{2}$
  • $x_{1,b}=1-\frac{1}{2}\times \frac{8}{5}=\frac{1}{5}$
  • $x_{1,x_1}=1$
  • $x_{1,x_2}=\frac{1}{2}-\frac{1}{2}\times \frac{3}{5}=\frac{1}{5}$
  • $x_{1,x_3}=\frac{1}{2}-\frac{1}{2}=0$
  • $x_{1,x_4}=\frac{1}{2}+\frac{1}{10}=\frac{3}{5}$
  • $x_{1,x_5}=-\frac{1}{5}$
  • $x_{1,x_6}=0$
• $x_6$ :
  • $j=0⟹$ sarà identica a prima!

PS : ho utilizzato $x_{i,x_j}$ che si capisce meglio Quindi avremo il nuovo tableau :

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

e la situazione sarà la seguente :

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

e :

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

e quindi con $x=(x_1,x_2,x_3,x_4,x_5,x_6)=(1/5,0,8/5,0,0,4)$ avremo che $z=-27/5$. Osserviamo ora che tutti i costi ridotti nella prima riga sono tutti $\ge 0$ e quindi la soluzione di base corrente è ottima!

Il problema PL ha come soluzione :

$$\begin{array}{rl}& x=(x_1,x_2,x_3)=(1/5,0,8/5)\\ & z_{max}=-z_{min}=27/5\end{array}$$

Metodo delle due fasi

Quando si usa il metodo delle due fasi? $\to$ Quando dopo aver portato in forma standard ci accorgiamo che non abbiamo una base ammissibile valida (es. presenza di $-1$ nella matrice di identità). Questo succede quando abbiamo :

• vincoli con $\ge$ (generano variabili surplus negative)
• vincoli con $=$ (non da surplus)

Fase 1

L’obiettivo di questa fase è quella di trovare una base valida con cui procedere/partire con il metodo del Simplesso.

1. ad ogni equazione di sistema a cui manca un pezzo della matrice di identità, aggiungiamo una variabile finta $y_i$
2. congeliamo la nostra funzione obiettivo ($-z$) per un attimo e adottiamo la funzione obiettivo che ci minimizza le variabili finte :

$$\min w=\sum y_i$$

3. costruiamo il tableau e mettiamo nella colonna della base : variabili $y_i$ e eventuali slack (solo quelli con segno positivo (es. $x_4$ e non $-x_4$))
4. questo tableau costruito non è “canonico” siccome le variabili in base $y$ sono in base ma hanno costo $1$
   • sottraiamo alla riga $-w$ tutte le righe del tableau delle variabili finte : $R_{-w}\leftarrow R_{-w}-R_{y_i}$
5. ora continuiamo sempre con questo tableau con il metodo del simplesso per trovare il valore di $-w$
   • se troviamo $=0$ procediamo alla Fase 2
   • altrimenti il problema è inammissibile e l’esercizio finisce

Fase 1

1. cancelliamo le colonne $y_i$
2. cancelliamo la riga $-w$ e mettiamo $-z$ e i costi originali di partenza
3. ora siccome abbiamo messo dei costi “vecchi” in una base nuova, sicuramente le variabili che ora sono in base avranno dei costi diversi da zero nella nuova riga $-z$, quindi dobbiamo azzerarli.
   • lo facciamo come abbiamo fatto prima nella fase 1 per azzerare le $y_i$ (vedi esercizio di esempio per capire meglio)
4. e ora iniziamo con il simplesso standard

Esercizio modello di esempio

$$\begin{array}{r}\min z=3x_1+2x_2\\ s.t.x_1+2x_2\ge 4\\ 3x_1+x_2\ge 3\\ x_1,x_2\ge 0\end{array}$$

Trasformiamo in forma standard :

$$\begin{array}{r}{x}_1+2x_2-x_3=4\\ 3_{x_1}+x_2-x_4=3\end{array}$$

siamo bloccati (abbiamo segno $-$) e nessuna delle due può entrare in base.

Fase 1

1. aggiungiamo le variabili $y_i$

$$\begin{array}{r}{x}_1+2x_2-x_3+y_1=4\\ 3_{x_1}+x_2-x_4+y_2=3\end{array}$$

2. la funzione obiettivo su cui lavoreremo sarà : $\min w=y_1+y_2$
3. costruiamo il tableau :

$$\begin{array}{cccccccc}& b& x_1& x_2& x_3& x_4& y_1& y_2\\ -w& 0& 0& 0& 0& 0& 1& 1\\ y_1& 4& 1& 2& -1& 0& 1& 0\\ y_2& 3& 3& 1& 0& -1& 0& 1\end{array}$$

4. azzeriamo $y_1$ e $y_2$ con $R_{-w}\leftarrow R_{-w}-R_{y_1}-R_{y_2}$ :
   • $x_1:0-1-3=-4$
   • $x_2:0-2-1=-3$
   • $x_3:0+1-0=1$
   • $x_4:0-0+1=1$
   • $y_1:1-1-0=0$ (top!)
   • $y_2:1-0-1=0$ (top!)
   • $b:0-4-3=-7$
5. quindi avremo il seguente tableau :

$$\begin{array}{cccccccc}& b& x_1& x_2& x_3& x_4& y_1& y_2\\ -w& -7& -4& -3& 1& 1& 0& 0\\ y_1& 4& 1& 2& -1& 0& 1& 0\\ y_2& 3& 3& 1& 0& -1& 0& 1\end{array}$$

e facciamo utilizziamo metodo del simplesso :

• minimo riga $-w$ : $-4⟹$ $x_1$ entra in base
• test quoziente :

$$\theta =\min \left\{\frac{4}{1},\frac{3}{3}\right\}=\min \{4,1\}=1$$

• quindi $y_2$ esce di base e il pivot è $3$
• nuova riga $x_1$ :

$$\begin{array}{r}{x}_1=\left(\frac{3}{3}||\frac{3}{3},\frac{1}{3},0,-\frac{1}{3},0,\frac{1}{3}\right)⟹\\ \begin{array}{cccccccc}& b& x_1& x_2& x_3& x_4& y_1& y_2\\ -w& & & & & & & \\ y_1& & & & & & & \\ \to x_1& 1& 1& 1/3& 0& -1/3& 0& 1/3\end{array}\end{array}$$

• procediamo calcolando le nuove righe :
  • riga $-w$ :
    • $-4-j=0⟹j=-4$
    • $-w_b=-7-(-4)\times 1=-7+4=-3$
    • $-w_{x_1}=-4-(-4)\times 1=0$
    • $-w_{x_2}=-3+\frac{4}{3}=-\frac{5}{3}$
    • $-w_{x_3}=1$
    • $-w_{x_4}=1-\frac{4}{3}=-\frac{1}{3}$
    • $-w_{y_1}=0$
    • $-w_{y_2}=\frac{4}{3}$
  • riga $y_1$ :
    • $j=1$
    • $y_{1,b}=3$
    • $y_{1,x_1}=0$
    • $y_{1,x_2}=5/3$
    • $y_{1,x_3}=-1$
    • $y_{1,x_4}=1/3$
    • $y_{1,y_1}=1$
    • $y_{1,y_2}=-1/3$
• quindi avremo il nuovo tableau :

$$\begin{array}{cccccccc}& b& x_1& x_2& x_3& x_4& y_1& y_2\\ -w& -3& 0& -5/3& 1& -1/3& 0& 4/3\\ y_1& 3& 0& 5/3& -1& 1/3& 1& -1/3\\ x_1& 1& 1& 1/3& 0& -1/3& 0& 1/3\end{array}$$

Facciamo ancora, siccome abbiamo costi negativi :

• $x_2$ entra
• test quoziente :

$$\theta =\min \left\{\frac{3}{5/3},\frac{1}{1/3}\right\}=\min \{9/5,3\}=9/5$$

• quindi $y_1$ esce e il pivot è $5/3$
• nuova riga $x_2$ :

$$\begin{array}{r}{x}_2=\left(\frac{3}{5/3}||0,1,-\frac{3}{5},\frac{1}{5},\frac{3}{5},-\frac{1}{5}\right)⟹\\ \begin{array}{cccccccc}& b& x_1& x_2& x_3& x_4& y_1& y_2\\ -w& & & & & & & \\ \to x_2& 9/5& 0& 1& -3/5& 1/5& 3/5& -1/5\\ x_1& & & & & & & \end{array}\end{array}$$

calcoliamo le nuove righe (diretto nel tableau lo faccio)

$$\begin{array}{cccccccc}& b& x_1& x_2& x_3& x_4& y_1& y_2\\ -w& 0& 0& 0& 0& 0& 1& 1\\ \to x_2& 9/5& 0& 1& -3/5& 1/5& 3/5& -1/5\\ x_1& 2/5& 1& 0& 1/5& -2/5& -1/5& 2/5\end{array}$$

PERFETTO abbiamo $-w=0$ e le due variabili artificiali sono state tolte dalla base.

Fase 2

Avremo il nuovo tableau :

$$\begin{array}{cccccc}& b& x_1& x_2& x_3& x_4\\ -z& 0& 3& 2& 0& 0\\ x_2& 9/5& 0& 1& -3/5& 1/5\\ x_1& 2/5& 1& 0& 1/5& -2/5\end{array}$$

• dobbiamo nella riga $-z$, azzerare $x_1=3$ e $x_2=2$ con $R_{-z}\leftarrow R_{-z}-3(R_{x_1})-2(R_{x_2})$ :
  • $x_1:3-3(1)-2(0)=0$ (top!)
  • $x_2:2-3(0)-2(1)=0$ (top!)
  • $x_3:0-3(1/5)-2(3/5)=3/5$
  • $x_4:0-3(-2/5)-2(1/5)=4/5$
  • $b:0-3(2/5)-2(9/5)=-24/5$ e quindi avremo il tableau :

$$\begin{array}{cccccc}& b& x_1& x_2& x_3& x_4\\ -z& -24/5& 0& 0& 3/5& 4/5\\ x_2& 9/5& 0& 1& -3/5& 1/5\\ x_1& 2/5& 1& 0& 1/5& -2/5\end{array}$$

che risulta già risolto siccome non ci sono costi negativi :

$$-z=-\frac{24}{5}⟹z=\frac{24}{5}$$