Regole

Per trasformare un problema originale di PL in forma standard :

1. trasformare vincoli $\le$ in $=$
   • aggiungiamo variabile di slack $s_i$ con $s\ge 0$
2. trasformare vincoli $\ge$ in $=$
   • sottraiamo una variabile di surplus $s_i$ con $s\ge 0$
3. sistemare le variabili negative ($\le 0$)
   • se abbiamo una variabile $x_i\le 0$ allora si sostituisce con $x_i=-x_i^{\prime }$ con $x_i^{\prime }\ge 0$
4. sistemare le variabili libere ($\in \mathbb{R}$)
   • se abbiamo una variabile $x_i\in \mathbb{R}$ allora si sostituisce con $x_i=x_i^{+}-x_i^{-}$ con $x_i^{-}\ge$ e $x_i^{+}\ge 0$
5. sistemare termini negativi nella RHS
   • se nella parte RHS (parte destra) abbiamo un numero $<0$ (es. $x_1-x_2=-4$), si moltiplica l’intera equazione per $-1$

Per ottenere il problema duale da un problema primale :

• primale $\max ⟹$ duale $\min$
  • segno $y_i$
    • vincolo primale $\ge ⟹y_i\le 0$
    • vincolo primale $\le ⟹y_i\ge 0$
    • vincolo primale $=⟹y_i\in \mathbb{R}$
  • segno vincoli
    • $x_j\ge ⟹$ vincolo duale di $x_j$ è $\ge$
    • $x_j\le ⟹$ vincolo duale di $x_j$ è $\le$
    • $x_j\in \mathbb{R}⟹$ vincolo duale di $x_j$ è $=$
• • primale $\min ⟹$ duale $\max$
    • segno $y_i$
      • vincolo primale $\ge ⟹y_i\ge 0$
      • vincolo primale $\le ⟹y_i\le 0$
      • vincolo primale $=⟹y_i\in \mathbb{R}$
    • segno vincoli
      • $x_j\ge ⟹$ vincolo duale di $x_j$ è $\le$
      • $x_j\le ⟹$ vincolo duale di $x_j$ è $\ge$
      • $x_j\in \mathbb{R}⟹$ vincolo duale di $x_j$ è $=$

Per fare esercizi dove ci chiedono soluzione ottima, questo può essere utile :

• $x_i>0⟹\text{vincolo di }{x}_i\text{ eˋ attivo}$
• $\text{vincolo di }{y}_i\text{ NON eˋ attivo}⟹x_i=0$
• $y_i>0⟹\text{vincolo di }{y}_i\text{ eˋ attivo}$
• $\text{vincolo di }{x}_i\text{NON eˋ attivo}⟹y_i=0$

Illimitatezza e inammissibilità

Per illimitatezza e inammissibilità (vuoto) :

• Primale ammette soluzione ottima finita $⟹$ Duale ammette soluzione ottima finita (uguale a quella del primale)
• Primale illimitato $⟹$ Duale inammissibile (vuoto)
• Duale illimitato $⟹$ Primale inammissibile (vuoto)
• Primale inammissibile (vuoto) $⟹$ Duale inammissibile (vuoto) OPPURE illimitato

Ricerca SBA

Dato un problema di PL di $n$ vincoli e $m$ variabili, una SBA è dato da :

$$\text{SBA}=B^{-1}b$$

dove $B$ deve essere una matrice $n\times n$ (quadrata) e $B^{-1}$ è la matrice inversa di $B$ e $b$ è il vettore dei termini noti.

Per esempio :

$$\begin{array}{rl}\min & x_1+2x_2\\ s.t.& x_1+3x_2+5x_3\le 6\\ & x_1+2x_2\le 4\\ & x_1,x_2,x_3\ge 0\end{array}$$

trasformiamo in forma standard :

$$\begin{array}{rl}\min & x_1+2x_2\\ s.t.& x_1+3x_2+5x_3+s_1=6\\ & x_1+2x_2+s_2=4\\ & x_1,x_2,x_3,s_1,s_2\ge 0\end{array}$$

allora :

$$B=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$

allora la matrice inversa sarà :

$$B^{-1}=\frac{1}{\det (B)}\left(\begin{array}{cc}d& -c\\ -b& a\end{array}\right)=(ad-cb)\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)=1\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]$$

allora possiamo calcolare il SBA :

$$\text{SBA}=B^{-1}b=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]\left[\begin{array}{c}6\\ 4\end{array}\right]=\left[\begin{array}{c}6\\ 4\end{array}\right]$$

Allora :

$$\left[\begin{array}{ccccc}0& 0& 0& 4& 5\end{array}\right]\text{ eˊ un SBA}$$