Programmazione lineare (generale) Flashcards
Siano x una soluzione ammissibile per (P), y una soluzione ammissibile per (D)
Se y ( b - Ax) = 0 allora sono entrambe soluzioni ottime
Riscrivi il teorema degli scarti complementari
Se Aix < bi => yi = 0. (se il vincolo i non è attivo nel problema primale, allora è attivo nel problema duale)
Se yi > 0 => Aix = bi (se il vincolo i non è attivo nel problema duale, allora è attivo nel problema primale).
Sia x in Rn ammissibile per (P). Allora, x è una soluzione ottima se e solo se…
esiste un y ammissibile per (D) che soddisfa gli scarti complementari.
Sia y in Rn ammissibile per (D). Allora y è soluzione ottima se e solo se…
Esiste un x ammissibile per (P) che soddisfa gli scarti complementari con y.
Graficamente, una soluzione di base ammissibile è…
Un vertice del problema.
Un base primale è degenere…
Se una vincolo non appartenente alla base è attivo.
Una soluzione duale di base è ammissibile…
Se yB è maggiore o uguale a zero.
Una soluzione di base duale è degenere se…
Un vincolo che appartiene alla base è attivo, ovvero è uguale a zero.
Una coppia di soluzioni della stessa base…
Soddisfa sempre gli scarti complementari.
Teorema della dualità debole
Siano x sol.ne ammissibile di (P), e y sol.ne ammissibile di (D).
Allora, il valore della funzione obbiettivo di (P) è minore o uguale al valore della funzione obbiettivo di (D). Quindi cx <= yb.
Se (P) è superiormente illimitato…
allora (D) è vuoto.
Se (D) è inferiormente illimitato…
Allora (P) è vuoto.
In pratica, il valore di (P)
può essere al massimo il valore di (D).
x sol.ne per (P), y per (D). Se cx = yb allora…
Sono rispettivamente soluzioni ottime di (P) e di (D).
Xi in Rn è una direzione ammissibile per x se…
Esiste un lamda segnato > 0 tale che x + lambda*Xi è ammissibile per (P) per ogni lambda tra zero e lambda segnato.
Insomma, una direzione è ammissibile se…
Permette di spostare la soluzione corrente di un passo lambda, senza uscire dalla regione ammissibile.
Una direzione per crescita per c*x
E’ uno Xi tale che c*Xi è maggiore di zero. (prodotto scalare).
Se non esistono direzioni ammissibili di crescita per x…
Significa che x è una soluzione ottima per (P).
Se il seguente sistema non ha soluzione Xi, allora la soluzione x è ottima.
A dei vincoli attivi in x. per Xi <= 0
c * Xi > 0
Dualità forte.
Supponiamo che (P) e (D) abbiano entrambi regioni ammissibili non vuote. Allora il massimo valore di (P) è uguale al minimo valore di (D).
Come sapere se un poliedro contiene vertici?
Se il rango della matrice A è pari al numero di variabili, allora P possiede almeno un vertice.
Quali sono le tre proprietà di un problema di Programmazione Lineare?
numero finito n di variabili, funzione obbiettivo lineare, insieme ammissibile definito da un insieme finito di m vincoli lineari.
