Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Antonio Sforza » 12.Ottimizzazione lineare: Analisi post-ottimale


Schema della lezione

In questa lezione si illustrano i concetti generali dell’analisi post-ottimale, cioè dell’analisi della soluzione ottima del modello, basata sostanzialmente sulla determinazione degli effetti che le possibili variazioni dei parametri del modello hanno sulla soluzione stessa. Tradizionalmente l’analisi post-ottimale si divide in analisi di stabilità ed analisi parametrica. Nel seguito si illustra, dapprima sotto l’aspetto grafico e poi sotto l’aspetto analitico, l’analisi di stabilità per variazioni dei termini noti dei vincoli e per variazioni dei coefficienti della funzione obiettivo.

Analisi post-ottimale

Nella formulazione dei modelli di programmazione matematica continua presentati si è fatta l’ipotesi che i parametri noti del problema (termini noti, coefficienti della funzione obiettivo) siano di tipo deterministico, cioè definiti senza elementi di incertezza. In realtà questi dati possono presentare un certo grado di aleatorietà, tipico dei meccanismi di funzionamento dei sistemi socio-economici e territoriali nell’ambito dei quali nascono i problemi decisionali da risolvere. La soluzione ottima del modello, determinato sulla base dei dati disponibili, contiene in sé questi elementi di incertezza. Si pone pertanto la necessità di sviluppare un’analisi della soluzione ottima del problema, definita per questo analisi post-ottimale, basata sostanzialmente sulla determinazione degli effetti che le possibili variazioni dei parametri del modello hanno sulla soluzione stessa. I parametri sottoposti ad analisi sono i termini noti e i coefficienti della funzione obiettivo. Tradizionalmente l’analisi post-ottimale si divide in analisi di stabilità ed analisi parametrica. La prima determina i campi di variazione dei parametri che consentono di mantenere inalterata la configurazione della soluzione basica ammissibile ottima. La seconda studia l’andamento della soluzione (valori delle variabili e della funzione obiettivo) al variare dei parametri oggetto di studio. Nel seguito si espongono gli elementi fondamentali dell’analisi di stabilità.

Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo

Si prenda in considerazione il vincolo 3, che contribuisce alla formulazione del vertice ottimo. Si supponga che il termine noto b3 subisca un incremento.


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo

Lo spigolo corrispondente (C-D) si sposta verso l’alto, per esempio fino alla posizione C’-D’, il dominio diventa O-A-B-C’-D’-E e il vertice ottimo D si sposta nel punto D’, in corrispondenza del quale non muta la configurazione della s.b.a. ottima.


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo

Il termine noto b3 può aumentare ancora fino a determinare una posizione limite del vincolo in corrispondenza della quale il dominio diventa O-A-B-D^-E. Il vincolo 3 diventa ridondante ed il vertice ottimo si porta nella posizione D^. La configurazione della s.b.a. ottima resta immutata, anche se la soluzione è degenere, infatti è:

x1 > 0, x2 > 0, y1 > 0, y2 = 0 (basica), y3 = y4 = 0.

L’incremento limite del termine noto si indica con Δb3+. Se il termine noto aumentasse ulteriormente la configurazione della s.b.a. ottima muterebbe, perché la variabile y3, nulla e non basica, diventerebbe positiva e quindi basica, mentre y2, nulla e basica, diventerebbe non basica.


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo

Se invece b3 subisce un decremento, lo spigolo C-D si sposta verso il basso, per esempio fino alla posizione C”-D”, ed il vertice ottimo D si sposta nel punto D”, in corrispondenza del quale non muta la configurazione della s.b.a. ottima. Il termine noto b3 può diminuire fino ad una posizione del vincolo B-D”’, in corrispondenza della quale diventa ridondante il vincolo 2 ed il vertice ottimo si sposta nel punto D”’, nel quale ancora non muta la s.b.a. ottima. Il termine noto b3 può diminuire ancora fino alla posizione limite del vincolo C”’-E, in corrispondenza della quale diventa ridondante il vincolo 4 e il vertice ottimo si sposta in E. La configurazione della s.b.a. ottima resta immutata anche se la soluzione è degenere, Si verificherà infatti: x1 > 0, x2 = 0 (basica), y1 > 0, y2 > 0, y3 = y4 = 0. Il decremento limite del termine noto si indica con Δb3-. Se il termine noto b3 diminuisse ulteriormente la configurazione della s.b.a. ottima muterebbe, perché la variabile y4, nulla e non basica, diventerebbe positiva e quindi basica, mentre x2, non nulla e basica, diventerebbe non basica.

Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo


Analisi di stabilità rispetto al termine noto bi di un vincolo saturo nel vertice ottimo


Espressioni analitiche di Δbi+ e Δbi-

Per determinare le espressioni di Δbi+ e Δbi- è necessario far riferimento ad una relazione nella quale sia possibile inserire le variazioni stesse come parametri da determinare. All’ottimo vale la condizione di ammissibilità diretta, xb* = (B*)-1b ≥ 0, (B*)-1 è l’inversa della matrice di base della tabella finale del Simplesso [Appendice E del testo di riferimento] che contiene i coefficienti bi. Pertanto se si vuole determinare qual’è il valore limite di Δbi+ e Δbi- in corrispondenza dei quali cambia la configurazione della soluzione basica ammissibile ottima, si deve determinare il valore limite in corrispondenza del quale non vale più la condizione di ammissibilità diretta. Si consideri inizialmente il calcolo di Δbi+.

Si indichi con bi+ il vettore dei termini noti contenente l’elemento bi+ = bi + Δbi+ e sia xb+ il vettore soluzione ottenuto effettuando una variazione Δbi+ del termine noto bi. Indicando con ui un vettore che presenta un 1 nella i-esima posizione e tutti gli altri elementi nulli, si potrà scrivere:

xb+=(B*)-1 b+, in cui b+=b+Δbi+ui

e pertanto:

xb+=(B*)-1 [b+=b+Δbi+ui]

Espressioni analitiche di Δbi+ e Δbi- 

Ricordando che (B*)-1b = b* = xb* l’espressione di xb+ diventa: xb+ = xb* + Δbi+ (B*)-1ui

Il prodotto (B*)-1ui genera la i-esima colonna della matrice (B*)-1, sia essa βi, e quindi: xb+ = xb* + Δbi+ βi 0.

Questa relazione può essere espressa attraverso le relazioni scalari relative alle m componenti del vettore xb+ : xkb* + Δbi+ βki ≥ 0 (k = 1,.., m).

Poiché xkb* e Δbi+ sono positivi, se il termine βki è non negativo la relazione non pone alcun limite all’aumento di Δbi+, se invece βki è negativo il valore limite di Δbi+, definito dalla singola relazione scalare, in corrispondenza del quale la variabile xkb si annulla, è espresso da: Δbi+ = xkb* / (-βki) (βki < 0)

Quindi il valore limite di Δbi+ , definito da tutte le relazioni scalari, è espresso da: Δbi+ = xwb* / (-βwi) = mink [xkb* / (ki )] ( βki < 0)

Se nella colonna βi non ci sono elementi βki > 0 allora Δbi+ = ∞.

L’espressione di Δbi si calcola nello stesso modo a partire dalla relazione bi- = bi - Δbi-

Il valore limite di Δbi-, è espresso da: Δbi- = xwb* / (βwi) = mink [xkb* / (βki)] (∀βki > 0)

Analisi di stabilità rispetto al coefficiente di costo cj

Se il coefficiente c1 della funzione obiettivo aumenta, la direzione della funzione obiettivo ruota in senso orario. Il vertice ottimo D non muta fino ad un certo valore di c1, in corrispondenza del quale la funzione obiettivo è parallela allo spigolo DE del dominio. Con questa posizione della f.o. sono ottimi tutti i punti del segmento DE.

Per valori superiori della variazione positiva Δcj+ il punto di ottimo si sposta nel punto E e quindi muta la configurazione della soluzione basica ammissibile ottima.


Analisi di stabilità rispetto al coefficiente di costo cj


Analisi di stabilità rispetto al coefficiente di costo cj

Se c1 diminuisce, la funzione obiettivo ruota in senso antiorario. Il vertice ottimo D non muta fino ad un certo valore di c1, in corrispondenza del quale la funzione obiettivo è parallela allo spigolo CD. Con questa posizione della f.o. sono ottimi tutti i punti del segmento CD. Per valori superiori della variazione negativa Δcj- il vertice ottimo si sposta in C e quindi muta la configurazione della s.b.a. ottima.

L’entità della variazione, positiva o negativa, di c1 è dunque proporzionale all’ampiezza dell’angolo tra la direzione della f.o. e lo spigolo al quale essa va a diventare parallela.


Analisi di stabilità rispetto al coefficiente di costo cj


Analisi di stabilità rispetto al coefficiente di costo cj

Le espressioni analitiche di Δcj+ e Δcj- si determinano a partire dalla condizione di ammissibilità duale:
cnb* = cnbcb (B*)-1NB0, nella quale (B*)-1 è l’inversa di base della tabella finale del Simplesso, cb e cnb sono i vettori dei coefficienti della tabella iniziale relativi rispettivamente alle variabili basiche e non basiche all’ottimo, NB è la matrice della tabella iniziale relativa alle variabili non basiche all’ottimo.

A partire da questa espressione si ricava che per un problema di massimizzazione le espressioni dei valori limite Δck+ e Δck- per i coefficienti di una variabile xk non basica sono Δcknb+ = – ck* , Δck- = – ∞.

Per un problema di minimizzazione le variazioni limite diventano: Δck+ = + ∞, Δck- = ck*

Le espressioni dei valori limite di Δck+ e Δck- per i coefficienti di una variabile xk basica sono invece

Δ chb+ = minj {- cj* / – ahj*} (ahj* < 0) (∀ j non basico)

Δ chb- = min j {- cj* / ahj*} (ahj* > 0) ( j non basico)

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion