AI Assistant
Transcript
00:00:02Buongiorno.
00:00:06Si è capito qualcosa l'altra volta? Sì, vero.
00:00:11Ricordandosi?
00:00:13Eh, certo.
00:00:14Allora, la scorsa volta cosa abbiamo detto?
00:00:17Abbiamo detto che vogliamo risolvere problemi di ottimizzazione,
00:00:21quindi trovare delle soluzioni ottime in presenza di incertezza.
00:00:27Abbiamo capito che questo vuol dire
00:00:30innanzitutto capire qual è il problema di
00:00:32ottimizzazione nominale quale quale sarebbe
00:00:35il problema se non ci fosse incertezza.
00:00:38Una volta che abbiamo appurato che c'è incertezza bisogna capire
00:00:41per avere
00:00:42una controparte robusta del problema bisogna capire uno
00:00:46come rappresentiamo l'incertezza due.
00:00:50Cosa vuol dire minimizzare o massimizzare in caso di incertezza?
00:00:54Tre Cosa può voler dire soddisfare i vincoli in
00:00:58caso di incertezza e diciamo che quello che vogliamo fare in
00:01:02questo corso è avere una sensibilità per
00:01:06trovare il modello giusto nelle tre per i per i
00:01:10tre aspetti quindi capire qual è
00:01:14la rappresentazione di incertezza che più si avvicina
00:01:18a quella reale
00:01:20capire qual è la funzione obiettivo da ottimizzare che più si
00:01:24avvicini a cosa vuol dire essere ottimo se c'è incertezza okay.
00:01:30Perché se c'è incertezza una soluzione ottima
00:01:32in uno scenario non lo è in un altro.
00:01:33Abbiamo fatto dei ragionamenti,
00:01:35ci siamo ispirati in questo all'analisi decisionale,
00:01:37okay e poi abbiamo detto
00:01:39anche bisogna capire cosa vuol dire se l'incertezza sta nella
00:01:42regione ammissibile cosa vuol dire essere
00:01:44ammissibile e ci siamo un po lì ci siamo limitati
00:01:47a dire robusta E una soluzione che è valida sempre,
00:01:52in ogni situazione oppure con un parametro di controllo in
00:01:56un numero controllato di
00:01:59situazioni definite col parametro di controllo.
00:02:02Abbiamo detto la scorsa volta da tutti gli
00:02:04scenari in cui al massimo un certo numero tra
00:02:07tutti una certa percentuale dei
00:02:08parametri incerti variano che è quella era la robustezza assoluta.
00:02:13Con parametro di controllo che serviva un po
00:02:15a mitigare il livello di protezione,
00:02:18il livello di conservatorismo e di conservatorismo.
00:02:22Ok e abbiamo fatto l'esempio di di come si procede no.
00:02:26Uno dice io ho questo problema,
00:02:29cerco una definizione della controparte robusta,
00:02:33mi confronto col committente e pian pianino arriviamo a qual è
00:02:36la definizione giusta che trova l'accordo su.
00:02:44Quanto è costoso.
00:02:46Gli strumenti che abbiamo visto
00:02:47la scorsa volta sono strumenti che ci fanno capire
00:02:50quali sono le possibili rappresentazioni,
00:02:53quali sono le possibili definizioni che ci tengono il
00:02:55problema più o meno difficile che
00:02:57questo è quello che abbiamo fatto.
00:02:58Non entro nei dettagli.
00:03:00Ci siamo poi concentrati sul problema
00:03:02del cammino minimo e abbiamo
00:03:04capito che il problema del cammino minimo,
00:03:06in alcuni casi pochi,
00:03:07rimane facile, come anche con una controparte robusta,
00:03:11in altri casi, più in
00:03:12generale rimane e diventa un problema difficile da risolvere.
00:03:15Okay, va bene. Quindi questo è
00:03:17proprio un giusto per capire su che cosa focalizzare.
00:03:21Passiamo adesso sempre a problemi,
00:03:24a definizioni di controparte robuste però in
00:03:27senso relativo che senso relativo abbiamo
00:03:31detto vuol dire che noi quando andiamo
00:03:35a valutare la robustezza di una soluzione e capire se quella
00:03:38è una soluzione buona o cattiva,
00:03:39lo facciamo non tenendo conto soltanto del valore
00:03:43della soluzione in sé.
00:03:45Nei vari scenari,
00:03:46ma anche confrontandola con altre soluzioni negli scenari che e in
00:03:51particolare noi ci concentriamo sull'incertezza
00:03:55a livello di funzione obiettivo
00:03:56e ci confronteremo con la soluzione ottima in
00:03:59ogni scenario, in ogni situazione.
00:04:01Okay, quindi stiamo parlando dell'analisi decisionale.
00:04:05Il criterio che veniva fuori dal minimizzare il mancato guadagno,
00:04:09per esempio Ok. Quindi adesso lo decliniamo per
00:04:12un problema di minimo e andiamo
00:04:14a considerare e a chiamare come CS asterisco
00:04:18la soluzione ottima del problema
00:04:21nominale nello scenario S.
00:04:24Ok. Quindi noi abbiamo un problema di ottimizzazione,
00:04:27abbiamo una certa funzione obiettivo determinata
00:04:30da una funzione C. Questa funzione chiaramente è diversa.
00:04:34In ogni scenario è data una soluzione
00:04:36X. Diciamo che quella soluzione è
00:04:38la soluzione ottima quando X minimizza
00:04:42il valore della soluzione in quello scenario.
00:04:44Quindi la migliore soluzione in
00:04:46quello scenario va bene, c'è l'asterisco.
00:04:48Definiamo il rimpianto Come la differenza tra il valore
00:04:55della soluzione ottima in quello scenario
00:04:58e il valore di una certa soluzione nello scenario stesso.
00:05:03Quindi, data una soluzione X. Diciamo che.
00:05:06La soluzione ottima è
00:05:07la migliore che potremmo trovare in quello scenario.
00:05:10Un'altra soluzione qualsiasi potrà essere o uguale o peggiore.
00:05:15La differenza delle funzioni obiettivo si chiama rimpianto.
00:05:18Cosa? Perché? Perché? Perché se io scelgo la soluzione
00:05:22X anziché della soluzione ottima mi pentirò di un valore.
00:05:26CSX meno CS asterisco chiaro
00:05:29Per i problemi di Massimo avevamo non avevamo parlato di.
00:05:32Abbiamo parlato di mancato guadagno ed era ovviamente l'opposto.
00:05:36Ok, comunque è sempre un rimpianto,
00:05:38anche il mancato guadagno è un rimpianto.
00:05:40Cosa vuol dire quindi in
00:05:43un problema in cui vogliamo fare una soluzione,
00:05:45in un problema in cui vogliamo trovare una soluzione ottima,
00:05:48robusta in senso relativo vuol dire
00:05:50risolvere quel problema indicato lì formalmente.
00:05:54Che quindi cosa succede?
00:06:02Vogliamo trovare una soluzione x tra tutte quelle
00:06:08che sono ammissibili vi ricordo che stiamo lavorando nell'ipotesi
00:06:11in cui l'insieme delle soluzioni ammissibili è deterministico.
00:06:13Okay, tra tutte quelle prendo una soluzione X e la valuto
00:06:18come la valuto con il massimo rigore,
00:06:22cioè la situazione nella quale mi
00:06:24farebbe più pentire quella soluzione lì.
00:06:26Quindi vado su ogni scenario,
00:06:27calcolo la differenza tra il valore della soluzione in
00:06:31quello scenario e la soluzione ottima in
00:06:32quello scenario e prendo il caso peggiore.
00:06:34Min max chiaro e il criterio del mancato guadagno girato,
00:06:39ma sostanzialmente la stessa cosa sempre minimizzo
00:06:43il massimo mancato guadagno.
00:06:45Il mancato guadagno era definito scambiando questi
00:06:48due termini, ma non cambia niente.
00:06:49Min Max riflette sempre comunque chiaro qual
00:06:52è il concetto perfetto.
00:06:54Chiaramente abbiamo già detto un criterio conservativo.
00:06:57Perché pessimista, no?
00:06:58Noi siamo sempre prendiamo una soluzione,
00:07:00abbiamo sbagliato a sceglierlo.
00:07:02Abbiamo pure sbagliato a scegliere lo scenario in cui valutarla,
00:07:05perché stiamo proprio prendendo il peggiore di tutti.
00:07:08Va bene, quindi è comunque un criterio molto conservativo.
00:07:12Allora. Come al solito io qui potrei fermarmi
00:07:17a dire ogni volta che vedo un problema di ottimizzazione
00:07:19cercate una formalizzazione di quel
00:07:21modello lì di esplicitarlo nel problema con non
00:07:24so con un modello di programmazione lineare intera o mista intera o
00:07:27lineare se basta lo formalizzate e se l'avete formalizzato lo date
00:07:32in pasto ad altri e lo risolvete
00:07:33ovviamente in generale saranno problemi difficili.
00:07:36Allora cerchiamo di fare qualche ragionamento e come al solito
00:07:39ci baseremo sul problema
00:07:41del cammino minimo nel problema del cammino minimo.
00:07:44Una soluzione che adesso abbiamo chiamato X e un e un cammino vero,
00:07:47quindi lo chiameremo P come path per
00:07:50he chiarezza che è l'insieme delle soluzioni ammissibili.
00:07:54E quell'insieme P di tutti i
00:07:56cammini possibili che veniva descritto dal poliedro,
00:08:00dai vertici di un poliedro che erano
00:08:02determinati dai vincoli di flusso.
00:08:04Per esempio tutte le soluzioni ammissibili,
00:08:06tutti i cammini possibili in un grafo.
00:08:08Okay, d'accordo.
00:08:10Allora il problema lo possiamo declinare in questo modo.
00:08:16Semplicemente una é una
00:08:18traduzione nella quale stiamo dicendo che voglio trovare
00:08:22il cammino P che massimizza il regret dove il è il costo e il il.
00:08:31In ogni scenario il in uno scenario
00:08:34è dato dal costo di quel cammino nello scenario.
00:08:36Quindi Kings sono i costi dell'arco che fa parte del cammino.
00:08:40Nello scenario S meno la soluzione è ottima
00:08:43nello scenario S che è
00:08:44chiaro quindi questo niente di nuovo ci siamo perfetto allora in
00:08:48generale trovare un problema un cammino minimo in
00:08:51senso relativo robusto è un problema difficile okay perché
00:08:57è difficile perché se voi volete un indice che
00:09:00è difficile e il fatto che se voi declinate l'abbiamo già visto
00:09:04quindi non lo rifaccio declinate questo
00:09:07eh questa definizione con un modello
00:09:11avrete minimizzare qualcosa è
00:09:13tra i vincoli avrete il secondo livello
00:09:15in cui volete massimizzare quindi avere due
00:09:18problemi da risolvere insieme un problema di livello una cosa
00:09:20difficile da risolvere okay l'intuizione sta
00:09:23nel fatto che comunque qual è l'unica cosa
00:09:27facile qui che si può risolvere L'unica cosa facile qui è
00:09:31risolvere un cammino minimo dato uno scenario no.
00:09:35Se io ho uno scenario posso calcolare
00:09:38in modo facile qual è il cammino minimo in quello scenario,
00:09:40perché è un problema nominale di fatto
00:09:42dati i costi in quello scenario Va bene,
00:09:44okay, ma per il resto
00:09:45cosa dovrei fare per risolvere questo problema?
00:09:47In linea di principio dovrei generare
00:09:49tutti i possibili cammini in una rete,
00:09:51tutti e per ogni cammino andare a vedere, per ogni scenario.
00:09:56Quindi prendo un cammino e considero tutti gli scenari in tutti.
00:10:00In ciascuno scenario calcolo il costo del cammino minimo e faccio
00:10:04la differenza sul costo del cammino in quello scenario che quindi,
00:10:09anche se gli scenari fossero pochi,
00:10:11io comunque dovrei considerare per trovare
00:10:13la soluzione ottima tutti i possibili cammini.
00:10:16Okay, e li devo considerare tutti perché non ho motivo di
00:10:21escludere qualcosa a priori con delle proprietà che sfrutta e
00:10:24quindi il problema diventa facile.
00:10:25Dovrei considerare tutti e quanti sono i cammini in
00:10:28un grafo da un'origine e una
00:10:29destinazione sono un numero esponenziale.
00:10:32Ok, vi faccio un esempio facile facile
00:10:34perché secondo me può essere utile capire
00:10:37dove sta il problema di ottimizzazione perché
00:10:40diventa di difficile se voi avete una rete di questo tipo.
00:10:43Questa è una rete molto semplice nella quale voi ho un nodo da un
00:10:49origine posso andare su due nodi da questo convergono
00:10:51in un altro nodo poi vado avanti okay.
00:10:54Quindi immaginate di avere
00:10:55questa rete fino ad arrivare in una situazione nella
00:10:58quale voi arrivo alla mia destinazione che è ST.
00:11:02Okay, in questo rete trovare il cammino minimo dati dai costi
00:11:07è facile perché applichiamo
00:11:09un algoritmo possiamo applicare
00:11:10il nostro modellino con le variabili continue diventano intere.
00:11:13Siamo d'accordo,
00:11:14ma se noi avessimo dei costi stocastici che variano
00:11:18per scenario e vogliamo trovare
00:11:19il cammino minimo in senso relativo,
00:11:21non funziona più quel modello.
00:11:22Abbiamo un modello più complesso, più difficile che in
00:11:24linea di principio cosa farà per trovare la soluzione ottima
00:11:27Considererà dice dicevamo tutti i possibili cammini e
00:11:30valuta tutti i possibili cammini con il massimo in ogni scenario.
00:11:34Anche se gli scenari fossero
00:11:36pochi quanti sono i possibili cammini in questa rete?
00:11:39Vediamo un cammino è questo
00:11:42qua in cui prendo sempre la direzione sopra.
00:11:44Vero? Ed è un cammino,
00:11:46un altro cammino qual è?
00:11:47Quello in cui prendo sempre la direzione sotto.
00:11:50Okay. Ma in mezzo ci sono delle scelte. Io ho un cammino.
00:11:53Ogni volta che faccio una scelta in
00:11:54questo modo qui posso scegliere se andare sopra o sotto.
00:11:58Quindi ho due possibilità moltiplicate per le
00:12:01due possibilità che ho qui per due, per due, per due.
00:12:04Quindi possibili cammini sono due
00:12:06alla numero di nodi diviso tre mal contati.
00:12:10Okay. Perché ogni tre nodi una scelta da fare?
00:12:14Sei d'accordo? Comunque un numero esponenziale e questo
00:12:17numero se voi se voi avete una rete
00:12:19con 100 nodi 100 diviso tre fa 30 e 2 alla 30.
00:12:25Non è poco sono circa o più di otto più di
00:12:298 milioni ma giù alla 40 son tantissimi
00:12:34no quindi c'è un'esplosione
00:12:37combinatoria si dice del numero di possibilità
00:12:40per cui non posso considerarle tutte,
00:12:42se no divento troppo vecchio.
00:12:43Anzi non ce la faccio proprio, anche se divento vecchio.
00:12:46Neanche se voi diventate vecchie che avete
00:12:47insomma un'aspettativa di vita più non ce la fate, ok?
00:12:51Quindi questo è il motivo per cui il problema è difficile.
00:12:54Cosa possiamo fare?
00:12:55Non possiamo fare niente qualcosina possiamo farlo perché
00:12:58studiando il problema c'è una proprietà
00:13:03per il caso intervalli di incertezza.
00:13:06Allora se voi avete la la
00:13:10l'incertezza definita su intervalli
00:13:13ovviamente gli scenari sarebbero infiniti
00:13:15quindi non ne uscirete vivi anche dal ragionamento combinatorio
00:13:18che però se avete degli intervalli c'è una proprietà che vale.
00:13:23Il problema rimane NP come vedremo però possiamo
00:13:26sfruttare una proprietà che ci aiuterà
00:13:28a risolvere almeno dei casi parziali.
00:13:29La proprietà è la seguente ed ha a che fare
00:13:33con il calcolo con questo calcolo qui
00:13:36cioè con il valorizzare questa
00:13:40espressione vedete che già se riusciamo
00:13:41a valorizzare questa espressione in modo facile.
00:13:44Non abbiamo il problema di considerare
00:13:46tutti gli scenari ma se abbiamo
00:13:49il valore del basta tra virgolette considerare
00:13:53tutti i possibili cammini.
00:13:55Vabbè e quindi comunque difficile il problema però
00:13:58almeno un pezzo della difficoltà l'abbiamo tolto
00:14:00che la proprietà che vale nel caso di intervalli di incertezza
00:14:03è che dato un dato un cammino se io conosco il cammino posso
00:14:07già determinare qual è lo scenario
00:14:10nel quale si realizza il maximum regret.
00:14:12Quindi non devo andare a guardarli tutti gli scenari,
00:14:14dato un cammino per quel cammino.
00:14:16Definisco uno scenario e calcolo il maximum e calcolo il in
00:14:21quello scenario e son sicuro che il maximum riflette
00:14:23che non ci sono scenari in cui è più alto. Va bene?
00:14:26Come si definisce lo scenario? In modo semplice?
00:14:28Lo scenario è quello in cui tutti gli archi del cammino assumono
00:14:34il costo più alto dell'intervallo e tutti gli archi
00:14:37fuori dal cammino assumono il costo più basso.
00:14:40Okay, quindi io prendo questo scenario.
00:14:43Calcola il costo del cammino P In quello scenario è facile,
00:14:46basta fare la somma dei DJ più in questo scenario.
00:14:49E poi calcola il cammino minimo in
00:14:51quello scenario che è facile perché ho i costi.
00:14:53Basta applicare sample facile, Ok?
00:14:56Oppure dai un algoritmo facile,
00:14:59d'accordo, quindi facilmente dato un cammino.
00:15:02So qual è il maximum right.
00:15:04Quindi a quel punto se io devo confrontare dei cammini tra loro,
00:15:07so qual è il cammino migliore tra quelli non tra tutti,
00:15:13ma tra quelli è facile determinare.
00:15:14Chiaro Esempio supponiamo di avere
00:15:18il cammino cat nella nostra solita rete.
00:15:21Ok?
00:15:21Supponiamo che gli intervalli l'intervallo di
00:15:23incertezza sia quello delle colonne indicate qua.
00:15:26Ok. Come faccio a determinare il
00:15:28maximum associato al cammino o cat?
00:15:32Lo faccio andando a considerare i costi
00:15:37uno scenario in cui i costi sono scelti
00:15:40come se l'arco fa parte del cammino.
00:15:43Prendo il costo massimo quindi suo.
00:15:47Ci considero il costo cinque suo B considero
00:15:50il costo uno suo A considero
00:15:52il costo uno che perché questi non
00:15:54sono non fanno parte del cammino poi di nuovo l'altro
00:15:57a fa parte del cammino sì.
00:15:59E quindi considero il costo più alto B,
00:16:02C e
00:16:03a B non fanno parte del cammino cioè fa parte del cammino quindi
00:16:06risolvo un problema cioè mi mi mi mi metto
00:16:11in una situazione nella quale questi sono i costi, chiaro?
00:16:15A questo punto il come lo calcolo calcolo il costo del cammino in
00:16:19questo scenario chiamato Sigma DP
00:16:21scenario DP scenario critico per P se
00:16:23volete ok e il costo è 19 va bene, d'accordo.
00:16:28Qual è il costo del cammino minimo
00:16:30Utilizzando i costi nell'ultima colonna,
00:16:33quelli nell'ultima colonna.
00:16:35Se dico bene. Non lo so.
00:16:37Posso applicare Apple e lo calcolo che qui è
00:16:40abbastanza facile capire qual è il costo del cammino minimo.
00:16:43Perché guardate, sto facendo un ragionamento combinatorio,
00:16:47cioè vedo che i costi sugli archi sono compresi tra 1 e 5,
00:16:52quindi come minimo non il cammino di costo più basso
00:16:57non può valere meno di uno.
00:16:59Siete d'accordo? Giusto? E ce ne sarebbe
00:17:05uno se ci fosse un cammino con un
00:17:06solo arco che va da o a T che costa uno.
00:17:08Qua non c'è proprio un cammino che costa uno,
00:17:10quindi uno non può essere il costo del cammino minimo vero?
00:17:15Il successivo costo qual è?
00:17:17Beh, si otterrebbe combinando due
00:17:20archi e ci sono archi che costano uno,
00:17:22quindi costo più basso sarebbe due.
00:17:25Ok, meno di due non può essere.
00:17:28Siete d'accordo Okay, Quindi siccome meno di due non può essere.
00:17:32In effetti qui trovo il cammino o BBT che è
00:17:36un cammino su questa rete che costa
00:17:37due e quello è sicuramente un cammino minimo.
00:17:40Okay, allora questi sono ragionamenti che servono per risolvere
00:17:43il problema del cammino minimo quando non avete tempo
00:17:46a disposizione o un algoritmo che per fare
00:17:49gli esercizi di fatto ma insomma non è
00:17:51essenziale bisogna risolve
00:17:53il problema del cammino minimo con uno strumento che sappiamo
00:17:56è facile risolverlo lo risolviamo quindi
00:17:58il massimo di ok è 17 19 meno due.
00:18:03Sono sicuro che in qualsiasi scenario
00:18:06la differenza tra il costo del cammino
00:18:08o c a T e l'ottimo in quello scenario sarà o 17 o di meno.
00:18:15Chiaro, va bene.
00:18:16Quindi io ho un modo facile per calcolare il massimo,
00:18:20il maximum di un qualsiasi cammino.
00:18:24Nel caso in cui l'incertezza è data
00:18:26per intervalli sui costi degli atti.
00:18:28Va bene, chiaro ci siamo.
00:18:30Per cui il problema diventerebbe questo no diventerebbe
00:18:35trova il minimo di questa differenza su ogni cammino
00:18:39dove la differenza è
00:18:40tra e e tra il costo del cammino P nello scenario critico
00:18:45per P meno il costo del cammino minimo in
00:18:47quello scenario va bene, ci siamo.
00:18:50Cosa vuol dire questo? Che è una possibile
00:18:52soluzione del problema potrebbe essere questa
00:18:54enumerare tutti i possibili cammini
00:18:57p da o a t calcolare in modo semplice il maximum regret.
00:19:02Questo maximum si chiama anche deviazione robusta in questi.
00:19:07In questo caso, deviazione robusta vuol dire
00:19:09è una deviazione dal costo minimo che robusta perché non può
00:19:14essere eh aumentata è
00:19:17la peggiore possibile e robusta in quel senso che.
00:19:20E poi c'è il cammino più asterisco cui corrisponde
00:19:23la minima deviazione robusta ripeto
00:19:25questo algoritmo che ho scritto lì
00:19:28è un algoritmo che però
00:19:29lascia il problema nell'ambito dei problemi difficili,
00:19:32perché il numero di cammini è esponenziale, come abbiamo visto.
00:19:36Va bene, quindi essendo il
00:19:37numero di cammini possibili esponenziale,
00:19:39anche se abbiamo questa proprietà che ci
00:19:41aiuta a trovare il cammino minimo,
00:19:43é robusto in senso relativo.
00:19:45Nel caso di incertezza data per intervalli.
00:19:48Però non basta per renderlo facile.
00:19:50Okay, d'accordo.
00:19:52In che cosa ci aiuta questa proprietà?
00:19:54Ci aiuta se dobbiamo confrontare un insieme
00:19:57dato di cammini che sono un insieme dato di cammini.
00:20:00È facile calcolare la deviazione robusta per ogni
00:20:02cammino e scelgo quello con la deviazione robusta più bassa.
00:20:04Okay, d'accordo.
00:20:06E alle volte capita questo nei problemi reali,
00:20:09dice Voglio il cammino minimo,
00:20:10però in realtà non voglio considerarli tutti,
00:20:12perché poi se li considero tutti,
00:20:14va a finire che non li posso fare.
00:20:16Quindi io ho già in mente una decina di cammini
00:20:18alternativi e scegli tra quelli. Va bene?
00:20:22Chiaro? Oppure, sempre nei discorsi
00:20:24che facevamo possiamo andare dal nostro committente e dire scusa,
00:20:28è un non ce la faccio a trovare
00:20:30il cammino minimo robusto
00:20:33in senso relativo perché ti serve quello in quella
00:20:35in quella applicazione che però ci sono un
00:20:39centinaio di alternative che secondo te hanno senso ma sì possiamo
00:20:43limitare a queste va bene
00:20:44se possiamo limitare te lo calcolo facilmente.
00:20:46Va bene chiaro vado avanti inoltre questa proprietà
00:20:50non entriamo nei dettagli.
00:20:51Ovviamente se qualcuno è curioso se li va
00:20:54a trovare in rete sul libro dove gli pare non ci servono.
00:20:58Si può sfruttare questa proprietà per scrivere un per scrivere un
00:21:02modello di programmazione lineare mista intera in
00:21:04cui il secondo livello si toglie,
00:21:07quindi diventa un problema che possiamo scrivere in
00:21:10ampli tranquillamente d'accordo in
00:21:12cui non c'è più il secondo livello.
00:21:13Si sfrutta quella proprietà per rendere
00:21:16il problema difficile perché rimangono le variabili intere
00:21:19ma almeno rappresentabile con un modello di quelli che conosciamo.
00:21:23Chiaro, va bene solo per.
00:21:26Così per saperlo.
00:21:28Ok, detto questo,
00:21:30adesso andiamo sul pratico.
00:21:32Facciamo qualche esercizio. Avete voglia.
00:21:35Avete carta e penna?
00:21:37Dai. Allora.
00:21:40Si consideri una rete stradale
00:21:43nella quale le macchine viaggiano di giorno,
00:21:47di notte o nelle ore di punta.
00:21:49Quindi questi sono tre scenari e i tempi
00:21:52di percorrenza sono quelli indicati nella tabellina.
00:21:55Quindi la rete è sempre la stessa B o C o B o
00:21:59A. Insomma è sempre la stessa e i costi sono nelle righe. Ci siamo?
00:22:07Allora? Ci chiede quindi facciamo un pezzo per volta,
00:22:14dalle cose facili alle cose meno facili
00:22:17Non direi difficili non o non oso dire difficili.
00:22:22Quindi adesso provo a vedere se riesco
00:22:25a trovare un angolino attraverso il quale prendere
00:22:28questa cosa e spostarla da un'altra parte.
00:22:31Non ne sono capace. Sì. Eccola qua.
00:22:34Ecco qua. Si legge appena appena.
00:22:39So che non è proprio il massimo.
00:22:40Ma riuscite a leggere il testo?
00:22:45Bene, così.
00:22:47Me lo tengo affiancato.
00:22:48Allora dobbiamo.
00:22:50C'è scritto lì. Calcolare il costo del cammino nei tre cammini
00:22:56dati in diversi scenari.
00:22:58Quindi prendiamo il cammino Hobbit.
00:23:00Fatemi sistemare in
00:23:02una tabellina perché poi ci serviranno per dopo.
00:23:04Quindi abbiamo il cammino Hobbit e vogliamo il costo
00:23:07nello scenario G giorno nello scenario.
00:23:13Notte.
00:23:17E nello scenario ore di punta che facciamo?
00:23:26Calcoliamo qual è il costo di giorno?
00:23:31Facile, no? Quindi faccio B tre.
00:23:33Più. Quindi prendo i costi nello scenario
00:23:36giorno o B più BT che è tre.
00:23:40Più. Basta, sono due archi quindi sei.
00:23:48Siete d'accordo che nello scenario notte cos'è o b che 30 più BT?
00:23:55Più 30 che fa 60 e nelle ore di punta
00:24:01è 102 più 102 che fa 204.
00:24:08Poi qual è l'altro cammino?
00:24:11O a, b c d o a B,
00:24:18C, t quindi o a e 30.
00:24:25Ne di giorno o A,
00:24:28quindi poi a, b e tre.
00:24:33Usate o A a B.
00:24:37A b e 30.
00:24:41Poi b c che 30 fatti apposta per essere tutti
00:24:4730 più CT che 30 che fa in tutto 120.
00:24:53Vero? Giusto? Sì, di
00:24:57notte se andate a guardare tutti e quattro gli archi costano
00:25:01tre che fa dodici
00:25:05e invece nelle ore di punta vediamo o ah, costa 21.
00:25:11Poi eh, o a a B costa 21.
00:25:20Costa sempre 21.
00:25:2321 piu 21 uguale 84.
00:25:29Va bene? No, ho sbagliato.
00:25:33Scusate, eh.
00:25:36Basta il fatto sbagliato. Scusami.
00:25:45É sbagliato. Ho sbagliato.
00:25:48Ho sbagliato? Va bene, Quindi facciamolo insieme.
00:25:50Scusate, riuscite a guardare che io ho qualche difficoltà
00:25:53a tenere tutto sotto controllo o a quanto costa
00:25:55o a. Questi numeri?
00:26:06Va bene o a Costa 21, vero?
00:26:10Mi aiutate o ha piu a B? Quanto costa?
00:26:1321. Più bici 21 no,
00:26:22più ct che costa 21.
00:26:28È giusto, Ho letto,
00:26:31ma sono contento che hai sbagliato tu.
00:26:33Grazie. 84 E poi l'altro cammino è ok o c a t. Cammino di giorno.
00:26:42Quanto costa?
00:26:43Allora sarebbe o C che fa 15 Cià che fa
00:26:5021 è a T
00:26:55che fa nove e la somma è 45.
00:27:01Poi invece di notte o C e nove C ha E 15.
00:27:10E T è 21 che fa 45 uguale
00:27:17e invece nelle ore di punta o ci fa 19 ci ha fa 39.
00:27:29E ti fa la bellezza
00:27:35di 55 per un totale di 113.
00:27:42Va bene, vabbè, questa era facile, giusto per scaldarci.
00:27:46Facile, Più che facile. Va bene, facile.
00:27:48Quindi? Però questo ci fa capire che ogni cammino
00:27:51ha un costo diverso nei diversi scenari.
00:27:53Ricordo benissimo domanda quale tra C1,
00:27:58C2, C3, migliore in senso assoluto rispetto a tre scenari?
00:28:02Chiaro la domanda. È una domanda di analisi decisionale
00:28:10o di ottimizzazione robusta secondo
00:28:11voi quella domanda lì o niente dei due?
00:28:20Qual è la differenza tra analisi decisionale,
00:28:23ottimizzazione robusta analisi decisionale ci dice
00:28:25che ci sono delle alternative con dei valori nei diversi
00:28:28stati di natura.
00:28:29E ci dà dei criteri per sceglierli.
00:28:32L'ottimizzazione robusta invece ci dice qual è il problema
00:28:34e ci fa trovare direttamente la soluzione ottima.
00:28:39Qui ci dice di trovare la soluzione ottima di
00:28:41trovare la migliore tra alcune date.
00:28:43La migliore ad alcune date.
00:28:45Si tratta di analisi decisionale e
00:28:47chiede la robusta in senso assoluto.
00:28:49Noi per robustezza in senso assoluto abbiamo inteso il
00:28:52criterio del min max min max
00:28:54in questo caso vero?
00:28:56Quindi come facciamo a risolvere questo problema andando
00:29:00a valorizzare ciascuna alternativa in
00:29:03EH o con un valore Che dipende dagli stati di natura,
00:29:10in questo caso con il costo peggiore con il
00:29:13caso peggiore vero min max?
00:29:15Giusto? Quindi andiamo a calcolare il max dell'alternativa.
00:29:20Il massimo dell'alternativa data è per out 204.
00:29:25Vero però a b CT 84.
00:29:30No, scusate e 120 non 84 120 perché vince G. Caso peggiore per
00:29:37lui però è il caso peggiore è le ore di punta e vale 113.
00:29:45Ok, d'accordo.
00:29:49Quindi qual è?
00:29:50Come rispondiamo alla domanda due?
00:29:52Il min max corrisponde a out due min max?
00:30:00Ok, va bene, quindi se voglio.
00:30:05Avere il cammino minimo.
00:30:07Nel caso peggiore scelgo Cat.
00:30:10Okay, perché è quello che è,
00:30:13Nel caso peggiore mi dà il costo più basso.
00:30:16Se scegliessi o A, B,
00:30:17C ti andrebbe meglio nelle ore di punta,
00:30:20però di giorno andrebbe peggio e peggio di quanto non vada o,
00:30:24nel caso peggiore. Chiaro, no?
00:30:26Vabbè, insomma, sto girando per essere sicuro che ci siamo.
00:30:29Quindi abbiamo risolto un problema di analisi
00:30:31decisionale col criterio del min max.
00:30:36Va bene. Andiamo al punto tre.
00:30:41Attenzione il punto tre dice soltanto è possibile calcolare in
00:30:46tempo polinomiale il cammino minimo robusto
00:30:49in senso assoluto rispetto ai tre scenari.
00:30:52Okay. Quindi prima abbiamo detto di
00:30:54queste tre alternative qual è la migliore?
00:30:56Ed è stato facile determinare qual era la migliore tra le tre.
00:30:59La domanda è posso capire qual
00:31:02è il cammino migliore in assoluto in senso robusto.
00:31:07Qual è il cammino?
00:31:09Ottimo, robusto in senso assoluto,
00:31:13Non tra quei tre.
00:31:14Tra tutti i possibili cammini.
00:31:16Quale problema dobbiamo risolvere?
00:31:18Il problema del cammino minimo,
00:31:20Robusto in senso assoluto?
00:31:21E questo problema è facile o è difficile?
00:31:24Perché quello vuol dire che
00:31:26è possibile calcolare in tempo polinomiale.
00:31:27Se fosse possibile calcolare in
00:31:28tempo polinomiale vuol dire problema è facile.
00:31:30Se non è possibile, il problema è difficile e quindi
00:31:34è possibile calcolare il problema in tempo polinomiale è facile.
00:31:38È difficile risolvere il problema del cammino minimo robusto
00:31:40in senso assoluto,
00:31:42quindi con criterio Minimax e come sono rappresentate?
00:31:47Come è rappresentata quell'incertezza?
00:31:49L'incertezza è rappresentata per scenari.
00:31:52Vero è il caso,
00:31:53è un caso facile, è un caso difficile.
00:31:56Vi ricordate ancora no io mi ricordo ed è
00:32:01un caso difficile
00:32:02no ricordate che qui avevamo detto perché è difficile perché
00:32:06se io ho il problema del cammino minimo robusto
00:32:08in senso assoluto per
00:32:10scenari devo risolvere quel problema
00:32:12lì che vedete proiettato vi ricordate.
00:32:16E quel problema voleva dire avere un problema di
00:32:17cammino minimo con dei vincoli aggiuntivi che mi
00:32:19spaccavano tutto e quello era
00:32:22un indice che era un problema difficile.
00:32:23E infatti abbiamo poi qualcuno lo ha studiato
00:32:26meglio ha detto sì effettivamente è difficile che quindi
00:32:29è difficile d'accordo quindi
00:32:32è possibile la risposta è no perché il problema è difficile.
00:32:38E voglio dire se uno vuole dare una risposta
00:32:40più completa magari si rifà un po al modello, se se lo ricorda.
00:32:44Insomma, poi ci sono vari livelli di risposta no?
00:32:47Dal livello è un problema?
00:32:50No, perché è un problema difficile
00:32:52in quanto il problema di questo è
00:32:53difficile a dire anche una abbozzare
00:32:57il perché e il perché ha a che
00:32:59fare con quel modello e col fatto che quel
00:33:00modello Diciamo ci porta
00:33:03a pensare che non sia possibile risolverlo facilmente.
00:33:06Okay, per curiosità io avevo.
00:33:15Scritto il modello.
00:33:18No. Avevamo visto come scriverlo in ampli.
00:33:21Il modello è questo qua. Vedete che le variabili binarie.
00:33:25Siccome devo fare un max introduco una variabile
00:33:28aggiuntiva y che mi dice che
00:33:29y deve essere maggiore o uguale
00:33:31del costo in ogni scenario e sono tre.
00:33:35Va bene, si capisce il modello che sto mostrando.
00:33:39Il modello che sto mostrando è esattamente questo qui.
00:33:48Dove sta questo?
00:33:50Okay, quindi sto minimizzando una y
00:33:55dove y è maggiore o uguale del costo in ogni scenario.
00:33:59E poi ci sono i vincoli di
00:34:00flusso che mi dicono le X devono determinare un cammino che.
00:34:04E se lo risolve questo problema dovrei riuscire
00:34:07a farcela senza sforare troppo,
00:34:09però mi devo mettere nella parte giusta.
00:34:13Ottimizzazione robusta modelli se lo faccio
00:34:17in tutti ce l'avete tutti questi modelli qua se volete confrontarli
00:34:21include eh dovevo fare
00:34:24qua cammino minimo robusto in senso assoluto 1.3 punto run.
00:34:33E se risolvo sto problema vedete che viene fuori come
00:34:36cammino o CCT che costa 45
00:34:42nel caso peggiore quindi esiste un cammino che
00:34:46migliore di quei tre nel senso
00:34:48che il cammino minimo robusto in senso assoluto.
00:34:51Okay chiaramente se ho qui giusto per rinfrescare un po.
00:34:57Questo problema è difficile non perché sto facendo quello che fa,
00:35:02ma un indice del fatto che il problema è difficile.
00:35:04Il fatto che se io faccio option relax integrali quindi non lo
00:35:10considero più un problema di programmazione binaria intera ma ma
00:35:14uno ma lo considero un problema facile da risolvere.
00:35:19Non risolvo niente perché le variabili rimangono frazionarie e
00:35:24quindi devo andare.
00:35:26Il fatto che rimangono frazionarie cosa vuol dire
00:35:28che tu hai un'idea di quale può essere la soluzione,
00:35:30ma poi devi cominciare a capire se una variabile
00:35:32è meglio metterla A0O1 quella che vale zero due,
00:35:35quella che vale zero nove.
00:35:36Quindi vedete che comincio a fare
00:35:37un'esplorazione combinatoria dello spazio di ricerca.
00:35:41Mi porta a potenziali tempi molto alti per la soluzione.
00:35:44Chiaro? Bene, siamo.
00:35:46Questo è il bound per chi lo ha sentito nominare.
00:35:50Va bene, questo è. Adesso andiamo al numero quattro ultimo.
00:36:00Adesso secondo me vi rispondete voi mettiamoci
00:36:04in questa situazione quindi cambiamo,
00:36:07cambiamo situazione e consideriamo per ogni arco
00:36:10i due costi CJ min che è il minimo tra
00:36:15tutti i costi nelle e nei diversi scenari e CJ imax CJ più che il
00:36:22massimo tra tutti i costi
00:36:24ok. Quindi per ogni arco abbiamo un minimo massimo e rispetto
00:36:30a questi intervalli di variabilità si
00:36:32calcoli un cammino minimo robusto in senso assoluto.
00:36:41Riusciamo a farlo?
00:36:43Tanto per cominciare,
00:36:45sì o no è facile o è difficile farlo?
00:36:54Quindi esserci
00:36:56messi nel punto quattro vuol dire che vogliamo trovare
00:36:59il cammino minimo, robusto in senso assoluto.
00:37:01Giusto? In quale caso?
00:37:04Come è rappresentata l'incertezza?
00:37:06L'incertezza è rappresentata mediante intervalli e
00:37:09in quel caso era facile o difficile?
00:37:11Se ricordate diventava facile?
00:37:13No, diventava facile perché avevamo visto che la definizione del
00:37:17problema ci portava a risolvere un problema nominale con
00:37:21i costi più alti nell'intervallo.
00:37:23Quindi diventava un problema di cammino minimo, normale, facile,
00:37:26a patto di sostituire,
00:37:29di considerare come costi per ogni arco il valore più alto.
00:37:33Okay, quindi di fatto si tratta di risolvere il problema
00:37:38mettendo un problema di cammino
00:37:40minimo con costi sugli archi pari a CJ.
00:37:44I++. Va bene.
00:37:45Chiaro? Quindi così si risponde già là alla domanda.
00:37:48Poi se voi avete un po'lo risolvete il problema con Apple.
00:37:51Se avete un algoritmo lo risolvete con l'algoritmo ok. Oppure,
00:37:56se si può risolvere con ragionamenti combinatori
00:37:59come abbiamo fatto prima loro risolviamo.
00:38:01Okay, però diciamo che l'esercizio il 90% del punto
00:38:04l'ottanta per 100 del punto è già fatto dicendo lo risolvo come
00:38:09problema di cammino minimo considerando come costi
00:38:13per gli archi x J più
00:38:15chiaro è questo
00:38:16se poi spiegate anche il perché perché il problema sarebbe
00:38:19questo in questo modello che però
00:38:21è facile risolvere in questo modo.
00:38:23Bene ci siamo. Perfetto, allora o lo facciamo con Apple?
00:38:28D'accordo, io l'ho fatto con Apple eh,
00:38:33Non so se vale la pena, ma insomma.
00:38:34Sì, va bene, dai, facciamolo con Apple.
00:38:38E quindi qua il modello l'ho implementato
00:38:42nel modello 1.4. Eccolo qui.
00:38:45Vedete che questo è un modello di cammino minimo standard
00:38:48nel quale ci sono solo i vincoli di bilanciamento e ho scelto
00:38:52per ogni arco l'intervallo il
00:38:56limite superiore dell'intervallo 30 per x a 102 per x BT.
00:39:01Vedete, ho preso 30 102 per x BT che così come dovrei fare?
00:39:07Se risolvo questo modello?
00:39:09Ovviamente posso lasciare opzioni
00:39:13relax integrale di uno perché tanto anche
00:39:16se sono sicuro in questo caso il problema
00:39:19è proprio il problema del cammino minimo
00:39:20standard senza altri vincoli,
00:39:22quindi sicuramente anche con quel relax integrale t1 otterrò.
00:39:27Eh scusate perché sto usando questo che non c'entra niente,
00:39:31che qua non sono definiti questi e quindi.
00:39:37Se risolvo quel problema li
00:39:39vedete che viene tutto intero tranquillo
00:39:40con lo con cammino minimo che costa 49.
00:39:44Va bene ok ci siamo.
00:39:48Risolto il problema e se questo problema mi capita l'esame
00:39:53e non ho ampolla
00:39:54a disposizione come non ce l'avete? Come lo risolvo?
00:39:57Proviamo a vedere se riusciamo a risolverlo in modo combinatorio.
00:40:00Ok, facciamo gli stessi ragionamenti di prima
00:40:05quindi sappiamo che i costi okay,
00:40:09che il allargo un pochino qua,
00:40:12i costi da considerare sugli archi.
00:40:20I costi da considerare sugli archi sono quelli evidenziati qui.
00:40:2719 qua 102 qua 30 30 102 55 30 30 39 però
00:40:37quindi la rete è
00:40:41questa qui che devo fare dei cammini su questa rete ma
00:40:46comunque Me lo dice anche i nomi degli archi no o
00:40:50C o C. Per esempio gli archi o C e BT mi determinano un cammino.
00:40:57No che non sono un cammino o c e c t. Sì, vero?
00:41:03Ok, quindi con questi costi
00:41:05qual è il più basso dei costi possibili?
00:41:08È di 19.
00:41:09Vero? Quindi non esistono cammini di costo più basso di 19,
00:41:14quindi il cammino minimo come minimo costa 19.
00:41:17Esiste un cammino che costa 19?
00:41:19No, perché dovrebbe essere un cammino
00:41:21fatto da un solo arco che va da O a T.
00:41:25Vero che non è cammino da o a T.
00:41:28Costa in questa rete non c'è proprio, non esiste.
00:41:32Ok, quindi mi servono almeno due archi.
00:41:35Giusto? Qual è il costo di un.
00:41:38Vedete che non sto guardando grafo
00:41:39niente solo facendo ragionamenti.
00:41:41Qual è il costo di un cammino minimo?
00:41:43Cioè scusate qual è il costo più basso possibile
00:41:47per un cammino con due archi.
00:41:49Se prendi due archi che costano meno sono 19:30.
00:41:56Vero quella rete, quindi se c'è
00:41:59un cammino a due archi non può costare meno di 49.
00:42:02Okay, esiste un cammino che costa 49.
00:42:05Con due archi vediamo sicuramente dovrà contenere o c che 19.
00:42:10E se io faccio C e CT il costo è proprio 49.
00:42:15Quindi o CCT è un cammino minimo,
00:42:18non possono esistere cammini più a costo minore di quello chiaro?
00:42:24E quindi anche con questi ragionamenti combinatori ci sono in
00:42:27grado in grado di trovare la soluzione ottima.
00:42:31Ci siamo? Sì o no? Va bene.
00:42:38A parte la parte 19 del 40, l'ho capita bene,
00:42:42nel senso che Si sta calcolando un cammino per
00:42:46andare da o atti come no.
00:42:51Però la parte precedente ha detto quella che ha detto
00:42:55che la dà o non si può dare direttamente quello ok.
00:42:59E quindi qual è. Nel punto
00:43:01quattro che cosa succede come faccio a calcolarlo io
00:43:04so che i cammini gli archi costano 19.
00:43:08Gli archi costano di meno costano 19.
00:43:11Gli archi il secondo arco che costa di meno costa 30.
00:43:15Il terzo arco costa di meno.
00:43:17Non lo so quant'è costa più di tre.
00:43:19Okay, d'accordo.
00:43:21Quindi se esistono cammini non possono costare meno di 19,
00:43:25ma un cammino che costa 19 dovrebbe essere fatto da un solo.
00:43:28Ma non esistono archi cammini con un solo arco
00:43:30quindi 19 non è possibile.
00:43:33Quindi vuol dire che per ottenere
00:43:35un cammino devo combinare almeno due costi.
00:43:39Okay, è il cammino più piccolo possibile.
00:43:42Combina i costi più bassi possibili.
00:43:44Il primo è 19, il secondo costo è 30.
00:43:47Quindi non esistono cammini di costo più basso di 49.
00:43:51Non so ancora se esiste un cammino che costa 49.
00:43:53Okay, ma se esistesse sarebbe minimo.
00:43:57E questo esiste perché se io prendo questo e questo o
00:44:02CCT è un cammino da Wat che costa 49 minimo, Va bene?
00:44:06Perfetto. Io farei ancora qualche esercizio, Va bene.
00:44:12Eh sì, dai facciamoli e così poi faremo solo una una una sessione,
00:44:21faremo anche altri esercizi, vedremo.
00:44:23Non proprio un giorno di esercizi soltanto.
00:44:25Però vediamo un po avanti con gli esercizi.
00:44:28Va bene, allora vediamo quest'altro.
00:44:34In una rete stradale il tempo di
00:44:37attraversamento di ciascun arco va da un minimo un massimo,
00:44:40come riportato nella seguente tabella.
00:44:43Va bene, quindi quando non ci serve
00:44:44il grafo abbiamo sappiamo che possiamo andare da ogni da ogni
00:44:48nodo a ogni altro nodo B CT insomma A,
00:44:51B CT sono i nodi ok e i costi sono quelli riportati.
00:45:00Domanda i costi sono certi o incerti? Sono incerti?
00:45:05Abbiamo una rappresentazione della
00:45:07dell'incertezza sia per intervalli,
00:45:09quindi abbiamo costi incerti rappresentati per intervalli.
00:45:14Si determini un cammino minimo per andare dal nodo
00:45:17al nodo T secondo il criterio della robustezza
00:45:20in senso assoluto che va bene,
00:45:24posso metterlo piccolo? Va bene.
00:45:50Quindi domanda prima cosa da
00:45:55fare è un è un problema di ottimizzazione robusta quindi
00:45:59se mi sta chiedendo di determinare un cammino vuol dire
00:46:02che devo prima essere sicuro che lo
00:46:03posso fare perché se il problema
00:46:05è difficile non è che io sono tanto
00:46:07bravo che mi metto lì e lo determini no.
00:46:10Quindi se lo posso fare devo dire prima se lo posso fare si può
00:46:13fare sì un problema facile
00:46:15perché di nuovo un cammino minimo robusto
00:46:16in senso assoluto con costi per intervalli
00:46:19vale quello che abbiamo detto prima quindi
00:46:20dobbiamo risolvere un problema del cammino
00:46:22minimo con quali costi degli archi li metto in una tabella?
00:46:28Riporto la tabella e faccio capire che ho capito cosa devo fare,
00:46:32cioè devo risolvere il problema del cammino minimo considerando
00:46:35i seguenti costi.
00:46:36Quindi metto S a b,
00:46:38c. Qua metto a b c t. Quali costi devo considerare?
00:46:45Qual è il costo per andare da essa?
00:46:47Nel problema che voglio risolvere, quindi,
00:46:49cammino minimo in senso assoluto, eh.
00:46:52Costi incerti su intervalli trovo
00:46:56il cammino minimo assoluto risolvendo un problema nominale,
00:46:59un problema con i
00:47:00numeri dati e i numeri li scelgo
00:47:02come estremi superiori dell'intervallo,
00:47:04quindi devo considerare 36 il costo cinque sette nove otto.
00:47:10Qua non c'è arco nove nove sette sette
00:47:15non c'è arco nove cinque due nove non c'è arco.
00:47:20Sei Sei d'accordo che questi sono i costi da considerare?
00:47:24Quindi o uso le faccio quello che devo fare oppure
00:47:27vediamo se riesco a farlo in modo combinatorio.
00:47:32Per me l'esercizio diciamo che già non dico
00:47:35fatto Però capisco che avete capito come si fa.
00:47:40D'accordo. Poi insomma, se riusciamo anche
00:47:43a fare dei ragionamenti ancora meglio e ragionamenti quali sono?
00:47:46Di nuovo voglio trovare un cammino da S a T, vero?
00:47:52Come posso fare con i soliti ragionamenti quali sono i costi qua?
00:47:56Qua c'è il costo che è più basso e due, vero?
00:47:59Poi ci sono dei costi che valgono cinque.
00:48:03Ok, poi gli altri costi valgono sette, 09:07.
00:48:09No, c'è anche un sei e mezzo sei sette, otto.
00:48:13Questi sono i costi in gioco. Va bene.
00:48:16Quindi col ragionamento che abbiamo fatto prima cosa diciamo?
00:48:19Posso andare da s t a costo due?
00:48:22Cosa vorrebbe dire avere un solo arco da S a T che costa due?
00:48:25Non è possibile quindi due
00:48:27Non esistono cammini di costo due. Va bene?
00:48:32Chiaro? La seconda possibilità qual è?
00:48:36La seconda possibilità
00:48:37è quella di dire se esiste un cammino di costo cinque,
00:48:41ma non è possibile.
00:48:43Noi sappiamo che il cammino con un
00:48:45arco solo costa come minimo otto.
00:48:46Vero? Quindi ci servono almeno
00:48:50due archi per avere un costo più basso di otto,
00:48:54quindi una prima possibilità di cammino sarebbe
00:48:57ST. Che costa otto va bene con un arco solo.
00:49:03Con due archi se apriamo ad usare due archi,
00:49:06quale potrebbe essere il cammino che.
00:49:08Quanto costa?
00:49:10Può costare due più cinque?
00:49:12C'è un cammino che costa sette da S a T. Beh,
00:49:16per costare sette dovrei andare in A per per tenere il cinque e SA,
00:49:21ma poi una volta che sono in A.
00:49:22Se faccio a T e cinque più dodici?
00:49:24Vero? Sei d'accordo?
00:49:30Okay, Non è possibile.
00:49:34Sicuramente abbiamo detto non esistono archi di costo
00:49:37sei e cammini di costo sei perché dovrebbe
00:49:40essere un solo arco ma non è possibile.
00:49:42Ok, a questo punto mi chiedo se mi
00:49:46chiedo se esistono archi di costo sette va bene.
00:49:50Di costo sette per avere anche di costo sette devo prendere o s
00:49:55a per prendere il cinque ma abbiamo visto che
00:49:57poi a ti costa troppo oppure
00:50:00posso fare sc sc costa due e
00:50:03poi scusate esso no C no scusate cosa sto dicendo?
00:50:10E sa costa?
00:50:16Ok. E niente, non ce la faccio lo stesso.
00:50:19No, non non riesco a combinare due archi
00:50:23a costo sette perché cinque due non con l'arco XA e l'arco CA.
00:50:29Non faccio sicuramente un cammino da S a T. Va bene, okay?
00:50:33Quindi neanche a sette.
00:50:34Esistono cammini che costano
00:50:36sette cammini che costano otto esistono?
00:50:39Sì, lo abbiamo già visto ed è questo quindi
00:50:42questo è un cammino minimo perché non
00:50:44esistono cammini di costo più basso di di di eh di 08:08.
00:50:50È un cammino va bene quindi questo
00:50:52è il cammino minimo fatto da un so
00:50:54va bene poi voglio dire l'abbiamo fatta
00:50:57lunga però uno lì lo vede abbastanza in fretta che cammino minimo.
00:51:00Va bene ci siamo comunque ripeto questi ragionamenti
00:51:05diciamo che sono apprezzati ma l'essenziale
00:51:10è andare a capire quale problema di
00:51:12cammino minimo dobbiamo risolvere.
00:51:14Forza forza che se no questo è uno.
00:51:22Andiamo al punto due possiamo Punto due Attenzione.
00:51:31Supponendo che gli unici cammini possibili
00:51:35da s a T possibili vuol dire.
00:51:37Gli unici cammini che ci interessano. Gli unici cammini.
00:51:39Gli unici cammini ammessi nel problema che stiamo
00:51:42risolvendo siano P1 e se
00:51:45ABCD oppure P2 s cb a T.
00:51:49Quale dei due è più conveniente e robusto in senso relativo?
00:51:54Possiamo risolvere questo problema?
00:51:58Beh, abbiamo detto di sì,
00:51:59perché uno dobbiamo risolvere un problema di cammino
00:52:02minimo in senso relativo,
00:52:03con incertezza data per intervalli,
00:52:06e noi sappiamo che dato un cammino,
00:52:10dato una soluzione, è facile derivare la deviazione robusta.
00:52:15Quindi deriviamo la deviazione robusta,
00:52:18il maximum regret per ogni per
00:52:21ciascuno dei cammini da analizzare e scegliamo il migliore chiaro.
00:52:26E per derivare il massimo sfruttiamo la proprietà,
00:52:30per cui il maximum si calcola facendo
00:52:33riferimento a uno scenario fatto in un certo modo.
00:52:36Okay, d'accordo.
00:52:38Quindi per il cammino P1 come faccio a calcolare il maximum right?
00:52:46E se a, B, C,
00:52:47t o il max regret?
00:52:52In nello scenario sigma di P1 che è fatto come.
00:52:57Qual è la tabellina dello scenario critico per P1?
00:53:01Ricordate, devo considerare il costo più alto
00:53:05per gli archi che fanno parte del cammino?
00:53:07Il costo più basso per tutti gli altri che.
00:53:09Quindi mi rifaccio la tabellina.
00:53:11E se A, B, C e poi a b ct?
00:53:17Qua mi scrivo sigma di P1 per dire che questi sono
00:53:20i costi nello scenario sigma di P uno scenario critico per P1.
00:53:24Essa fa parte del cammino sul quale voglio considerare il maximum.
00:53:28Sì, quindi considero questo cinque SB non fa parte,
00:53:32quindi considero costo più basso tre
00:53:35SC neanche costo 07:07 neanche costo due.
00:53:40Poi questo non c'è A a B fa parte del cammino.
00:53:45Sì, quindi considero il costo più alto costo nove
00:53:48che poi a C non fa parte.
00:53:52Considero uno come costo a T non fa parte considero. No A.
00:54:04A T non fa parte considero uno perché ho scritto sette,
00:54:09quindi scusate uno.
00:54:11Ok, va bene.
00:54:12Poi B a fa parte del cammino che sto considerando.
00:54:18No, perché A, B e B sono anche diversi, Okay.
00:54:22Chiaro? Quindi non fa parte,
00:54:26per cui considero il costo più basso sei BB non c'è BC fa parte,
00:54:31quindi costo nove BT non fa parte costo cinque
00:54:36CIA non fa parte costo uno CB non fa parte costo
00:54:41sei cc non c'è CT fa parte costo
00:54:45sei ok quindi questo è lo
00:54:48scenario da considerare a questo punto Calcolo.
00:54:51Come faccio a calcolare la deviazione robusta?
00:54:57O il maximum di P1?
00:55:01Devo calcolare il costo nello scenario sigma di P1?
00:55:06Di P1, vero?
00:55:09E qual è il costo è 09:05 più
00:55:14nove Più nove più sei che fa la bellezza di 29.
00:55:19Vero?
00:55:20E poi devo calcolare il costo del cammino
00:55:24minimo nello scenario sigma
00:55:26di P1 e qual è
00:55:29il costo del cammino Cammino minimo nello scenario sigma
00:55:32di P1 o ampolle e metto i costi di quella tabella.
00:55:36Okay, e lo calcolo facilmente
00:55:40oppure di nuovo cerchiamo di fare dei ragionamenti combinatori.
00:55:43Va bene, cerco di fargli un po più in fretta,
00:55:46D'accordo, vediamo se arriviamo.
00:55:48Quindi il costo più basso possibile sarebbe uno,
00:55:51ma non è possibile perché ci vorrebbe
00:55:53un solo arco e quindi uno non c'è.
00:55:55Uno non è un costo ammesso
00:55:57per un cammino in questa rete da St. Vero?
00:56:00Due Un costo ammesso?
00:56:02Sì, ed è ST. Quindi il costo del cammino minimo in
00:56:06questa rete è due cammino ST diretto bene
00:56:10quello è il costo del cammino minimo.
00:56:12Quindi qual è il maximum di P1 o deviazione robusta?
00:56:17È uguale a 29 meno due che fa 27.
00:56:22D'accordo, Chiaro. Ci siamo.
00:56:24Benissimo. Posso fare lo stesso ragionamento per P2?
00:56:30Tanto io devo confrontare P1 e P2.
00:56:32Quindi P2 che è uguale a sc b a t s
00:56:38cb a t e il maximum
00:56:41right lo calcolo con riferimento allo scenario sigma P2?
00:56:47Cosa c'è Sigma P2?
00:56:49Vediamo un po, eh. Quindi cominciamo.
00:56:52Qua ci sarà s a,
00:56:54b, C. Qui ci sarà.
00:56:57A b, c, t. Quindi essa fa parte del cammino che voglio analizzare.
00:57:03No. Quindi metto il più basso.
00:57:06Due SB Fa parte del cammino.
00:57:09No. Quindi metto tre.
00:57:13Poi SC fa parte del cammino.
00:57:15Sì, quindi metto nove ST. fa parte del cammino no.
00:57:20Quindi metto due poi A non c'è
00:57:24a B fa parte del cammino no e
00:57:26quindi metto tre a C fa parte del cammino no.
00:57:30Quindi metto uno A fa parte del cammino Sì, quindi metto sette.
00:57:37B A fa parte del cammino?
00:57:39Sì. Quindi devo mettere il più grande
00:57:41sette B B Non c'è B C fa parte del cammino, no?
00:57:47Quindi metto il più basso che
00:57:48è otto bit fa parte del cammino no e metto
00:57:53cinque cha fa parte del cammino no e
00:57:58quindi metto uno C B fa parte del cammino Sì.
00:58:03E quindi metto nove.
00:58:07C c non c'è CT non fa parte del cammino.
00:58:11Metto due va bene,
00:58:13quindi devo.
00:58:14Cosa devo calcolare?
00:58:16Calcolo il costo del nello scenario sigma di P due del cammino
00:58:21P2 è uguale a nove più sette più sette più
00:58:26nove che fa la bellezza di 32,
00:58:30mentre il costo ottimale.
00:58:33In questo scenario nello scenario Sigma DP due.
00:58:36A che cosa è uguale?
00:58:38È facile vedere che di nuovo due è vero,
00:58:40perché non può essere uno ed è sempre due.
00:58:42Col cammino e sette ci siamo.
00:58:44Ok? Quindi qual è la deviazione robusta Maximum di P2 è uguale
00:58:51a 32 meno due che fa 30?
00:58:55Ok, siamo in grado di rispondere
00:58:58con questi semplici calcoli alla domanda?
00:59:01Due Qual è il miglior cammino
00:59:03minimo robusto in senso relativo tra P1 e P2?
00:59:11P1. È meglio perché corrisponde alla deviazione robusta più bassa
00:59:19è quello che ci farà pentire di meno nel caso peggiore.
00:59:22Va bene, ci siamo?
00:59:24Facile, no? Domanda numero tre.
00:59:31È facile capire se esistono cammini migliori e robusti
00:59:35in senso relativo.
00:59:40Quindi noi tra questi due
00:59:42sappiamo scegliere facilmente chi è il migliore.
00:59:45Ma se io dicessi esistono cammini migliori di più uno
00:59:50In senso che siano robusti in senso relativo, cosa dovrei fare?
00:59:55Dovrei calcolare il miglior cammino robusto in
00:59:57senso relativo e vedere
01:00:00se è migliore sotto quell'aspetto di più uno.
01:00:03Ma come faccio a calcolare miglior cammino robusto
01:00:05in senso relativo?
01:00:06E dovrei considerare tutte
01:00:08le alternative e valutarle con la deviazione robusta,
01:00:10eccetera eccetera. È un problema difficile.
01:00:13Non è facile perché è difficile trovare il cammino minimo,
01:00:16robusto in senso relativo,
01:00:18anche con la incertezza per intervalli.
01:00:21Chiaro? La risposta sta se
01:00:24volete e nella slide che abbiamo visto poco fa in questa slide qua.
01:00:34Okay. Okay, è comunque un problema
01:00:44difficile che rimane difficile
01:00:47ecco perché bisognerebbe considerare.
01:00:50Abbiamo già detto va bene è
01:00:51chiaro allora vedete che quello che a me
01:00:53serve non che a me serve
01:00:56quello che riusciamo a fare in questo corso non è tanto
01:00:59darvi strumenti operativi di risoluzione di problemi
01:01:04quanto ed è quello che è richiesto
01:01:07sensibilità nel capire quali
01:01:09sono le possibilità quali sono i problemi
01:01:11che potete impostare e quanto è facile o difficile risolverli.
01:01:16Va bene, chiaro? Ci siamo.
01:01:19Bene, poi come si risolvono
01:01:22questi problemi sapremo una mezz'oretta di
01:01:24tempo un'idea la da Roma che
01:01:26magari qualcuno che sa qualcosa di ma insomma vedremo vedremo.
01:01:30Senza senza ansia va bene vado avanti basta questa parte basta e
01:01:37adesso abbiamo chiuso l'ottimizzazione
01:01:40robusta e direi che possiamo passare
01:01:46all'altro l'altra sezione di questo capitolo che
01:01:50è la programmazione stocastica che.
01:01:57Posso andare ci son domande
01:01:59vado avanti allora vi ricordate cosa abbiamo detto
01:02:03noi vogliamo dato un problema in cui c'è
01:02:06incertezza vogliamo trovare la migliore soluzione a quel problema.
01:02:13L'analisi decisionale ci diceva ti do strumenti per
01:02:17confrontare diverse soluzioni date
01:02:21tra loro con dei criteri di robustezza o di ottimalità.
01:02:25Adesso vogliamo trovare la migliore soluzione.
01:02:28Abbiamo parlato di robustezza quando prescindiamo dalle
01:02:31EMH distribuzioni di probabilità.
01:02:34Adesso invece consideriamo l'incertezza con informazione di natura
01:02:40probabilistica che quindi cerchiamo di sfruttare se ce l'abbiamo,
01:02:45la conoscenza su distribuzioni di probabilità associate
01:02:48ai parametri incerti.
01:02:49Bene, quindi quando parliamo di robustezza di soluzioni robuste,
01:02:52vedete che non abbiamo mai parlato di probabilità.
01:02:55Tutti gli scenari hanno la stessa
01:02:58dignità e vengono trattati allo stesso modo dai criteri.
01:03:01Ok. Qui invece c'è una
01:03:03probabilità associata agli scenari o comunque ai
01:03:07parametri Stocastici associata una distribuzione di probabilità.
01:03:12Quindi parliamo di ottimizzazione stocastica e, come abbiamo detto,
01:03:15ci concentreremo sulla programmazione stocastica perché
01:03:19considereremo problemi di ottimizzazione andandoli
01:03:26a rappresentare con modelli di
01:03:27programmazione matematica, quindi programmazione stocastica.
01:03:30Abbiamo già visto degli esempi in questo senso, vero?
01:03:33Vi ricordate giusto Contadino?
01:03:36Avevamo visto incertezza nella funzione obiettivo,
01:03:40quindi la situazione è sempre la stessa.
01:03:42Avete un problema?
01:03:44Possiamo anche adesso pensare
01:03:45a un modello di programmazione matematica che ha i suoi parametri.
01:03:48Ok, le variabili decisionali,
01:03:50i parametri e i
01:03:52parametri sono della funzione obiettivo dei vincoli.
01:03:55Possiamo avere incertezza nella funzione
01:03:58obiettivo e l'incertezza era data come tre scenari,
01:04:02ciascuno con la sua probabilità e quindi
01:04:05avevamo detto ad esempio vogliamo trovare
01:04:07la soluzione che massimizza il valor medio,
01:04:10ma li il valor medio si poteva calcolare che andando
01:04:13a dire la resa in
01:04:15ogni scenario pesata dà la probabilità dello scenario.
01:04:18Avevamo trovato un modello di programmazione
01:04:20lineare che ci risolveva il problema.
01:04:23L'altra situazione è quella in cui avevamo visto un caso in cui la.
01:04:27L'incertezza stava nei vincoli,
01:04:30quindi l'incertezza è nella regione ammissibile.
01:04:33E lì era stato un po più delicato se vi ricordate
01:04:35no perché che cosa vuol dire probabilità associata ai vincoli.
01:04:40L'idea era quella di dire.
01:04:42La probabilità che i vincoli siano soddisfatti deve
01:04:45essere maggiore o uguale di un certo valore di una certa soglia.
01:04:48No. Quindi c'era un certo un certo livello
01:04:50di protezione della nostra
01:04:52soluzione in termini probabilistici che quindi è lì.
01:04:57Avevamo trovato un modo sfruttando le
01:05:00abilità modellistiche del qui presente
01:05:03ricercatore operativo che era riuscito.
01:05:05Vabbè, insomma, diciamo con un po di dimestichezza con i modelli.
01:05:10In quel caso si era riusciti
01:05:11a fare un modello di
01:05:12programmazione matematica chiuso che dava la eh.
01:05:17Che che che riusciva a formulare l'idea
01:05:20probabilità che questi vincoli siano
01:05:22rispettati maggiore o uguale di una somma.
01:05:24Okay va bene non sempre sarà possibile però in
01:05:27quel caso ce l'avevamo fatta quindi questi
01:05:29sono il tipo di problemi che vogliamo considerare.
01:05:32Cerchiamo di generalizzare un po.
01:05:34Okay, quindi consideriamo
01:05:36un modello di programmazione stocastica definito da.
01:05:39Che da che cosa?
01:05:40Definito? Dal fatto che i parametri sono realizzati in
01:05:45conseguenza della realizzazione di un
01:05:47evento aleatorio Omega che in uno spazio continuo o discreto,
01:05:51tanto per noi, diciamo che i
01:05:53ragionamenti riterremo sempre abbastanza generale.
01:05:56Quindi il modello è del tipo minimizzare una certa funzione
01:06:02obiettivo è la funzione obiettivo dipende
01:06:04dal valore delle x le variabili decisionali,
01:06:07ma anche dal valore ovviamente dei parametri che
01:06:10a loro volta dipendono dalla realizzazione di Omega.
01:06:13Okay, va bene.
01:06:15Dall'evento Omega che si realizza.
01:06:18Ok, va bene.
01:06:19I vincoli saranno del tipo una certa funzione di X e
01:06:25dei parametri che però dipendono anche da Omega.
01:06:29Deve essere confrontata con un valore.
01:06:32Anch'esso potrebbe essere stocastico e quindi
01:06:36distribuito a seconda dell'evento omega che.
01:06:40E poi ci sono dei vincoli altri vincoli che non dipendono
01:06:44dalla dal dal dall'evento
01:06:48aleatorio e
01:06:50sono dei vincoli che chiameremo deterministici che quindi
01:06:54se volete qui nell'esempio del contadino noi avevamo dei
01:06:58vincoli deterministici se Excel è minore uguale
01:07:00di 70 era un vincolo deterministico perché
01:07:0470 era un numero che non cambiava mai.
01:07:07Sette non cambiava mai era lo stesso
01:07:09in tutti gli scenari, se volete.
01:07:10Ok quindi abbiamo dei vincoli deterministici che non cambiano
01:07:17al variare della realizzazione della variabile
01:07:20stocastica KEE e dei vincoli invece stocastici che la cui EMH,
01:07:25la cui formulazione cambia,
01:07:27cioè il cui valore,
01:07:29il cui valore di verità, anche se volete,
01:07:31cambia a seconda della realizzazione dell'evento.
01:07:33Chiaro, va bene. Ovviamente abbiamo sempre detto attenzione che
01:07:40in un modello di questo tipo cosa vuol dire minimizzare?
01:07:43Rispetto a quale criterio?
01:07:45Rimangono gli stessi discorsi
01:07:46che abbiamo fatto non abbiamo parlato di
01:07:48analisi decisionale in condizioni di
01:07:51rischio avevamo detto di no cioè
01:07:52quando abbiamo l'esplosione probabilità cosa vuol dire
01:07:54minimizzare minimizza il caso medio.
01:07:57Ma potevamo minimizzare anche il caso più verosimile? Non lo so.
01:08:01Abbiamo 1000 modi di capire cosa vuol dire minimo o massimo.
01:08:05E l'altra cosa altrettanto critica è capire cosa vuol
01:08:09dire rispettare un vincolo stocastico.
01:08:12Ok? Cosa vuol dire? Non lo sappiamo.
01:08:15Quindi, come al solito andare da un modello,
01:08:19da un modello non nominale ad una controparte stocastica.
01:08:23Okay, vuol dire capire qual è
01:08:27il criterio di ottimizzazione e qual è
01:08:29il criterio di accettabilità nell'incertezza.
01:08:33Ok, va bene.
01:08:35Benissimo. Allora noi ci concentriamo perché
01:08:38già i discorsi sono difficili,
01:08:40Ci concentriamo, ci concentreremo per lo più ai
01:08:43casi in cui abbiamo modelli di programmazione lineare.
01:08:46Quindi cosa vuol dire? Vuol dire che la funzione obiettivo
01:08:49sarà una somma pesata delle x dove i pesi sono aleatori.
01:08:53Okay quindi l'evento incerto andrà
01:08:58determinare il valore dei pesi delle X,
01:09:01quindi dei coefficienti di costo di ciascuna
01:09:03x. Ma allo stesso modo i
01:09:05parametri aleatori saranno una matrice dei dei dei coefficienti.
01:09:09Nei vincoli lineari la T
01:09:12è il vettore dei termini noti h che va bene diciamo.
01:09:16Abbiamo semplificato un po perché adesso sappiamo che i
01:09:18parametri aleatori sono il vettore dei costi.
01:09:21Il vettore dei termini noti la matrice dei
01:09:24coefficienti nei vincoli lineari
01:09:27ci siamo va bene okay e poi abbiamo sempre i nostri
01:09:30vincoli eh deterministici oltre vincoli stocastici.
01:09:34Rimane sempre il fatto di dover definire cosa vuol dire minimo,
01:09:36cosa vuol dire soddisfarli questi vincoli,
01:09:38anche se lineari. D'accordo. Vado avanti.
01:09:43Allora noi abbiamo parlato di controparte stocastica.
01:09:49Dato un modello nominale,
01:09:50abbiamo la controparte stocastica,
01:09:52ma dato un modello non nominale,
01:09:55abbiamo anche la parte, la controparte deterministica.
01:09:59Cos'è la controparte deterministica di un modello?
01:10:02È quella in cui abbiamo stabilito bene cosa vuol dire minimo,
01:10:06cosa vuol dire soddisfare i vincoli
01:10:08e inoltre abbiamo assegnato un valore numerico
01:10:11a tutti i parametri che ad esempio come faccio?
01:10:15A quale potrebbe essere
01:10:17una controparte deterministica di questo problema
01:10:21generale di ottimizzazione di programmazione stocastica?
01:10:24Una parte potrebbe essere quella in cui, ad esempio,
01:10:26minimizzare vuol dire tenere
01:10:28la stessa funzione e anziché
01:10:31utilizzare una variabile aleatoria associata ai costi,
01:10:36prendo il valore medio,
01:10:39che quindi ogni parametro
01:10:41lo valorizzo col valore medio di quel parametro.
01:10:44È un modo di dire assegno un numero.
01:10:48Okay, d'accordo,
01:10:51attenzione, non ha a che fare con la Realizzazione dei dei dei
01:10:56parametri ha semplicemente a che fare col fatto di
01:10:58dire il costo della variabile x
01:11:00uno C1 è distribuito con una normale di un certo tipo.
01:11:05Va bene, però anziché
01:11:07considerare la normale considero che C1 è uguale
01:11:10al valor medio di quella normale
01:11:12punto e e faccio lo stesso con tutti i parametri aleatori,
01:11:16li valorizzo in modo faccio finta che siano deterministici
01:11:20e che il valore deterministico corrisponda al valor medio
01:11:24che questa controparte deterministica ha un nome particolare e si
01:11:29chiama controparte deterministica con
01:11:31valor medio expected value ok,
01:11:34quindi controparte deterministica con valore
01:11:37atteso col valor medio expected expected.
01:11:40Bene, quindi.
01:11:42Una controparte deterministica diventa
01:11:45un problema che io posso implementare
01:11:47in ambo le risolverlo questo vuol dire va bene, ci siamo.
01:11:51Perfetto, Vado avanti adesso generale. Abbiamo detto.
01:11:59Per dato un problema nominale e dato che abbiamo dei
01:12:05parametri che non sono noti deterministicamente ma sono noti
01:12:10come distribuzioni di probabilità.
01:12:12Un primo passo per capire qual è il problema
01:12:15stocastico che vogliamo risolvere
01:12:17è capire cosa vuol dire minimi che.
01:12:19Allora, ad esempio,
01:12:22possiamo prendere i criteri dell'analisi decisionale.
01:12:25Anche qui si potrebbe considerare il caso peggiore,
01:12:28ma saremo nell'ambito delle ottimizzazione robusta, okay.
01:12:31Oppure si potrebbe prendere non lo so il
01:12:33valore più verosimile con un criterio di massima verosimiglianza
01:12:39ok. Oppure il caso
01:12:43più usato è il valore atteso
01:12:45Perché il caso più usato soprattutto in questo corso?
01:12:47Perché il valore atteso preserva la linearità.
01:12:50Se abbiamo la funzione obiettivo lineare.
01:12:52Nelle variabili aleatorie la media
01:12:54continua a essere una funzione lineare.
01:12:57Okay, va bene, quindi quello è il motivo.
01:12:59Ci sono altre misure e se
01:13:01facciamo in tempo vedremo qualche esempio.
01:13:03Ad esempio delle volte si usa la varianza come misura, no?
01:13:08Immaginate di avere un problema che vuole.
01:13:10É un problema di ottimizzazione in ambito di investimenti.
01:13:13Voi avete un certo budget, okay,
01:13:16e magari volete garantire una certa resa minimizzando il rischio,
01:13:21minimizzando la varianza, per esempio.
01:13:23Okay, però la varianza è un'espressione quadratica,
01:13:25quindi insomma potrebbe crearci dei problemi per cui insomma.
01:13:28Tendenzialmente però esistono che quindi
01:13:32si può concludere la varianza si perdono proprietà come
01:13:34la linearità che che sappiamo è
01:13:37importante per cercare di tenere il problema se non facile
01:13:40almeno con la speranza di poterlo risolvere senza grossi
01:13:44inghippi che va bene vado avanti.
01:13:48Allora facciamo degli esempi quindi
01:13:49io uso questo esempio che un esempio
01:13:51proprio molto astratto ma che ci servirà per fare dei ragionamenti.
01:13:55Allora questo è un problema di ottimizzazione
01:13:57okay nel quale abbiamo la funzione obiettivo di massimo.
01:14:03Abbiamo quattro variabili decisionali x1, x2,
01:14:07x3, x4 che sono variabili semplicemente continue.
01:14:12Va bene e due vincoli di uguaglianza.
01:14:15D'accordo, Allora questo è un problema secondo voi?
01:14:19Deterministico o stocastico stocastico?
01:14:23Perché la funzione obiettivo è deterministica?
01:14:28Però poi esiste un vincolo deterministico.
01:14:31Il primo perché deterministico?
01:14:33Perché tutti i parametri sono noti deterministicamente,
01:14:37ma il secondo vincolo è un vincolo stocastico,
01:14:39perché due dei parametri che lo definiscono sono noti
01:14:43come distribuzione di probabilità.
01:14:45E in particolare sono noti come distribuzione per scenari va bene,
01:14:50ne abbiamo due scenari.
01:14:51Il primo scenario con probabilità zero sette
01:14:54in cui A e B assumono i valori rispettivamente uno e 3/4.
01:14:58Il secondo scenario, con probabilità residua zero tre,
01:15:01in cui A e B assumono rispettivamente meno tre 9/4.
01:15:05Comunque va bene.
01:15:07Quindi questo è un problema di ottimizzazione stocastica di
01:15:10programmazione lineare stocastica. Ci siamo.
01:15:14La domanda è come lo risolviamo?
01:15:22Avete qualche idea?
01:15:26E boh. Allora facciamo un tentativo.
01:15:30No, come al solito cerchiamo di fare un tentativo.
01:15:33Il tentativo qual è?
01:15:34Noi sappiamo risolvere controparti deterministiche.
01:15:38Possiamo ottenere una controparte deterministica,
01:15:41come abbiamo detto prima?
01:15:42No. Potrei passare dalla controparte deterministica in
01:15:45cui A e B non sono più stocastici,
01:15:49ma li sostituisco con i loro valori medi che.
01:15:52Quindi il valore medio di A qual è è zero sette per
01:15:55uno più zero tre per meno tre.
01:15:59Okay che se ho fatto bene i conti vale -0,2.
01:16:03E qual è il valore medio di B?
01:16:06È zero sette per 3/4 più zero tre per
01:16:099/4 che se ho fatto bene i conti vale 1,2.
01:16:12Ok, va bene.
01:16:14Quindi sostituisco meno zero 2AE07 e 1,2 a B.
01:16:20A quel punto un problema che posso risolvere con a
01:16:22capo lo risolvo e ottengo come.
01:16:25Attenzione ottengo come
01:16:28soluzione ottima della controparte
01:16:31deterministica al valor medio meno uno 1E51E50 e
01:16:36come valore della funzione obiettivo 2,5.
01:16:39Okay, ti faccio una
01:16:41domanda quanto è significativa questa soluzione che ho ottenuto.
01:16:49La soluzione che io ho ottenuto è una
01:16:53soluzione che di fatto non sarà mai ammissibile.
01:16:58Vero? Perché nello scenario uno se fate i conti,
01:17:02non è ammissibile perché nello scenario uno è meno uno.
01:17:08Quindi uno per meno uno più 3/4 per 1,5 più zero non fa due.
01:17:16Okay, ma neanche nello scenario due se io faccio eh.
01:17:21Nello scenario due meno tre per uno,
01:17:26più nove quattro per 1 e 5 più zero per 1,5 più
01:17:30zero per zero più uno per zero non fa due che quindi
01:17:35la controparte deterministica che ho risolto non mi serve
01:17:39a niente perché la soluzione
01:17:42ottenuta potrebbe non essere ammissibile
01:17:44per alcune o tutte le realizzazioni.
01:17:46Sei d'accordo? Okay, questa è una cosa ovvia.
01:17:50Però cominciamo a ragionare sul fatto qui che non è così ovvio.
01:17:54Come risolvo un problema di questa natura qui?
01:17:56Come trovo la soluzione ottima?
01:17:57Bene io so risolvere
01:18:00controparti deterministiche però rischiano di
01:18:02non rischia di non KEE che queste non servono a nulla.
01:18:05Ho una vaga idea che è il valore atteso,
01:18:09che è il non valore atteso.
01:18:10Il valore della funzione obiettivo è 02:05,
01:18:13che non è il valor medio della del della mia soluzione non lo
01:18:16so il valor medio della mia soluzione perché valor medio
01:18:19della mia soluzione è
01:18:21niente non so neanche definirlo perché
01:18:23non è ammissibile la soluzione
01:18:25quindi non posso calcolare il valore nello scenario uno il valore
01:18:28dello scenario due calcolare la media non posso
01:18:30farlo chiaro perché non è ammissibile
01:18:34due e mezzo è un valore così che
01:18:37mi dà un'idea vaga di
01:18:39che cosa potrebbe succedere, ma niente di più.
01:18:41Va bene. Chiaro? Un altro tentativo quale potrebbe essere?
01:18:45Vabbè, a sto punto se voglio la soluzione ammissibile
01:18:47mi metto nei due casi che risolve il problema.
01:18:51Nello scenario uno risolve il problema nello scenario due,
01:18:54ma a questo punto avrei due soluzioni no?
01:18:57O la soluzione ottima nello scenario uno in cui
01:19:00A e B sono sostituite con uno e 3/4 ottengo questa
01:19:04x meno uno tre zero.
01:19:06Insomma con valore quattro Okay?
01:19:11E nello scenario due la soluzione sarebbe
01:19:14quest'altra qui e il valore 1,05.
01:19:18Allora queste due soluzioni ho due soluzioni diverse,
01:19:22una realizzabile nello scenario uno ottima,
01:19:24l'altra realizzabile, uno scenario, due ottima.
01:19:26Potrei calcolare la media che è
01:19:293,11 e però questo secondo voi è una cosa che io posso fare o no?
01:19:33Posso implementare questa soluzione?
01:19:36In realtà ho trovato due soluzioni,
01:19:37ma se io potessi aspettare
01:19:40la realizzazione degli
01:19:42scenari e calcolare la soluzione ottima in ogni scenario,
01:19:45non sarebbe un problema di ottimizzazione stocastica, vero?
01:19:48Sarebbero due problemi
01:19:50deterministici che io risolvo in modo utopico,
01:19:55conoscendo già a priori quale scenario si realizzerà.
01:19:59Vi ricordate no dei ragionamenti
01:20:00che avevamo fatto durante l'analisi decisionale
01:20:02per dire questa cosa non si può fare.
01:20:05Okay, in questo ambito si parla anche di soluzione wait and see,
01:20:10cioè come dire poi aspettare la realizzazione,
01:20:13risolvere il problema dopo che l'hai realizzato.
01:20:15Okay, d'accordo.
01:20:18E in questo caso quindi quel 3,11 è un valore utopico.
01:20:23Son sicuro che meglio di così
01:20:25non posso fare perché al meglio io posso risolvere
01:20:28il problema all'ottimo nei vari scenari e poi mediare le soluzioni.
01:20:32Ottime. Ma ripeto, questo modo di operare non
01:20:37è possibile non
01:20:39è possibile nella realtà perché il problema lo devo risolvere oggi,
01:20:42una volta sola e domani applicherò una sola soluzione,
01:20:46quella che ho deciso oggi.
01:20:47Chiaro, va bene quindi questo me lo utopico
01:20:51perché non è raggiungibile d'accordo ci siamo.
01:20:56Bene allora questo per rinfrescarci un po il discorso che.
01:21:04Ci son cose che possiamo fare magari sono
01:21:07inutili cose che sarebbero utili ma che non possiamo fare,
01:21:10quindi dobbiamo trovare un modo di risolvere questo problema.
01:21:13Vi faccio notare che ovviamente le due
01:21:14soluzioni che abbiamo trovato una
01:21:16è ammissibile in uno scenario l'altra nell'altro
01:21:18quindi se anche risolvesse la.
01:21:21Noi potremmo anche dire guardate potremmo anche
01:21:23dire va bene o oggi ho risolto questi
01:21:26due problemi e ho trovato
01:21:28due soluzioni devo sceglierne una tra queste due.
01:21:30Ad esempio scelgo la prima perché quattro però
01:21:34la prima comunque una
01:21:35probabilità zero tre di non essere ammissibile.
01:21:39Se questo è accettabile la prendo,
01:21:41Ma se non è accettabile per me avere
01:21:43una probabilità del 30% che non sia ammissibile,
01:21:45è quella soluzione la devo scartare e cercarne
01:21:47un'altra che magari sia ammissibile con più probabilità.
01:21:51Che vuol dire di nuovo riuscire
01:21:53a capire cosa vuol dire soddisfare
01:21:55i vincoli stocastici con una certa probabilità?
01:21:57Va bene, ci siamo, okay.
01:22:00Quindi vedete che ancora non abbiamo risolto il
01:22:02problema cioè non non sappiamo bene
01:22:05come operare qual è il discorso
01:22:07il discorso che questo esempio semplice che abbiamo fatto ci fa
01:22:11capire che dobbiamo ridefinire il concetto di ammissibilità.
01:22:15Okay. Quanti modi ci sono di
01:22:17ridefinire il concetto di ammissibilità.
01:22:19Tantissimi e noi ovviamente cerchiamo di di
01:22:23concentrarci su alcuni perché
01:22:25su questi possiamo fare dei ragionamenti
01:22:27e possiamo avere la speranza di risolvere il problema che uno.
01:22:32Quindi tra i modi che i
01:22:34due modi che considereremo in questo corso saranno quelli in
01:22:37cui è possibile distinguere le decisioni in due stadi.
01:22:42Chiameremo modelli a due stadi con ricorso.
01:22:44Adesso facciamo un esempio subito così si capisce cosa vuol dire.
01:22:47Oppure cercheremo dei modelli con vincoli probabilistici
01:22:52in cui cerchiamo di capire.
01:22:54Ci sono delle condizioni sotto le quali esprimere
01:22:57il vincolo probabilità che questo vincolo sia soddisfatto
01:23:00maggiore o uguale di una soglia
01:23:02è possibile farlo con una forma chiusa?
01:23:04Va bene, quelli sono i vincoli probabilistici.
01:23:07Introduciamo però
01:23:08una categoria importante di
01:23:11modelli di programmazione stocastica che sono i modelli in
01:23:13cui l'ammissibilità è definita con
01:23:17un una formulazione a due o più stadi con ricorso.
01:23:22Cosa vuol dire ve lo dico in due parole poi facciamo l'esempio qual
01:23:26è il punto il punto è che noi sappiamo che oggi
01:23:30dobbiamo decidere per domani.
01:23:32Okay, Allora cosa potrebbe succedere qui?
01:23:35Supponete di scegliere voi no.
01:23:38E di di di anzi abbiamo una cosa più facile
01:23:41supponete di risolvere questo problema deterministico cosa
01:23:45succederà domani?
01:23:46Domani quando io provo ad applicare quella
01:23:49soluzione lì o in un caso o nell'altro comunque non
01:23:52è ammissibile nel caso di più
01:23:55stadi con ricorso io sto
01:23:57ipotizzando la possibilità domani di mettere una pezza.
01:24:02Okay quindi se ho fatto degli errori,
01:24:05se il vincolo non è soddisfatto,
01:24:06posso pagare una penalità per rimettere a posto le cose?
01:24:10Quello è il secondo stadio.
01:24:12Okay, Quindi prendo una decisione oggi,
01:24:15sapendo che domani la decisione che prendo oggi
01:24:19dovrò eventualmente sistemarla pagando una penalità.
01:24:22Okay, quindi domani dovrò decidere come
01:24:26aggiustare le cose a
01:24:27seconda della realizzazione degli eventi incerti.
01:24:29Bene, questa è l'idea.
01:24:31Però vediamola con un esempio così si capisce meglio, spero.
01:24:39Vabbè, non so se riusciamo a finirlo.
01:24:44Allora sai cosa facciamo per farmi perdonare che ho sempre sforato?
01:24:49Finisco 5 minuti prima, così stiamo pari.
01:24:52Va bene, siamo a posto.
01:24:53Allora domani cominceremo a vedere domani,
01:24:56lunedì vedremo come trattare i vincoli di natura probabilistica,
01:25:01in particolare in queste due modalità.
01:25:05Bene inutile che lo introduco che poi dobbiamo riprendere
01:25:08ci rifaremo all'esempio quello che abbiamo
01:25:10fatto al primo giorno della produzione
01:25:12di dadi bulloni quindi
01:25:14se volete ve lo ricordate così ce l'abbiamo fresco.
01:25:16Grazie allora ti.