Appunti di Ricerca Operativa

Anno Accademico 2012/13

Versione completa (2.6Mb, con hyperlinks).

• Prefazione

• 1. Problemi e Modelli

• 1.1 Modelli e Problemi

• 1.2 Tecniche di Modellazione

  • 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. Programmazione Lineare

  • 2.1 Problemi di Programmazione Lineare

    • 2.1.1 Geometria della Programmazione Lineare

  • 2.2 Teoria della Dualità

    • 2.2.1 Coppie di problemi duali
    • 2.2.2 Il teorema debole della dualità
    • 2.2.3 Il teorema forte della dualità e sue conseguenze
    • 2.2.4 Il teorema degli scarti complementari
    • 2.2.5 Soluzioni complementari e basi

  • 2.3 Algoritmi del Simplesso

    • 2.3.1 L'Algoritmo del Simplesso Primale
    • 2.3.2 L'Algoritmo del Simplesso Duale
    • 2.3.3 Analisi post-ottimale

• 3. Grafi e reti di flusso

  • 3.1 Flussi su reti

    • 3.1.1 Alcuni modelli di flusso
    • 3.1.2 Trasformazioni equivalenti
    • 3.1.3 Algoritmi del Simplesso per (MCF)

  • 3.2 Cammini di costo minimo

    • 3.2.1 Il problema
    • 3.2.2 Alberi, etichette e condizioni di ottimo
    • 3.2.3 L'algoritmo SPT
    • 3.2.4 Algoritmi a coda di priorità
    • 3.2.5 Algoritmi a selezione su lista
    • 3.2.6 Cammini minimi su grafi aciclici
    • 3.2.7 Cammini minimi con radici multiple

  • 3.3 Il problema di flusso massimo

    • 3.3.1 Tagli, cammini aumentanti e condizioni di ottimo
    • 3.3.2 Algoritmo per cammini aumentanti
    • 3.3.3 Flusso massimo con più sorgenti/pozzi
    • 3.3.4 Algoritmo basato su preflussi

  • 3.4 Il problema di flusso di costo minimo

    • 3.4.1 Cammini, cicli aumentanti e condizioni di ottimo
    • 3.4.2 Algoritmo basato su cancellazione di cicli
    • 3.4.3 Algoritmo basato su cammini minimi successivi

  • 3.5. Problemi di accoppiamento

    • 3.5.1 Accoppiamento di massima cardinalità
    • 3.5.2 Assegnamento di costo minimo
    • 3.5.3 Accoppiamento di massima cardinalità bottleneck

• 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.2 Implementare un algoritmo enumerativo

    • 7.2.1 Rilassamento ed euristica
    • 7.2.2 La strategia di visita
    • 7.2.3 Regole di dominanza
    • 7.2.4 Regole di branching
    • 7.2.5 Preprocessing

  • 7.3 Esempi di algoritmi enumerativi

    • 7.3.1 Il problema dello zaino
    • 7.3.2 Il problema del commesso viaggiatore
    • 7.3.3 Il problema del cammino minimo vincolato

• 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

  • B.3 Visita di un grafo

    • B.3.1 Implementazioni della procedura di visita
    • B.3.2 Usi della procedura di visita

  • B.4 Albero di copertura di costo minimo

    • B.4.1 Algoritmo di Kruskal
    • B.4.2 Algoritmo di Prim
    • B.4.3 Albero di copertura bottleneck

Aggiornamento: 09/12/2012