Lezione 26 (5 maggio 2026)

Assistente AI

Trascrizione

00:00:02Buongiorno.

00:00:07Siamo pronti per risolvere

00:00:10problemi con incertezza di ottimizzazione,

00:00:14poi altri problemi con incertezza non sappiamo risolverli.

00:00:17Insomma dovete andare da qualcos'altro.

00:00:20Allora cerchiamo un po di capire come ci posizioniamo.

00:00:24Abbiamo detto che problemi di ottimizzazione esistono,

00:00:28possiamo risolverli con diversi strumenti.

00:00:30Abbiamo mostrato come strumento

00:00:32la programmazione matematica che abbiamo visto è

00:00:34uno strumento flessibile e abbiamo anche imparato a dire che,

00:00:38dato un problema di ottimizzazione,

00:00:40quando si parla di incertezza possiamo

00:00:43distinguere due casi per lo stesso problema

00:00:46il caso nominale e la controparte robusta o stocastica.

00:00:54Quindi cos'è il caso nominale di un problema di ottimizzazione?

00:00:57È il problema definito

00:01:00come se l'incertezza non

00:01:02esistesse o indipendentemente dall'incertezza.

00:01:05E noi abbiamo capito che i problemi di

00:01:06ottimizzazione che ci interessano sono fatti da una funzione

00:01:09obiettivo che vogliamo massimizzare o minimizzare

00:01:11e da una descrizione delle soluzioni ammissibili entro

00:01:15le quali vogliamo trovare la migliore soluzione,

00:01:18quella che ottimizza la funzione obiettivo

00:01:20che Funzione obiettivo, vincoli.

00:01:22E funzione, obiettivo e vincoli sono determinati da parametri.

00:01:25Ci saranno dei dati del problema?

00:01:27Okay. E questi dati se

00:01:29non hanno incertezza o se prescindiamo dall'incertezza che potrebbe

00:01:34esistere se definiamo un parametro semplicemente come il

00:01:37costo dell'arco dal nodo al nodo B. Stiamo definendo

00:01:42il problema nominale in

00:01:45un problema di ottimizzazione può intervenire incertezza.

00:01:47Perché? Perché i parametri

00:01:51che definiscono la funzione obiettivo

00:01:53e o le caratteristiche delle delle

00:01:55delle soluzioni ammissibili possono essere soggetti

00:01:57a incertezza KEE e quindi non abbiamo detto

00:02:00se c'è incertezza possiamo parlare di ottimizzazione robusta

00:02:04se prescindiamo da una distribuzione di probabilità

00:02:07associata a parametri incerti oppure

00:02:09di ottimizzazione stocastica, se.

00:02:11Se vogliamo sfruttare informazioni,

00:02:14se abbiamo e vogliamo sfruttare informazioni

00:02:16su una distribuzione di probabilità legata

00:02:19ai parametri incerti.

00:02:20Abbiamo però imparato ieri che,

00:02:23dato un problema nominale,

00:02:25esistono possono esistere più controparti robuste che.

00:02:30E da che cosa dipendono queste controparti robuste?

00:02:32Da diversi fattori che abbiamo classificato in qualche modo in

00:02:37due da una modalità di rappresentazione dell'incertezza.

00:02:41Se l'incertezza è per scenari se c'è incertezza data

00:02:45per intervalli entro i quali possono variare dei parametri.

00:02:48Abbiamo visto che ci possono essere diversi modi di

00:02:51descrivere l'incertezza o di modellare l'incertezza.

00:02:55Okay. E inoltre non basta definire,

00:02:58descrivere l'incertezza, quindi avere un modello per l'incertezza,

00:03:02perché si tratta sempre di modelli.

00:03:04Dire che il costo dell'arco da A a B varia tra tre e 05:01 modello

00:03:08magari nella realtà può essere tre oppure 3,1 oppure tre.

00:03:14Tutti i possibili valori tra tre virgola 02:05.

00:03:17Va bene se ci conviene.

00:03:19Possiamo modellare dicendo va bene,

00:03:22considero tutti i valori tra 03:05 e poi vedremo.

00:03:25Così come facciamo per un modello,

00:03:26per una qualsiasi semplificazione

00:03:28che noi introduciamo per modellare.

00:03:30Quindi una parte del modello sta nella

00:03:33rappresentazione dell'incertezza e una parte del modello sta

00:03:37in un altro fattore che e che e definire i criteri

00:03:40di robustezza che esistono diverse controparti robuste e

00:03:44anche perché possiamo concordare

00:03:47con il committente un criterio di robustezza.

00:03:50Cosa vuol dire massimizzare la funzione obiettivo se

00:03:52la funzione obiettivo è definita per diversi scenari.

00:03:55Abbiamo visto max il max min,

00:03:57il valore medio o quello che è.

00:04:00A seconda dei casi,

00:04:02però ciascuna di queste scelte porta a una

00:04:04controparte robusta o stocastica diversa che.

00:04:07Ma anche il criterio di robustezza ha

00:04:08a che fare con la potrebbe avere

00:04:11a che fare con cosa consideriamo come

00:04:13accettabile Quando c'è una probabilità,

00:04:16ad esempio, che una soluzione sia ammissibile o no?

00:04:18Ok, abbiamo visto degli esempi

00:04:20basandoci sul problema del contadino,

00:04:22che quindi, caso nominale è chiaro cos'è ed

00:04:25è chiaro che possono esistere diverse controparti robuste,

00:04:28ciascuna definita dalle modalità di

00:04:30rappresentazione dell'incertezza e dai criteri di

00:04:33robustezza che noi vogliamo

00:04:34considerare nell'ottima dell'ammissibilità delle soluzioni.

00:04:39Va bene, vado avanti.

00:04:42Detto questo, riepilogo vi ricordate allora qual è?

00:04:48Diciamo che io potrei fermarmi qua.

00:04:52Che dire, abbiamo finito il corso,

00:04:54siamo tutti felici quanto piove

00:04:56quindi non possiamo andare neanche in vacanza. Vabbè insomma.

00:04:59Quindi stiamo qua e facciamo qualcos'altro perché altrimenti

00:05:02potrei dire va bene,

00:05:03una volta che voi avete il problema nominale e che avete

00:05:06definito come rappresentare l'incertezza e

00:05:09come eh e avete stabilito i criteri

00:05:12di ottimalità di robustezza di di di ammissibilità

00:05:15per la vostra per il vostro problema

00:05:17cosa fate quello che abbiamo fatto ieri cercate di rappresentare

00:05:20queste eh di di formulare

00:05:25il problema con un modello di

00:05:27programmazione matematica se ci riuscite

00:05:29lo risolvete e siete a posto come abbiamo fatto ieri.

00:05:32Ieri abbiamo detto beh se prendiamo il max min per

00:05:35la resa o se prendiamo una certa probabilità di essere ammissibili,

00:05:40cerchiamo di formulare il modello di quel problema

00:05:43e poi abbiamo un risolutore che ce lo risolve,

00:05:46perché non è sufficiente questo?

00:05:48Perché abbiamo visto che esiste un

00:05:50diverso livello di difficoltà per risolvere

00:05:52i problemi e quindi

00:05:53definire una controparte robusta che non sappiamo

00:05:55risolvere può essere inutile e quindi in

00:05:58questo corso cosa faremo cercheremo di di

00:06:01di di acquisire una certa sensibilità su come

00:06:05trovare il miglior compromesso tra il problema

00:06:09reale con la sua incertezza reale con i suoi criteri reali.

00:06:13E una formulazione che modelli il

00:06:16più possibile quell'incertezza capendo

00:06:18se quel modello che abbiamo trovato quella

00:06:21formulazione che abbiamo trovato

00:06:22abbiamo speranza di poterla risolvere

00:06:24e con che sforzo computazionale.

00:06:26Se il problema che se

00:06:28la controparte robusta che noi definiamo è facile o

00:06:30difficile in alcuni casi accetteremo anche eh

00:06:35solo controparti facili come

00:06:38compromesso perché non abbiamo risorse computazionali qualche altra

00:06:41volta potremmo permetterci anche controparti difficili

00:06:43ma sapremo che sarà un po'più

00:06:46difficile risolvere quel problema e magari dovremmo rivolgerci

00:06:50a qualche esperto di tecniche di ottimizzazione.

00:06:52Okay, quindi noi siamo un po l'interfaccia,

00:06:55cerchiamo di capire il miglior compromesso.

00:06:57Per capire il miglior compromesso dobbiamo avere

00:06:59degli strumenti di modellazione,

00:07:01di problemi robusti e di problemi stocastici,

00:07:04che è quello che faremo.

00:07:06Quindi dobbiamo ricordarci che esistono problemi facili

00:07:09ai problemi difficili. Vi ricordate?

00:07:10No? Vabbè, ovviamente

00:07:11a noi interessa di tutta la teoria della complessità questa slide

00:07:15nella quale diciamo il problema è

00:07:16facile quando è noto un algoritmo che trova la soluzione in

00:07:20tempo polinomiale trova la soluzione ottima di quel problema

00:07:22in tempo polinomiale.

00:07:24Ok? E quindi questo vuol dire che anche

00:07:26se il problema diventa più grande come

00:07:28dimensione se l'istanza del problema non dobbiamo

00:07:31trovare il cammino minimo in

00:07:33una rete con dieci nodi ma dobbiamo trovare il cammino

00:07:35minimo in tutta la città di Padova o in tutta Europa,

00:07:38abbiamo la speranza di riuscire a risolverlo.

00:07:40Se il problema da risolvere è di complessità polinomiale, ok,

00:07:45Abbiamo invece problemi difficili sono quei problemi per cui non è

00:07:49noto un algoritmo di complessità controllabile quindi

00:07:54non scalano bene con la dimensione quindi magari riusciamo

00:07:58a risolvere istanze di quel problema piccoline limitate che ne so

00:08:03a un quartiere ma se poi dobbiamo risolvere

00:08:04il problema nella città di Padova trovare il cammino minimo

00:08:08in tutta la città diventa un problema non riusciamo

00:08:10a farlo perché non ci mancano risorse.

00:08:13Okay. Questo è quello che ci interessa.

00:08:15Noi abbiamo detto che abbiamo

00:08:17visto l'esempio del cammino minimo che un problema

00:08:19facile e abbiamo detto guardate è

00:08:21facile tant'è vero che se anche lo

00:08:23formuliamo un problema di programmazione lineare intera alla

00:08:25fine possiamo risolvere come un problema di programmazione lineare.

00:08:28Per cercare di generalizzare un po il concetto che vi ricordate

00:08:32che invece ci sono altri problemi che sono formulabile

00:08:36come problemi di programmazione

00:08:38lineare intera e non riusciamo

00:08:39a trovare un modo di risolverli

00:08:41se prescindendo dalla interezza delle variabili e

00:08:43quindi rimangono problemi tendenzialmente difficili questo è

00:08:47un diciamo è un è un è un metodo

00:08:51che utilizziamo noi in questo corso come diciamo una per

00:08:55farci un'idea della difficoltà di un di un problema non è

00:08:58uno strumento teoricamente diciamo

00:09:02accettabile però per noi per i nostri ragionamenti va bene okay.

00:09:06In questo corso noi diciamo stiamo

00:09:08facendo tante cose le stiamo facendo

00:09:10in modo tale da essere in

00:09:11grado di parlare poi con chi tecnicamente ha delle competenze in

00:09:17ambito di complessità in

00:09:18ambito di soluzione di modelli di programmazione matematica in

00:09:21ambito di soluzione di equazioni differenziali eccetera eccetera.

00:09:25Che già le nostre competenze sono già

00:09:28abbastanza quelle di riuscire a formulare un problema.

00:09:32Va bene quindi questo e quindi passiamo a parlare di ottimizzazione

00:09:36robusta che cos'è

00:09:37ottimizzazione robusta vi ricordo

00:09:40abbiamo un problema di ottimizzazione.

00:09:43Abbiamo incertezza e non abbiamo informazioni o

00:09:47non vogliamo sfruttare informazioni di tipo probabilistico che.

00:09:51Ma ad esempio abbiamo degli scenari o meglio situazioni

00:09:55in cui la nostra soluzione deve funzionare.

00:10:00Vi ricordo che noi abbiamo sempre una

00:10:02soluzione che dovrà andar bene in tutti gli scenari per

00:10:05esempio e dovrà essere

00:10:07il miglior compromesso tra la soluzione che

00:10:08funziona e che costa poco

00:10:11o che mi dà abbastanza.

00:10:14Se la funzione obiettivo è di massimo KEE,

00:10:16quindi una soluzione robusta,

00:10:17una soluzione valida e di valore ragionevole

00:10:20in ogni scenario in un insieme definito.

00:10:23Quindi la decisione è una sola.

00:10:26Una volta presa non possiamo cambiarla,

00:10:28quindi vogliamo che poi sia una soluzione la migliore possibile.

00:10:33Considerando un insieme definito di scenari di possibilità.

00:10:38Quando parlo di insieme definito di scenari abbiamo visto già un

00:10:41esempio no nel problema del contadino avevamo avevamo tre scenari e

00:10:45poi abbiamo definito una una una

00:10:47controparte robusta nella quale volevamo la soluzione che si

00:10:50comportava il meglio possibile che

00:10:53massimizza la resa in tutti e tre gli scenari okay.

00:10:58Che voleva dire massimizzare il minimo nei nei tre

00:11:01scenari d'accordo quindi questa era

00:11:03una era una soluzione robusta diremmo con

00:11:07un livello di conservativi con un livello di protezione

00:11:10massimo che considerava tutti gli scenari oppure

00:11:13abbiamo visto che questa robustezza sempre in

00:11:15senso assoluto possiamo un po parametrare

00:11:18la renderla meno esigente.

00:11:21Vi ricordate abbiamo detto vogliamo la la soluzione che

00:11:24massimizza il minimo guadagno

00:11:26in due scenari vi ricordate

00:11:29no Quindi avevamo un po alleggerito questa richiesta.

00:11:31La robustezza rimane sempre in

00:11:33senso assoluto perché definiamo dei sottoinsiemi di scenari e

00:11:37in tutti quegli scenari vogliamo avere.

00:11:39Vogliamo andare bene.

00:11:41E va bene quindi ecco perché si parla

00:11:43di robustezza in senso assoluto.

00:11:47Okay, poi si parlerà di robustezza

00:11:49in senso relativo così lo capiamo quando

00:11:51parleremo e vorremmo una

00:11:53soluzione che sia la migliore in confronto ad altre soluzioni.

00:11:57Ad esempio vi ricordate il criterio del minimum

00:12:00del massimo o del EMH, come l'avevamo chiamato?

00:12:04Eh sì, del eh.

00:12:07Il criterio nel quale noi volevamo

00:12:09massimizzare il mancato guadagno perché è mancato guadagno?

00:12:15Perché andavamo a valorizzare ciascuna opzione, ciascuna soluzione,

00:12:20ciascuno ciascuna alternativa,

00:12:22con la differenza rispetto alla migliore alternativa

00:12:24in quello scenario lì.

00:12:25Vedete che nasce un confronto nel criterio di scelta,

00:12:29un confronto con le altre alternative.

00:12:31Ecco perché lì si parlerà di senso relativo.

00:12:33Qui parliamo in senso assoluto perché vogliamo una

00:12:36soluzione che si comporti

00:12:37meglio rispetto agli scenari indipendentemente dalle altre.

00:12:41Che poi ci sarà una migliore dell'altra.

00:12:43Ma l'essere migliore o peggiore non deriva da un confronto diretto,

00:12:47ma da un confronto delle performance

00:12:49nelle diverse nei diversi casi di incertezza.

00:12:52Bene quindi robustezza in senso assoluto.

00:12:55E poi abbiamo degli esempi in

00:12:57cui mitiga un po questa assolutezza andando a

00:13:00dire abbiamo un livello di protezione che può

00:13:03essere scalato okay quindi

00:13:04ecco ottimizzazione robusta di fatto parametri incerti

00:13:08ma non sfruttiamo nessuna nozione di probabilità.

00:13:11Allora siccome rischiamo di fare dei discorsi troppo

00:13:14generali, cosa facciamo?

00:13:16Prendiamo un problema che ci farà da guida in

00:13:19questi nostri ragionamenti che

00:13:22nel 90% dei casi e

00:13:25scegliamo il cammino minimo come problema che ci fa da guida.

00:13:28Perché il cammino minimo perché un esempio di problema

00:13:31che ha un caso nominale semplice e ci farà capire

00:13:35come definire

00:13:37diverse controparti robuste di uno stesso problema nominale

00:13:40può rendere più o meno difficile la soluzione di quel problema lì.

00:13:44Quindi vedremo che il problema del cammino minimo,

00:13:48che è facile nel caso nominale,

00:13:50può può restare facile in alcuni casi in

00:13:53alcune controparti robuste scegliendo certe

00:13:56rappresentazioni dell'incertezza scegliendo certi

00:13:58criteri di robustezza e invece

00:14:03diventa difficile se facciamo scelte diverse.

00:14:06Va bene, il problema del cammino minimo lo conoscete?

00:14:08Non sto lì a rivederlo,

00:14:11È un problema facile nel caso nominale,

00:14:13perché esistono algoritmi polinomiali che lo risolvono.

00:14:16Qualcuno di voi avrà sentito parlare dell'algoritmo

00:14:18di destra o destra l'algoritmo di Belmont?

00:14:21Okay, esistono algoritmi che

00:14:24fanno risolvere il problema in modo facile.

00:14:26Se nel problema nominale, se c'è incertezza,

00:14:28vedremo che cosa succede e vedremo qual è la

00:14:32le competenze che noi vogliamo avere dopo questo corso.

00:14:35L'incertezza deriva dal fatto che, ad esempio,

00:14:38i costi sugli archi possono essere incerti.

00:14:41Non lo so, perché può essere incerto il costo sull'arco,

00:14:43perché se il costo è associato

00:14:44al consumo e o al tempo di attraversamento di un arco,

00:14:47se c'è congestione ovviamente il tempo è diverso.

00:14:52Più congestione c'è, più sarà il tempo di attraversamento.

00:14:55Il costo, la benzina che io consumo per attraversarlo.

00:14:57Va bene chiaro che quindi quello può

00:15:00essere una fonte di incertezza.

00:15:02Un esempio un altro esempio è c he

00:15:06si modifica la struttura del

00:15:07problema si potrebbero guastare degli archi,

00:15:10guastare dei nodi un incrocio lo dobbiamo chiudere c'è una un non

00:15:14so un allagamento su una strada non ci possiamo passare.

00:15:17Okay ovviamente l'allagamento domani ci potrà essere con sì o

00:15:22no va bene oppure ripeto la notte il giorno la

00:15:27notte l'autostrada è chiusa perché ci sono lavori e di giorno

00:15:31no Quindi vogliamo trovare

00:15:32il percorso che funzioni bene non sapendo se domani arriveremo

00:15:36in quel tratto di giorno o di notte.

00:15:39Okay, per esempio va bene

00:15:42così il cammino minimo robusto determinare un cammino valido e

00:15:46di costo accettabile ragionevole sotto ogni sotto ogni

00:15:49condizione tra quelle che vogliamo considerare

00:15:52tra gli scenari che ci interessa.

00:15:53Va bene e che cosa vuol dire determinare un cammino valido e

00:15:57accettabile sotto ogni condizione dipende

00:16:00dalla controparte robusta che decideremo di risolvere.

00:16:02E adesso vediamo alcuni esempi.

00:16:04Okay, d'accordo.

00:16:06Cioè vedremo alcuni esempi su questo problema.

00:16:09Allora abbiamo detto che,

00:16:11dato un problema di ottimizzazione,

00:16:12la controparte robusta o stocastica è

00:16:14determinata da come vogliamo rappresentare l'incertezza.

00:16:17Allora adesso cerchiamo di capire quali possono essere

00:16:19le modalità interessanti di rappresentare l'incertezza.

00:16:23Non pretenderò di essere esaustivo dicendo che l'incertezza si

00:16:27può rappresentare in questi modi,

00:16:28ma vi mostrerò alcuni alcune delle

00:16:31modalità che sono più interessanti verso con l'ottica

00:16:34di costruire dei delle controparti robuste o

00:16:38stocastiche che siano che possano andar bene

00:16:41in moltissimi casi quindi

00:16:43che possono ragionevolmente rappresentare l'incertezza

00:16:46in molti casi e che però poi ci danno la speranza o

00:16:50ci danno la possibilità di valutare quanto è difficile

00:16:54risolvere il problema che sceglie quella

00:16:56modalità di rappresentazione dell'incertezza.

00:16:59Allora innanzitutto modelliamo il fatto che l'incertezza

00:17:04è legata ai parametri del problema,

00:17:06ai dati del problema.

00:17:07L'accordo va bene.

00:17:09Questo è come

00:17:10possiamo rappresentare primo modo semplice mediante scenari.

00:17:13Quindi abbiamo un numero finito di scenari che

00:17:16rappresentano le possibili realizzazioni dei parametri incerti.

00:17:19Va bene.

00:17:20Nell'ottimizzazione robusta non abbiamo nessuna probabilità.

00:17:24Cosa ho fatto? Tutto a posto? Ah, no, Che?

00:17:31Ah, ecco, pensavo non mi avevi fatto detto no.

00:17:33Stai dicendo un sacco di persone.

00:17:35Mi viene il dubbio che ogni tanto.

00:17:36Quindi non.

00:17:38Non abbiate pietà se vi

00:17:40rendete conto che sto dicendo cose incomprensibili.

00:17:43Magari mi sbaglio. Vabbè. Quindi scenari.

00:17:46Ripeto, se siamo in condizioni di robustezza non abbiamo

00:17:50o non prescindiamo da probabilità associate a queste realizzazioni.

00:17:55Altrimenti magari abbiamo anche una distribuzione di

00:17:57probabilità ma adesso voglio dire

00:17:58l'incertezza rappresentiamo possiamo rappresentanza per

00:18:01scenari c'è un numero finito di scenari ok.

00:18:05Oppure possiamo rappresentare l'incertezza un'altra modalità è

00:18:08quella di rappresentare l'incertezza mediante

00:18:10intervalli cioè un parametro

00:18:12è noto in un certo intervallo.

00:18:15Ripeto non abbiamo non stiamo dicendo che è il valore

00:18:19distribuito in modo equiprobabili o non so come in

00:18:21quell'intervallo lì stiamo dicendo che

00:18:22quel che vogliamo considerare

00:18:24tutte le soluzioni in cui quel parametro varia tra A meno e A+.

00:18:28Ok, questa è l'incertezza.

00:18:31Oppure mediante poliedri.

00:18:33Cos'è poliedri?

00:18:35Poliedri?

00:18:35Vuol dire che abbiamo

00:18:37delle relazioni matematiche lineari che devono

00:18:40essere soddisfatte dal dal dall'insieme dei miei parametri.

00:18:46Va bene quindi dico non lo so io

00:18:49non so quanto vale il parametro A1A2OAOA3 non lo so.

00:18:54Sono incerto, so soltanto che la loro somma deve essere uguale a

00:18:57quattro o che la loro somma deve essere compresa tra 03:05.

00:19:02Se volete un caso particolare,

00:19:05possiamo vedere come una generalizzazione

00:19:07delle della rappresentazione

00:19:10mediante intervalli mediante intervalli

00:19:12vuol dire che il poliedro è una box,

00:19:13una scatola no in cui noi stiamo ammettendo soltanto tutte

00:19:17le tutte le realizzazioni che stanno in

00:19:20una scatola cioè in cui i valori

00:19:23di ciascun parametro sono compresi tra un

00:19:25minimo un massimo che come dire che c'è un vincolo lineare che dice

00:19:28ha compreso tra meno e A più B compreso tra B meno e B più.

00:19:32Facciamo l'intersezione di tutte queste equazioni disequazioni

00:19:37lineari otteniamo un poliedro

00:19:38particolare che è molto bello perché è un box,

00:19:40una scala che va bene.

00:19:42Più in generale potremmo dire perché.

00:19:44Relazioni lineari così semplici Potremmo avere delle delle

00:19:48relazioni lineari da soddisfare un po

00:19:50più complicate che mi definiscono un poliedro in

00:19:52generale che ovviamente potrei

00:19:55avere delle situazioni nelle quali io voglio considerare tutte

00:19:57le realizzazioni dei parametri tali che il

00:19:59prodotto del parametro il parametro B

00:20:01è uguale a 28.

00:20:04Sì, è una possibilità se ha

00:20:06senso dal punto di vista del problema che sto risolvendo.

00:20:08Ha senso soltanto che una rappresentazione dell'incertezza un po

00:20:11più complicata che sarà difficile gestire.

00:20:14Quindi io adesso

00:20:15vi presento delle modalità di rappresentazione sulle

00:20:19quali abbiamo qualcosa da dire possiamo

00:20:20dire qualcosa di significativo va bene

00:20:23e altri che potrebbero però portare

00:20:25a controparti troppo difficili da trattare.

00:20:27Va bene, abbiamo detto okay.

00:20:31Allora noi abbiamo detto che l'incertezza per

00:20:35scenari è data quando noi

00:20:39abbiamo un insieme finito di scenari di possibili

00:20:42realizzazioni dei parametri incerti che

00:20:45in realtà possiamo generalizzare.

00:20:47Questo concetto sarà utile in alcuni casi.

00:20:49Dicendo che volendo anche altri non lo so

00:20:51anche la rappresentazione mediante

00:20:53intervalli possiamo rappresentarla.

00:20:54Per per scenari con numero

00:20:56infinito di scenari perché perché prendiamo tutte le

00:20:59possibili realizzazioni nel box diciamo c'è lo scenario uno

00:21:02in cui siamo in questo punto lo scenario due in quest'altro punto

00:21:04ovviamente abbiamo bisogno di infinite rappresentazioni

00:21:08per rappresentare

00:21:10tutte le possibili realizzazioni

00:21:12però da un punto di vista concettuale potrà essere

00:21:14utile pensare alle altre agli

00:21:16altri tipi di rappresentazioni quindi a tutti i

00:21:18tipi di rappresentazione come

00:21:20rappresentazione per scenari con un numero infinito di scenari.

00:21:22Un caso un po degenere lo

00:21:23utilizzeremo solo per fare dei ragionamenti.

00:21:25Va bene, ma va avanti.

00:21:28Esempio sempre per il nostro problema del cammino minimo,

00:21:32consideriamo la rete prototipo lì in alto a destra,

00:21:34che è la solita e possiamo dire quali sono i costi.

00:21:38I costi possono essere nello scenario uno,

00:21:41quelli elencati, quindi abbiamo la rete.

00:21:43In questo caso tutti i parametri

00:21:46sono incerti perché tutti i parametri

00:21:48sono incerti perché e e possono cambiare tutti hanno valori diversi

00:21:55in scenari diversi che quindi tutti i parametri

00:21:58sono incerti o una realizzazione possibile dello scenario uno

00:22:01quindi o tutti i costi assumono

00:22:03tutti contemporaneamente il valore della colonna uno o

00:22:06tutti i costi assumono contemporaneamente

00:22:08tutti i valori della colonna due.

00:22:09Okay, va bene, allora ripassino.

00:22:14Cosa facciamo in questi casi?

00:22:16Come facciamo a trovare il cammino minimo che funziona meglio?

00:22:19Vi ricordate allora un'idea è quella di dire

00:22:21abbiamo detto possiamo andare a vedere vari vari casi per esempio

00:22:25il cammino BT è uno dei possibili cammini

00:22:28è un cammino Sì quindi è una delle possibili soluzioni che può

00:22:31essere valorizzata da due nello scenario 1 o 20 nello scenario

00:22:34due vedete che quei cammini hanno due possibili valori

00:22:37in un valore per ogni scenario.

00:22:39Questo è un altro cammino che vale 40 e 4 a seconda

00:22:43dello scenario questo è un altro cammino che vale

00:22:4515:15 eccetera eccetera.

00:22:47Quale scegliamo tra questi tre cammini?

00:22:49Applichiamo l'analisi decisionale a

00:22:51questi tre cammini con i criteri che ci interessano.

00:22:53Ok, ovviamente non è detto che tra questi

00:22:57tre cammini ci sia il migliore,

00:22:59secondo il criterio dell'analisi decisionale ad esempio

00:23:01tra questi tre se utilizza un criterio di minimax,

00:23:05qual è il cammino migliore?

00:23:06Allora diciamo che BT sarebbe valorizzato

00:23:09con venti perché nel caso peggiore mi costa venti.

00:23:11Obi CT sarebbe valorizzato con 40 perché nel caso peggiore costa

00:23:1540 e o sarebbe

00:23:17valorizzato con 15 perché nel caso peggiore mi costa 15,

00:23:20quindi tra questi tre è migliore 15.

00:23:22Ma chi l'ha detto che non esiste un altro cammino che nel caso

00:23:25migliore che nel caso peggiore costa meno di 15? Non lo so.

00:23:28Noi sappiamo possiamo cercare di

00:23:31formalizzare ad esempio con un modello di programmazione matematica

00:23:33impareremo a vedere se è facile o difficile risolvere.

00:23:36Va bene, okay, vado avanti.

00:23:41Rappresentazione mediante intervalli, diciamo.

00:23:44Qui invece l'arco OC mi

00:23:48porta un parametro incerto il costo su OC e il costo.

00:23:52Perché incerto perché può assumere tutti i

00:23:54possibili valori tra 03:05 tre tre

00:23:56zero uno 3,8 4,9 3,723.

00:24:03Ok. Va bene, ok. Anche qui potrei fare lo stesso discorso.

00:24:11Però attenzione cosa succede al cammino Hobbit?

00:24:13Cammino Hobbit Può assumere,

00:24:15tu può assumere tutti i possibili costi compresi tra 02:20, vero?

00:24:20Come fate a determinare questo?

00:24:22Vado a vedere qual è il costo del cammino nello nel caso migliore

00:24:27tra tutti quelli che stanno dentro quell'intervallo e vedo che quel

00:24:32cammino mi costerà due ma potrebbe mi

00:24:35potrebbe costare minimo due massimo venti.

00:24:38Okay vedete che qui è analogamente gli altri e

00:24:41come mi comporto qui quando il costo

00:24:43è compreso tra degli intervalli.

00:24:45L'analisi decisionale comincia ad avere

00:24:47insomma qualche problema perché non mi è chiaro

00:24:52come valorizzare perché non

00:24:55mi è chiaro se c'è uno scenario peggiore.

00:24:57In realtà qui potrei ancora abbastanza semplice

00:24:59dire va bene siccome mi

00:25:00può sicuramente mi potrà costare massimo venti

00:25:04allora quella sarà la valorizzazione

00:25:06se utilizzo la controparte robusta in

00:25:07cui valuto con il massimo con

00:25:10il con il costo peggiore realizzabile.

00:25:13che però vedete che andare

00:25:15a capire qual è il costo peggiore realizzabile non è un

00:25:17semplice confronto tra scenari ci vuole un

00:25:19ragionamento va bene chiaro.

00:25:22Va beh comunque son tutte cose che se riusciamo

00:25:24a mettere dentro un modello lo risolviamo se riusciamo

00:25:27a mettere dentro un algoritmo ragionato che lo risolve

00:25:30risolviamo altrimenti abbiamo una

00:25:32controparte robusta di cui non sappiamo che cosa farcene.

00:25:34Impareremo a capire di quali controparti

00:25:36robuste possiamo farcene qualcosa

00:25:38e con che complessità.

00:25:40Va bene, vado avanti.

00:25:42Rappresentazione mediante poliedri Questo era un altro caso abbiamo

00:25:46già detto allora il vettore dei

00:25:47parametri ignoti quindi noi che cosa abbiamo?

00:25:49Abbiamo i nostri parametri raccogliamo tutti i

00:25:52parametri incerti in un vettore che chiamiamo Alfa.

00:25:55Genericamente quindi ci sarà Alfa

00:25:57uno il primo parametro incerto alfa due e il

00:25:59secondo nel caso dei eh dei del cammino minimo.

00:26:03Questo vettore alfa raccoglierà i J

00:26:05uno uno dopo l'altro va

00:26:07bene d'accordo e diremo che c'è una presentazione per poliedri

00:26:14se noi se definiamo un insieme di

00:26:18possibili realizzazioni attraverso un

00:26:21poliedro cioè Q che rappresenta

00:26:23in questo caso l'insieme delle possibili realizzazioni dei

00:26:27parametri incerti quindi del vettore alfa,

00:26:29è dato da tutti gli alfa che soddisfano quel sistema di equazioni

00:26:35lineari a alfa minore o uguale a g. H è una

00:26:39matrice con m vincoli e n colonne perché n il numero

00:26:44di parametri incerti e g è

00:26:47un vettore di m. Elementi dei termini noti.

00:26:49Chiaro, no? Io assumo che sia chiaro.

00:26:53Se non è chiaro, fermatemi.

00:26:55Ci siamo. Va bene H Alfa minore.

00:26:59G vuol dire non.

00:27:03Vogliamo Greco che io H che moltiplico per alfa

00:27:09e lo confronto con G. Ma io faccio prima riga per

00:27:14prima colonna lo confronto col primo

00:27:15G. E la prima equazione disequazioni lineari e

00:27:18così via tutte quanto che bene

00:27:20la rappresentazione mediante intervalli è

00:27:22un caso particolare perché ha tutte queste

00:27:24disequazioni qua CJ maggiore uguale di CG meno CJ minore uguale

00:27:28di CG più è un caso particolare

00:27:30va bene ogni punto in cui possiamo pensare.

00:27:33Dicevamo in quella generalizzazione un po anomala

00:27:35a ogni punto dentro questo poliedro

00:27:37come uno degli scenari e quindi

00:27:40come una delle possibili realizzazioni.

00:27:42Esempi Vedete che può avere senso.

00:27:45Supponete sempre di stare nel problema del cammino minimo,

00:27:48nel problema del cammino minimo.

00:27:49Io potrei dire va bene il costo per passare

00:27:53eh nel tratto tra le

00:27:56due rotonde di fronte all'ospedale, ce l'avete presente?

00:28:00No, è compreso tra un minimo e un massimo.

00:28:03Potrei dire va bene però potrei anche dire

00:28:06attenzione Che il fatto di passare con un certo

00:28:10tempo davanti all'ospedale dipende anche dalla.

00:28:14Dipende dalla congestione,

00:28:15ma la congestione si distribuisce in qualche modo.

00:28:18Okay, quindi è vero che è compreso tra un minimo e massimo,

00:28:21però se c'è tanta gente davanti all'ospedale ci sarà meno gente.

00:28:24Non lo so, eh.

00:28:26Nella strada che va dall'altra parte della rotonda,

00:28:31quindi se considero la rotonda come un nodo,

00:28:33posso dire che è vero che i costi per gli archi che escono

00:28:36dalla rotonda o che sono o C o B o A sono incerti,

00:28:41però la loro somma è minore o uguale di 15 perché la congestione si

00:28:44distribuirà e quindi se uno vale.

00:28:48Se il costo di attraversamento di un arco è dieci,

00:28:51la somma degli altri due non potrà essere dieci anche quelli.

00:28:54Okay, quindi vedete che sono un po

00:28:56più preciso nella rappresentazione,

00:28:59al costo di avere un poliedro un po più complesso rispetto al box.

00:29:02Va bene chiaro e altri esempi Va bene,

00:29:05questi sono gli archi entranti minore o uguale?

00:29:0715? É ABC?

00:29:09Ci sono nel ciclo ABC,

00:29:12i costi sono controllati,

00:29:14eccetera eccetera. Va bene.

00:29:15Chiaro?

00:29:16Quindi ci potrebbero essere delle relazioni

00:29:18ragionevoli che voglio rappresentare.

00:29:20E proprio così che i costi sono sempre minori, uguali a 15.

00:29:24La somma dei costi minori 15.

00:29:26Forse no, però è un

00:29:29modo di rappresentarli e se mi fa comodo lo metto

00:29:32a disposizione per rendere più

00:29:34fedele possibile il mio modello di incertezza al modello,

00:29:36ovvero all'incertezza.

00:29:38Va bene. Un particolare poliedro

00:29:41che vi voglio é che vi voglio citare.

00:29:45Scusate ma sto cercando un caricatore per

00:29:49la mia lavagnetta che però non trovo e

00:29:55quindi faremo a meno se serve.

00:29:57E supponete di avere e il poliedro di cose che.

00:30:01Poliedro è importante perché può essere utile in

00:30:05diversi casi e rappresenta una situazione di incertezza che

00:30:08può essere ragionevole.

00:30:10L'esempio qual è? Pensate a una rete di trasporto.

00:30:13Una rete di telecomunicazione viene un po più semplice come

00:30:17esempio rete telecomunicazione vuol dire che voi avete dei nodi.

00:30:20Questi nodi devono comunicare tra loro.

00:30:22Okay, e per ogni coppia di

00:30:25nodi avete definito quanto traffico c'è, no?

00:30:28Quindi immaginate di questi nodi sono router di internet.

00:30:32Voi sapete che tendenzialmente tra Padova e Milano ci si

00:30:34scambia un certa quantità di dati che tra

00:30:37Padova e Torino un'altra quantità tra Padova e Roma un'altra

00:30:40quantità tra Roma e Bari un'altra quantità

00:30:42tra Bari e Milano un'altra quantità.

00:30:44Questo vuol dire che abbiamo un insieme di coppie origine

00:30:46destinazioni e abbiamo una richiesta di comunicazione.

00:30:50Dal nodo dall'origine alla destinazione di questa coppia

00:30:53quindi H mi definisce l'indice della coppia okay.

00:30:58Qual è l'incertezza che abbiamo

00:31:01qui l'incertezza è questa qui io posso dire io non so

00:31:04esattamente quanti dati devo comunicare tra

00:31:07Padova e Bari e tra Padova e Milano,

00:31:10tra Padova e Roma.

00:31:12Ok però so

00:31:13che Padova ha una certa

00:31:15dimensione quindi sicuramente il la quantità

00:31:18di traffico che genera Padova genererà Padova indipendentemente da

00:31:23dove è destinata e compresa tra un minimo e un massimo.

00:31:27Okay, non so esattamente come si distribuirà.

00:31:30Qui c'è l'incertezza, non solo la domanda come andrà a finire,

00:31:33ma so che la somma delle domande uscenti da una certa origine

00:31:37è minore o uguale di un massimo definito ed è. E

00:31:43so anche che la quantità di

00:31:46eh di dati richiesti da una certa destinazione

00:31:52tutto ciò che arriverà a Torino Torino

00:31:54a certe dimensioni quindi non potrà

00:31:56richiedere il traffico che

00:31:58arriva e sicuramente sotto un certo limite superiore.

00:32:01Okay, quindi ho questi vincoli che sono vincoli lineari,

00:32:04quindi mi definiscono un poliedro.

00:32:05Se li metto tutti insieme e hanno

00:32:08questa struttura la somma delle domande su tutte ehm che ha dato

00:32:14un nodo la somma delle domande che hanno origine in quel nodo deve

00:32:18essere è limitata da una per bound noto oppure e o.

00:32:24La somma delle domande che arrivano

00:32:27in una certa destinazione è limitata da una per bound nodo.

00:32:30Va bene? Chiaro? Ci siamo.

00:32:32Questo è il poliedro di Oz.

00:32:35Qui c'è un esempio,

00:32:37ma mi sa che l'abbiamo capito.

00:32:39Va bene, ci siamo.

00:32:42Quindi la domanda generata dopo verso ciascuna

00:32:44destinazione incerta.

00:32:45Sappiamo solo che il totale è al massimo uno.

00:32:48La domanda generata da ciascuna origine

00:32:50verso la destinazione T è incerta,

00:32:52sappiamo solo che il totale è al massimo due.

00:32:54Ok, va bene, quindi io vorrò trovare delle

00:32:58soluzioni che si comportano bene o il meglio possibile.

00:33:01Considerando che non so se la domanda che arriva

00:33:05in o è da ciascuna,

00:33:08non so come si distribuisce la domanda che arriva o

00:33:10no ma ma so che la loro somma e al massimo quindi per tutte

00:33:14le possibilità che mi dicono che quella somma

00:33:16è massimo uno voglio trovare

00:33:17la soluzione che va che mi va bene ok questo è il progetto di cose.

00:33:21Adesso vedete che qui ribadisco quello che ho detto

00:33:25allora c'è la parola modello tra virgolette per

00:33:29dire che anche l'incertezza va modellata in

00:33:31un problema sottoposto a incertezza anche l'incertezza

00:33:35è un qualcosa che noi dobbiamo modellare.

00:33:37La scelta della modalità di rappresentazione

00:33:40dell'incertezza è un compromesso tra la natura

00:33:42dell'incertezza la natura del

00:33:43problema e la possibilità di modellare

00:33:45il problema e di trattarlo con metodi di soluzione.

00:33:49E una scelta modellistica che,

00:33:51come tutte le scelte modellistiche, semplificano la realtà.

00:33:53Va bene, l'ho già detto,

00:33:55lo ribadisco E ribadisco anche che tutto

00:33:59ciò che abbiamo visto finora sono alcune

00:34:01delle modalità quelle più promettenti,

00:34:03perché chi ha studiato queste cose ha

00:34:05visto che in quei casi si riesce

00:34:07a fare molto e inoltre quei casi riescono

00:34:11a rappresentare un sacco di situazioni incerte

00:34:13in un modo abbastanza fedele.

00:34:15Va bene? Chiaro? Okay, quindi il primo punto per definire

00:34:22la controparte robusta o

00:34:24stocastica è scegliere la

00:34:26modalità di rappresentazione dell'incertezza.

00:34:28L'altro punto è avere dei criteri e dei modelli di robustezza,

00:34:33poi vedremo quelli nel caso stocastico.

00:34:35Quindi adesso entriamo più nelle cose proprie della ottimizzazione

00:34:38robusta e cerchiamo di stabilire dei criteri e dei modelli

00:34:42per la robustezza.

00:34:44Allora lo schema è il seguente abbiamo il caso nominale

00:34:49per per i nostri ragionamenti adesso

00:34:51fissiamo un problema di minimizzazione

00:34:53visto che poi parleremo del problema del

00:34:54costo del cammino minimo che

00:34:56quindi immaginiamo il nostro problema sia di minimizzazione.

00:34:59Okay quindi il caso nominale in generale è quella roba lì.

00:35:03Minimizzare una funzione obiettivo

00:35:05su un insieme su è ammissibile F sta per ok,

00:35:11quindi voglio trovare la x che sta in

00:35:14un insieme F e che tra tutte quelle dell'insieme F corrisponde

00:35:19al minimo di una certa funzione CDX questa molto

00:35:22generale un problema di ottimizzazione di minimo un caso

00:35:25nominale che ci f sono rossi perché Perché CF potrebbero

00:35:30essere sottoposti a incertezza cioè.

00:35:33In C e in F ci sono dei

00:35:36parametri che possiamo mettere nel nostro vettore

00:35:38alfa fatto di n parametri che sono incerti

00:35:41okay e che quindi definiscono incertezza su C e o su F,

00:35:48e noi vogliamo trovare una

00:35:50controparte robusta che tenga conto di queste incertezze.

00:35:53Allora abbiamo detto, considereremo

00:35:55la robustezza in senso assoluto o in senso relativo.

00:35:58Ribadisco quello che ho detto prima che io e ribadisco e

00:36:03inoltre vado a fissare dei limiti entro i quali ci muoviamo,

00:36:07che come al solito non è che siano tutti possibili limiti,

00:36:10però ci concentriamo su questi casi.

00:36:12La robustezza in senso assoluto abbiamo

00:36:14detto cosa vuol dire vuol dire che noi cerchiamo una

00:36:17soluzione di compromesso che sia la migliore possibile considerando

00:36:22la soluzione in tutti i possibili

00:36:24scenari che vogliamo considerare che

00:36:27indipendentemente dalle altre soluzioni nello stesso

00:36:29scenario e valuteremo situazioni in

00:36:32cui l'incertezza si ferma alla funzione

00:36:35obiettivo quindi parametri Alfa incerti

00:36:38sono tutti dentro C ok oppure tutti i

00:36:43parametri incerti sono dentro F Ok.

00:36:48Chiaramente questo non è che vuol

00:36:49dire che sono tutti possibili casi.

00:36:50Ci sono casi in cui l'incertezza sia a livello di funzione

00:36:52obiettivo sia a livello di regione ammissibile.

00:36:55Quei casi sono ancora più complicati di quelli che vediamo.

00:36:58Insomma, non è che possiamo fare tutto noi.

00:37:00Poi se volete facciamo un altro corso, va bene.

00:37:03E inoltre considereremo dei casi di robustezza

00:37:07in senso assoluto con parametro di controllo che attenzione,

00:37:10che non vuol dire in senso relativo.

00:37:12Abbiamo già spiegato spero che sia chiaro questo è sempre in

00:37:16senso assoluto perché io ogni alternativa ogni possibile soluzione

00:37:20la considero in tutti gli scenari questo vuol dire

00:37:24è indipendentemente dalle altre soluzioni

00:37:27quindi è una robustezza in

00:37:28senso assoluto con parametro di

00:37:30controllo vuol dire che magari anziché considerare tutti i

00:37:33possibili scenari ne considero una certa

00:37:35percentuale come il caso del contadino che avevamo visto.

00:37:38Nel caso del contadino avevamo detto qual è la migliore

00:37:40soluzione che massimizza il minimo tra tutti gli scenari?

00:37:44Ok, e la robustezza

00:37:47in senso assoluto con un livello di protezione massimo.

00:37:50Poi avevamo detto qual è la soluzione che

00:37:51minimizza che massimizza il caso

00:37:53peggiore in

00:37:55due scenari su tre vedete che abbiamo questo parametro due su 03:01

00:37:58parametro di controllo che rende

00:38:00un pochino meno forte la richiesta.

00:38:03A un livello di conservatorismo più blando un

00:38:07livello di di protezione più basso ma sempre stiamo parlando

00:38:11di robustezza in senso assoluto perché ogni soluzione

00:38:13è valutata per sé dentro gli scenari non in confronto con altro.

00:38:18Perché poi vedremo anche robustezza in

00:38:19senso relativo in cui ogni soluzione

00:38:22considererà anche il cosa

00:38:25perdo cosa guadagno rispetto alle altre soluzioni?

00:38:27Nello stesso scenario abbiamo visto il

00:38:30mancato guadagno o nei problemi di minimo si chiama minimum,

00:38:33che vuol dire?

00:38:35Io di quanto mi pento se cerco questa soluzione?

00:38:39Ma pentirsi vuol dire rispetto a un'altra scelta.

00:38:41Ecco perché in senso relativo okay accordo,

00:38:44differenza tra senso assoluto quindi sempre di robustezza stiamo

00:38:47parlando in senso assoluto in

00:38:49senso relativo e i casi che considereremo.

00:38:51Va bene, quindi cominciamo con il primo caso robustezza in

00:38:56senso assoluto e incertezza limitata alla funzione obiettivo.

00:39:01Va bene, quindi come

00:39:03al solito pensiamo all'incertezza rappresentata per scenari,

00:39:08se non altro a livello concettuale.

00:39:10Okay quindi anche gli altri casi per

00:39:12il momento pensiamo per scenari infiniti scenari se serve.

00:39:15E quindi ci sono esse possibili e se l'insieme degli scenari.

00:39:20Ogni scenario lo rappresenteremo con S.

00:39:23Piccolo e cos'è un piccolo e

00:39:25una possibile realizzazione dei

00:39:28del vettore Alfa dei parametri incerti.

00:39:31Okay quindi questi sono gli

00:39:33scenari e quindi abbiamo è come se avessimo una regione ammissibile

00:39:36attenzione sto utilizzando questo termine apposta

00:39:38per cercare di confondervi con la seconda riga,

00:39:41ma per chiarire che son cose diverse.

00:39:43Io ho una un insieme di possibili Realizzazioni dei parametri.

00:39:47È come se definisci una regione ammissibile dei

00:39:50parametri che non è la regione ammissibile del problema.

00:39:53Okay, nel problema del cammino

00:39:55minimo la regione ammissibile sono tutti i possibili cammini.

00:39:58F è la regione ammissibile del problema,

00:40:02tutti i possibili cammini e invece S grande

00:40:06e l'insieme delle possibili

00:40:08realizzazioni che sono due cose diverse.

00:40:11CDX la funzione obiettivo

00:40:14nominale che dipende dal parametro alfa e csx Che cos'è?

00:40:20È la funzione obiettivo valutata per la soluzione

00:40:23x in corrispondenza della realizzazione S dei parametri incerti.

00:40:28Va bene caro, come notazione penso che sia semplice,

00:40:31però la prima volta che la vediamo,

00:40:32quindi cerchiamo di acquisirla.

00:40:3510 secondi la acquisite e andiamo avanti.

00:40:40Va bene, allora come posso.

00:40:45definire un problema

00:40:47incerto con robustezza un problema di ottimizzazione robusta

00:40:52in senso assoluto con questi.

00:40:54Con questa notazione che criterio utilizziamo?

00:40:58Normalmente utilizziamo un criterio di tipo minimax che

00:41:03è lo stesso criterio maximin che abbiamo visto per

00:41:05i problemi di massimizzazione.

00:41:07Il problema di minimizzazione quindi vogliamo

00:41:10la soluzione che minimizza

00:41:12il caso peggiore il caso peggiore è un massimo no.

00:41:15Il costo massimo negli scenari.

00:41:17Attenzione vedete che qui è come se avessimo due

00:41:20ottimizzazioni che interagiscono. È chiaro.

00:41:24Quindi vogliamo trovare qual è il ragionamento qui.

00:41:30Sperando che.

00:41:34Vogliamo trovare che cosa?

00:41:38No. Zero otto.

00:41:55Cerotto, purtroppo.

00:41:57Cerotto. Non ho il caricatore.

00:42:03Allora cosa vogliamo trovare?

00:42:06Vediamo un po. Vogliamo trovare la soluzione migliore?

00:42:12Cosa vuol dire migliore?

00:42:14Vuol dire Come valuto la soluzione X?

00:42:16Risolvendo un altro problema se volete,

00:42:18cioè andando a vedere la X quanto costa in ogni scenario

00:42:23e scegliendo come valuta di quella X il caso peggiore.

00:42:28Okay, va bene.

00:42:31Quindi dato un X

00:42:33lo valorizzo col suo caso peggiore in tutti gli scenari.

00:42:36Considero tutti gli X nella regione ammissibile e scelgo quello che

00:42:40ha il minor caso peggiore il minor costo nel caso peggiore.

00:42:45Nel caso peggiore che vedete,

00:42:48che è il caso peggiore, dipende solo da X, da nessun altro.

00:42:51Ecco perché la robustezza in senso assoluto è chiaro,

00:42:54dipende da x e da S e non da altre soluzioni.

00:42:57Va bene, ci siamo. Facile, no?

00:43:00Relativamente facile.

00:43:02Il criterio è molto conservativo, molto pessimistico.

00:43:04Perché? Perché abbiamo pessimismo.

00:43:06Noi diciamo qualsiasi sia la soluzione che io scelgo,

00:43:09questa si comporterà il peggio possibile.

00:43:12Succederà la cosa peggiore per quella soluzione lì.

00:43:14Eh, Mamma mia quanto sei pessimista.

00:43:16Vabbè, però voglio essere sicuro che

00:43:18non voglio, non voglio rischiare,

00:43:21Mi accontento di guadagnare poco,

00:43:24o meglio qui di spendere magari un pochino di più.

00:43:27Però son sicuro che se esco con il portafoglio,

00:43:32qualsiasi cosa succeda, riesco a pagare.

00:43:34E se sei un problema di cammino minimo ad esempio, ecco.

00:43:38E i costi sono la batteria che consumo.

00:43:41Magari a me non interessa tanto consumare meno batteria possibile.

00:43:46Alle volte sì, ma alle volte mi interessa

00:43:48essere sicuro di arrivare dove devo arrivare.

00:43:51Quindi voglio capire se la batteria che ho,

00:43:54se c'è un cammino che è fattibile con la batteria che ho

00:43:57in qualsiasi situazione.

00:43:59Okay, quindi vado a vedere qual è il costo più

00:44:01basso di una soluzione,

00:44:04tenendo conto che quella soluzione potrà spendere.

00:44:07Si realizzerà la situazione peggiore per quella soluzione

00:44:10lì e quindi funzionerà in tutti gli scenari.

00:44:13Va bene caro Max,

00:44:16un esempio avevamo già visto quello del contadino.

00:44:19Ripeto, siamo in una situazione nella quale vedete,

00:44:21gli scenari dipendono solo dalla funzione obiettivo,

00:44:25quindi tutti i parametri incerti che stanno dentro Alfa sono

00:44:30influenzano la funzione

00:44:31obiettivo mentre lasciano invariata la Regione ammissibile questa

00:44:34è un'altra cosa importante che la Regione ammissibile,

00:44:37vedete, è sempre la stessa non

00:44:40dipende dagli scenari che

00:44:42dipendono gli scenari solo il costo va bene.

00:44:45Abbiamo avuto questo mi può aiutare un po ok va bene.

00:44:51Un esempio l'avevamo visto il problema del contadino, eh.

00:44:54Le rese erano in tre scenari e

00:44:57quindi volevamo il massimizzare il minimo.

00:44:59Data una XL XP data una una soluzione

00:45:03si valorizzava col minimo guadagno in

00:45:06tutti gli scenari che avevamo visto che

00:45:08questo era un problema che comunque era un problema

00:45:10facile che rimaneva facile in

00:45:11questo caso particolare perché

00:45:13riuscivamo a linearizzare la funzione obiettivo.

00:45:15Va bene ci siamo questo ve lo ricordate

00:45:17Andiamo al nostro esempio cosa

00:45:20vuol dire un cammino minimo robusto in

00:45:22senso assoluto okay cosa vuol dire.

00:45:27Allora adesso vedremo che come

00:45:29si realizza come definiamo la controparte robusta dipende da come

00:45:34rappresentiamo l'incertezza okay quindi stiamo dicendo

00:45:39il problema nominale il problema del cammino minimo come criterio

00:45:43per capire qual è la migliore soluzione.

00:45:45Stiamo utilizzando un criterio di robustezza in

00:45:47senso assoluto e vogliamo minimizzare il costo massimo del cammino

00:45:53in un qualsiasi situazione incerta.

00:45:56Ma come rappresentiamo le situazioni incerte?

00:45:58Esempio consideriamo l'incertezza per scenari

00:46:01e ci mettiamo nel caso degli scenari,

00:46:03proprio dove abbiamo pochi scenari.

00:46:05Pochi vuol dire un numero finito, un numero controllabile.

00:46:091015203040.

00:46:11Insomma un numero trattabile di scenari.

00:46:15Okay, allora cosa vuol dire che il X è un X? Cos'è in questo?

00:46:20In questo caso è un cammino F La regione

00:46:23ammissibile F è fatta da tutti i possibili cammini, okay?

00:46:26E X è uno di questi cammini

00:46:28e possiamo associare a ciascuno di questi

00:46:30cammini un costo per ogni scenario.

00:46:33Quindi abbiamo dei costi possibili.

00:46:35Okay, quindi come valorizziamo il

00:46:38singolo cammino attraverso il

00:46:39massimo tra tutti questi costi con lo scenario

00:46:42peggiore lo scenario peggiore.

00:46:43Ovviamente dipende dal cammino che ogni cammino

00:46:47avrà un suo caso peggiore sarà valorizzato dal caso peggiore.

00:46:50Ora riusciamo

00:46:54a risolvere questo problema facilmente o difficilmente?

00:46:57Vediamo cosa succede.

00:46:58Quindi proviamo

00:47:00ad aiutarci sempre con la programmazione matematica.

00:47:03Okay quindi adesso io vi insieme cerchiamo di sviluppare

00:47:06anzi lo guardiamo direttamente che facciamo prima.

00:47:10Cerco di convincervi che questo è il modello

00:47:14per il cammino minimo in senso assoluto.

00:47:19Cammino minimo robusto in

00:47:21senso assoluto con un certo numero di scenari.

00:47:24Nell'esempio ne abbiamo solo due,

00:47:26giusto per riuscire a scrivere.

00:47:28Va bene, ci siamo.

00:47:29A me gli occhi. Allora cosa succede?

00:47:32Vedete che qui abbiamo la funzione obiettivo

00:47:34quale sarebbe Sarebbe minimizzare

00:47:37il massimo quindi minimizzare il massimo tra due possibili costi.

00:47:44Se fossero tre quattro scenari avremmo tre quattro componenti tra

00:47:48le parentesi graffe va bene.

00:47:50Quindi minimizzare y dove y è il massimo tra il costo del

00:47:54cammino X. Nello scenario

00:47:56uno il costo del cammino X nello scenario due e così via.

00:47:59Fai attenzione che questo

00:48:02massimo dipende dallo scenario

00:48:05e funziona data una certa X. Vi ricordate?

00:48:09No? Come risolviamo qui?

00:48:11Da un punto di vista concettuale, cosa stiamo dicendo?

00:48:13Vogliamo trovare il minimo y dove y è definito? Da che cosa?

00:48:19Dal massimo tra due valori e questi valori li calcoli

00:48:22in funzione di x?

00:48:23E che cosa x è uno dei possibili cammini?

00:48:26La regione ammissibile E vi ricordate

00:48:28che possibili cammini erano rappresentati dai vincoli di flusso?

00:48:31No. Vi ricordate sì o no? Ci siamo.

00:48:34Perfetto. Quindi questa

00:48:37è una rappresentazione di un problema di

00:48:38programmazione matematica un po strano.

00:48:41Vedete che abbiamo una funzione obiettivo

00:48:44e tra i vincoli abbiamo un altro problema di ottimizzazione.

00:48:48Qual è la differenza tra il primo minimo e questo

00:48:51problema di ottimizzazione che sta dentro i

00:48:54vincoli che il problema di ottimizzazione che sta dentro i

00:48:56vincoli dobbiamo risolverlo per un dato x.

00:49:00Okay qui stiamo minimizzando su

00:49:03x. Qui stiamo massimizzando sugli scenari.

00:49:06È la stessa definizione che abbiamo qui che.

00:49:10Minimizza su X,

00:49:13ma la valorizzazione delle X dipende dalla

00:49:17soluzione di un altro problema di ottimizzazione

00:49:19in cui x è fissato e variano gli scenari.

00:49:22Siete d'accordo? Sì o no?

00:49:24Sì o no? Se non mi dite tutti sì, non vado avanti.

00:49:28Okay. Okay. Perché è importante che poi faremo

00:49:33ragionamenti simili quindi insomma qui che la

00:49:35prima volta vorrei che fosse chiaro.

00:49:38Come risolviamo questo problema qua?

00:49:40Allora questo è un problema.

00:49:41Allora lasciate da parte

00:49:44le note blu okay per un momento lasciatele da parte.

00:49:49Come risolviamo un problema di questo tipo.

00:49:51Però un problema di questo tipo

00:49:53se andiamo da qualcuno che capisce di

00:49:56ottimizzazione lo chiama problema di ottimizzazione B livello.

00:50:00Vabbè lo sa risolvere.

00:50:02Cioè lo sa risolvere bene però prima di.

00:50:04Perché perché B livello perché abbiamo

00:50:06due livelli di ottimizzazione no.

00:50:08C'è un problema che ottimizza su su sulle

00:50:11x e un altro problema che ottimizza su un altro spazio.

00:50:14Data la x che e questi problemi interagiscono uno

00:50:18dentro l'altro cioè il problema

00:50:20leader è il problema follower leader e

00:50:22trovare il cammino migliore e il follower

00:50:24è quello che ci valorizza ogni cammino va bene.

00:50:27La gerarchia è chiara?

00:50:29Sì, benissimo.

00:50:31In realtà in questo caso forse siamo un po fortunati,

00:50:34perché possiamo trasformare questo problema di

00:50:36ottimizzazione di livello in un problema

00:50:39a un livello solo perché dire che Y

00:50:41è il massimo tra questi due valori cosa vuol dire?

00:50:43L'avevamo visto l'altra volta che Y

00:50:45è maggiore o uguale del costo nel primo scenario ed

00:50:49è anche contemporaneamente maggiore o

00:50:50uguale del costo nel secondo scenario.

00:50:52Quindi possiamo togliere.

00:50:55Eh già,

00:50:58possiamo togliere questo vincolo e lasciare questi

00:51:03due okay e quindi

00:51:04abbiamo un problema di programmazione

00:51:06matematica come li conosciamo noi in cui abbiamo

00:51:08dei vincoli dei vincoli lineari qua questi son

00:51:12dei vincoli lineari delle variabili

00:51:14intere e degli altri vincoli lineari.

00:51:18Sei d'accordo? Okay.

00:51:19Quanti vincoli ci sono tanti

00:51:21quanti sono gli scenari ma gli scenari abbiamo detto che sono

00:51:23in un numero trattabile quindi

00:51:24lo possiamo scrivere sotto

00:51:25questo problema possiamo implementarlo in AMP.

00:51:28Okay, questo problema.

00:51:31Quindi tolto il livello,

00:51:33avendolo messo in un livello solo,

00:51:35è un problema facile o difficile secondo voi?

00:51:41Parlate, parlate direttamente.

00:51:45Se i coefficienti delle x

00:51:50e i termini noti sono uno meno uno, forse potevamo rilassare.

00:51:55Cosi posso fare un passo indietro.

00:51:58Faccio un passo indietro. Il passo indietro

00:52:01è che questo è un problema di programmazione lineare intera, vero?

00:52:05I vincoli sono tutti lineari e abbiamo però le variabili intere.

00:52:11Quindi, in linea di principio un problema difficile.

00:52:14Però giustamente qualcuno dice sì,

00:52:16però i vincoli sono abbastanza semplici

00:52:19per cui abbiamo visto sicuramente

00:52:22se non ci fossero questi vincoli

00:52:24qua quelli che abbiamo aggiunto per

00:52:26tener conto che Y deve essere maggiore uguale

00:52:28eccetera eccetera se non ci fossero questi vincoli qua.

00:52:31Quindi se la Regione ammissibile fosse

00:52:33definita dagli dall'insieme dei

00:52:34cammini potremmo rilassare l'interezza e risolverlo

00:52:38come se fosse un problema la variabili

00:52:40continue vero e quindi diventerebbe facile.

00:52:43La domanda è possiamo rilassare l'interezza o

00:52:46no perché abbiamo aggiunto dei vincoli anche

00:52:50se sono semplici abbiamo aggiunto

00:52:51dei vincoli che hanno cambiato la struttura del poliedro vero.

00:52:56Quindi vale ancora questa possibilità di di rilassare vediamo

00:53:01così lo vediamo una volta e ci rendiamo conto vediamo.

00:53:04Allora io ho implementato questi modelli

00:53:06apro un po nella mia interfaccia che

00:53:10è un po più facile e il modello implementato qui

00:53:12vedete qua c'è cammino un minimo robusto per scenari vedete che

00:53:17c'è sono le variabili ho definito la variabile per il min max,

00:53:21quindi voglio minimizzare ma minimizzare

00:53:25y con Y che

00:53:27è maggiore o uguale del costo

00:53:28di un certo cammino nello scenario uno.

00:53:30Qui ho messo i costi nello scenario uno,

00:53:32qui ho messo i costi nello scenario due e poi ho messo i vincoli,

00:53:36quelli soliti per dire è un cammino.

00:53:38Ci siamo, Quindi questo è P. E questi sono i vincoli aggiuntivi.

00:53:42Risolviamo il problema.

00:53:43Per risolvere il problema ho preparato questo file

00:53:47run nel quale carico il modello e risolvo.

00:53:51Va bene, ci siamo.

00:53:53Quindi vado e quindi faccio

00:53:56include cms run e ottengo la soluzione ottima.

00:54:03Vedete, ovviamente la ottengo e usa il branch bound,

00:54:06quindi vuol dire che lo sta trattando come

00:54:07problema di programmazione lineare intera.

00:54:09Difficile. Ok, uno dice va bene,

00:54:12però mi sembra abbastanza semplice quindi forse rilassando,

00:54:17quindi dicendo option Relax.

00:54:20Avevamo visto queste cose ieri no option relax

00:54:24integrali integrali t1 dicendo va bene,

00:54:29fai finta che le variabili sono continue,

00:54:32modello lineare trattalo come un problema facile e risolvi lo.

00:54:37Okay? E cosa succede?

00:54:40Ahia. Le variabili sono frazionate.

00:54:43L'aggiunta di quei due vincoli ci ha sparigliato tutto.

00:54:48Ha reso il problema difficile.

00:54:50Non è che basta questo per dire che il problema è difficile,

00:54:53Però questo è un indice del fatto che il problema non è facile

00:54:57quanto prima e si può dimostrare che il problema

00:54:59è difficile perché abbiamo rovinato il poliedro.

00:55:02Chiaro? Per i matematici all'ascolto cosa succede?

00:55:08Che hanno già i matematici,

00:55:10Però non ho la penna oggi, mannaggia.

00:55:13Che il poliedro p. È fatto in questo modo?

00:55:17No, il poliedro è un poliedro fatto così.

00:55:21Senza quelle robe? Senza quelle robe in mezzo, ovviamente.

00:55:26E in quel poliedro i vertici son

00:55:29garantito che tutti questi vertici

00:55:31abbiano componenti intere. Va bene.

00:55:34Ecco perché era facile risolverlo,

00:55:36anche se faccio finta che le variabili sono reali.

00:55:38Comunque trovo un vertice intero e sono felice facilmente.

00:55:41Chiaro? Abbiamo già detto,

00:55:42ma lo ripeto, cosa succede quando aggiungo questi vincoli,

00:55:46questi vincoli è come dire ho dei vincoli in

00:55:48più questi vincoli qua per

00:55:50esempio no quindi anzi questi vincoli mi

00:55:54dicono che adesso i vertici del poliedro dove potrei trovare la

00:55:57soluzione ottima sono questo che è

00:56:00rimasto intero questo eh ma questo intero boh non lo so

00:56:05e non lo è perché abbiamo visto che alle volte non lo

00:56:07è. Eh, sono diventati questo.

00:56:10Vedete che è cambiato il poliedro?

00:56:11Alcuni vertici son rimasti, altri no.

00:56:14Quindi, a seconda della direzione di

00:56:15ottimizzazione potrò ottenere un vertice intero oppure no.

00:56:18Quindi sono nel caso della programmazione lineare intera generale e

00:56:23quindi diventa difficile va bene.

00:56:25Chiaro quindi questo è un caso in cui abbiamo definito un problema.

00:56:29Siamo partiti da un problema facile e abbiamo definito

00:56:31una controparte robusta quale la controparte robusta.

00:56:34Problema nominale il cammino minimo

00:56:36controparte robusta cammino minimo robusto in

00:56:38senso assoluto con incertezza definita per

00:56:41scenari e la controparte robusta

00:56:44in questo caso è difficile, chiaro.

00:56:47Va bene, ci siamo sì o no?

00:56:51Perché Se sì, vado avanti,

00:56:52altrimenti vado avanti lo stesso. Va bene?

00:56:55Perfetto.

00:56:57Quindi queste cose era ora

00:57:00consideriamo sempre posso andare avanti perché adesso faccio

00:57:05un altro esempio di un'altra controparte robusta in

00:57:06senso assoluto con la stessa funzione obiettivo

00:57:10Min max ma cambia solo la

00:57:12modalità di rappresentazione dell'incertezza,

00:57:14l'incertezza rappresentata da intervalli.

00:57:16In questo caso vediamo se il problema è più facile,

00:57:19più difficile rispetto a prima.

00:57:21Allora, se l'incertezza è

00:57:24rappresentata da intervalli, cosa posso fare?

00:57:27Intervalli vuol dire che ogni costo

00:57:29è compreso tra un minimo e un massimo.

00:57:30Va bene, allora vedete che posso di nuovo

00:57:33tornare a una formulazione di programmazione matematica.

00:57:36Allora parto dalla mia solita formulazione B livello in cui voglio

00:57:41minimizzare y. Y lo minimizzo facendo variare x,

00:57:48cioè considero tutti i possibili cammini X appartenente

00:57:52a B vuol dire soddisfo quei vincoli per cui X è un cammino.

00:57:55Ci siamo, va bene e dico che la Y,

00:57:59data la x e il massimo su tutti i possibili costi,

00:58:03su tutte le possibili realizzazioni dei costi.

00:58:05Di che cosa? Del costo di quel cammino che è dato dalla

00:58:08somma c j x J. Siete d'accordo?

00:58:11Okay, dove ci sei in

00:58:15questo problema di secondo livello è come se

00:58:18la variabile fosse fossero i

00:58:20costi perché devo considerare tutte

00:58:22le possibili realizzazioni e quali

00:58:23sono tutte le possibili realizzazioni quelle in cui

00:58:26c'è Ciascun costo è compreso tra un minimo e un massimo.

00:58:29Sei d'accordo? Quindi se riesco

00:58:31a risolvere questo problema ho

00:58:32risolto il problema del cammino minimo robusto

00:58:34in senso assoluto con,

00:58:36devo ancora dire incertezza rappresentata per intervalli.

00:58:40Ok, quindi potrei risolvere questo problema a livello.

00:58:44Però se vado da un mio tecnico

00:58:47di ottimizzazione dico me lo risolvi a me guarda però

00:58:50ragioniamo un attimo cosa vuol dire data

00:58:53la X risolvere questo problema di secondo livello.

00:58:57In realtà la soluzione la vedo a occhio subito,

00:59:00non c'è, non c'è la data x.

00:59:02La sua valorizzazione peggiore avverrà quando

00:59:05tutti ci assumeranno il valore più alto possibile, cioè l'accordo.

00:59:10Quindi per trovare la data la x per

00:59:13trovare Y non c'è

00:59:14bisogno di risolvere un problema di ottimizzazione.

00:59:16Sicuramente Y sarà uguale a questa espressione qua. Sei d'accordo?

00:59:22Cioè Y e la somma su sul su tutti gli archi di XJ,

00:59:28cioè capire se quell'arco fa parte o

00:59:30meno del cammino che stai valutando per il

00:59:32costo massimo possibile su quegli su quell'arte sei d'accordo?

00:59:36Okay quindi posso sostituire al problema

00:59:40di secondo livello semplicemente il

00:59:43fatto che Y è la

00:59:44somma sugli su su sulle x

00:59:47j. Considerando il costo più alto possibile, okay.

00:59:51E quindi secondo me vuol dire minimizza Y,

00:59:54ma y so che è la somma di J più per x

00:59:57j sul poliedro che rappresenta i cammini ammissibili sei d'accordo?

01:00:03Quindi siete d'accordo che risolvere il

01:00:05problema del cammino minimo robusto in

01:00:07senso assoluto con incertezza rappresentata mediante intervalli.

01:00:11E assolutamente equivalente

01:00:13a risolvere un problema di cammino minimo semplicemente

01:00:16considerando come costi il più alto valore nell'intervallo.

01:00:20Va bene, e questo è un problema facile o difficile.

01:00:24Problema facile è facile come problema di

01:00:26un cammino minimo e diventando un problema di cammino minimo in

01:00:28cui è come se fosse nominale tra virgolette con.

01:00:33Semplicemente considerando una certa

01:00:35particolare realizzazione dei costi.

01:00:37Va bene, è chiaro.

01:00:39Quindi vedete che lo stesso

01:00:40problema nominale ha una controparte robusta,

01:00:43difficile da risolvere se l'incertezza è la

01:00:47stessa controparte robusta dal punto di

01:00:49vista del criterio di ammissibilità e ottimalità,

01:00:52ma è diversa perché è una rappresentazione diversa dell'incertezza

01:00:55ed è difficile con incertezza rappresentata per

01:00:59scenari facile o rappresentata con incertezza rappresentata per

01:01:02intervalli perché perché sfrutto delle

01:01:05proprietà del modello che posso risolvere.

01:01:07Va bene, okay, d'accordo.

01:01:11Quindi va bene quindi lo facciamo.

01:01:15Alla fine se no non ci arriviamo.

01:01:16Chiaro? Vado avanti.

01:01:21Vabbè, è inutile che ve lo mostri.

01:01:24Vi fidate di me, no?

01:01:26Quindi cammino minimo robusto su questa rete particolare.

01:01:30Lo risolvo.

01:01:31Come? Andando? Risolvo il problema del cammino minimo normale in

01:01:35cui avrò come costi quelli più alti possibili. Va bene?

01:01:43Bene. Ci siamo. Vado avanti.

01:01:56Consideriamo ancora un'altra controparte

01:01:59robusta del problema del cammino minimo.

01:02:00Quindi fin qui abbiamo detto

01:02:02che abbiamo visto cammino minimo robusto abbiamo

01:02:06come funzione obiettivo quindi incertezza sulla funzione

01:02:09obiettivo e abbiamo detto criterio Min Max ok

01:02:13fermiamoci lì rappresentazione per per scenari problema diventa

01:02:17difficile rappresentazione con intervalli di incertezza rimane

01:02:24facile con la regola che abbiamo visto che queste son cose

01:02:27che vi chiedo di ricordare che in qualche modo a me

01:02:30piacerebbe che voi foste in

01:02:32grado anche di fare dei semplici ragionamenti

01:02:34per dire rimane facile per

01:02:35questo motivo qui perché se risolve

01:02:38il problema lo posso rappresentare con un modello di

01:02:40questo tipo e con questo ragionamento diventa

01:02:43facile oppure con questo ragionamento rimane difficile.

01:02:47Okay, vado avanti adesso consideriamo lo stesso

01:02:51problema con un'altra rappresentazione dell'incertezza

01:02:54incertezza su poliedri

01:02:56okay allora se l'incertezza sui poliedri facciamo un esempio.

01:03:02Quindi il problema del cammino minimo,

01:03:04robusto in senso assoluto e l'incertezza, ad esempio,

01:03:08è rappresentata dal fatto che

01:03:11i costi sono noti ma non in modo deterministico,

01:03:18non in modo preciso.

01:03:20Sappiamo che devono soddisfare

01:03:22dei vincoli lineari che

01:03:24interessano tutte le possibili realizzazioni dei costi in

01:03:27cui la somma di costi l'abbiamo

01:03:30già commentate queste cose qua va bene?

01:03:33Come risolvo questo problema?

01:03:36Allora se ci pensate io questo problema lo posso risolvere.

01:03:41Un po ritornando al concetto generale di scenari, no?

01:03:46Vi ricordate qui che cosa avevamo detto?

01:03:47Avevamo detto che questo problema con gli

01:03:49scenari dicevamo vogliamo risolvere questo problema.

01:03:52In cui minimizziamo y con y

01:03:56maggiore o uguale del valore in ogni possibile scenario vero?

01:04:00Ora, da un punto di vista concettuale,

01:04:02potremmo dire che l'insieme di incertezza lo chiamiamo

01:04:06I ed è fatto da tanti scenari.

01:04:08Un numero infinito di scenari in questo caso va bene,

01:04:11però concettualmente non cambia niente rispetto ai pochi scenari.

01:04:14Quello che possiamo fare è scrivere,

01:04:16vogliamo minimizzare y. Tenendo conto che.

01:04:24L'insieme delle soluzioni ammissibili è sempre lo stesso.

01:04:28I cammini okay, ma Y deve essere maggiore o uguale

01:04:32del costo in ogni possibile scenario.

01:04:36Qual è il problema?

01:04:37Quindi siete d'accordo concettualmente con questa scrittura?

01:04:41Cioè Y è il massimo in ogni possibile realizzazione,

01:04:44cioè Y è maggiore o uguale del costo,

01:04:47qualsiasi sia il vettore C dei KEE.

01:04:50Okay, va bene, il problema è qual è?

01:04:54In questo modello riusciamo

01:04:55a implementarlo in questo modello qui così

01:04:57com'è Sempre il discorso è facile o difficile da risolvere.

01:05:01Non lo so se è facile o difficile da risolvere.

01:05:06Proviamo a implementarlo in Apple.

01:05:08Riesco a implementarlo in Apple.

01:05:10Comincio a scrivere, minimizza e scrivo la funzione obbiettivo.

01:05:14Poi scrivo i vincoli per dire che un cammino,

01:05:17i vincoli di flusso e poi comincio

01:05:18a scrivere un vincolo per ogni scenario.

01:05:21Ma quanti scenari abbiamo?

01:05:23Infiniti. Riesco a mettere infiniti scenari in un file di Apple?

01:05:26No, non posso scriverlo.

01:05:29Quindi vedete che già è un problema,

01:05:30quindi non riesco a risolverlo direttamente questo problema.

01:05:34Ho bisogno di qualche artificio e questo mi sta

01:05:38a testimoniare che il problema rimane difficile.

01:05:41Okay, quindi su poliedri rimane difficile

01:05:44se volete poliedri potevano essere una via

01:05:46di mezzo tra gli intervalli e gli scenari.

01:05:50No perché gli intervalli abbiamo sappiamo che un poliedro

01:05:53particolare su cui su

01:05:55quel poliedro particolare il problema del cammino,

01:05:58del cammino minimo assoluto,

01:06:00del cammino minimo, robusto in senso assoluto,

01:06:02è facile da risolvere e per poliedri non è facile da risolvere.

01:06:08Va bene, chiaro?

01:06:09Rimane difficile.

01:06:10D'accordo. Ora sui poliedri uno potrebbe dire sì,

01:06:15ma allora non esco più.

01:06:16Allora, sempre se vogliamo

01:06:20fare un piccolo approfondimento matematico,

01:06:22che cosa vuol dire questo? Vuol dire.

01:06:25Ci provo proprio oggi ci voleva che l'insieme i cos'è l'insieme?

01:06:32L'insieme. Abbiamo detto che un poliedro vero.

01:06:35D'accordo. Quindi qual è la questione?

01:06:38La questione è che questo sia un problema bi livello.

01:06:40Ma risolvere questo problema di ottimizzazione è un.

01:06:45Non è facile, perché in

01:06:46linea di principio dovrei scrivere infiniti vincoli.

01:06:49Cioè, se questo ehi,

01:06:51questo è poliedro, questo

01:06:53non è l'insieme delle soluzioni ammissibili.

01:06:55Questo è l'insieme delle realizzazioni dei possibili costi.

01:06:59Ok, d'accordo.

01:07:01Quindi io qui devo scrivere quando dico per ogni

01:07:04appartenente a vuol dire che devo che devo prendere questo

01:07:07valore e metterci il vincolo.

01:07:09Nel modello questo valore metterci il vincolo infiniti

01:07:12ok però se questo è un poliedro si può

01:07:15dimostrare che non c'è bisogno di dire che

01:07:19tutti i vincoli che io scrivo per realizzazioni che sono

01:07:24dentro il poliedro sono

01:07:26ridondanti se ho i vincoli relativi ai soli vertici,

01:07:30ok. Quindi, anziché qui scrivere per

01:07:33ogni C appartenente a questo problema,

01:07:36potrei scrivere per ogni C che è un vertice del poliedro

01:07:39I. E il numero di vertici del poliedro è limitato,

01:07:43quindi riesco a scriverlo il modello,

01:07:45almeno riesco a scriverlo.

01:07:46Rimane difficile, ma riesco a scriverlo chiaro.

01:07:50Perché un numero finito?

01:07:51Quanti sono quei possibili vertici di un poliedro

01:07:55I potrebbero essere pochi se sono fortunato,

01:07:57ma potrebbero essere milioni di miliardi.

01:08:00Se sono sfortunato, okay.

01:08:02E quindi ho sempre un problema che

01:08:05è difficile non solo perché la

01:08:07programmazione lineare rimane intera,

01:08:08ma perché potrebbe avere un numero spropositato di vincoli.

01:08:12Per fortuna ci sono vincoli come il metodo dei

01:08:15piani di taglio che magari qualcuno di voi,

01:08:17anche all'ascolto avrà sentito nominare e quindi mi salvo.

01:08:22Ecco perché è importante

01:08:23ecco perché è importante la differenza tra un tra

01:08:26l'incertezza definita su poliedri e

01:08:28l'incertezza definita su insiemi che non sono poliedri.

01:08:31Perché se sono poliedri riesco

01:08:33a trattarli magari con metodi

01:08:35computazionali avanzati ma almeno riesco a trattarli.

01:08:38Altri metodi sono proprio veramente troppo complicati per noi.

01:08:41Va bene, chiaro vado avanti.

01:08:46Osservazioni quindi

01:08:48faccio una sintesi di quello che ci siamo detti.

01:08:53Ovviamente quindi stiamo parlando di.

01:08:56Abbiamo un problema nominale,

01:08:57vogliamo risolvere una controparte robusta in

01:09:00cui l'incertezza è confinata alla funzione obiettivo.

01:09:03Ok. E vogliamo considerare un criterio di robustezza

01:09:06in senso assoluto,

01:09:07cioè considerare tutti gli scenari un loro sottoinsieme?

01:09:11Ok, e il criterio che abbiamo adottato di fatto è il min max

01:09:15per problemi di minimo sarebbe max min

01:09:18per problemi di massimo ovviamente.

01:09:20Ok allora abbiamo capito che

01:09:23questo criterio ce l'ha ispirato l'analisi decisionale?

01:09:26No, è lo stesso criterio di prima,

01:09:28soltanto che dobbiamo considerare

01:09:31anche implicitamente tutte le possibili

01:09:33alternative e non un numero dato o delle alternative date.

01:09:38E inoltre gli scenari potrebbero essere in

01:09:40linea di principio infiniti che stiamo considerando tanti scenari,

01:09:44tanti possibili stati di natura definiti da intervalli,

01:09:48da scenari, da poliedri eccetera eccetera.

01:09:51Okay allora in sintesi abbiamo visto che le modalità con cui.

01:09:57Quindi come definiamo il problema dipende a questo punto da come

01:10:03rappresentiamo l'incertezza e a seconda di come

01:10:06rappresentiamo l'incertezza abbiamo delle

01:10:07modalità diverse per risolvere il problema.

01:10:10Alcune modalità sono facili alcune modalità rimangono difficili.

01:10:13Okay, per renderci conto noi abbiamo

01:10:17utilizzato in questo corso stiamo utilizzando

01:10:19la modellazione in programmazione

01:10:21matematica che già fa ci ha fatto capire in

01:10:24alcuni casi che il problema ad esempio il problema del calcolo del

01:10:27cammino minimo anche se il problema nominale facile

01:10:30la controparte robusta rimane facile in

01:10:33altri casi la controparte robusta prima diventa

01:10:37difficile che abbiamo visto tre casi possiamo ricordarci.

01:10:42Va bene ci siamo questa è la sintesi ora.

01:10:49Robustezza in senso assoluto cambiamo

01:10:53dove c'è l'incertezza anziché nella funzione obiettivo.

01:10:56Confiniamo adesso in questo secondo caso l'incertezza

01:10:59a livello di Regione ammissibile

01:11:01quindi la situazione è quella che vedete lì.

01:11:04Data una soluzione la

01:11:05soluzione ha quel valore lì quindi il valore della

01:11:08della della soluzione non dipende dagli

01:11:10scenari ciò che dipende dallo scenario.

01:11:13Che cos'è la Regione ammissibile e quindi siccome

01:11:16la Regione ammissibile diventa dipende dallo

01:11:18scenario vuol dire che una certa soluzione

01:11:20in alcuni scenari.

01:11:22E ammissibile in altri scenari non lo è

01:11:24okay cosa vuol dire in questo caso robustezza in senso assoluto.

01:11:28La funzione obiettivo non c'entra più quindi

01:11:30il criterio c'è un problema di

01:11:31minimo e il minimo di un certo valore,

01:11:33il massimo di un certo valore che è sempre quello data da x. Ma

01:11:37data la x diciamo che la che quella X ammissibile

01:11:41in senso assoluto se ammissibile

01:11:43in tutti gli scenari che ci interessano.

01:11:46Chiaro? Quindi è come

01:11:48dire che la regione ammissibile è

01:11:50l'intersezione di tutte le possibili regioni ammissibili.

01:11:54Ok, chiaro.

01:11:56Quindi concettualmente vogliamo trovare il minimo x dove X?

01:12:02Vedete che scusate.

01:12:08Dove X? Semplicemente lo limitiamo a questo

01:12:13f asterisco che è l'intersezione di tutte le regioni ammissibili.

01:12:17Quindi quella soluzione noi.

01:12:19A noi interessano solo tutte

01:12:21e sole le soluzioni che sono ammissibili

01:12:23sempre in tutti gli scenari che ci interessano. Va bene?

01:12:27Chiaro? Allora anche questo è

01:12:30un criterio molto conservativo che stiamo dicendo.

01:12:35Voglio essere sicuro

01:12:36che la che la soluzione che trovo funzioni non voglio

01:12:40avere nessun caso in cui non funziona.

01:12:42Okay. Eh. Osservazioni come potete immaginare adesso

01:12:52lo vedremo il modo di risolvere

01:12:55il problema il fatto che il problema rimanga diventi eh rimanga

01:12:58facile o diventi difficile eccetera dipende

01:13:03da come definiamo la rappresentazione della incertezza.

01:13:09Okay quindi in

01:13:10genere le controparti robuste saranno sempre difficili

01:13:13tranne alcuni casi particolari che impareremo a riconoscere.

01:13:16Allora esempio l'avevamo visto già

01:13:19un esempio vi ricordate l'agricoltore era quello in

01:13:22cui dicevamo gli scenari non sono più per le rese,

01:13:26ma gli scenari sono sulle quantità disponibili.

01:13:28E avevamo messo tutti i vincoli possibili e

01:13:30immaginabili tutti gli scenari però di

01:13:33fatto era sempre un problema di programmazione lineare

01:13:35a variabili continue in quel caso lì il problema era facile.

01:13:38E rimaneva facile in quel caso.

01:13:40Okay, ci siamo, ve lo Ricordate?

01:13:48Anche nel problema del cammino minimo.

01:13:51Okay, voi potete andare

01:13:55a fare l'intersezione e in quel caso

01:13:58il problema rimane minimo e rimane facile o difficile

01:14:01e dipende dal Stiamo aggiungendo

01:14:04un vincolo che potrebbe metterci nel caso in

01:14:07cui perdiamo l'integralità e quindi diventa

01:14:11difficile o nel caso in

01:14:12cui l'integralità la conserviamo e il problema rimane facile okay.

01:14:17Però in generale, non sapendo bene quali sono i vincoli quali come

01:14:21sono definiti gli scenari potrebbe diventare difficile. Va bene.

01:14:25Chiaro ora un caso particolare ed ecco perché eh.

01:14:31Abbiamo introdotto il poliedro di Oz.

01:14:33E il caso in cui

01:14:35abbiamo un'incertezza sui parametri che definiscono il problema.

01:14:40E questa incertezza sta in un poliedro di Oz.

01:14:43Okay, qual è il problema che consideriamo?

01:14:46Non è il problema del cammino minimo, ovviamente,

01:14:47perché dobbiamo definire altre cose.

01:14:49Lo consideriamo un problema nel quale noi

01:14:51vogliamo costruire una rete di

01:14:54telecomunicazione okay che metta

01:14:58in comunicazione le città d'Italia come

01:15:01abbiamo detto prima sapendo che c'è una

01:15:03certa quantità di traffico che dobbiamo scambiare tra le città.

01:15:08Questa quantità di traffico si chiama D, H,

01:15:11dove H è una delle possibili coppie di città.

01:15:14Va bene, quindi il parametro incerto è DH.

01:15:17Qual è il problema nominale?

01:15:18Il problema nominale?

01:15:20Ve lo descrivo rapidamente.

01:15:22Non mi interessa entrare nei dettagli,

01:15:23ma di fatto cosa vogliamo fare?

01:15:25La funzione obiettivo è quella di minimizzare

01:15:28il costo di installazione della dei link dei

01:15:33cavi tra le diverse città quindi abbiamo una rete

01:15:37a un grafo è sugli archi dobbiamo installare la fibra ottica che.

01:15:43Quanto ci costa installare

01:15:45un'unità di fibra ottica CGG su ogni cavo?

01:15:48Va bene, d'accordo.

01:15:49E ovviamente su ogni cavo che cosa ci andrà? Ci andrà.

01:15:55E per capire quanto cavo ci serve dobbiamo capire come instradare,

01:16:00quindi trovare, capire qual è il cammino che farà su questa rete.

01:16:05Il traffico che va da Padova a Roma potrebbe fare Padova,

01:16:10Milano, Roma oppure Padova Bologna,

01:16:12Firenze, Roma per esempio.

01:16:13Quindi vedete che per ogni coppia devo

01:16:16trovare un cammino che poi mi dice dove devo

01:16:18mettere la eh dove dove devo installarla.

01:16:24Quindi dove mi serve capacità di rete per

01:16:26quella per quel per quella domanda.

01:16:30Chiaro il problema che tenendo conto che magari io potrei

01:16:34dire che metà del traffico tra Padova e Roma lo

01:16:37in via Milano l'altra metà via Bologna Firenze.

01:16:40Che quindi cos'è XJ,

01:16:42xj e la H e la quantità di traffico La percentuale di traffico

01:16:49tra l'origine di H,

01:16:51la destinazione di H che andrà a finire su un certo arco J.

01:16:55Okay, quali sono i vincoli, I vincoli?

01:16:58Questi sono vincoli simili al vincolo di cammino.

01:17:00Ne scrivo un gruppo per ogni coppia, origine,

01:17:04destinazione e sto dicendo che flussi

01:17:08entranti meno flussi uscenti devono essere

01:17:10meno uno più uno origine destinazione zero.

01:17:14Altrimenti cosa sto dicendo?

01:17:15Sto dicendo che per ogni coppia,

01:17:18origine destinazione tutta la domanda deve uscire dall'origine,

01:17:23si sparge sulla rete,

01:17:25raggiunge dei nodi intermedi,

01:17:28ma se raggiunge dei nodi intermedi li deve superare.

01:17:30Quindi se entra in un nodo intermedio ci deve anche uscire e

01:17:34poi a raccolto il 100% arriva a destinazione.

01:17:38Chiaro, è un flusso,

01:17:40ma ho tanti flussi tutti insieme che ho in questo modello,

01:17:44uno per ogni coppia, origine, destinazione.

01:17:46Questo è un flusso multi commodity, si chiama.

01:17:49D'accordo, di quello che sto dicendo

01:17:52mi interessa la parte non di modello ma quello che dirò dopo.

01:17:55Però è importante capire che cosa stiamo dicendo.

01:17:58Chiaro qual è il problema e come

01:18:01lo stiamo modellando ora, qual è il punto.

01:18:04Il punto è che chiaramente ogni su ogni

01:18:08arco ho un limite alla quantità di link che posso installare

01:18:14quindi una capacità massima per cui se vado

01:18:16a sommare tutta tutto il traffico che passa sull'arco che è

01:18:22dato da la somma su tutte le domande

01:18:24di quanto passa di quella domanda su quell'arco

01:18:27moltiplicato ovviamente per la domanda

01:18:28perché questa la x una percentuale.

01:18:30E questo mi dice che per ogni arco devo essere a posto.

01:18:35Vedete che di qui interviene sia nella funzione

01:18:38obiettivo ma interviene anche in questo vincolo.

01:18:42Okay e quindi questo diventa un vincolo stocastico Perché?

01:18:46Perché questo deve essere vero per ogni arco e

01:18:49per ogni possibile realizzazione della domanda.

01:18:52D. Dentro e dietro di me.

01:18:54Okay, va bene.

01:18:56Dove poi è odioso,

01:18:58abbiamo detto è definito da quei vincoli abbastanza semplici

01:19:00no somma su degli archi che escono dall'origine

01:19:03deve essere di tutte le domande

01:19:05deve essere minore o uguale di una certa quantità somma di tutte

01:19:09le domande che arrivano deve essere minore o

01:19:10uguale di un'altra quantità Okay non so da dove

01:19:13arrivano ma devono essere minori uguali di una certa quantità.

01:19:18Okay, alle volte questo vincolo dipende non

01:19:20solo o non tanto dalla dimensione della città,

01:19:24ma anche dal fatto che io so che in quella città

01:19:26ho installato dei ricevitori che non mi permettono di ricevere

01:19:31più di quella domanda da qualsiasi parte arrivi o

01:19:35dei trasmettitori non in città che mi

01:19:37dicono che non posso trasmettere più di quella domanda.

01:19:39Da quel verso, qualsiasi destinazione siano eh destinati.

01:19:44Va bene, chiaro sì o no?

01:19:48Quello che sto dicendo è che ho il modello in nero.

01:19:52È il modello nominale, qualsiasi esso sia.

01:19:54Ci siamo fatti un'idea di di come funziona.

01:19:57Okay per passare alla controparte robusta devo

01:20:02aggiungere come dire il vincolo

01:20:05nero questo vincolo qui che dipende.

01:20:10Da questo vincolo che dipende dalla domanda.

01:20:16Non lo non lo scrivo una volta sola ma devo scrivere tanti

01:20:22vincoli quanti sono le possibili realizzazioni della domanda.

01:20:28E quali sono le realizzazioni?

01:20:30Quelle che rispettano il poliedro di osso va bene come prima?

01:20:33Ho un problema di livello

01:20:35nel quale questa cosa qui cioè più non mi

01:20:38livello scusa non c'entra niente livello.

01:20:39Ho un problema nel quale devo

01:20:41aggiungere tanti vincoli uno per ogni scenario.

01:20:44Infiniti scenari in questo caso.

01:20:46D'accordo, va bene ci siamo come prima

01:20:51quindi però so che questo

01:20:52è un po lieto quindi poter scrivere un numero

01:20:54limitato di scenari però potrebbero essere un sacco.

01:20:56Okay, perché è interessante Perché vi sto citando questo problema?

01:21:01Perché qualcuno ha studiato bene che cosa succede in questi casi?

01:21:05E con il poliedro di Oz vale la proprietà

01:21:09rossa trasformato può essere trasformato in un problema di allora.

01:21:14Scusatemi ancora.

01:21:15Vedete che qui tutte le variabili sono frazionarie,

01:21:18qui non ho variabili intere perché x una variabile compresa

01:21:21tra 0 e 1 una percentuale che.

01:21:23Quindi il problema nominale è un problema facile.

01:21:27Va bene, è facile perché

01:21:30è un problema di programmazione lineare con variabili continue.

01:21:34Okay. Ora, se io aggiungo se io

01:21:39devo avere la controparte robusta

01:21:42in cui devo aggiungere un numero infinito di vincoli,

01:21:44il problema diventa difficile.

01:21:45Però poi una ragione dice non devo aggiungere un

01:21:47numero infinito di vincoli, un poliedro.

01:21:49Basta che aggiunga i vincoli relativi ai

01:21:51vertici ma possono essere tanti lo stesso.

01:21:53Quindi il problema rimarrebbe difficile.

01:21:56C'è qualcuno che ha studiato questo

01:21:58poliedro nella situazione particolare in cui.

01:22:02Il poliedro di incertezza è

01:22:04il poliedro di Oz con questi vincoli che sono piuttosto semplici.

01:22:08E ragionando ha scoperto che si può trasformare in

01:22:12un problema di programmazione lineare con un

01:22:14numero finito di vincoli e

01:22:17può essere risolto in un modo abbastanza facile, tutto sommato.

01:22:21Okay. Qual è il messaggio

01:22:24dopo tutta questa slide che mi devo ricordare questo modello?

01:22:27No, quello che mi devo ricordare è che io so

01:22:31che ci sono problemi di flusso nei quali io devo stabilire

01:22:36come muovere

01:22:37certe certi beni su una rete e se la quantità di beni che devo

01:22:42muovere è incerta e l'incertezza riesco a a formularla.

01:22:47Con il poliedro di Oz

01:22:49ho qualche speranza di risolvere quel problema lì.

01:22:52Okay quindi se se io avrò a che fare con un

01:22:56problema di questo tipo

01:22:57posso contrattare col mio committente per dire,

01:23:00ma riusciamo a rappresentare l'incertezza in questo modo?

01:23:03Sì, e allora c'è speranza.

01:23:05Perché se non riusciamo.

01:23:06Eh vabbè, il problema

01:23:08è veramente troppo difficile da risolvere. Va bene.

01:23:11Chiaro? Quindi questo è

01:23:13l'unico messaggio che mi interessa che rimanga di questa slide.

01:23:17Il fatto che esistono questo esempio in cui

01:23:20un poliedro particolare mi rappresenta può

01:23:23rappresentarmi un buon compromesso

01:23:25tra fedeltà alla rappresentazione dell'incertezza e

01:23:29riuscire a risolvere il problema.

01:23:32La controparte robusta Caro vado avanti.

01:23:37Ci rimane un altro pezzettino per la robustezza in senso assoluto,

01:23:42per l'ottimizzazione, quindi l'ottimizzazione

01:23:45robusta in senso assoluto.

01:23:47Abbiamo visto la incertezza definita

01:23:51a livello di funzione obiettivo.

01:23:52Abbiamo fatto dei ragionamenti,

01:23:53in particolare il problema del cammino minimo abbiamo

01:23:56visto la robustezza in

01:23:57senso assoluto con eh incertezza soltanto nei eh

01:24:02nella regione ammissibile abbiamo

01:24:05detto che tutto sommato non basta lavorare

01:24:07su l'intersezione di tutti i possibili scenari

01:24:11ok tutte le possibili regioni ammissibili questa intersezione

01:24:14qualche volta se gli scenari sono

01:24:15sono tanti potrebbe essere complessa

01:24:17ma ci sono casi come il poliedro di

01:24:19OSA nel quale possiamo salvarci.

01:24:21Ok, Adesso vediamo il terzo

01:24:23caso che ci interessa che ce ne sono tanti altri lo abbiamo già

01:24:27detto ed è quello in

01:24:29cui vogliamo la robustezza in

01:24:31senso assoluto con un parametro di controllo.

01:24:33Adesso in

01:24:34questo caso io darò delle definizioni

01:24:37eh una definizione generale

01:24:41quale cosa vuol dire un parametro di controllo.

01:24:44Pensate al problema del contadino quando abbiamo

01:24:46detto vogliamo la soluzione si comporta

01:24:48meglio in almeno due degli scenari.

01:24:50Okay, quel due poteva essere uno o poteva essere tre?

01:24:54Poteva essere zero.

01:24:55Quello il parametro di controllo

01:24:57ci sta controllando il livello di protezione

01:24:59il livello di conservatorismo di

01:25:01conservatorismo conservatorismo in inglese okay quindi io

01:25:06so che la mia incertezza

01:25:08è riassunta nel nel vettore Alfa dei parametri incerti.

01:25:11Quello che abbiamo fatto finora e assumere che

01:25:14tutti i parametri incerti potessero

01:25:17variare contemporaneamente quindi il mio

01:25:20caso peggiore era definito da da dal fatto che

01:25:23tutti i parametri potevano variare contemporaneamente.

01:25:26Invece io ho un modo di rendere la soluzione un po più flessibile.

01:25:31Faccio un esempio se non ci

01:25:33capiamo il problema del cammino minimo robusto

01:25:36in senso assoluto che cosa voglio fare?

01:25:39Voglio trovare per esempio min max,

01:25:40voglio trovare il miglior cammino e ogni

01:25:43cammino lo definisco andando a dire qual è il caso peggiore?

01:25:47Okay, quindi immaginate di avere come controparte il sindaco.

01:25:50Il sindaco mi dice Senti,

01:25:52mi devi dire che strada devo suggerire agli utenti

01:25:57per andare dalla non so per

01:26:00uscire a Padova est e andare

01:26:02a a in via cave insomma all'hotel Milano ho fatto pubblicità.

01:26:09Va bene ok quindi dici va bene allora perché qual è il problema?

01:26:14Perché qua ci può essere traffico quindi parametro

01:26:16non ci va bene possiamo rappresentare quindi.

01:26:19No, potrei dire possiamo.

01:26:21Ma come sono questi parametri?

01:26:23Eh guarda, ho studiato l'ufficio tecnico,

01:26:25mi ha detto che.

01:26:26Eh vabbè, fatemi finire l'esempio,

01:26:28così finisco questa parte qua.

01:26:30l'Ufficio tecnico mi ha detto che in quell'arco lì ci può il.

01:26:34Il tempo di attraversamento è 3 minuti,

01:26:36oppure cinque, oppure sette, oppure nove.

01:26:38In quell'altro arco qualsiasi numero compreso tra 03:10.

01:26:42E mi dà questa rappresentazione dell'incertezza che

01:26:45io lo guardo negli occhi e gli dico ma proprio tre sette nove.

01:26:50Perché mi ha detto ho seguito

01:26:52un corso non gli dite questo

01:26:54però dite beh insomma potremmo dire prima

01:26:56approssimazione che tra tre nove

01:26:58anche quello eh ma sì può andar bene okay quindi posso

01:27:02considerare la rappresentazione per

01:27:05intervalli che mi semplifica la vita, okay.

01:27:07Quindi io faccio una bella figura vado lì

01:27:09risolve il problema, prendo Apple,

01:27:11lo risolvo mettendone funzioni obiettivo

01:27:13il valore massimo degli intervalli di incertezza.

01:27:16Quindi il mio problema di ottimizzazione robusta l'ho modellato

01:27:21come un cammino minimo in senso assoluto,

01:27:23con incertezza sui costi, rappresentata da intervalli.

01:27:29Vedete che è un processo di modellazione

01:27:31già solo la definizione del problema.

01:27:33Va bene che ho definito quel problema

01:27:36lì lo risolvo vado dal Sindaco dico Sindaco ecco

01:27:39il cammino dice mamma mia quanto è lungo cammino

01:27:42qua Ma perché è così e perché guarda questo è

01:27:44il cammino che si comporta meglio nel caso peggiore.

01:27:47E vabbè, qual è il caso peggiore di questo cammino qua?

01:27:50Uno glielo mostra e dice Guarda,

01:27:52il caso peggiore è quello in

01:27:54cui su questo arco il costo il

01:27:56tempo è 10 minuti 10 minuti, 10 minuti, 10 minuti dieci.

01:27:59Sì, ma sto cammino qua vuol dire che

01:28:01non ho mai visto che non si è mai realizzato in

01:28:05questa città che tutti questi archi siano

01:28:09congestionati al massimo nello stesso

01:28:11momento non si è

01:28:12verificato mai quindi è troppo conservativa questa soluzione qua.

01:28:17Ah, va bene, aspetta un attimo. Cosa vuol dire?

01:28:19Eh? Vuol dire che se se c'è se c'è congestione qui non ci sarà lì.

01:28:23Quindi c'è una correlazione tra queste tra

01:28:26la congestione degli archi

01:28:28e voi dite vabbè ma correlazione possiamo

01:28:30prescindere dalla correlazione?

01:28:32Ecco che cosa vuol dire.

01:28:34Possiamo fare finta che non tutti gli archi.

01:28:39Varieranno dal loro valore nominale contemporaneamente,

01:28:43ma solo il 50% degli archi,

01:28:46non sapendo dove stanno okay, possono variare contemporaneamente.

01:28:52Ad esempio, in questo caso, in questo cammino,

01:28:53se io considero solo il 50% degli archi,

01:28:56allora magari c'è un altro cammino in cui,

01:28:57considerando solo il 50% degli

01:28:59archi su quel cammino che eh variano rispetto al valore nominale

01:29:03va meglio okay ed è un

01:29:05cammino un po più dritto che cosa sto facendo?

01:29:08Sto diminuendo il livello di robustezza.

01:29:12Sto parlando sempre di robustezza in senso assoluto,

01:29:15perché voglio cercare il cammino che si comporta

01:29:17meglio nel caso peggiore.

01:29:18Ma il caso peggiore non è tutti i casi possibili,

01:29:22ma è il caso definito da un insieme ristretto di scenari.

01:29:26E questo insieme ristretto di scenari

01:29:28dipende da un parametro gamma che

01:29:31è compreso tra zero e il numero di parametri incerti.

01:29:34Ok, posso dire 1/2,

01:29:37quindi gamma uguale a n mezzi.

01:29:39Voglio considerare tutti gli scenari, ma non tutti,

01:29:42solo gli scenari in cui al massimo gamma

01:29:45dei parametri incerti sono variati rispetto al valore nominale.

01:29:49Chiaro cosa voglio dire con questo parametro di controllo?

01:29:53Quindi se gamma uguale a zero vuol dire che sono nel caso nominale.

01:29:56Trovami la migliore soluzione in cui

01:29:58nessuno dei parametri cambia rispetto al valore nominale.

01:30:02Vabbè, vuol dire che considero il valore

01:30:04nominale gamma uguale a zero gamma uguale

01:30:07a N solo nel caso la controparte robusta in

01:30:10senso assoluto senza parametro di controllo in

01:30:12cui tutti possono cambiare una via di mezzo.

01:30:15Mi dice che sto cercando una soluzione,

01:30:17che la migliore soluzione,

01:30:20quella che si comporta meglio in un sottoinsieme ristretto

01:30:22di scenari e il sottoinsieme ristretto di scenari.

01:30:25Lo sto definendo attraverso una percentuale

01:30:27di parametri incerti che possono

01:30:30assumere un valore diverso da quello nominale.

01:30:33Non so quali, ma al massimo un certo numero.

01:30:36Okay. Chiaro cosa vuol dire parametro di controllo?

01:30:39Benissimo, se è chiaro questo,

01:30:40allora consideriamo la robustezza

01:30:43in senso assoluto con parametro di controllo.

01:30:45Facciamo l'esempio in cui

01:30:48limitiamo l'incertezza alla sola funzione obiettivo.

01:30:52Quindi vedete che la controparte robusta

01:30:54è definita come abbiamo visto prima in

01:30:56modo simile a quello che abbiamo

01:30:59visto nel caso di robustezza in senso assoluto,

01:31:01cioè vogliamo trovare la x fra tutte le x ammissibili,

01:31:07tenendo conto che le x ammissibili qui sono sempre

01:31:09le stesse perché non abbiamo incertezza nell'insieme

01:31:11di ammissibilità e come valorizzo ogni x prima dicevamo col

01:31:16massimo in tutti gli scenari qui invece diciamo col massimo

01:31:19in un sottoinsieme ristretto di scenari cioè quegli scenari in

01:31:23cui al massimo gamma

01:31:25parametri hanno variato il loro valore rispetto

01:31:28al MH rispetto al valore nominale.

01:31:33Okay quindi vedete che la valorizzazione

01:31:38è il massimo ma non su tutti gli scenari,

01:31:40ma non su insieme un po più piccolo,

01:31:41quindi sono meno conservativo,

01:31:43quindi posso trovare una soluzione che nel caso

01:31:46peggiore costa meno,

01:31:47ma è perché il caso peggiore tra i casi che sto

01:31:50considerando sto escludendo altri

01:31:52casi che potrebbero essere ancora peggio.

01:31:54Va bene? Chiaro? Quindi in

01:31:56genere un problema NP perché

01:31:59ve lo sto citando questo fatto, allora?

01:32:02Questo è comunque una modellazione.

01:32:05Cioè io posso andare dal mio sindaco e dire guarda,

01:32:08ti ho trovato quest'altro compromesso, ti piace di più?

01:32:10Lui potrebbe dire sì, mi piace di più,

01:32:12anche se vedi su questo cammino che mi stai proponendo

01:32:17come il migliore possibile.

01:32:18C'è congestione sia sul

01:32:21su questo che su questo arco che non succede mai.

01:32:25E io gli dico accontentati,

01:32:27va bene sì se non si accontenta cosa vuol dire vuol dire

01:32:31che non basta il parametro di controllo vuol

01:32:33dire che bisogna mettere in

01:32:34campo altri un altro modello di ottimizzazione

01:32:37altri strumenti okay.

01:32:39Qual è la cosa buona del parametro di controllo che siccome

01:32:42voi prescinde dalla correlazione che

01:32:45ci può essere tra i parametri che assumono

01:32:47contemporaneamente valori diversi da quello nominale allora avete

01:32:52potete fare dei ragionamenti più

01:32:54generali che vi permettono ad

01:32:55esempio nel caso del problema del cammino minimo.

01:32:59Con parametro di controllo robustezza in

01:33:02senso assoluto con eh con incertezza

01:33:05in funzione obiettivo e parametro di controllo.

01:33:09Il problema rimane facile.

01:33:11Ok il perché io non vi do dimostrazioni in questo corso.

01:33:16Ovviamente se qualcuno di voi interessato

01:33:18alle dimostrazioni va nel libro di riferimento

01:33:20che vi ho dato andando in biblioteca, le guardate.

01:33:22Ma insomma a me non interessano che mi

01:33:24interessa la sensibilità sul fatto che un parametro

01:33:27di controllo può essere un compromesso tra un criterio troppo

01:33:31conservativo e il fatto di riuscire

01:33:33a risolvere un problema di cammino minimo,

01:33:35ad esempio con robustezza in

01:33:36senso assoluto il parametro di controllo che il teorema dice.

01:33:40Se il problema nominale è

01:33:42un problema di ottimizzazione binaria polinomiale,

01:33:45cos'è un problema di ottimizzazione binaria polinomiale?

01:33:47È un problema che voi potete

01:33:48rappresentare con un modello di programmazione binaria,

01:33:51cioè con variabili intere

01:33:53zero uno che godono della proprietà di integralità,

01:33:56per esempio come il problema del cammino minimo

01:33:58che potete far finta che un problema

01:34:00é facile che che è un problema variabili continue

01:34:03questo vuol dire ottimizzazione binaria

01:34:06polinomiale e se si considera

01:34:08la rappresentazione con intervalli di incertezza e

01:34:13il valore nominale

01:34:14è il più basso nell'intervallo di incertezza e potete variare

01:34:19in qualsiasi.

01:34:21Cioè, potete e l'incertezza è definita

01:34:24dal fatto che un parametro può

01:34:26variare il suo valore rispetto al valore nominale in

01:34:29un intervallo tra un minimo e un massimo.

01:34:32Allora potete risolvere

01:34:35il problema di ottimizzazione robusta con parametro di controllo,

01:34:38risolvendo n più uno problemi facili.

01:34:43Cioè si tratta di andare a capire se si può capire

01:34:47quali sono i coefficienti da utilizzare nella funzione di costo.

01:34:52Quelli critici risolvere n volte il problema e scegliere quello.

01:34:55Il caso peggiore tra questi n. Non è proprio così,

01:34:58ma l'idea è un pochino quello che non è

01:35:01facile quanto risolvere un problema nominale,

01:35:04ma è facile quanto risolvere n più uno problemino nominali.

01:35:08Ma siccome questo numero è controllato,

01:35:10il numero di problemi che devo risolvere rimane un problema facile.

01:35:13Okay, d'accordo.

01:35:16Quindi è un compromesso tra essere troppo

01:35:19conservativi e considerare il

01:35:21fatto che posso trovare delle vie di mezzo.

01:35:23Non è perfetto perché non considera

01:35:25le correlazioni che ci possono essere perché voi dite gamma

01:35:29qualsiasi non gamma in

01:35:32modo tale che se uno varia

01:35:34varia anche l'altro se uno non vale non vale neanche l'altro.

01:35:36Perché se volete aggiungere anche

01:35:38queste informazioni nella rappresentazione

01:35:39dell'incertezza il problema rimane

01:35:42diventa molto difficile da risolvere.

01:35:44Va bene è chiaro ci siamo.

01:35:47Ovviamente mi fermo qui. È come se mi fermo.

01:35:49Scusate, ho sforato parecchio, eh?

01:35:51Ci vediamo giovedì e continuiamo.

01:35:54Grazie, Scusate, Arrivederci.