Lezioni 1 e 2 - 26/09/2006

Modelli matematici (vedi dispensa ):

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

• 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 - 27/09/2006

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

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

Lezioni 5 e 6 - 28/09/2006

• Problema del trasporto di merci
  • modellizzazione
  • modello di set partitioning
• Problema del portafoglio

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

Lezioni 7 e 8 - 3/10/2006

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

• Geometria:
  • insieme ammissibile = poliedro
  • ottimi sui vertici
  • determinazione di un vertice degenerazione

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

Lezioni 9 e 10 - 4/10/2006

• Metodo del simplesso:
  • basi e vertici
• Dualità:
  • come valore delle risorse in base alla domanda-offerta
  • come valore delle risorse in base al loro valore aggiunto

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

Lezioni 11 e 12 - 5/10/2006

• complementarità
• definizione formale -> dualità forte

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

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

Lezioni 13 e 14 - 10/10/2006

Programmazione lineare intera:

(vedi anche dispensa, Ottimizzazione cap. 13 e 14):

• suddivisione del problema
• limitazioni inferiori
• limitazioni superiori
• complessità computazionale
• esempio: node covering pesato (file lingo, file excel)
• branch-and-bound (albero di ricerca: slides formato web page, slides formato powerpoint)

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

Lezioni 15 e 16 - 12/10/2006

• branch-and-cut
• esempi particolari di variabili 0-1

Presenza di più obiettivi (vedi dispensa) :

• definizione di ottimi di Pareto
• determinazione aggiungendo vincoli

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

Lezioni 17 e 18 - 17/10/2006

• determinazione come combinazione convessa
• generazione degli ottimi di Pareto in PL
• esempio d'investimento (appunti) (file excel)

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

Lezioni 19 e 20 - 18/10/2006

• esempio d'investimento (continuazione)
• ottimi lessicografici

Risoluzione del problema della turnazione del personale

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

Lezioni 21 e 22 - 19/10/2006

Modelli di routing

(vedi anche Ottimizzazione cap. 9 e dispense):

• Cammini minimi
  • grafi orientati: principio di ottimalità -> equazione di Bellman
  • risoluzione dell'equazione di Bellman:
    • per grafi aciclici

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

Lezioni 23 e 24 - 24/10/2006

• algoritmo di Dijkstra (richiami)
• per grafi generici
• 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 - 25/10/2006

• cammini e vertici

• [ non svolto: Studio di un caso: due obiettivi: minima distanza e minimo rischio:
  • valutazione del rischio d'impatto ambientale
  • modello di programmazione dinamica
  • modello di PL
    • file Lingo per minima distanza e/o danno
    • file Lingo per minima distanza e/o danno attesi e massima probabilita`
    • file Excel per danno atteso e con distanza attesa]
• confronto di stringhe in biologia computazionale

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

Lezioni 27 e 28 - 26/10/2006

• prodotto di matrici

• Cammini minimi con capacità - Flussi (vedi anche Ottimizzazione cap. 8 e dispensa ):
  • flussi di costo minimo con PL (file Excel)
  • massimo flusso e minima capacità di taglio (con sergente e destinazione)
    • Algoritmo di Ford-Fulkerson

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

Lezioni 29 e 30 - 31/10/2006

• equivalnza fra minimo taglio e massimo flusso

• minima capacità di taglio (senza sorgente e destinazione)
  • algoritmo probabilistico
  • [ non svolto: algoritmo deterministico]

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

Lezioni 31 e 32 - 2/11/2006

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

  (vedi anche Ottimizzazione cap. 12 e dispensa):

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

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

Lezioni 33 e 34 - 7/11/2006

• euristiche: (dispensa)
  • Ricerca locale
  • Simulated annealing

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

Lezioni 35 e 36 - 9/11/2006

vedi anche Ottimizzazione cap. 10 e dispensa):

• Accoppiamento
  • pesato con PL
  • inserzione di piani di taglio
• Assegnamento
  • pesato con PL
  • [non svolto: pesato con algoritmo di cammino minimo ]

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

Lezioni 37 e 38 - 14/11/2006

• Applicazioni sportive (file Lingo per min breaks)
• Cammini minimi che passano per tutti gli archi (vedi dispensa)
  • grafi euleriani non orientati
  • il problema del postino cinese su grafi non orientati

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

Lezioni 39 e 40 - 15/11/2006

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

Modelli di allocazione

• Knapsack (vedi anche Ottimizzazione cap. 9 e dispensa)
  • modello di Programmazione Dinamica per knapsack 0-1

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

Lezioni 41 e 42 - 16/11/2006

• modello di PLI per knapsack 0-1
• rilassamento continuo
• modello di Programmazione Dinamica per knapsack intero

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

Lezione 43 e 44 - 22/11/2006

Programmazione Lineare con generazione di colonne

• condizioni di ottimalità primale-duale
• ammissibilità duale
• problema generatore di colonne
• Bin packing (slides powerpoint)
  • modello avanzato: generazione di colonne (file Lingo: master , generatore; file Excel)
• altri esempi:
  • massimo flusso

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

Lezioni 45 e 46 - 23/11/2006

• problemi multi-flusso (vedi appunti, file Excel per modello normale)

• Modello di bin packing compatto (file Lingo, file Excel)

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

Lezioni 47 e 48 - 28/11/2006

• metodi approssimati per bin-packing
• altre formulazioni per bin-packing