|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.RO-AnalisiPost-Ottimale History
Hide minor edits - Show changes to output
Changed line 8 from:
Tutte le immagini di questa pagina sono prese dalle slide del prof [[Giovanni Righini]]
to:
Quasi tutte le immagini di questa pagina sono prese dalle slide del prof [[Giovanni Righini]]
Changed lines 87-99 from:
to:
!!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.
%rframe%Attach:ROanalisiParam.jpg\\
''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
Added line 81:
%rframe%Attach:ROvariazCoeffEs2.jpg Deleted line 82:
%rframe%Attach:ROvariazCoeffEs2.jpg
Changed line 85 from:
Attach:ROvariazTerminiA2.jpg to:
->Attach:ROvariazTerminiA2.jpg
Changed line 82 from:
%rframe%ROvariazCoeffEs2.jpg to:
%rframe%Attach:ROvariazCoeffEs2.jpg
Changed lines 65-87 from:
to:
!!Variazione del termine noto
Considerando il seguente caso di riferimento:
%center%Attach:ROvariazTermini.jpg
Da un punto di vista geometrico, cambiare il termine noto b'_3_' significa traslare il vincolo x'_3_' 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'_4_' e x'_5_', ma spostando il vincolo 3 spostiamo anche lei, che continua a rimanere ottima finché non incontriamo una nuova intersezione.\\
Nell'esempio: se b'_3_' diminuisce, il vincolo 3 trasla verso il basso finché non incontra l'intersezione tra l'asse x e il vincolo di x'_2_', facendo diventare quest'ultimo attivo. Se invece b'_3_' aumenta, allora il vincolo 3 trasla verso l'alto finché non si arriva all'intersezione tra x'_2_' e x'_1_', attivando quest'ultimo.
Per quanto riguarda i valori, nel nostro caso la base rimane ottima per 8 <= b'_3_' <= 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:
%center%Attach:ROvariazTerminiNA.jpg
dove c'_i_' è la colonna della variabile di slack del vincolo i su cui sto facendo l'analisi
* se b'_i_' è attivo avrò che:
%center%Attach:ROvariazTerminiA.jpg
Partiamo dallo stesso tableau di prima:
%rframe%ROvariazCoeffEs2.jpg
* consideriamo la riga 3. La variabile di slack della riga è x'_6_', 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'_3_' >= -2
* consideriamo ora il primo vincolo, che corrisponde alla variabile di slack x'_4_'. 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:
Attach:ROvariazTerminiA2.jpg
TO BE CONTINUED
Changed line 8 from:
Alcune immagini di questa pagina sono prese dalle slide del prof [[Giovanni Righini]]
to:
Tutte le immagini di questa pagina sono prese dalle slide del prof [[Giovanni Righini]]
Changed lines 23-24 from:
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'_1_', 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'_1_' 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'_4_' è 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!\\
Il coefficiente di x'_1_' può anche essere diminuito all'infinito? No, perché ruotando in senso antiorario arriveremo ad un punto in cui le curve di livello diventeranno parallele al vincolo di x'_5_' (esattamente quando C'_1_' = 1), e se diminuissero anche solo di un infinitesimo diventerebbe ottimo il vertice in alto. to:
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'_1_', 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'_1_' 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'_4_' è 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'_1_' 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'_5_' (esattamente quando C'_1_' = 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:
%center%Attach:ROvariazCoeff.jpg
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:
(:table cellpadding=10 cellspacing=10 width=80%:)
(:cellnr width=49% align=center valign=middle bgcolor=#f9f9f9:)
Attach:ROvariazCoeffEs1.jpg
(:cell align=center:)[+[@->@]+]\\
'''tableau'''\\
[+[@->@]+]
(:cell width=49% align=center valign=middle bgcolor=#f9f9f9:)
Attach:ROvariazCoeffEs2.jpg
(:tableend:)
Cosa succede quando cambiamo x'_1_'?\\
Ragioniamo: j = 1 appartiene a B? No! Quindi Δc'_1_' <= 7/8.
Cosa succede se invece provo a cambiare il coefficiente di x'_2_'?\\
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?\\
Attach:ROvariazCoeffEs3.jpg\\
Nessuno.
[[<<]]
E quali sono invece i coefficienti strettamente negativi della riga 2 delle colonne fuori base?\\
Attach:ROvariazCoeffEs4.jpg\\
Solo l'elemento della quinta colonna, che ha valore -1.
Quindi ho scoperto che:\\
Attach:ROvariazCoeffEs5.jpg\\
cioè che il coefficiente di x'_2_' può decrescere finché vuole, ma può aumentare al massimo fino a 3/4 se non vogliamo cambiare basi.
Added lines 1-27:
(:title Ricerca Operativa - Analisi post-ottimale:)
[[Torna alla pagina di Ricerca Operativa->Ricerca Operativa]]
----
%titolo%''':: Ricerca Operativa - Analisi post-ottimale ::'''
>>frame<<
Alcune 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:
%center%Attach:ROanalisiSens.jpg
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'_1_', 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'_1_' 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'_4_' è 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!\\
Il coefficiente di x'_1_' può anche essere diminuito all'infinito? No, perché ruotando in senso antiorario arriveremo ad un punto in cui le curve di livello diventeranno parallele al vincolo di x'_5_' (esattamente quando C'_1_' = 1), e se diminuissero anche solo di un infinitesimo diventerebbe ottimo il vertice in alto.
----
[[Torna alla pagina di Ricerca Operativa->Ricerca Operativa]]
|
|
