Swappa : Uni / Ricerca Operativa - Analisi post-ottimale

:: Ricerca Operativa - Analisi post-ottimale ::

Quasi tutte le immagini di questa pagina sono prese dalle slide del prof Giovanni Righini

Cos'è

Il nome lascia poco all'immaginazione: l' analisi post-ottimale viene effettuata solo dopo aver trovato la soluzione ottima. Ma se l'abbiamo già trovata che altro dobbiamo calcolare a fare? Perché prima di tradurre la soluzione ottima in una decisione (assumendoci dunque una responsabilità) è opportuno studiare la robustezza del modello, ovvero valutare quanto cambierebbero i risultati se cambiassero i dati. Ricordiamo infatti che questi ultimi derivano da misurazioni, stime o previsioni, che dunque nel tempo potrebbero diventare più accurate o rivelarsi errate. I dati sono la matrice A, il vettore dei termini noti b e i coefficienti di costo ridotto C^T.

Andando al sodo, quello che vogliamo studiare con l'analisi post-ottimale sono gli intervalli di variazione dei costi ridotti c_j o dei termini noti b_i entro cui la soluzione ottima rimane tale. Questo studio prende il nome di analisi di sensitività.
Perché la soluzione rimanga ottima dobbiamo garantire due condizioni:

ammissibilità (variabili di base non negative). Dipende solo dai termini noti b
ottimalità (costi ridotti opposti in segno alla direzione di ottimizzazione). Dipende solo dai costi ridotti c

Esempio

Consideriamo il seguente problema:

Cambiamo uno dei coefficienti della funzione obiettivo e facciamolo variare finché non cambia la base ottima B = {1,2,3}. Interveniamo ad esempio sul "2" di x₁, portandolo progressivamente a "2,1", "2,2", "2,3", e così via. La prima cosa che notiamo è che i valori dei coefficienti non influenzano in alcun modo il sistema dei vincoli, mentre hanno grande impatto sull'orientamento delle curve di livello: se il valore aumenta la curva ruota in senso orario, e viceversa.
Tornando al nostro caso, potremo continuare ad incrementare il coefficiente di x₁ finché ci pare, dato che all'infinito la curva di livello assume una posizione verticale e dunque la base non cambia (il vincolo di x₄ è infatti leggermente inclinato verso destra). Nota bene però: la base ottima e le x non cambiano, ma la soluzione sì! Non dimentichiamo che stiamo modificando i coefficienti della funzione obiettivo!
Continuiamo a considerare il coefficiente di x₁ e proviamo stavolta a diminuirlo. Possiamo andare avanti finché vogliamo? No, perché ruotando in senso antiorario arriveremo ad un punto in cui le curve di livello diventeranno parallele al vincolo di x₅ (esattamente quando C₁ = 1), e se ruotassero anche solo di un millimetro la base cambierebbe perché diventerebbe ottimo il vertice in alto.

Variazione dei costi ridotti

Distinguiamo ora le conseguenze della variazione dei costi ridotti e di quelle dei termini noti. Cominciamo dai primi.
Se j appartiene alla base B, allora la variazione dei valori del coefficiente C_j è compresa tra i valori minimi e massimi riportati nella seguente formula:

Dove:

i valori con asterisco sono quelli che si leggono dal tableau corrispondente alla soluzione ottima
r_j indica la riga su cui è in base la variabile j
la parte sinistra della formula concorre a definire il valore minimo, e considera solo le colonne che hanno coefficiente strettamente positivo
la parte destra concorre invece a definire il valore massimo, e considera solo le colonne con coefficienti strettamente negativi

Riportiamo l'esempio presente sulle slide:

->
tableau
->

Cosa succede quando cambiamo x₁?
Ragioniamo: j = 1 appartiene a B? No! Quindi Δc₁ <= 7/8.

Cosa succede se invece provo a cambiare il coefficiente di x₂?
j = 2 appartiene a B? Sì, e in particolare r_j = 2.
Quali sono i coefficienti strettamente positivi della riga 2 delle colonne fuori base?

Nessuno.
E quali sono invece i coefficienti strettamente negativi della riga 2 delle colonne fuori base?

Solo l'elemento della quinta colonna, che ha valore -1.

Quindi ho scoperto che:

cioè che il coefficiente di x₂ può decrescere finché vuole, ma può aumentare al massimo fino a 3/4 se non vogliamo cambiare basi.

Variazione del termine noto

Considerando il seguente caso di riferimento:

Da un punto di vista geometrico, cambiare il termine noto b₃ significa traslare il vincolo x₃ verso il basso o verso l'alto a seconda che - rispettivamente - diminuiamo o aumentiamo il suo valore. La base ottima rimane sempre nell'intersezione tra i vincoli x₄ e x₅, ma spostando il vincolo 3 spostiamo anche lei, che continua a rimanere ottima finché non incontriamo una nuova intersezione.
Nell'esempio: se b₃ diminuisce, il vincolo 3 trasla verso il basso finché non incontra l'intersezione tra l'asse x e il vincolo di x₂, facendo diventare quest'ultimo attivo. Se invece b₃ aumenta, allora il vincolo 3 trasla verso l'alto finché non si arriva all'intersezione tra x₂ e x₁, attivando quest'ultimo.

Per quanto riguarda i valori, nel nostro caso la base rimane ottima per 8 <= b₃ <= 24, ma la soluzione ottima cambia e insieme ad essa anche il sistema dei vincoli, quindi la regione ammissibile.

Spostando questi ragionamenti nel tableau otterremo qualcosa di simile a quanto avevamo visto per le variazioni dei costi ridotti. Abbiamo due casi: o spostiamo un vincolo che in quel momento è attivo, o ne spostiamo un altro che in quel momento non lo è. Consideriamoli separatamente:

se b_i non è attivo, allontanandolo dalla regione ammissibile non cambia nulla, mentre se lo avviciniamo a un certo punto diventerà attivo. In formule:

dove c_i è la colonna della variabile di slack del vincolo i su cui sto facendo l'analisi

se b_i è attivo avrò che:

Partiamo dallo stesso tableau di prima:

consideriamo la riga 3. La variabile di slack della riga è x₆, che è in base e dunque il vincolo non è attivo. Per capire di quanto posso variarlo senza che diventi attivo devo guardare il valore della variabile, quindi Δb₃ >= -2
consideriamo ora il primo vincolo, che corrisponde alla variabile di slack x₄. Essendo questa fuori base allora il vincolo è attivo, quindi per avere informazioni sulle variazioni permesse noti dovrò guardare sulla quarta colonna gli elementi positivi e negativi del tableau:

Analisi parametrica

L'analisi di sensitività ci dice qual è il range di variazione di coefficienti o termini noti entro cui non varia la base ottima, ma come facciamo a sapere cosa succede al di fuori di tale intervallo? Eseguiamo un' analisi parametrica, che ci permette di calcolare quanto varia il valore ottimo della funzione obiettivo al variare dei dati. Il risultato di questa attività è quasi sempre una funzione che lega il valore ottimo a un termine noto o a un coefficiente di costo ridotto. Con l'analisi parametrica potremo perciò identificare e modificare un vincolo e osservare come cambia la soluzione.

v(i) è il vincolo che stiamo facendo variare; z* è l'ottimo

Come è fatta la funzione? Dato che il legame tra soluzione e coefficienti è di tipo lineare e che rimane tale indipendentemente dalla base, ne ricaviamo che a ogni range corrisponde un segmento di retta e quindi la funzione sarà lineare a tratti.

Altre due considerazioni sulla funzione:

ha la concavità rivolta sempre dalla stessa parte, proprio per come è realizzato il poliedro
la proiezione di ogni tratto sull'asse x ha una sua base ottima, sempre diversa dalle altre

Ovviamente anche l' analisi parametrica è un tipo di analisi post-ottimale

Torna alla pagina di Ricerca Operativa