Lezioni 1 e 2 - 27/9/2005

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

vedi dispensa

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

Lezioni 3 e 4 - 28/9/2005

Esempio della dieta

• Individuazione delle grandezze:
  • alimenti (quantità da determinare -> variabili decisionali)
  • costi (dati)
  • preferenze (parametri decisionali)
  • nutrienti (quantità da determinare -> variabili decisionali)
• Individuazione dei vincoli:
  • non negatività delle quantità di alimenti e di nutrienti (vincoli strutturali)
  • legami fra alimenti e nutrienti (vincoli strutturali)
• Individuazione degli obiettivi
  • minimizzazione della spesa
  • massimizzazione della preferenza
  • raggiungimento di una dieta "salutare" (trasformazione in vincolo flessibile)

Descrizione matematica del primo modello:

• formulazione matematica come Programmazione Lineare

vedi dispensa

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

• Geometria:
  • insieme ammissibile = poliedro
  • ottimi sui vertici

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

Lezioni 5 e 6 - 4/10/2005

• determinazione di un vertice degenerazione

• 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 7 e 8 - 6/10/2005

• complementarità
• definizione formale -> dualità forte

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

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

Lezione 9 - 11/10/2005

Presenza di più obiettivi (vedi dispensa) :

• definizione di ottimi di Pareto
• determinazione aggiungendo vincoli

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

Lezioni 10 e 11 - 12/10/2005

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

Risoluzione del modello della dieta (vedi dispensa):

• rappresentazione in Lingo del modello della dieta (file dieta1)
• rappresentazione in Excel del modello della dieta (file dieta1)
• analisi della soluzione

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

Lezioni 12 e 13 - 13/10/2005

• revisione del modello -> secondo modello (file Lingo dieta2, file Excel dieta2)
• secondo modello, analisi (grafico) -> terzo modello (file dieta3)

Programmazione lineare intera:

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

• suddivisione del problema
• limitazioni inferiori
• limitazioni superiori

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

Lezioni 14 e 15 - 18/10/2005

• complessità computazionale
• esempio: node covering pesato (file lingo, file excel)
• branch-and-bound (albero di ricerca: slides formato web page, slides formato powerpoint)
• branch-and-cut

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

Lezioni 16 e 17 - 19/10/2005

• esempi particolari di variabili 0-1

Caso della dieta:

• risoluzione del terzo modello (grafico)

  [ parte non svolta

• quarto modello ( (vedi dispensa , file Lingo)
• analisi (grafico)
• quinto modello
  • giustificazione teorica
  • prima fase del modello (file Lingo)
  • seconda fase del modello (file completo Lingo e parziale Lingo)

analisi (grafico) ]

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 18 e 19 - 20/10/2005

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

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

Lezioni 20 e 21 - 25/10/2005

• interpretazione del duale come flusso

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

Lezioni 22 e 23 - 26/10/2005

• Studio di un caso: due obiettivi: minima distanza e minimo rischio:
  • valutazione del rischio d'impatto ambientale
  • modello di programmazione dinamica
  • modello di PL

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

Lezioni 24 e 25 - 27/10/2005

• 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

• Altri problemi di programmazione dinamica:
  • confronto di stringhe in biologia computazionale

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

Lezioni 26 e 27 - 2/11/2005

• moltiplicazione di matrici

• Cammini minimi con capacità - Flussi (vedi anche Ottimizzazione cap. 8 e dispensa ):
  • flussi di costo minimo con PL (file Excel)

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

Lezioni 28 e 29 - 3/11/2005

• algoritmo per flussi di costo minimo
• massimo flusso e minima capacità di taglio (con sergente e destinazione)
  • Algoritmo di Ford-Fulkerson

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

Lezioni 30 e 31 - 8/11/2005

• minima capacità di taglio (senza sorgente e destinazione)
  • algoritmo probabilistico
  • algoritmo deterministico

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

Lezioni 32 e 33 - 9/11/2005

• 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 34 e 35 - 10/11/2005

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

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

Lezioni 36 e 37 - 15/11/2005

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

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

Lezioni 38 e 39 - 16/11/2005

• 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

Modelli di allocazione

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

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

Lezioni 40 e 41 - 17/11/2005

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

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

Lezioni 42 e 43 - 22/11/2005

Programmazione Lineare con generazione di colonne

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

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

Lezione 44 - 23/11/2005

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

Modelli di schedulazione

• a risorsa infinita
  • PERT (vedi dispensa)
    • alberi dei cammini massimi

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

Lezioni 45 e 46 - 24/11/2005

• crashing
• valutazione con incertezza

• a risorsa finita
  • modelli a una macchina (vedi dispensa)
    • minimo della somma pesata
    • minimo della massima penalità (con programmazione dinamica)

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

Lezioni 47 e 48 - 29/11/2005

• presenza di date di rilascio: problemi NP-difficili
• modellazione come LP (file Lingo: big-M, 5job, 20job)