Calcolo della soluzione ottima di un problema di PL

Consideriamo il problema (PL) in Forma Standard:

$min \space z = \underline{c}^T \underline{x} \\ A \underline{x} = \underline{b} \\ \underline{x} \geq 0$

Data una base $B$ ammissibile, riscriviamo il problema in funzione di $B$ come segue:

$min \space z = z_0 - \sum_{j \in N} (z_j-c_j) x_j \\ \underline{x}B = \underline{\overline{b}} - \sum{j \in N} \underline{y}_j x_j \\ \underline{x} \geq 0$

con $z_0 = \underline{c}^T_B A_B^{-1} \underline{b}$, $z_j = \underline{c}_B^T A_B^{-1} \underline{a}_j$, $\underline{\overline{b}} = A_B ^{-1} \underline{b}$, $\underline{y}_j = A_B^{-1} \underline{a}_j$

Soluzione migliorabile

Consideriamo la funzione obiettivo: $min \space z = z_0 - \sum _{j \in N} (z_j - c_j) x_j$

Supponiamo che esista un coefficiente $k \in N$ tale che: $z_k -c_k >0$

Incrementando la variabile fuori base $x_k$, che è attualmente nulla, la funzione obiettivo migliora: $z = z_0 - \overbrace{(z_k -c_k)}^{>0}\overbrace{x_k}^{>0}$

Teorema (condizione di ottimalità)

Una soluzione di base non degenere di un problema di PL è ottima se e solo se:

  1. $\overline{b}_i \geq 0$ $i = 1,..,m$ (ammissibile)
  2. $z_j-c_j \leq 0$ $\forall j \in N$ (non migliorabile)

Nel caso di soluzione degenere possono esistere soluzioni ottime in cui il punto 2. del teorema non è soddisfatto

Tuttavia, se un problema ammette una soluzione ottima finita allora ammette una soluzione di base ottima che soddisfa le condizioni 1. e 2. del teorema

Test dei minimi rapporti

Utilizzato per individuare la variabile in base $x_{B_r}$ che si azzererà per prima, al crescere di $x_k$, e che quindi uscirà dalla base

Riassumendo