Primale_Duale

Esercizio 2 - esercizio_esame_04

Risolvere il seguente problema di PL con algoritmo Primale-Duale partendo dal punto iniziale $y^{(0)}=\left[\begin{array}{c}0\\ 0\end{array}\right]$.

$$\begin{array}{rl}\min & z=x_1-x_2\\ s.t.& 2x_1-x_2\le 6\\ & x_1+x_2\ge 1\\ & x_1\ge 0,x_2\le 0\end{array}$$

Trasformazione del problema originale in forma standard

• sostituiamo $x_2\le 0$ con $x_2=-x_2^{\prime }$ e impongo $x_2^{\prime }\ge 0$ , quindi avremo :

$$\begin{array}{rl}\min & z=x_1-(-x_2^{\prime })⟹z=x_1+x_2^{\prime }\\ s.t.& 2x_1-(-x_2^{\prime })\le 6⟹2x_1+x_2^{\prime }\le 6\\ & x_1-x_2^{\prime }\ge 1\\ & x_1\ge 0,x_2^{\prime }\ge 0\end{array}$$

• trasformo i vincoli in $=$ :

$$\begin{array}{rl}\min & z=x_1+x_2^{\prime }\\ s.t.& 2x_1+x_2^{\prime }+s_1=6\\ & x_1-x_2^{\prime }-s_2=1\\ & x_1\ge 0,x_2^{\prime }\ge 0,s_1\ge 0,s_2\ge 0\end{array}$$

quindi avrò :

$$\begin{array}{rl}& x=(x_1,x_2^{\prime },s_1,s_2{)}^T\\ & c=(1,1,0,0{)}^T\\ & A=\left[\begin{array}{cccc}2& 1& 1& 0\\ 1& -1& 0& -1\end{array}\right]\\ & b=\left[\begin{array}{c}6\\ 1\end{array}\right]\end{array}$$

Problema duale

Il problema duale è :

$$\begin{array}{rl}\max & w=6y_1+y_2\\ s.t.& 2y_1+y_2\le 1\\ & y_1-y_2\le 1\\ & y_1+(0)y_2\le 0⟹y_1\le 0\\ & (0)y_1-y_2\le 0⟹y_2\ge 0\end{array}$$

Verifico ora l’ammissibilità duale per calcolare lo “scarto” con i vincoli duali e il punto iniziale dato $y^{(0)}=\left[\begin{array}{c}0\\ 0\end{array}\right]$ :

• $2(0)+0\le 1⟹0\le 1\to \text{scarto}=1$ (vincolo non attivo)
• $0-0\le 1\to \text{scarto}=1$ (vincolo non attivo)
• $0\le 0\to \text{scarto}=0$ (vincolo attivo)
• $0\ge 0\to \text{scarto}=0$ (vincolo attivo) quindi avremo che gli slack duali sono :

$$\left[\begin{array}{c}1\\ 1\\ 0\\ 0\end{array}\right]$$

Per il teorema degli scarti complementari, se un vincolo è largo allora la variabile primale associata deve essere spenta ($=0$) :

• vincolo 1 è largo $⟹x_1=0$
• vincolo 2 è largo $⟹x_2^{\prime }=0$
• vincoli 3 e 4 saturi $⟹$ $s_1$ e $s_2$ restano

Primale ausiliario (PR) e duale ausiliario

Andiamo ora nel primale (forma standard) è sostituiamo $x_1,x_2^{\prime }=0$ :

$$\begin{array}{rl}\min & 0+0\\ s.t.& 2(0)+0+s_1=6\\ & 0-0-s_2=1\\ & 0\ge 0,0\ge 0,s_1\ge 0,s_2\ge 0\end{array}⟹\begin{array}{rl}s.t.& s_1=6\\ & s_2=-1\\ & s_1\ge 0,s_2\ge 0\end{array}$$

Abbiamo però una contraddizione per $s_2$ che deve essere $\ge 0$ ma abbiamo $s_2=-1$. Questo vuol dire che l’offerta duale $y^{(0)}$ non va bene. Per “riparare” aggiungiamo 1 variabile artificiale $a_1,a_2\ge 0$, creando il problema ausiliario o primale ristretto (PR) che ha come obiettivo distruggere le variabili artificiali minimizzandole :

$$\begin{array}{rl}\min & z=a_1+a_2\\ s.t.& s_1+a_1=6\\ & -s_2+a_2=1\\ & a_1\ge 0,a_2\ge 0,s_1\ge 0,s_2\ge 0\end{array}$$

PS : in verità qui dovremmo fare la fase 1 del metodo a due fase, poi vedere quanto viene $w$ (in questo caso ho scritto $z$), se viene $\ne 0$ allora non va bene e continuiamo prendendo sempre in considerazione i valori delle variabili in base che troviamo, siccome lo utilizzeremo dopo per calcolare ${\pi }^{\ast }$.

Scriviamo ora il duale ausiliario :

$$\begin{array}{rl}\max & w=6{\pi }_1+1{\pi }_2\\ s.t.& {\pi }_1\le 0\\ & -{\pi }_2\le 0⟹{\pi }_2\ge 0\\ & {\pi }_1\le 1\\ & {\pi }_2\le 1\end{array}$$

vogliamo quindi massimizzare $w=6{\pi }_1+1{\pi }_2$ e quindi :

• per ${\pi }_1$ abbiamo ${\pi }_1\le 0\wedge {\pi }_1\le 1⟹{\pi }_1\le 0$, quindi il meglio che possiamo fare per massimizzare è ${\pi }_1=0$
• per ${\pi }_2$ abbiamo $0\le {\pi }_2\le 1$, quindi il meglio è ${\pi }_2=1$

PS : qui infatti se vogliamo essere corretti 100% non usiamo questo metodo diretto, ma utilizziamo i valori delle variabili in base trovati con la fase 1 di prima. Infatti diciamo se il valore della variabile $>0$ allora il vincolo del duale associato è attivo (uguaglianza) etc etc. In questo troveremo sempre gli stessi valori ($0$ e $1$).

quindi la direzione ottima sarà :

$${\pi }^{\ast }=\left[\begin{array}{c}0\\ 1\end{array}\right]$$

Ora prendiamo il problema duale e calcoliamo $A^T{\pi }^{\ast }$ :

$$A^T{\pi }^{\ast }=\left[\begin{array}{cc}2& 1\\ 1& -1\\ 1& 0\\ 0& -1\end{array}\right]\times \left[\begin{array}{c}0\\ 1\end{array}\right]=\left[\begin{array}{c}(0)2+1\\ (0)1-1\\ (0)1+0\\ 0-1\end{array}\right]=\left[\begin{array}{c}1\\ -1\\ 0\\ -1\end{array}\right]$$

Ora riprendiamo gli slack duali di prima, è calcoliamo $\theta$ :

$$\theta =\min \left\{\frac{\text{slack\_duale}}{\text{componente positiva di }{A}^T{\pi }^{\ast }}\right\}=\min \left\{\frac{1}{1}\right\}=1$$

e quindi la nuova offerta duale è :

$$y^{(1)}=y^{(0)}+\theta {\pi }^{\ast }=\left[\begin{array}{c}0\\ 0\end{array}\right]+1\times \left[\begin{array}{c}0\\ 1\end{array}\right]=\left[\begin{array}{c}0\\ 0\end{array}\right]+\left[\begin{array}{c}0\\ 1\end{array}\right]=\left[\begin{array}{c}0\\ 1\end{array}\right]$$

Seconda iterazione

Ripetiamo il ciclo e testiamo la nuova offerta $y^{(1)}=\left[\begin{array}{c}0\\ 1\end{array}\right]$ nei vincoli originale del duale :

• $2(0)+1\le 1⟹1\le 1\to \text{scarto}=0$ (vincolo attivo) $⟹x_1$ resta
• $0-1\le 1⟹-1\le 1\to \text{scarto}=2$ (vincolo non attivo) $⟹$ $x_2^{\prime }=0$
• $0\le 0\to \text{scarto}=0$ (vincolo attivo) $⟹s_1$ resta
• $-1\le 0\to \text{scarto}=1$ (vincolo non attivo) $⟹s_2=0$

Nuovo primale ristretto con $x_2^{\prime },s_2=0$ :

$$\begin{array}{rl}& \begin{array}{rl}s.t.& 2x_1+0+s_1=6\\ & x_1-0-0=1\\ & x_1\ge 0,0\ge 0,s_1\ge 0,0\ge 0\end{array}⟹\begin{array}{rl}s.t.& 2x_1+s_1=6\\ & x_1=1\\ & x_1\ge 0,s_1\ge 0\end{array}\\ & \\ ⟹& \begin{array}{rl}& \\ s.t.& s_1=4\\ & x_1=1\\ & x_1\ge 0,s_1\ge 0\end{array}\end{array}$$

siccome non abbiamo variabili negative, il sistema ammette soluzione senza l’ausilio di variabili artificiali., quindi l’obiettivo del primale ristretto è quindi $z_{pr}=0$ e l’algoritmo termina.

Quindi abbiamo trovato che :

$$\begin{array}{rl}& x^{\ast }=(1,0,4,0)\leftarrow \text{soluzione ottima}\\ & z^{\ast }=1\end{array}$$

Verifichiamo che anche il duale va bene :

$$\begin{array}{rl}& y=(0,1)\\ & w\ast =6y_1+y_2⟹6(0)+1=1\end{array}$$