Lezioni 1 e 2 - 30/09

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

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)

vedi dispensa (pagine da 1 a 3)

Descrizione matematica del primo modello:

• formulazione matematica come Programmazione Lineare

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

Lezioni 3 e 4 - 1/10

• Programmazione Lineare in Lingo, piccolo file di esempio
• Programmazione Lineare in Excel, piccolo file di esempio
• rappresentazione in Lingo del modello della dieta (file dieta1)
• rappresentazione in Excel del modello della dieta (file dieta1)

Risoluzione del modello della dieta:

• Presenza di più obiettivi (vedi dispensa) :
  • definizione di ottimi di Pareto
  • determinazione come combinazione convessa
  • determinazione aggiungendo vincoli
• generazione dei Pareto ottimi (grafico)
• analisi della soluzione

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

Lezioni 5 e 6 - 2/10

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

Programmazione lineare intera:

(vedi anche Ottimizzazione cap. 13 e 14):

• suddivisione del problema
• limitazioni inferiori
• limitazioni superiori
• complessità computazionale
• esempio

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

Lezioni 7 e 8 - 7/10

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

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

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

Lezioni 9 e 10 - 9/10

• degenerazione

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

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

Lezioni 11 e 12 - 14/10

• come valore delle risorse in base al loro valore aggiunto
• definizione formale -> dualità forte

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

Lezioni 13 e 14 - 15/10

• complementarità

• piccoli esempi Lingo: analisi
• piccoli esempi Excel: analisi

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

Lezioni 15 e 16 - 16/10

Caso della dieta:

• quarto modello (file Lingo)
• analisi (grafico)
• quinto modello (file Lingo)
• analisi (grafico)
• sesto modello:
  • giustificazione teorica
  • prima fase del modello (file Lingo)
  • seconda fase del modello (file completo Lingo e parziale Lingo)
  • analisi della soluzione (grafico)

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

Lezioni 17 e 18 - 21/10

Modelli di routing

(vedi anche Ottimizzazione cap. 9 e dispense):

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

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

Lezioni 19 e 20 - 22/10

• per grafi generici
• con PL (file Lingo per grafi orientati e per grafi non orientati)

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

Lezioni 21 e 22 - 23/10

• interpretazione del duale come flusso

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

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

Lezioni 23 e 24 - 28/10

• modello di flusso (file Lingo e risultati)
• modello di programmazione dinamica

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

Lezioni 25 e 26 - 29/10

• modello di programmazione dinamica

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

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

Lezioni 27 e 28 - 30/10

(vedi anche Ottimizzazione cap. 8):

• Flussi
  • massimo flusso e minima capacità di taglio (con sergente e destinazione)
    • Algoritmo di Ford-Fulkerson
    • Perfezionamento dell'algoritmo
  • minima capacità di taglio (senza sorgente e destinazione)
    • algoritmo probabilistico (vedi appunti)

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

Lezioni 29 e 30 - 4/11

• flussi di costo minimo

(vedi anche Ottimizzazione cap. 12):

• Cammini minimi che passano per tutti i nodi (TSP)
  • modello di PL (caso non orientato)

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

Lezioni 31 e 32 - 6/11

• descrizione poliedrale: piani di taglio
• metodo branch-and -cut

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

Lezioni 33 e 34 - 11/11

• euristiche

• Cammini minimi che passano per tutti gli archi
  • grafi euleriani
  • il problema del postino cinese
  • grafi non orientati, orientati e misti

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

Lezioni 35 e 36 - 12/11

(vedi anche Ottimizzazione cap. 10):

Modelli di allocazione

• Assegnamento
  • pesato con PL
• Accoppiamento
  • pesato con PL
  • inserzione di piani di taglio

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

Lezioni 37 e 38 - 13/11

• Assegnamento
  • pesato con algoritmo di cammino minimo (vedi appunti)
  • esempio

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

Lezioni 39 e 40 - 18/11

• Knapsack
  • modello di Programmazione Dinamica
  • rilassamento continuo
  • modello di PLI

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

Lezioni 41 e 42 - 19/11

• Bin packing
  • modello di PL
    • simmetria -> ridondanza di soluzioni equivalenti
    • povertà delle limitazioni inferiori
  • modello avanzato: generazione di colonne (vedi slides)

Programmazione Lineare con generazione di colonne

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

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

Lezioni 43 e 44 - 25/11

• altri esempi:
  • massimo flusso
  • problemi multi-flusso (vedi appunti)

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

Lezioni 45 e 46 - 26/11

Modelli di schedulazione

• a risorsa infinita
  • PERT
    • alberi dei cammini massimi
    • crashing
    • valutazione con incertezza

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

Lezioni 47 e 48 - 27/11

• a risorsa finita
  • modelli a una macchina
    • minimo della massima penalità (con programmazione dinamica)
    • presenza di date di rilascio: problemi NP-difficili
    • modellazione come LP