📈Optimization

L’ottimizzazione combinatoria è un altro nome per la ricerca operativa. È uno strumento utile a prendere le decisioni migliori, fatto sta che è anche molto utile al machine learning e si potrebbe dire che ne sia una base, questa è una cosa molto buona. Ricerca operativa Questo è un campo a forte impatto economico perché prova a minimizzare i costi e massimizzare i profitti. Steps 🟩, 🟨 Individuazione del problema (almeno riconoscere che ci sia un problema) Raccoglimento dei dati Modellizzazione del problema Ricerca di una soluzione Analisi dei risultati della soluzione La ricerca operativa si interessa principalmente degli step 3 e 4, nonostante gli steps non sempre vengono eseguiti in maniera lineare, ma c’è un ciclo di feedback a riguardo....

Questi problemi sono una sottoclasse della programmazione lineare con variabili reali. (Alcuni riescono a riconoscere se un problema è in questa forma, e lo risolvono in modo istantaneo se questo succede). Un problema dei router è un classico problema di flusso, che si risolvono con questi algoritmi polinomiali Note introduttive Rete, terminologia In questo caso andiamo ad indicare con rete un grafo con $G = (N, A)$ con $N$ nodi e $A$ archi, che solitamente sono diretti con pesi associati....

È una branca dell’algebra lineare che ci permette di semplificare tutti i concetti. Intro dualità🟩 <img src="/images/notes/image/universita/ex-notion/Programmazione lineare/Untitled 8.png" alt="image/universita/ex-notion/Programmazione lineare/Untitled 8"> Si fa una sorta di trasposta alla matrice di A. y è pari al numero di righe di A La trasformazione al duale è molto facile, ed è abbastanza intuitiva una volta che capiamo che vogliamo andare a fare l’upper bound. Dualità asimmetrica 🟥+ Teorema debole di dualità 🟩 Slide...

Questa sezione la tengo separata rispetto agli altri per favorire lo studio, così questa roba nuova la ripasso più spesso, in seguito si può accorpare. Goldberg Tarjan/Push-relabel Questo algoritmo è importante perché introduce ragionamenti sul minimo locale che possa alla fine essere ricomposto come soluzione globale. Questa lezione youtube lo spiega da Dio Preflusso 🟩 Slide La parte nuova di questa cosa è che i vincoli di bilanciamento possono diventare una disuguaglianza....

I problem idi accoppiamento sono abbastanza comuni per ottimizzazione a grafi. In questa serie di note andiamo a trattare brevemente i problemi principali, con un accenno veloce ad alcuni algoritmi di soluzione per esse. Grafo bipartito🟩 Un grafo bipartito è un insieme $(O \cup D), (A)$ di nodi e di archi. Tutti i nodi sono o fra i nodi di origine oppure fra i nodi di destinazione, e gli archi sono solamente collegati fra nodi di origine e nodi di destinazione....