Simplesso Primale Flashcards
In programmazione Lineare, cosa è una base?
E’ un insieme di indici di lunghezza pari al numero di variabili tale che la sua matrice di base è invertibile. La matrice si ottiene prendendo le righe di indici appartenenti alla base.
Come si calcola una soluzione primale di base?
x segnato è pari all’inversa della matrice di base per bB ovvero le componenti in B del vettore b.
Quando è che una soluzione primale è ammissibile?
Se soddisfa i vincoli del problema primale, ovvero se Anx <= bn, dove n sono gli indici non appartenenti alla base.
Quando una base primale è degenere?
E’ degenere se ci sono vincoli attivi che non appartengono alla base.
Sia B una base. Allora la coppia di soluzioni x = ab-1bb e y = (cab-1,0)…
Soddisfano il teorema degli scarti complementari perché sono definite in modo da soddisfarli.
Sia x in Rn una soluzione primale id base ammissibile. Allora x è soluzione ottima di (P) se e solo se
esiste una base B associata a x t.c. la soluzione duale ammissibile per (D)
Se x non è degenere allora…
Esiste una sola base associata.
In breve, cosa fa l’algoritmo del simplesso?
Considera l’insieme dei vertici del problema principale, e, ad ogni passo, cerca un vertice che migliori il valore della funzione obbiettivo.
Quali sono i passi del simplesso primale?
1) Data una base primale ammissibile, si calcolano la soluzione primale e duale di base.
2) Se la soluzione duale è ammissibile, abbiamo trovato la soluzione ottima.
3) Altrimenti scegliere un h della base tale che yh viola i vincoli duali.
4) Trovare una direzione di crescita, pari a meno la colonna h-esima della matrice di base.
5) Il passo è il minimo dei passi ammissibili in ogni direzione.
6) Se il passo è infinito, il problema è illimitato.
7) Scegliere k in N tale che lambda = lambda-k-
8) Cambiare base, togliendo h e mettendo k.
Iterare.
Qual è la regola anticiclo di Bland?
L’indice uscente dev’essere il minimo tra quelli che infrangono i vincoli del problema duale.
