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

Lezioni 1 e 2 - 26/09/2012

Presentazione del corso

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

Lezioni 3 e 4 - 27/09/2012

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 pianificazione di attività
  • Modellizzazione
  • Primo e secondo modello
• Problema della turnazione del personale
  • modello di programmazione lineare intera
• Problema del portafoglio
  • modello di programmazione non lineare

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

Lezioni 5 e 6 - 3/10/2012

Presenza di più obiettivi (vedi RO Cap. 3)

• definizione di ottimi di Pareto
• determinazione come combinazione convessa
• determinazione aggiungendo vincoli
• minima distanza da punti ideali

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

Lezioni 7 e 8 - 4/10/2012

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 9 e 10 - 10/10/2012

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

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

Lezioni 11 e 12 - 11/10/2012

• dualità per il caso generale
• Programmazione Lineare in Excel, piccolo file di esempio
• Programmazione Lineare in Lingo, piccolo file di esempio

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

Lezioni 13 e 14 - 17/10/2012

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

• suddivisione del problema
• limitazioni inferiori
• limitazioni superiori

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

Lezioni 15 e 16 - 18/10/2012

• esempio: 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 - 24/10/2012

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
  • per grafi generici
    • algoritmo di Bellman-Ford
    • algoritmo di Dijkstra

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

Lezioni 19 e 20 - 25/10/2012

• algoritmo di Floyd-Warshall
• Algoritmo di Dijkstra per grafi molto grandi (dispensa)

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

Lezioni 21 e 22 - 31/10/2012

• Algoritmo di Dijkstra per 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 - 7/11/2012

• 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
  • algoritmo probabilistico, analisi di probabilità;

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

Lezioni 25 e 26 - 8/11/2012

• algoritmo probabilistico, strutture dati e complessità
• Particolare applicazione del massimo flusso ad un problema di assegnazione del personale

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

Lezioni 27 e 28 - 14/11/2012

• Assegnamento (vedi RO Cap. 13)
  • di cardinalità
  • pesato con PL
• Accoppiamento
  • pesato con PL
  • inserzione di piani di taglio
• Applicazioni ad eventi sportivi (vedi RO Cap. 14)
  • costruzione di un calendario

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

Lezioni 29 e 30 - 15/11/2012

• effetto di riporto
• 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 - 21/11/2012

• Cammini minimi che passano per tutti i nodi (TSP) (vedi RO Cap. 16, Ott cap. 12)
  • modello di PL (caso non orientato)
  • diseguaglianze di sottocircuito e loro identificazione come minimo taglio
  • metodo branch-and -cut
  • articolo di Pataki sui modelli di PLI per TSP
• 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
  • grafi euleriani orientati e misti

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

Lezioni 33 e 34 - 22/11/2012

• 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;)

• esempi al calcolatore per Circuiti euleriani:
  • 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 PLI per knapsack 0-1
  • rilassamento continuo

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

Lezioni 35 e 36 - 28/11/2012

• modello di Programmazione Dinamica 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)

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

Lezioni 37 e 38 - 29/11/2012

• Programmazione Lineare con generazione di colonne (vedi RO Cap. 11)
  • condizioni di ottimalità primale-duale
  • ammissibilità duale
  • problema generatore di colonne
  • esempio massimo flusso
  • esempio multi flusso