Lezioni 1 e 2 - 28/09/2004

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

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

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

Lezioni 3 e 4 - 29/09/2004

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

• Geometria:
  • insieme ammissibile = poliedro
  • ottimi sui vertici
  • determinazione di un vertice degenerazione
• Metodo del simplesso:
  • basi e vertici

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

Lezioni 5 e 6 - 30/09/2004

• Dualità:
  • come valore delle risorse in base alla domanda-offerta

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

Lezioni 7 e 8 - 5/10/2004

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

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

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

Lezioni 9 e 10 - 6/10/2004

Presenza di più obiettivi (vedi dispensa) :

• definizione di ottimi di Pareto
• determinazione come combinazione convessa
• determinazione aggiungendo vincoli
• generazione degli ottimi di Pareto in PL

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 11 e 12 - 7/10/2004

• 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
• complessità computazionale
• esempio

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

Lezioni 13 e 14 - 12/10/2004

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

Caso della dieta:

• risoluzione del terzo modello (grafico)
• quarto modello ( (vedi dispensa , file Lingo)
• analisi (grafico)

  [parte non svolta

• quinto modello
  • giustificazione teorica
  • prima fase del modello (file Lingo)
  • seconda fase del modello (file completo Lingo e parziale Lingo)
• analisi (grafico) ]

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

Lezioni 15 e 16 - 13/10/2004

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 17 e 18 - 14/10/2004

• 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 19 e 20 - 20/10/2004

• interpretazione del duale come flusso

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

Lezioni 21 e 22 - 26/10/2004

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

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

Lezioni 23 e 24 - 27/10/2004

• 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

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

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

Lezioni 25 e 26 - 28/10/2004

• moltiplicazione di matrici

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

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

Lezioni 27 e 28 - 2/11/2004

• algoritmo per flussi di costo minimo

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

Lezioni 29 e 30 - 3/11/2004

• massimo flusso e minima capacità di taglio (con sergente e destinazione)
  • Algoritmo di Ford-Fulkerson
• minima capacità di taglio (senza sorgente e destinazione)
  • algoritmo probabilistico

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

Lezioni 31 e 32 - 4/11/2004

• algoritmo deterministico

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

Lezioni 33 e 34 - 9/11/2004

(vedi anche Ottimizzazione cap. 12 e dispensa):

• Cammini minimi che passano per tutti i nodi (TSP)
  • modello di PL (caso non orientato)
  • descrizione poliedrale: piani di taglio
  • metodo branch-and -cut

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

Lezioni 35 e 36 - 10/11/2004

• varianti
• euristiche:
  • Ricerca locale
  • Simulated annealing

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

Lezioni 37 e 38 - 11/11/2004

(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 orientati, non orientati e misti
  • il problema del postino cinese su grafi non orientati

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

Lezioni 39 e 40 - 16/11/2004

• il problema del postino cinese su grafi orientati

Modelli di allocazione

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

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

Lezioni 41 e 42 - 17/11/2004

• modello di Programmazione Dinamica per knapsack intero

Programmazione Lineare con generazione di colonne

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

   

• Bin packing (slides)
  • modello avanzato: generazione di colonne (file Lingo: master , generatore)

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

Lezioni 43 e 44 - 18/11/2004

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

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

Lezioni 45 e 46 - 23/11/2004

Modelli di schedulazione

• a risorsa infinita
  • PERT (vedi dispensa)
    • alberi dei cammini massimi
    • crashing
    • valutazione con incertezza

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

Lezioni 47 e 48 - 24/11/2004

• a risorsa finita
  • modelli a una macchina (vedi dispensa)
    • minimo della somma pesata
    • minimo della massima penalità (con programmazione dinamica)
    • presenza di date di rilascio: problemi NP-difficili
    • modellazione come LP (file Lingo: big-M, 5job, 20job)