Domande d'esame VERIFICATO
DMO PAST EXAMS
17 visualizzazioni
22 download
Nessun voto ancora
Di cosa parla
- 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.