Soluzione dei Problemi di Programmazione Lineare Consideriamo un problema di Programmazione Lineare (PL) con m vincoli ed n variabili in Forma Standard max x0 = cT x Ax = b x0 x Rn dove: (1) (2) x è il vettore nx1 delle variabili decisionali c è il vettore nx1 dei coefficienti della funzione obiettivo b è il vettore mx1 dei termini noti dei vincoli A è la matrice mxn dei coefficienti dei vincoli; Aaij], i=1n, j=1m Inoltre, si assumono soddisfatte le seguenti ipotesi: b 0 b j 0 j = 1,K , m m0 La variabile xk entra in base con tale valore, ed in corrispondenza la variabile xBr esce di base. PL-42 Il coefficiente yrk è detto Pivot, (l'aggiornamento della base si dice Pivoting) e viene usato per aggiornare i valori delle variabili in base dopo l'ingresso in base di xk: y x Bi = yi0 - yik r 0 y rk i = 0, m; i r y xk = r 0 y rk xj = 0 j R = R - k La nuova soluzione di base x Br = 0 Le nuove variabili fuori base Con il cambio delle variabili in base, la nuova matrice di base risulta composta delle stesse colonne della vecchia base ad eccezione del fatto che la colonna associata a xBr è stata sostituita dalla colonna associata a xk. Aggiorniamo le equazioni (5) dopo il cambio di base: y rj y rj y r0 x Bi = y i0 - y ik - y ij - y ik x Br xj + y rk jR - k y rk y rk i = 0,1,K, m; i r y rj y 1 = r0 - xk xj - x Br y rk jR - k y rk y rk PL-43 (5') I nuovi valori delle variabili in base si ottengono ponendo nelle (5') xj = 0 j R - k x Br = 0 La nuova soluzione di base ha migliorato il valore della funzione obiettivo: 0 y x B 0 = y 00 - y 0k r 0 y 00 y rk 0 E possibile iterare il procedimento fino a che esiste qualche variabile fuori base che può migliorare l'obiettivo se portata in base. 5. Teorema (Condizione di ottimalità) Una soluzione di base non degenere di un problema di PL è ottima se e solo se: 1) y i0 0 2) y 0 j 0 i = 1, m (ammissibile) (non migliorabile) j R Nel caso di soluzione degenere possono esistere soluzioni ottime in cui il punto (2) del terorema 5 non è soddisfatto. Tuttavia, se un problema ammette soluzione ottima finita allora ammette una soluzione di base ottima che soddisfa le condizioni (1) e (2) del teorema 5. PL-44 Scelta della variabile entrante. Quando la condizione di ottimalità non è verificata è sempre possibile scegliere una variabile fuori base xk da portare in base per migliorare l'obiettivo. Quando esistono più alternative la scelta non preclude il raggiungimento della soluzione ottima, ma può al peggio aumentare il tempo necessario per la sua ricerca. Esistono due criteri di scelta della variabile entrante: a) Il metodo del gradiente (il più utilizzato) Sceglie la variabile che localmente fa aumentare più rapidamente l'obiettivo: y = min y 0k jR y0j 0 x B i = y i 0 - y ik x k 0 sempre ! 0 Nota. Se per una variabile di base i si ha che yik0 e yr0=0 (soluzione degenere), xk entra in base con valore nullo. In questo caso la soluzione non cambia, ed in particolare rimane degenere. Per questa ragione la ricerca della soluzione pot Continua »