Lezioni 1 e 2 - 13/01
Modelli matematici:
- 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
- Individuazione delle grandezze:
- alimenti (quantità da
determinare -> variabili decisionali)
- costi (dati)
- preferenze (parametri
decisionali)
- 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
- massimizzazione della
preferenza
- raggiungimento di una dieta
"salutare" (trasformazione in vincolo flessibile)
vedi
dispensa
(pagine da 1 a 3)
----------------------------------------------------------------
Lezioni 3 e 4 - 14/01
Descrizione matematica del primo modello:
- formulazione matematica
- rappresentazione in Lingo (file
dieta1)
- rappresentazione in Excel (file
dieta1)
---------------------------------------------------------------
Lezioni 5 e 6 - 16/01
Presenza di più obiettivi:
- struttura di preferenze
- definizione di ottimi di Pareto
----------------------------------------------------------------
Lezioni 7 e 8 - 27/01
- determinazione come combinazione convessa
----------------------------------------------------------------
Lezioni 9 e 10 - 28/01
- determinazione aggiungendo vincoli
(vedi
dispensa)
Risoluzione del modello della dieta:
- generazione dei Pareto ottimi
(grafico)
- analisi della soluzione
- revisione del modello -> secondo modello (file
Lingo)
- secondo modello, analisi
(grafico)
-> terzo modello
Caratteristiche della PL (vedi
dispensa):
- Geometria:
- insieme ammissibile = poliedro
- ottimi sui vertici
- determinazione di un vertice
- degenerazione
----------------------------------------------------------------
Lezioni 11 e 12 - 30/01
- Metodo del simplesso:
- Dualità:
- come valore delle risorse in base alla domanda-offerta
----------------------------------------------------------------
Lezioni 13 e 14 - 3/02
- come valore delle risorse in base al loro valore aggiunto
- definizione formale -> dualità forte
----------------------------------------------------------------
Lezioni 15 e 16 - 4/02
- piccoli esempi Lingo: analisi
- piccoli esempi Excel: analisi
Caso della dieta:
--------------------------------------------------------------
Lezioni 17 e 18 - 6/02
Programmazione lineare intera:
- suddivisione del problema
- limitazioni inferiori
- limitazioni superiori
- complessità computazionale
- esempio
----------------------------------------------------------------
Lezioni 19 e 20 - 10/02
Caso della dieta:
- quarto modello (file
Lingo)
- analisi
(grafico)
- quinto modello (file
Lingo)
- analisi
(grafico)
- sesto modello:
- giustificazione teorica
- prima fase del modello (file
Lingo)
- seconda fase del modello (file completo
Lingo
e parziale
Lingo)
- analisi della soluzione
(grafico)
---------------------------------------------------------------
Lezioni 21 e 22 - 11/02
Modelli di routing
- Cammini minimi
- algoritmo di Dijkstra (richiami)
- grafi orientati: principio di ottimalità ->
equazione di Bellman
- risoluzione dell'equazione di Bellman:
- per grafi aciclici
- per grafi generici
----------------------------------------------------------------
Lezioni 23 e 24 - 13/02
----------------------------------------------------------------
Lezioni 25 e 26 - 17/02
- Studio di un caso: due obiettivi: minima distanza e minimo
rischio:
- modello di flusso (file
Lingo
e
risultati)
- modello di programmazione dinamica
---------------------------------------------------------------
Lezioni 27 e 28 - 18/02
- Flussi
- massimo flusso
- costo minimo
----------------------------------------------------------------
Lezioni 29 e 30 - 20/02
- Cammini minimi che passano per tutti i nodi (TSP)
- modello di PL (caso non orientato)
- descrizione poliedrale: piani di taglio
- metodo branch-and -cut
- euristiche
----------------------------------------------------------------
Lezioni 31 e 32 - 24/02
- Cammini minimi che passano per tutti
gli archi
- grafi euleriani
- il problema del postino cinese
- grafi non orientati, orientati e
misti
---------------------------------------------------------------
Lezioni 33 e 34 - 25/02
Modelli di allocazione
- Assegnamento
- di cardinalità
- pesato
- relazione con il massimo
flusso
----------------------------------------------------------------
Lezioni 35 e 36 - 27/02
- Accoppiamento
- di cardinalità (cenni)
- pesato con PL
- inserzione di piani di taglio
----------------------------------------------------------------
Lezioni 37 e 38 - 3/03
- Knapsack
- rilassamento contino
- modello di PL
- modello di Programmazione
Dinamica
----------------------------------------------------------------
Lezioni 39 e 40 - 4/03
- Bin packing
- modello di PL
- simmetria -> ridondanza di
soluzioni equivalenti
- povertà delle limitazioni
inferiori
- modello avanzato: generazione di
colonne
Programmazione Lineare con generazione di
colonne
- condizioni di ottimalità
primale-duale
- ammissibilità duale
- problema generatore di colonne
----------------------------------------------------------------
Lezioni 41 e 42 - 6/03
- altri esempi:
- massimo flusso
- problemi multi-flusso
- Problemi di staffing
----------------------------------------------------------------
Lezioni 43 e 44 - 10/03
Modelli di schedulazione
- a risorsa infinita
- PERT
- alberi dei cammini massimi
- crashing
- valutazione con incertezza
- a risorsa finita
----------------------------------------------------------------
Lezioni 45 e 46 - 11/03
- minimo della massima penalità
(con programmazione dinamica)
- presenza di date di rilascio: problemi
NP-difficili
----------------------------------------------------------------
Lezioni 47 e 48 - 13/03
- modellazione come LP a generazione di
colonne
- modelli a più macchine (cenni)
- flow-shop
- job-shop
- open-shop
----------------------------------------------------------------