Sito in costruzione. Il materiale è ancora in lavorazione: slide e notebook arriveranno più avanti; il laboratorio interattivo è già aperto e crescerà.
Programmazione lineare¶
Materiale didattico ideato e sviluppato da Fabio Furini, professore associato al DIAG, Sapienza Università di Roma.
Le dispense del corso, online: problemi di programmazione lineare, poliedri, algoritmo del simplesso, dualità, metodi avanzati e tecniche di modellazione, con definizioni, teoremi con le loro dimostrazioni, esempi svolti passo per passo ed esercizi con le soluzioni.
Comincia dai problemi di PL Gli esercizi Prova un grafico interattivo Scarica le dispense (PDF)
Come è organizzato ogni capitolo¶
Ogni capitolo è una delle note del corso, con gli stessi numeri e gli stessi colori della dispensa: sul sito e nel PDF trovi tutto allo stesso posto.
Definizione
Il significato preciso di un concetto nuovo.
Teorema, proposizione, osservazione
Un risultato da ricordare, con le sue ipotesi.
Esempio
Un calcolo svolto per intero, un passo alla volta.
In verde il punto chiave da portare a casa.
Dimostrazione — si apre con un clic
Le dimostrazioni ci sono tutte, ma chiuse: prima leggi l'enunciato, poi apri la dimostrazione quando vuoi studiarla. Lo stesso vale per le soluzioni degli esercizi.
Le parti del corso¶
-
1 · Funzioni lineari, poliedri e problemi di programmazione lineare
Funzioni lineari (gradiente, Hessiano e insiemi di livello), semispazi e poliedri, problemi di ottimizzazione lineare con le loro soluzioni ottime, esempi e proprietà, le forme canonica e standard con il metodo grafico, esiti possibili ed equivalenze fra le forme.
1. Funzioni lineari · 2. Semispazi e poliedri · 3. Problemi di ottimizzazione lineare · 4. Problemi di programmazione lineare · 5. Esiti possibili e formulazioni equivalenti
-
2 · L'algoritmo del simplesso
L'algoritmo del simplesso sui dizionari, condizioni di ottimalità, regole di pivot e ciclaggio, la Fase 0 con il problema ausiliario. Esempi svolti passo per passo ed esercizi con la soluzione completa in fondo a ogni capitolo.
6. Algoritmo del simplesso · 7. Condizioni di ottimalità e regole di pivot · 8. Fase 0 dell'algoritmo del simplesso
-
3 · Dualità e simplesso duale
Il problema duale, i teoremi della dualità debole e forte, gli esiti possibili della coppia primale-duale, gli scarti complementari; l'algoritmo del simplesso duale, i certificati di inammissibilità e la riottimizzazione. Esempi svolti passo per passo ed esercizi con la soluzione completa in fondo a ogni capitolo.
9. Teoria della dualità · 10. Algoritmo del simplesso duale
-
4 · Metodi matriciali, sensitività e geometria
Il simplesso rivisto primale e duale, il metodo primale-duale, l'analisi di sensitività, la geometria della programmazione lineare (facce, vertici e soluzioni di base). Esempi svolti passo per passo ed esercizi con la soluzione completa in fondo a ogni capitolo.
11. Algoritmo del simplesso rivisto · 12. Algoritmo del simplesso duale rivisto · 13. Il metodo primale-duale · 14. Analisi di sensitività · 15. La geometria della programmazione lineare
-
5 · Modellazione
Le tecniche per scrivere un modello di programmazione lineare a partire dalla descrizione di un problema (produzione, miscelazione, trasporto, pianificazione multi-periodo, linearizzazioni), con esempi svolti. I modelli completi sono nell'eserciziario 5.
16. Tecniche di modellazione per la programmazione lineare
Da non perdere¶
-
Esercizi con le soluzioni
Esercizi per ogni capitolo, ciascuno con la soluzione svolta che si apre con un clic.
-
Laboratorio interattivo
Muovi i parametri con i cursori, trascina i punti e guarda poliedri, rette di livello, vertici ottimi e problemi duali cambiare sotto i tuoi occhi.
-
Dispense ed eserciziari in PDF
Cinque volumi di dispense, cinque di esercizi e il catalogo dei problemi, con la stessa numerazione del sito.
-
Catalogo dei problemi
I problemi P0–P86 usati negli esempi e negli esercizi, con la figura della regione ammissibile.
-
Indice completo
Tutti i capitoli con le loro sezioni, in una pagina.
Dello stesso autore:
- Ottimizzazione convessa — insiemi e funzioni convesse, problemi di ottimizzazione convessa, con grafici interattivi;
- Algoritmi — rappresentazione dei numeri, pseudocodice, ordinamento e ricerca, analisi e algoritmi ricorsivi;
- Programmazione lineare intera — rilassamento continuo, disuguaglianze valide, piani di taglio, branch-and-bound e branch-and-cut;
- Ottimizzazione combinatoria — zaino, bin packing, colorazione, TSP, scheduling e lot sizing, risolti in tutti i modi;
- Ottimizzazione su reti — grafi, alberi ricoprenti, cammini minimi, flussi su reti, simplesso su reti e gestione dei progetti;
- Modellazione MIP — modelli di programmazione lineare a variabili intere, dalla formulazione alla soluzione con i solver;
- Laboratorio di Ricerca Operativa — modellazione e risoluzione di problemi di ottimizzazione con Python e i solver;
- Analisi Matematica 1 — numeri reali, funzioni, limiti, derivate e serie, con i grafici interattivi;
- Algebra lineare — vettori, matrici, determinanti, sistemi lineari e autovalori, con il laboratorio di calcolo.
Materiale didattico di Fabio Furini — DIAG, Sapienza Università di Roma.
This website is also available in English.