In questa lezione si illustra l’algoritmo del Simplesso Revisionato, così definito perché realizza una diversa implementazione dell’algoritmo del Simplesso, più efficace dal punto di vista computazionale, basata sulla constatazione che nel corso delle iterazioni l’algoritmo utilizza in effetti soltanto una parte di tutte le informazioni contenute nella tabella del sistema.
Si introducono le relazioni utilizzate dall’algoritmo, si descrive lo schema operativo di funzionamento e si riporta un esempio numerico.
L’algoritmo del Simplesso Revisionato (Revised Simplex) mantiene inalterata la struttura generale dell’algoritmo (1a s.b.a., test di ottimalità, stop o nuova s.b.a., ritorno al test di ottimalità e così via fino alla soluzione ottima), ma ne realizza una diversa implementazione, basata sulla constatazione che nel corso delle iterazioni l’algoritmo utilizza in effetti soltanto una parte di tutte le informazioni contenute nella tabella del sistema.
Si può notare infatti che per il test di ottimalità e per la determinazione della variabile entrante, viene utilizzato il vettore cjnb dei coefficienti della funzione obiettivo relativi alle variabili non basiche. Per determinare la variabile uscente, se s è il pedice della colonna pivot corrispondente alla variabile entrante, è necessario calcolare il minimo dei rapporti bi /ais, con i che varia da 1 a m. Per calcolare questi rapporti si utilizzano quindi altri due vettori: il vettore b della colonna dei termini noti ed il vettore ps dei coefficienti della colonna della variabile entrante.
L’algoritmo del Simplesso Revisionato realizza un’implementazione dell’algoritmo orientata a calcolare solo i tre vettori effettivamente necessari per passare da una tabella all’altra: cnb‘, b’, ps‘ .
È possibile determinare con una procedura algebrica, descritta in dettaglio nel testo di riferimento, le espressioni di cnb‘, b’, ps‘ relative ad ogni tabella dell’algoritmo in funzione di elementi noti o calcolabili nel corso della procedura:
L’espressione della funzione obiettivo è infine -z = – cb B-1b. Gli elementi noti di queste espressioni sono i seguenti:
La matrice B-1, inversa della matrice di base allo stadio k, deve invece essere calcolata ad ogni iterazione della procedura attraverso una operazione di pivoting limitata alle colonne della tabella k corrispondenti alle colonne in cui si trova la matrice identità della tabella iniziale.
Si ricordi che un sistema Ax = b di dimensioni mxn (m<n) può essere messo in forma canonica rispetto a m variabili con una semplice operazione algebrica, premoltiplicando il sistema Ax = b per la matrice B-1, inversa della matrice B, detta matrice di base, costituita dalle colonne iniziali di A relative alle variabili rispetto alle quali si vuole il sistema in forma canonica.
Com’è noto, ogni tabella del simplesso contiene un sistema in forma canonica, necessario per identificare una soluzione basica ammissibile. Esso quindi può essere pensato come ottenuto da una trasformazione del sistema iniziale attraverso la pre-moltiplicazione per la matrice B-1, inversa della matrice B relativa all’insieme di variabili basiche di quella tabella.
Si noti ancora che il nostro sistema è in forma canonica sin dalla prima tabella (per l’aggiunta delle variabili slack e/o delle variabili artificiali). Il sistema quindi può essere scritto nella forma [A · I ] x = b. Se si effettua la pre-moltiplicazione per B-1 al fine di ottenere il sistema in forma canonica rispetto ad un prefissato insieme di variabili, si ottiene: B-1 [A · I ] x = B-1b, [B-1 A · B-1I ] x = B-1b, [D · B-1] x = B-1b.
Ciascuna tabella del Simplesso contiene quindi la matrice B-1, inversa della matrice di base associata alla soluzione relativa a quella tabella. Essa si trova nelle colonne corrispondenti alla matrice identità iniziale. Per ricavare B-1 ed applicare le espressioni dei tre vettori cnb‘, b’, ps‘ è sufficiente quindi effettuare le operazioni di pivoting limitate a queste colonne della matrice.
Prima di svolgere esempi numerici è opportuno riassumere le operazioni del Simplesso Revisionato. In tabella sono riportate schematicamente le tabelle relative alla soluzione di un problema con 3 vincoli del tipo ≤ e 10 variabili originarie. La prima soluzione basica ammissibile è costituita quindi da 10 variabili originarie, non basiche, e 3 variabili slack, basiche, rispetto alle quali il sistema è in forma canonica.
Si supponga che dall’esame dei coefficienti della funzione obiettivo sia stata determinata come variabile entrante la variabile x8. Attraverso i rapporti bi /ai8 è possibile determinare la riga pivot e la variabile uscente (si supponga y2). L’elemento pivot è quindi a28. Con il Simplesso Standard si effettuerebbe l’operazione di pivoting estesa a tutta la tabella, generando una seconda tabella completa. Nel Simplesso Revisionato, invece, l’operazione di pivoting viene limitata alle colonne corrispondenti alla matrice identità della prima tabella, che contengono necessariamente la matrice B-1, inversa della matrice di base B. Calcolata in questo modo la matrice B-1 è possibile utilizzare l’espressione di c’nb, in funzione di B-1 e degli altri elementi noti, per calcolarne i relativi valori. Dall’esame di c’nb è possibile individuare la nuova variabile entrante (sia x4) e calcolare successivamente p’4, utilizzando l’espressione di p’s. Dopo aver calcolato b‘ è possibile calcolare i rapporti bi /ai4. Ciò consente di determinare la variabile uscente (sia y1) ed individuare il nuovo elemento pivot a14. La procedura continua identicamente senza mai trasformare tutta la tavola, ma solo la parte relativa alla B-1, necessaria per calcolare i vettori cnb, pj e bi, rilevanti per lo sviluppo dell’algoritmo.
Si consideri il seguente problema:
Bisogna aggiungere tre variabili slack nei tre vincoli di ≤. Per agevolare la numerazione delle colonne le variabili slack y1, y2 e y3 sono indicate con x7, x8 e x9.
La prima tabella del simplesso assume quindi la configurazione riportata in tabella.
Le variabili basiche sono x7, x8 e x9. Le variabili non basiche sono x1, x2, x3, x4, x5 e x6.
Si può quindi scrivere
La variabile entrante è la x5, la variabile uscente e la x9. Dunque nella tabella successiva le basiche saranno x7, x8 e x5. Le variabili non basiche saranno x1, x2, x3, x4, x6 e x9. Pertanto:
Si calcola B1 con il pivoting alle colonne della matrice I della prima tabella ottenendo:
Si avrà pertanto:
Il test di ottimalità su cnb‘ mostra che la soluzione non è ottima perchè ci sono ancora coefficienti positivi.
La variabile entrante è la x2. Per determinare la variabile uscente è necessario calcolare le colonne p2‘ e b‘:
Con le matrici e i vettori calcolati [B-1,cnb', p2' e b'] si può costruire la nuova tabella parziale, riportata in figura.
Pioché il rapporto Min i {bi/ais}=Min i {4}=4, la variabile uscente è la x7 e quindi nella tabella successiva si avrà (si ricordi che i valori di cb e cnb vanno sempre presi nella prima tabella):
Per costruire la B’1 della tabella successiva si effettua l’operazione di pivoting limitata alle colonne della matrice identità della tabella iniziale:
In base al test di ottimalità su cnb’ la soluzione risulta ottima.
Si determini il vettore b’ per ottenere i valori delle variabili:
L’ultima tabella assume pertanto la configurazione riportata in figura.
La soluzione ottima è la seguente:
2. Ottimizzazione non lineare monodimensionale
3. Ottimizzazione non lineare multidimensionale non vincolata
4. Ottimizzazione non lineare multidimensionale vincolata
5. Ottimizzazione lineare: formulazione di modelli
6. Ottimizzazione lineare: Algoritmo del Simplesso
7. Ottimizzazione lineare: Algoritmo del Simplesso - II parte
8. Ottimizzazione lineare: Algoritmo del Simplesso - III parte
9. Ottimizzazione lineare: il metodo del Big M
10. Ottimizzazione lineare: il metodo delle due fasi
11. Ottimizzazione lineare: Algoritmo del Simplesso revisionato
12. Ottimizzazione lineare: Analisi post-ottimale
13. Ottimizzazione lineare: il modello duale
15. Ottimizzazione intera: il metodo del piano di taglio
16. Ottimizzazione intera: il metodo Branch and Bound
17. Ottimizzazione su rete: Introduzione alla Teoria dei Grafi
18. Ottimizzazione su rete: Problemi di percorso
19. Ottimizzazione su rete: Problemi di flusso
20. Ottimizzazione su rete: Problemi di progetto, circuito e locali...