Metodo simplesso condizione di illimitatezza

[davcarnaby]

Ciao a tutti .

Stavo studiando il metodo del simplesso ma non riesco a capire la condizione di illimitatezza, mi spiego meglio.

Una volta superato il test di ottimalità è quindi trovato un cj (costo ridotto) negativo, vado a controllare se sulla sua colonna di pivot esiste un elemento -db che sia non negativo per stabilire quale è la variabile che deve uscire dalla base.

Ora se tutti i -db sono >=0 allora la regione ammissibile risulta essere illimitata.

Perchè avviene ciò? o per meglio dire, qual'è la spiegazione algebrica a questa cosa??

grazie a tutti

[Giux1]

Ciao, il motivo è semplice.
Se in una colonna relativa ad un costo ridotto $<0$ tutti i coefficienti sono anch'essi $<0$ significa che il massimo incremento ($\epsilon$ o $\delta$" a seconda delle notazioni), che garantisce un "non peggioramento" della funzione obiettivo non ha limiti

esempio: se tu hai il seguente problema:
già in forma standard

$min -x_1 -3x_2$
$s.t. x_1 -2x_2 + x_3 = 4 $
$ -x_1 + x_2 + x_4 = 3 $
$ x_j>=0, j=1,..,4 $

passando al tableau in forma canonica rispetto alla base $ B = (x_3, x_4)$ si ottiene

$ ( (1, 2, 1, 0, |, 4), (-1, 1, 0, 1, |, 3 ), (-1, -3, 0, 0, |, 0)) $

facendo pivot sul primo $1$ in alto a sinistra si ottiene

$ ( (1, -2, 1, 0, |, 4), (0, -1, 1, 1, |, 7 ), (0, -1, 1, 0, |, 4)) $

ora in corrispondenza dell'unico costo ridotto negativo tutti i coefficienti sono negativi

se riscriviamo il tutto in forma di sistema ed esplicitiamo rispetto alla base $B = [x_1, x_4]$ otteniamo

$x_1 = 2x_2 - x_3 + 4 $
$x_4 = x_2 - x_3 + 7 $

si vede ora che per rispettare l'ammissibilità occorre che

$x_1 >=0 => 2x_2 - x_3 + 4 >=0$
$x_4 >=0 => x_2 - x_3 + 7 >=0$

e siccome si incrementa una sola variabile per volta mentre tutte le altre rimangono nulle , il tutto diviene:

$2x_2 + 4 >= 0$
$x_2 + 7 >=0$

da qui si vede che non c'è limite all'incremento della variabile $x_2$ quindi la funzione è illimitata