Lezioni 1 e 2 - 8/3/2010
Modelli matematici: (vedi Ricerca Operativa Cap. 1)
- grandezze (valori quantitativi che
entrano nel processo decisionale):
- dati (valori esterni fuori dal
controllo diretto del decisore);
- grandezze decisionali:
- parametri decisionali (valori
fissati direttamente dal decisore);
- variabili decisionali (valori
calcolati dal modello);
- vincoli fra le grandezze:
- vincoli strutturali (dipendono dalla
struttura del problema);
- vincoli flessibili (introdotti dal
decisore in base alle sue preferenze);
- obiettivi (esplicitano le
relazioni di preferenza del decisore).
Esempio della dieta (vedi Ricerca Operativa Cap. 2)
- Individuazione delle grandezze:
- alimenti (quantità da
determinare -> variabili decisionali)
- costi (dati)
- nutrienti (quantità da
determinare -> variabili decisionali)
- Individuazione dei vincoli:
- non negatività delle
quantità di alimenti e di nutrienti (vincoli
strutturali)
- legami fra alimenti e nutrienti
(vincoli strutturali)
- Individuazione degli obiettivi
- minimizzazione della spesa
- raggiungimento di una dieta
"salutare" (trasformazione in vincolo flessibile)
- Primo modello
---------------------------------------------------------------
Lezioni 3 e 4 - 9/3/2010
Esempio della pianificazione di attività (vedi Ricerca Operativa Cap. 2)
- Con vincoli temporali di precedenza
- Modello con grafo orientato aciclico
- Con costi e durate variabili
- Modello di programmazione lineare
Esempio della turnazione (vedi Ricerca Operativa Cap. 2)
-----------------------------------------------------------------
Lezioni 5 e 6 - 10/3/2010
- Programmazione Lineare in Excel
- piccolo file di esempio
◊
altri esempi ◊,
&loz
- primo modello
della dieta
&loz
- modello
della pianificazione, solo precedenze
&loz, con costi
&loz
- modello
della turnazione
&loz
- Programmazione Lineare in Lingo
- piccolo file di esempio
◊
- primo modello
della dieta
&loz
- modello
della pianificazione, con costi e precedenze
&loz
-----------------------------------------------------------------
Lezioni 7 e 8 - 11/3/2010
Programmazione Lineare (vedi Ricerca Operativa Cap. 4 e anche
Ottimizzazione
cap. 6 e 7):
- Geometria:
- insieme ammissibile = poliedro
- ottimi sui vertici
- algoritmo del simplesso (cenni)
- degenerazione
-----------------------------------------------------------------
Lezioni 9 e 10 - 15/3/2010
- Dualità:
- come valore delle risorse in base alla domanda-offerta
- come valore delle risorse in base al loro valore aggiunto
----------------------------------------------------------------
Lezioni 11 e 12 - 16/3/2010
- complementarità
- vincoli di eguaglianza
- esercizi
-------------------------------------------------------------
Lezioni 13 e 14 - 17/3/2010
Programmazione lineare intera: (vedi Ricerca Operativa Cap. 7 e anche
Ottimizzazione
cap. 13 e 14):
- metodo branch-and-bound
- esemplificazione al calcolatore del
metodo branch-and-bound (slides powerpoint per
node covering pesato )
---------------------------------------------------------------
Lezioni 15 e 16 - 18/3/2010
- miglioramento della limitazione inferiore
- miglioramento della limitazione superiore
Presenza di più obiettivi: (vedi Ricerca Operativa Cap. 3)
- definizione di ottimi di Pareto
----------------------------------------------------------------
Lezioni 17 e 18 - 22/3/2010
- determinazione come combinazione convessa
- determinazione aggiungendo vincoli
----------------------------------------------------------------
Lezioni 19 e 20 - 23/3/2010
Modelli di percorsi
(vedi Ricerca Operativa Cap. 9 e anche
Ottimizzazione
Cap. 9):
- Cammini minimi e programmazione dinamica
- grafi orientati: principio di ottimalità ->
equazione di Bellman
- risoluzione dell'equazione di Bellman:
----------------------------------------------------------------
Lezioni 21 e 22 - 24/3/2010
- per grafi aciclici
- per grafi generici
--------------------------------------------------------------
Lezioni 23 e 24 - 25/3/2010
- algoritmo di Dijkstra
- Floyd-Warshall
- con PL
---------------------------------------------------------------
Lezioni 25 e 26 - 29/3/2010
- interpretazione del duale come flusso (file Excel per problema
primale e per problema
duale)
----------------------------------------------------------------
Lezioni 27 e 28 - 30/3/2010
Flusso a costo minimo (vedi Ricerca Operativa Cap. 10)
- massimo flusso e minima capacità di taglio
---------------------------------------------------------------
Lezioni 29 e 30 - 7/4/2010
- algoritmo probabilistico per minimo taglio
---------------------------------------------------------------
Lezioni 31 e 32 - 8/4/2010
- Assegnazione biproporzionale: seggi elettorali calcolati con reti di flusso (vedi Ricerca Operativa Cap. 14)
---------------------------------------------------------------
Lezioni 33 e 34 - 12/4/2010
- Assegnazione biproporzionale: continuazione
Cammini minimi che passano per tutti i nodi (TSP) (vedi Ricerca Operativa Cap. 16,
Ottimizzazione
cap. 12)
- modello di PL (caso non orientato)
- descrizione poliedrale: piani di taglio
---------------------------------------------------------------
Lezioni 35 e 36 - 13/4/2010
Problema di Knapsack (vedi Ricerca Operativa Cap. 17,
Ottimizzazione
Cap. 9))
- modello di PLI per knapsack 0-1
---------------------------------------------------------------
Lezioni 37 e 38 - 14/4/2010
- modello di Programmazione Dinamica per
knapsack 0-1
-
knapsack intero
Problema di Bin packing
- formulazione con schemi di
riempimento
----------------------------------------------------------------
Lezioni 39 e 40 - 15/4/2010