Bibliografia:
Ricerca
Operativa (RO), Ottimizzazione
(Ott)
Lezioni 1 e 2 -
1/10/2014
Presentazione del corso (file
ppt)
----------------------------------------------------------------
Lezioni 3 e 4 -
2/10/2014
Modelli
matematici (vedi RO 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).
Esempi di problemi
(vedi RO Cap.
2)
- Problema
della dieta
- Definizione delle
grandezze: alimenti, nutrienti
- Vincoli fra le grandezze
- Obiettivi: costi,
preferenze
- Modello di programmazione
lineare. Raffinamento del modello
---------------------------------------------------------------
Lezioni 5 e 6 -
8/10/2014
- Problema della pianificazione di
attività
- Problema
della turnazione del personale
- modello di
programmazione lineare intera
---------------------------------------------------------------
Lezioni 7 e 8 -
9/10/2014
- Ottimalità
secondo molti
obiettivi
- Soluzioni non dominate -
ottimi di Pareto
- Combinazione lineare degli
obiettivi
- Trasformazione degli
obiettivi in vincoli
---------------------------------------------------------------
Lezioni 9 e 10 -
15/10/2014
Caratteristiche della PL
(vedi RO
Cap. 4, Ott Cap. 6 e 7)
- Geometria:
- insieme ammissibile =
poliedro
- ottimi sui vertici
- determinazione di un
vertice, degenerazione
- Metodo del simplesso:
- basi e vertici
- inizializzazione del
metodo
----------------------------------------------------------------
Lezioni 11 e 12 -
16/10/2014
- Dualità:
- definizione formale
- dualità forte
- come valore delle
risorse in base al loro valore aggiunto
---------------------------------------------------------------
Lezioni 13 e 14
- 22/10/2014
- come valore determinato
dalla domanda e offerta
- complementarità
Programmazione
lineare intera (vedi
RO
Cap. 7, Ott Cap. 13 e 14)
- suddivisione del problema
- limitazioni inferiori
- limitazioni superiori
----------------------------------------------------------------
Lezioni 15 e 16
- 23/10/2014
- Esempi
di Programmazione
Lineare in
Excel,
piccolo file di esempio
- Esempi
di Programmazione Lineare in
Lingo,
piccolo file di esempio
- Esempi
di Programmazione Lineare Intera in
Lingoesempio:
- set covering ((file lingo)
- node covering
(file lingo,
file excel
per node covering pesato)
- branch-and-bound (albero
di
ricerca: slides
formato powerpoint per node
covering pesato)
----------------------------------------------------------------
Lezioni 17 e 18
- 29/10/2014
- continuazione esempio al
calcolatore
Modelli di percorsi
(vedi RO Cap. 9)
- Cammini
minimi
- grafi orientati:
principio di ottimalità ->
equazione di Bellman
- risoluzione
dell'equazione di Bellman:
- per grafi aciclici
----------------------------------------------------------------
Lezioni 19 e 20
- 30/10/2014
- per
grafi con costi
positivi: algoritmo di Dijkstra
- per grafi generici
- algoritmo di
Bellman-Ford
- algoritmo di
Floyd-Warshall
----------------------------------------------------------------
Lezioni 21 e 22
- 5/11/2014
----------------------------------------------------------------
Lezione 23 e 24
- 6/11/2014
- Cammini
minimi con capacità -
Flussi (vedi
RO Cap. 10, Ott Cap. 8):
- flussi di costo minimo con PL (file Excel)
- Massimo
flusso e minima capacità di taglio (con
sergente e destinazione)
- Algoritmo di Ford-Fulkerson
- equivalenza fra minimo taglio e
massimo
flusso
- Minima capacità di taglio (senza sorgente e destinazione)
(vedi RO Sez. 10-4)
- algoritmo deterministico con massimo
flusso
--------------------------------------------------------------
Lezioni 25 e 26
- 12/11/2014
- algoritmo deterministico diretto,
descrizione;
- algoritmo probabilistico, analisi
probabilistica, strutture dati e complessità
----------------------------------------------------------------
Lezioni 27 e 28
- 13/11/2014
- Assegnamento
(vedi RO Cap.
13)
- di cardinalità
- pesato con PL
- teorema del matrimonio
- Accoppiamento
- pesato con PL
- inserzione di piani di taglio
----------------------------------------------------------------
Lezioni 29 e 30
- 19/11/2014
- Applicazioni ad eventi sportivi
(vedi RO Cap. 14)
- costruzione di un calendario
- incontri in casa-fuori
casa
- modellazione come max-cut
- Minimi
alberi di supporto (vedi RO
Sez. 16.9)
- Algoritmo di Kruskal
- Algoritmo di Prim
- Algoritmo di Boruvka
----------------------------------------------------------------
Lezioni 31 e 32
- 20/11/2014
- Cammini
minimi che passano per tutti i nodi (TSP)
(vedi RO
Cap. 16, Ott cap. 12)
- modello di PL (caso
non
orientato e caso orientato)
- diseguaglianze di
sottocircuito e loro identificazione come
minimo taglio
- metodo branch-and -cut
- articolo
di Pataki sui modelli di
PLI per TSP
----------------------------------------------------------------
Lezioni 33 e 34
- 26/11/2014
- esempi al calcolatore
per
TSP:
- file
Mathematica, scaricare anche mystile;
- file
Lingo con generatore di tagli come massimi flussi;
- file
Lingo con generatore di
tagli come tagli minimi fatti con PLI;)
- Cammini minimi che passano per tutti
gli
archi (vedi
RO Cap. 15)
- grafi euleriani non orientati
- grafi euleriani orientati
- grafi euleriani misti
- il problema del postino cinese su
grafi
non orientati
----------------------------------------------------------------
Lezioni 35 e 36
- 27/11/2014
- il
problema del postino cinese su
grafi
orientati
- il problema del postino
cinese su
grafi
misti
- file
Lingo per postino
cinese per grafi misti
- file
Lingo per postino
rurale per grafi non orientati
Modelli di allocazione
(vedi RO Cap. 17, Ott Cap. 9)
- Knapsack
- modello di Programmazione Dinamica
per
knapsack 0-1
- modello di Programmazione Dinamica
per
knapsack intero
----------------------------------------------------------------
Lezioni 37 e 38
- 3/12/2014
- rilassamento continuo
- modello di PLI per knapsack 0-1
- modello di PLI per knapsack intero
- Bin Packing
- formulazione e varianti (Multi
processor scheduling, Cutting Stock)
- modello di PLI
- modello con generazione di colonne
(slides
powerpoint, file Lingo: master
, generatore; file Excel)
- Programmazione Lineare con
generazione
di
colonne (vedi
RO Cap. 11)
- condizioni di ottimalità
primale-duale
- ammissibilità duale
- problema generatore di colonne
----------------------------------------------------------------
Lezioni 39 e 40
- 4/12/2014
- esempio massimo flusso
- esempio multi
flusso
- esempio per rotte
di veicoli
----------------------------------------------------------------
Lezioni 41 e
42 - 10/12/2014
- Euristiche
(vedi RO Cap. 12 e 16-7,
Ott
cap. 10)
- metodi
greedy
- ricerca locale
- simulated annealing
----------------------------------------------------------------
Lezioni 43 e
44 - 11/12/2014
- Rotte
di veicoli
(vedi RO Cap. 19)
- Modello di PLI diretto
- Modello a generazione di colonne
- Euristica di Clark e Wright
----------------------------------------------------------------
Lezioni 45 e
46 - 17/12/2014
- Schedulazione
- Problemi ad una
macchina.
- Algoritmo per minima somma pesata
(regola di Smith)
- Algoritmo per minimo massimo ritardo
(regola di Jackson)
----------------------------------------------------------------
Lezioni 47 e
48 - 18/12/2014
- Problemi
a molte macchine
- Job Shop, Flow Shop,
Open Shop
- Flow
Shop con due macchine
- Flow Shop no wait
- Job Shop con euristica
Shifting Bottleneck
- Open Shop con preemption