Programmazione dinamica¶
Un corso della collana Ricerca Operativa e Matematica · tutti i corsi
Materiale didattico ideato e sviluppato da Fabio Furini, professore associato al DIAG, Sapienza Università di Roma.
Le dispense del corso, online: i principi della programmazione dinamica e gli algoritmi di PD per i problemi di zaino (0/1, illimitato, limitato, subset sum, a scelta multipla, multidimensionale, con setup, zaini multipli), per il lot sizing senza capacità e capacitato, per il cambio monete e il taglio delle aste; con ricorrenze, pseudocodice, complessità, tabelle svolte passo per passo, esercizi con le soluzioni e app interattive.
Prerequisiti: Problemi di ottimizzazione combinatoria per i problemi e Algoritmi per lo pseudocodice, la ricorsione e l'analisi degli algoritmi.
Provalo subito¶
La tabella della programmazione dinamica per lo zaino 0/1, già piena: ogni cella è il miglior profitto con i primi j oggetti e capacità k, e il percorso verde ricostruisce la soluzione. Premi «Esegui» per vederla riempirsi una cella alla volta.
Le parti del corso¶
Le stesse voci del menu: ogni scheda dice a quale parte e a quali capitoli della dispensa corrisponde.
-
Principi
Parte 1 · Capitolo 1
Principi
-
Problemi di zaino
Parte 2 · Capitoli 2–9
Zaino 0/1 (KP) · Zaino illimitato (UKP) · Zaino limitato (BKP) · Subset sum (SSP) · Zaino a scelta multipla (MCKP) · Zaino multidimensionale (MDKP) · Zaino con setup (KPS) · Zaini multipli (MKP)
-
Problemi di lot sizing
Parte 3 · Capitoli 10–11
Lot sizing senza capacità (ULS) · Lot sizing capacitato (CLS)
-
Problemi misti
Parte 4 · Capitoli 12–13
Cambio monete (CCP) · Taglio delle aste (RCP)
-
Autovalutazione
Facsimile d'esame
Un facsimile nuovo a ogni avvio: 13 domande, 33 punti, con la soluzione e il link alle dispense.
-
Laboratorio
App interattive
Le tabelle della PD che si riempiono passo per passo, sulle istanze di riferimento o su istanze tue.
Da non perdere¶
-
Esercizi con le soluzioni
Esercizi per ogni capitolo, ciascuno con la soluzione svolta che si apre con un clic.
-
Quiz di autovalutazione
Un facsimile d'esame nuovo a ogni avvio: 13 domande, 33 punti, con la soluzione e il link alle dispense. In Materiale c'è anche la banca completa delle domande.
-
Laboratorio interattivo
App che girano nel browser: muovi i parametri e guarda le idee del corso lavorare, un passo alla volta.
-
Dispense in PDF
Dispense, eserciziari e slide in PDF, con la stessa numerazione del sito.
-
Indice completo
Tutti i capitoli con le loro sezioni in una pagina, e come è fatto ogni capitolo.
La collana¶
Tutti i corsi della collana hanno la stessa impostazione: dispense online e in PDF, esercizi con le soluzioni, laboratorio interattivo e quiz di autovalutazione.
-
numeri reali, funzioni, limiti, derivate e serie, con i grafici interattivi
-
vettori, matrici, determinanti, sistemi lineari e autovalori, con il laboratorio di calcolo
-
rappresentazione dei numeri, pseudocodice, ordinamento e ricerca, analisi e algoritmi ricorsivi
-
poliedri, algoritmo del simplesso, dualità e simplesso duale, con il laboratorio interattivo
-
rilassamento continuo, disuguaglianze valide, piani di taglio, branch-and-bound e branch-and-cut
-
insiemi e funzioni convesse, problemi di ottimizzazione convessa, con grafici interattivi
-
grafi, alberi ricoprenti, cammini minimi, flussi su reti, simplesso su reti e gestione dei progetti
-
Problemi di ottimizzazione combinatoria
zaino, bin packing, colorazione, TSP, scheduling e lot sizing: i problemi, le formulazioni e gli algoritmi ad hoc
-
Programmazione dinamica · questo corso
principi e algoritmi di PD per zaino, lot sizing, cambio monete e taglio delle aste
-
euristiche costruttive, ricerca locale, metaeuristiche ed euristiche MIP per i problemi di ottimizzazione combinatoria
-
garanzie di prestazione, schemi di approssimazione e limiti dell'approssimazione per i problemi combinatori
-
modelli di programmazione lineare per problemi gestionali, risolti con Python e Gurobi
-
modelli di programmazione non lineare, dal portafoglio al machine learning, con Python e Gurobi
-
modelli di programmazione lineare a variabili intere, dalla formulazione alla soluzione con i solver
Materiale didattico di Fabio Furini — DIAG, Sapienza Università di Roma.
Questo sito è disponibile anche in inglese.