Appunti di Ricerca Operativa

Anno Accademico 2013/14

Versione completa.

• 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. Grafi e reti di flusso

  • 2.1 Flussi su reti

    • 2.1.1 Alcuni modelli di flusso
    • 2.1.2 Trasformazioni equivalenti

  • 2.2 Cammini di costo minimo

    • 2.2.1 Il problema
    • 2.2.2 Alberi, etichette e condizioni di ottimo
    • 2.2.3 L'algoritmo SPT
    • 2.2.4 Algoritmi a coda di priorità
    • 2.2.5 Algoritmi a selezione su lista
    • 2.2.6 Cammini minimi su grafi aciclici
    • 2.2.7 Cammini minimi con radici multiple

  • 2.3 Il problema di flusso massimo

    • 2.3.1 Tagli, cammini aumentanti e condizioni di ottimo
    • 2.3.2 Algoritmo per cammini aumentanti
    • 2.3.3 Flusso massimo con più sorgenti/pozzi
    • 2.3.4 Algoritmo basato su preflussi

  • 2.4 Il problema di flusso di costo minimo

    • 2.4.1 Cammini, cicli aumentanti e condizioni di ottimo
    • 2.4.2 Algoritmo basato su cancellazione di cicli
    • 2.4.3 Algoritmo basato su cammini minimi successivi

  • 2.5. Problemi di accoppiamento

    • 2.5.1 Accoppiamento di massima cardinalità
    • 2.5.2 Assegnamento di costo minimo
    • 2.5.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 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

• 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

  • A.4 Algoritmi

    • A.4.1 Algoritmi greedy
    • A.4.2 Algoritmi di ricerca locale
    • A.4.3 Algoritmi enumerativi

• 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: 14/02/2014