Bibliografia: Ricerca Operativa (RO), Ottimizzazione (Ott)

Lezioni 1 e 2 -  1/10/2015

Presentazione del corso

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

Lezioni 3 e 4 - 2/10/2015

• Obiettivi: costi, preferenze
• Modello di programmazione lineare. Raffinamento del modello

• Problema della pianificazione di attività
  • Modellizzazione
  • Primo e secondo modello

---------------------------------------------------------------

Lezioni 5 e 6 -  8/10/2015

• Problema della turnazione del personale 
• modello di programmazione lineare intera
• Problema del trasporto merci
  • modellizzazione

---------------------------------------------------------------

Lezioni 7 e 8 -  9/10/2015

• 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/2015

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/2015

• Dualità:
  • come valore determinato dalla domanda e offerta
  • definizione formale
  • dualità forte
  • come valore delle risorse in base al loro valore aggiunto

---------------------------------------------------------------

Lezioni 13 e 14 -  22/10/2015

• complementarità
• esempi

Programmazione lineare intera (vedi RO Cap. 7, Ott Cap. 13 e 14)

• introduzione

Lezioni 15 e 16 - 23/10/2015

• suddivisione del problema
• limitazioni inferiori
• limitazioni superiori
• 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/2015

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/2015

• per grafi con costi positivi: algoritmo di Dijkstra
• per grafi generici
• algoritmo di Bellman-Ford
• algoritmo di Floyd-Warshall
• cammini minimi su grafi molto grandi

----------------------------------------------------------------

Lezioni 21 e 22 -  5/11/2015

• cammini minimi su grafi molto grandi
• con PL (file Lingo per grafi orientati e per grafi non orientati files Excel primale e duale)
• interpretazione del duale come flusso
• Flussi e cammini

----------------------------------------------------------------

Lezione 23 e 24 -  6/11/2015

• cammini con più obiettivi

• 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

Lezioni 25 e 26 -  12/11/2015

• Minima capacità di taglio (senza sorgente e destinazione) (vedi RO Sez. 10-4)
  • algoritmo deterministico con massimo flusso
  • algoritmo deterministico diretto, descrizione
  • algoritmo probabilistico, analisi probabilistica

Lezioni 27 e 28 -  13/11/2015

• Assegnamento (vedi RO Cap. 13)
  • di cardinalità
  • pesato con PL

Lezioni 29 e 30 -  19/11/2015

• Applicazioni a sistemi elettorali (vedi RO Cap. 4 e dispensa)
  • assegnazione di seggi a distretti
  • allocazione biproporzionale

Lezioni 31 e 32 -  20/11/2015

• allocazione biproporzionale (continuazione)

• Accoppiamento
  • pesato e di cardinalità con PL
  • inserzione di piani di taglio

• Minimi alberi di supporto (vedi RO Sez. 16.9)
• algoritmo di Kruskal

Lezioni 33 e 34 -  26/11/2015

• algoritmo di Prim
• algoritmo di Boruvka

• Cammini minimi che passano per tutti i nodi (TSP) (vedi RO Cap. 16, Ott cap. 12)
• circuiti hamiltoniani
• modello di PL (caso simmetrico)
• diseguaglianze di sottocircuito e loro identificazione come minimo taglio
• metodo branch-and-cut
• articolo di Pataki sui modelli di PLI per TSP

Lezioni 35 e 36 -  27/11/2015

• 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
  • il problema del postino cinese su grafi non orientati

Lezioni 37 e 38 -  3/12/2015

• grafi euleriani orientati
• grafi euleriani misti
• 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

Lezioni 39 e 40 -  4/12/2015

• modello di programmazione dinamica per knapsack intero
• modello di PLI per knapsack 0-1
• rilassamento continuo
• modello di PLI per knapsack intero

• Bin Packing
  • 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 41 e 42 -  10/12/2015

• esempio massimo flusso
• esempio multi flusso

Lezioni 43 e 43 -  11/12/2015

• esempi al calcolatore
• Euristiche
(vedi RO Cap. 12 e 16-7, Ott cap. 10)
• metodi greedy
• ricerca locale
• simulated annealing

----------------------------------------------------------------

Lezioni 45 e 46 -  17/12/2015

• Schedulazione
  • Problemi ad una macchina.
  • Algoritmo per minima somma pesata (regola di Smith)
  • Algoritmo per minimo massimo ritardo (regola di Jackson)
  • Modelli a tempi indicizzato
    

Lezioni 47 e 48 -  18/12/2015

• 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