Analisi di Post-Ottimalità

Dato un problema di PL:

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

sia $\underline{x}^*$ la soluzione di base ammissibile ottima e $B$ la base ottima associata a tale soluzione

Quindi:

• $\underline{x}^*_B = A_B^{-1} \underline{b} \geq \underline{0}$ (ammissibilità)
• $z_j -c_j \leq 0$ $\forall j \in N$

Determinare come sia possibile variare i parametri del problema lasciando invariata tale base ottima

Caso 1: variazione nel vettore dei costi $\underline{c}$

Data una soluzione di base ammissibile ottima $\underline{x}^*$, supponiamo che il coefficiente di una delle variabili sia cambiato da $c_k$ a $c_k'$

L’effetto di questo cambio si ripercuoterà solo sui coefficienti di costo ridotto

• caso 1.1: variazione di un coefficiente di costo relativo ad una variabile non in base
• caso 1.2: variazione di un coefficiente di costo relativo ad una variabile in base

Caso 1.1

Sia $c_k$, $k \in N$, il coefficiente che viene modificato come segue: $_k' = c_k + \delta$

In questo caso $\underline{c}_B^T$ non subisce variazioni e quindi $z_j = \underline{c}_B^T A_B^{-1} \underline{a}_j$ rimane inalterato $\forall j \in N$

Solo il coefficiente di costo ridotto $z_k- c_k$ cambia come segue: $z_k - c_k' = z_k -(c_k+ \delta) = (z_k -c_k) -\delta$

• se $z_k - c_k' \leq 0$ allora $\underline{x}^*$ è ancora la soluzione ottima
• se $z_k -c_k' >0$ allora $\underline{x}^*$ non è più la soluzione ottima e quindi occorre effettuare un’iterazione del simplesso per far entrare in base la variabile $x_k$

Qual è l’intervallo di valori che può assumere $\delta$ affinché l’attuale base $B$ continui a rimanere ottima?