Domande d'esame VERIFICATO
DMO PAST EXAMS
171 visualizzazioni
22 download
Nessun voto ancora
Di cosa parla
Riassunto AI · si legge in un minuto
Il documento offre una panoramica completa sui concetti di Decision Making e Ottimizzazione, presentando formulazioni di Programmazione Lineare (LP) e Programmazione Lineare Intera (ILP) per una varietà di problemi. Sono inclusi problemi di ottimizzazione di rete come Shortest Path, Max-Flow, Minimum Spanning Tree e varianti del Traveling Salesman Problem (TSP), come il Bottleneck TSP. Vengono inoltre fornite formulazioni per diverse versioni del Knapsack Problem (Multiple-Choice, Multiple, Penalized) e problemi di copertura (Supermercati, Scheduling di annunci TV, Grafi di Incompatibilità). Le sezioni teoriche approfondiscono la Programmazione Stocastica (Two-Stage, Multi-Stage, EVPI, Progressive Hedging), la Rilassamento Lagrangiano, il Metodo del Simplesso, la Programmazione Dinamica, le Classi di Complessità (P, NP, NP-Complete), la Riducibilità dei Problemi, le condizioni di Karush-Kuhn-Tucker (KKT), l'Ottimizzazione tramite Colonia di Formiche (ACO), il Recovery Beam Search e i criteri di Aspirazione nella Tabu Search.
Leggi il riassunto completo
- Formulazioni di Programmazione Lineare (LP) e Programmazione Lineare Intera (ILP): Il documento descrive modelli LP/ILP per una varietà di problemi di ottimizzazione, tra cui:
- Shortest Path Problem (SPP): Minimizzazione della lunghezza del percorso tra due nodi con vincoli specifici.
- Bottleneck Traveling Salesman Problem (B-TSP): Ricerca di un tour Hamiltoniano con il minor costo massimo degli archi.
- Multiple-Choice Knapsack Problem (MCKP): Selezione esattamente di un oggetto per classe per massimizzare il profitto entro una capacità.
- Multiple Knapsack Problem (MKP): Assegnazione di oggetti a più zaini per massimizzare il profitto totale rispettando le capacità individuali.
- Minimum Spanning Tree (MST): Ricerca di un albero di copertura di costo minimo in un grafo non diretto.
- Covering Supermarkets: Posizionamento di un numero definito di supermercati per massimizzare la popolazione coperta.
- Penalized Knapsack Problem (PKP): Massimizzazione del profitto meno la penalità massima, con selezione condizionale degli oggetti.
- Max-Flow Problem: Massimizzazione del flusso da sorgente a pozzo con vincoli di capacità e condizioni aggiuntive sul flusso.
- TV Ads Scheduling: Pianificazione di blocchi pubblicitari in slot orari per massimizzare gli spettatori, con vincoli di tempo e tipo di slot.
- Incompatibility Graph: Selezione di nodi non incompatibili per massimizzare i ricavi meno il costo di rimozione degli archi.
- Feasible Flow: Garanzia della conservazione del flusso e della consegna della domanda in una rete con larghezza di banda condivisa.
- Concetti Teorici nell'Ottimizzazione:
- Programmazione Stocastica: Approfondisce i modelli Two-Stage e Multi-Stage, il Valore Atteso dell'Informazione Perfetta (EVPI) e l'algoritmo Progressive Hedging.
- Rilassamento Lagrangiano: Spiega il suo utilizzo per ottenere limiti inferiori per problemi di minimizzazione tramite il rilassamento di vincoli "cattivi".
- Classi di Complessità (P, NP, NP-Complete): Definisce queste classi e il concetto di riducibilità dei problemi, dimostrando come il problema della Partizione possa essere ridotto a quello dello Zaino.
- Programmazione Dinamica: Esplora il principio di ottimalità e le relazioni ricorsive, in particolare per il Knapsack Problem 0/1.
- Metodo del Simplesso: Delinea la sua filosofia, i vantaggi (geometria, problemi di piccole dimensioni) e gli svantaggi (complessità nel caso peggiore, problemi di grandi dimensioni).
- Metaeuristiche: Copre la filosofia dell'Ottimizzazione tramite Colonia di Formiche (ACO) (tracce di feromoni, scelte probabilistiche), il Recovery Beam Search (miglioramento delle soluzioni da parziali) e il criterio di Aspirazione nella Tabu Search (consentendo mosse "tabu" per soluzioni migliori).
- Condizioni di Karush-Kuhn-Tucker (KKT): Presenta le condizioni necessarie per i minimi locali in problemi di programmazione non lineare con vincoli di disuguaglianza.
Riassunto generato con l'intelligenza artificiale a partire dagli appunti. Come lo facciamo
Stai vedendo l'anteprima delle prime pagine. Il file completo è gratis: registrati per leggerlo tutto.
Studia questi appunti con l'AI
Riassunto e domande d'esame sono gratis: chiedili e ti mandiamo un'email quando sono pronti.
In preparazione: di solito è pronto in giornata.
Questo appunto è gratis. Registrati in 30 secondi per leggere tutte le pagine e scaricarlo.
Simula l'esame con domande costruite su questi appunti.
Di cosa parla l'insegnamento
Decision making and optimization · 1° anno · 1° semestre · 8 CFU · MAT/09
Expected knowledge: Students will study methods and algorithms for solving constrained optimization problems. They will learn how to use existing linear continuous, linear integer and nonlinear solution methods and develop new ones. Particular attention will be given to optimization on graphs and networks. The…