Lezioni 1 e 2 - 30/09/2008

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).

Esempi di problemi

• 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 - 2/10/2008

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

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

Lezioni 5 e 6 - 7/10/2008

• Problema del trasporto di merci
  • modellizzazione
  • modello di set partitioning
• Problema dell'orario scolastico

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

Lezioni 7 e 8 - 9/10/2008

• Problema dell'orario scolastico (continuazione)

Presenza di più obiettivi

• definizione di ottimi di Pareto

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

Lezioni 9 e 10 - 14/10/2008

• determinazione come combinazione convessa
• determinazione aggiungendo vincoli
• esempio

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

Lezione 11 - 16/10/2008

Caratteristiche della PL (vedi anche Ottimizzazione cap. 6 e 7):

• Geometria:
  • insieme ammissibile = poliedro

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

Lezioni 12 e 13 - 21/10/2008

• ottimi sui vertici
• determinazione di un vertice degenerazione

• Metodo del simplesso:
  • basi e vertici

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

Lezioni 14 e 15 - 23/10/2008

• 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 16 e 17 - 28/10/2008

• complementarità

• Programmazione Lineare in Lingo, piccolo file di esempio
• Programmazione Lineare in Excel, piccolo file di esempio

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

Lezione 18 - 30/10/2008

Programmazione lineare intera:

(vedi anche Ottimizzazione cap. 13 e 14):

• suddivisione del problema
• limitazioni inferiori
• limitazioni superiori

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

Lezioni 19 e 20 - 4/11/2008

• esempio: node coloring (file lingo, file excel per node covering pesato )
• branch-and-bound (albero di ricerca: slides formato powerpoint per node covering pesato )

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

Lezioni 21 e 22 - 6/11/2008

Modelli di routing

• Cammini minimi
  • grafi orientati: principio di ottimalità -> equazione di Bellman
  • risoluzione dell'equazione di Bellman:
  • per grafi aciclici
  • per grafi generici
    • algoritmo di Dijkstra (richiami)

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

Lezioni 23 e 24 - 11/11/2008

• con PL (file Lingo per grafi orientati e per grafi non orientati files Excel primale e duale)
• interpretazione del duale come flusso

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

Lezioni 25 e 26 - 13/11/2008

• cammini e vertici

• confronto di stringhe in biologia computazionale
• prodotto di matrici

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

Lezioni 27 e 28 - 18/11/2008

• Cammini minimi con capacità - Flussi (vedi anche Ottimizzazione 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
  • massimo flusso per ammissibilità

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

Lezioni 29 e 30 - 20/11/2008

• Applicazione del massimo flusso ai seggi elettorali
  • assegnazione seggi a distretti

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

Lezioni 31 e 32 - 25/11/2008

• assegnazione biproporzionale

• Minima capacità di taglio (senza sorgente e destinazione)

  • algoritmo probabilistico

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

Lezione 33 - 27/11/2008

• strutture dati e complessità

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

Lezioni 34 e 35 - 4/12/2008

• Cammini minimi che passano per tutti i nodi (TSP)

  (vedi anche Ottimizzazione cap. 12):

  • modello di PL (caso non orientato)
  • descrizione poliedrale: piani di taglio
  • metodo branch-and -cut (file Mathematica, scaricare anche mystile; file Lingo)

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

Lezioni 36 e 37 - 11/12/2008

• euristiche:
  • metodi greedy
  • Ricerca locale
  • Simulated annealing

edi anche Ottimizzazione cap. 10):

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

Lezioni 38 e 39 - 16/12/2008

• Assegnamento
  • di cardinalità
  • pesato con PL
• Accoppiamento
  • pesato con PL
  • inserzione di piani di taglio
• Applicazioni sportive
  • costruzione di un calendario

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

Lezioni 40 e 41 - 18/12/2008

• minimizzazione dei breaks (file Lingo per min breaks)

• Cammini minimi che passano per tutti gli archi
  • grafi euleriani non orientati
  • 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

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

Lezioni 42 e 43 - 8/01/2009

Modelli di allocazione

• Knapsack (vedi anche Ottimizzazione cap. 9)
  • modello di Programmazione Dinamica per knapsack 0-1
  • modello di PLI per knapsack 0-1
  • rilassamento continuo
  • modello di Programmazione Dinamica per knapsack intero
• Bin Packing
  • formulazione e varianti (Multi processor scheduling, Cutting Stock)
  • modello di PLI

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

Lezione 44 e 45 - 13/01/2009

• modello con generazione di colonne

Programmazione Lineare con generazione di colonne

• condizioni di ottimalità primale-duale
• ammissibilità duale
• problema generatore di colonne
• massimo flusso

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

Lezioni 46 e 47 - 15/01/2009

• problemi multi-flusso (file Excel per modello normale)
• esempio Bin packing (slides powerpoint, file Lingo: master , generatore; file Excel)
• metodi approssimati per bin-packing

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

Lezione 48 - 20/01/2009

• Capacitated Vehicle Routing
  • (file Lingo per modello diretto, master e generatore per modello a generazione di colonne)