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

Lezioni 1 e 2 - 29/9/2009

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
  • Individuazione delle grandezze:
  • Individuazione dei vincoli:
  • Individuazione degli obiettivi
• Descrizione matematica del primo modello: formulazione come Programmazione Lineare

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

Lezioni 3 e 4 - 30/9/2009

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

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

Lezioni 5 e 6 - 6/10/2009

• Problema della turnazione del personale (continuazione)
• Problema del trasporto di merci
  • modellizzazione
  • modello di set partitioning

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

Lezioni 7 e 8 - 7/10/2009

• Problema dell'orario scolastico

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

Lezioni 9 e 10 - 13/10/2009

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

• definizione di ottimi di Pareto
• determinazione come combinazione convessa
• determinazione aggiungendo vincoli

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

Lezion1 11 e 12 - 14/10/2009

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 13 e 14 - 20/10/2009

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

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

Lezioni 15 e 16 - 21/10/2009

• complementarità

• Programmazione Lineare in Excel, piccolo file di esempio
• Programmazione Lineare in Lingo, piccolo file di esempio
• Esempio della dieta in Excel: modello 1
• Esempio della dieta in Lingo: modello 1

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

Lezioni 17 e 18 - 27/10/2009

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

• suddivisione del problema
• limitazioni inferiori
• limitazioni superiori
• 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 19 e 20 - 3/11/2009

• esempi
  • turnazione
  • orario scuola media
  • pert

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 21 e 22 - 4/11/2009

• per grafi generici
  • algoritmo di Bellman-Ford
  • algoritmo di Dijkstra (richiami)
  • algoritmo di Floyd-Warshall
  con PL (file Lingo per grafi orientati e per grafi non orientati files Excel primale e duale)

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

Lezioni 23 e 24 - 10/11/2009

• interpretazione del duale come flusso
• cammini e vertici

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

Lezioni 25 e 26 - 11/11/2009

Esempio di PD: confronto di stringhe in biologia computazionale

Cammini minimi con capacità - Flussi (vedi RO Cap. 10, Ott Cap. 8):

• flussi di costo minimo con PL (file Excel)

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

Lezioni 27 e 28 - 17/11/2009

• massimo flusso e minima capacità di taglio (con sergente e destinazione)
  • Algoritmo di Ford-Fulkerson
  • equivalenza fra minimo taglio e massimo flusso
• massimo flusso per ammissibilità

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

Lezioni 29 e 30 - 18/11/2009

• Applicazione del massimo flusso ai seggi elettorali (vedi RO Sez. 14-4 e 14-5)
  • assegnazione seggi a distretti
  • assegnazione biproporzionale

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

Lezioni 31 e 32 - 24/11/2009

• Minima capacità di taglio (senza sorgente e destinazione) (vedi RO Sez. 10-4)
  • algoritmo deterministico
  • algoritmo probabilistico
  • strutture dati e complessità

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

Lezioni 33 e 34 - 25/11/2009

• 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 (file Mathematica, scaricare anche mystile; file Lingo)

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

Lezioni 35 e 36 - 1/12/2009

• esempi al calcolatore
• prize collecting TSP
• Cammini minimi che passano per tutti gli archi (vedi RO Cap. 15)
  • grafi euleriani non orientati

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

Lezioni 37 e 38 - 2/12/2009

• il problema del postino cinese su grafi non orientati
• grafi euleriani orientati e misti
• il problema del postino cinese su grafi orientati e su grafi misti
• il problema del postino rurale

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

Lezioni 39 e 40 - 9/12/2009

• Assegnamento (vedi RO Cap. 13)
  • di cardinalità
  • pesato con PL
• Accoppiamento
  • pesato con PL
  • inserzione di piani di taglio
  • circuiti negativi nei grafi

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

Lezioni 41 e 42 - 15/12/2009

• costruzione di un calendario
• minimizzazione dei breaks (file Lingo per min breaks)
• problema max-cut