Appunti di Ricerca Operativa

Anno Accademico 2008/09

• Prefazione

• 1. Problemi e Modelli
  • 1.1 Problemi

  • 1.2 Modelli
    • 1.2.1 Programmazione Lineare
    • 1.2.2 Variabili logiche
    • 1.2.3 Relazioni binarie
    • 1.2.4 Vincoli di assegnamento e semiassegnamento
    • 1.2.5 Selezione di sottoinsiemi
    • 1.2.6 Variabili a valori discreti
    • 1.2.7 Minima quantità positiva prefissata
    • 1.2.8 Funzione con carico fisso
    • 1.2.9 Vincoli di soglia
    • 1.2.10 Come rappresentare il valore assoluto
    • 1.2.11 Funzioni lineari a tratti
    • 1.2.12 Vincoli disgiuntivi
    • 1.2.13 Un esempio di formulazione ed alcuni esercizi

• 2. Grafi e reti di flusso
  • 2.1 Flussi su reti
    • 2.1.1 Alcuni modelli di flusso
    • 2.1.2 Trasformazioni equivalenti

  • 2.2 Visita di un grafo
    • 2.2.1 Implementazioni della procedura di visita
    • 2.2.2 Usi della procedura di visita

  • 2.3 Cammini di costo minimo
    • 2.3.1 Il problema
    • 2.3.2 Alberi, etichette e condizioni di ottimo
    • 2.3.3 L'algoritmo SPT
    • 2.3.4 Algoritmi a coda di priorità
    • 2.3.5 Algoritmi a selezione su lista
    • 2.3.6 Cammini minimi su grafi aciclici
    • 2.3.7 Cammini minimi con radici multiple

  • 2.4 Albero di copertura di costo minimo
    • 2.4.1 Algoritmo di Kruskal
    • 2.4.2 Algoritmo di Prim
    • 2.4.3 Albero di copertura bottleneck

  • 2.5 Il problema di flusso massimo
    • 2.5.1 Tagli, cammini aumentanti e condizioni di ottimo
    • 2.5.2 Algoritmo per cammini aumentanti
    • 2.5.3 Algoritmo basato su preflussi
    • 2.5.4 Flusso massimo con più sorgenti/pozzi

  • 2.6 Il problema di flusso di costo minimo
    • 2.6.1 Cammini, cicli aumentanti e condizioni di ottimo
    • 2.6.2 Algoritmo basato su cammini minimi successivi
    • 2.6.3 Algoritmo basato su cancellazione di cicli
    • 2.6.4 Basi di cicli

  • 2.7. Problemi di accoppiamento
    • 2.7.1 Accoppiamento di massima cardinalità
    • 2.7.2 Assegnamento di costo minimo
    • 2.7.3 Accoppiamento di massima cardinalità bottleneck

• 3. Programmazione Lineare
  • 3.1 Problemi di Programmazione Lineare
    • 3.1.1 Geometria della Programmazione Lineare

  • 3.2 Teoria Matematica della Dualità
    • 3.2.1 Coppie di problemi duali
    • 3.2.2 Il teorema debole della dualità
    • 3.2.3 Il teorema forte della dualità e sue conseguenze
    • 3.2.4 Il teorema degli scarti complementari
    • 3.2.5 Soluzioni complementari e basi

  • 3.3 Algoritmi del Simplesso
    • 3.3.1 L'Algoritmo del Simplesso Primale
    • 3.3.2 L'Algoritmo del Simplesso Duale
    • 3.3.3 Analisi post-ottimale

• 4. Ottimizzazione Combinatoria
  • 4.1 Introduzione

  • 4.2 Programmazione Lineare Intera (Mista)
    • 4.2.1 Il rilassamento continuo
    • 4.2.2 Formulazioni di PL equivalenti per la PLI
    • 4.2.3 Diseguaglianze valide

  • 4.3 Dimostrazioni di ottimalità

• 5. Algoritmi euristici
  • 5.1 Algoritmi greedy
    • 5.1.1 Esempi di algoritmi greedy
    • 5.1.2 Algoritmi greedy con garanzia sulle prestazioni
    • 5.1.3 Matroidi

  • 5.2 Algoritmi di ricerca locale
    • 5.2.1 Esempi di algoritmi di ricerca locale
    • 5.2.2 Intorni di grande dimensione
    • 5.2.3 Metaeuristiche

• 6. Tecniche di rilassamento
  • 6.1 Rilassamento continuo
    • 6.1.1 Efficacia del rilassamento continuo
    • 6.1.2 Informazione generata dal rilassamento continuo

  • 6.2 Eliminazione di vincoli
    • 6.2.1 Esempi di rilassamenti per eliminazione di vincoli

  • 6.3 Rilassamento Lagrangiano
    • 6.3.1 Teoria del rilassamento Lagrangiano
    • 6.3.2 Algoritmi per il rilassamento Lagrangiano
    • 6.3.3 Informazione generata dal rilassamento Lagrangiano

  • 6.4 Rilassamento surrogato

• 7. Algoritmi enumerativi
  • 7.1 Algoritmi di enumerazione implicita
    • 7.1.1 Uno schema generale
    • 7.1.2 Implementare un algoritmo enumerativo
    • 7.1.3 Esempi di algoritmi enumerativi

• Appendice A: Algoritmi e Complessità
  • A.1 Modelli computazionali

  • A.2 Misure di complessità

  • A.3 Problemi trattabili e problemi intrattabili
    • A.3.1 Le classi P e NP
    • A.3.2 Problemi NP-completi e problemi NP-ardui
    • A.3.3 Complessità ed approssimazione

• Appendice B: Grafi e Reti
  • B.1 I grafi: notazione e nomenclatura
    • B.1.1 Grafi, nodi, archi
    • B.1.2 Cammini, cicli
    • B.1.3 Tagli e connettività
    • B.1.4 Alberi

  • B.2 Rappresentazione dei grafi ed alberi
    • B.2.1 Matrici di incidenza e liste di adiacenza
    • B.2.2 Rappresentazione di alberi: la funzione predecessore
    • B.2.3 Visite di un albero
    • B.2.4 Livello dei nodi di un albero

Aggiornamento: 23/02/2009