ECTS - University of Pisa
Scheda programma d'esame
MATHEMATICAL PROGRAMMING
GIANCARLO BIGI
Academic year2020/21
CourseCOMPUTER SCIENCE
Code029AA
Credits6
PeriodSemester 1
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
RICERCA OPERATIVAMAT/09LEZIONI48
GIANCARLO BIGI unimap
Obiettivi di apprendimento
Conoscenze

Il corso presenta gli strumenti necessari alla costruzione e alla risoluzione di modelli analitici di ottimizzazione per problemi reali, tipicamente di gestione, di allocazione delle risorse e di logistica. Verranno illustrate le proprietà teoriche ed alcune delle principali tecniche algoritmiche per la soluzione di tre grandi classi di problemi di ottimizzazione: problemi di flusso su reti, di programmazione lineare e di programmazione lineare intera.
Prerequisiti (conoscenze iniziali)
  • Logica elementare: connettivi logici, proposizioni, principio di induzione, metodi di dimostrazione

  • Spazi vettoriali: spazi, semispazi, vettori, combinazioni lineari, indipendenza lineare, basi, coordinate

  • Geometria del piano e dello spazio tridimensionale: sottospazi affini, equazione di rette, piani e semispazi

  • Prodotto scalare euclideo, ortogonalità

  • Matrici: operazioni con le matrici, determinante, invertibilità

  • Concetto di funzione, funzioni lineari (ed affini)

  • Sistemi lineari di equazioni e loro risoluzione

  • Cosa è un algoritmo

  • Complessità di un algoritmo

  • Classi P e NP

  • Strutture dati: fila, pila, deque, code di priorità, heap

  • Grafi: nodi, archi, alberi, cammini, cicli

  • Grafi: rappresentazione e visite (DFS e BFS)

  • Alberi: rappresentazioni e visite

  • Ricerca dei punti di massimo e minimo di funzioni di una variabile
Programma (contenuti dell'insegnamento)

Introduzione (2 ore)

    • Problemi decisionali e problemi di ottimizzazione
    • Classi di problemi ed esempi
  1. Modelli e loro formulazione (6 ore)
    • Tipi di variabili: quantitative, logiche, continue, discrete
    • Formulazione di vincoli
    • Formulazione della funzione obiettivo
  2. Grafi e Reti di flusso (18 ore)
    • Modello generale dei problemi di flusso
    • Alberi, cammini e tagli, visite di grafi e alberi
    • Il problema dei cammini minimi
    • Il problema dell'albero di copertura di costo minimo
    • Il problema del flusso massimo
    • Il problema del flusso di costo minimo
  3. Programmazione Lineare (14 ore)
    • Geometria della programmazione lineare e teorema fondamentale
    • Dualità e scarti complementari
    • Basi: complementarità, degenericità ed ottimalità
    • Algoritmi del simplesso primale e duale
  4. Programmazione Lineare Intera (8 ore)
    • Metodi poliedrali: tagli ed algoritmo di Gomory
    • Metodi enumerativi: l'algoritmo "Branch&Bound"
    • Implementazioni ad-hoc per i problemi dello zaino e del commesso viaggiatore
Syllabus

Introduction (2 hours)

    • Decision-making problems and optimization
    • Classification of problems and examples
  1. Models and formulations (6 hours)
    • Kinds of variables: quantitative, logic, continuous, discrete
    • Constraint formulation
    • Formulation of objective functions
  2. Graphs and network flows (18 hours)
    • General model for network flow problems
    • Trees, paths and cuts,  search procedures for graphs and trees
    • Shortest path problems
    • Minimum spanning trees
    • Maximum flow
    • Minimum cost problem
  3. Linear Programming (14 hours)
    • Geometry of linear programming and fundamental theorem
    • Duality and complementarity slackness
    • Basis: complementarity, degeneracy and optimality
    • Primal and dual simplex algorithms
  4. Integer Linear Programming (8 hours)
    • Polyedral methods: Gomory cuts and algorithm
    • Enumeration methods: Branch&Bound algorithm
    • Ad-hoc implementations for knapsack and traveling salesman problems
Bibliografia e materiale didattico

Testo di riferimento

    • G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa (PDF)

Altri testi di consultazione

    • R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993

    • M. Pappalardo, M. Passacantando, Ricerca operativa, Pisa University Press, 2012

    • P. Serafini, Ottimizzazione, Zanichelli, 2000

    • C. Vercellis, Modelli e decisioni, Progetto Leonardo, 1999

    • C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008
Bibliography

Lecture notes

    • G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa (PDF) - in Italian

Further references

    • R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993

    • M. Pappalardo, M. Passacantando, Ricerca operativa, Pisa University Press, 2012 (in Italian)

    • P. Serafini, Ottimizzazione, Zanichelli, 2000 (in Italian)

    • C. Vercellis, Modelli e decisioni, Progetto Leonardo, 1999 (in Italian)

    • C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008 (in Italian)
Modalità d'esame

Prova scritta seguita da una prova orale. Sono ammessi alla prova orale solo gli studenti che hanno superato la prova scritta. Sono esonerati dalla prova scritta coloro che hanno superato le due prove in itinere/prove di verifica intermedia (nel seguito denominate "compitini"). Sono ammessi al secondo compitino soltanto gli studenti che hanno superato il primo.

Per sostenere la prova scritta dell'esame, inclusi i compitini, è necessario iscriversi entro le date indicate su esami.unipi.it.In genere la scadenza per le iscrizioni è fissata 48 ore prima della prova. In caso di mancata iscrizione da parte di uno o più studenti non è possibile garantire la loro partecipazione alla prova.

Durante la prova scritta non è possibile consultare libri o appunti.

La prova orale viene effettuata nella stessa sessione (Gennaio-Febbraio, Giugno-Luglio, Settembre) della prova scritta secondo un calendario di possibili date comunicato durante il compito e pubblicato contemporaneamente sulla pagina web. La consegna di una prova scritta successiva a quella già superata comporta la rinuncia alla prova precedentemente sostenuta con esito positivo.

Gli studenti che sono stati esonerati dalla prova scritta a seguito di valutazione positiva dei compitini possono svolgere la prova orale in uno dei primi due appelli. La consegna di una prova scritta successiva ai compitini comporta la rinuncia all'esonoro eventualmente già ottenuto.
Pagina web del corso

http://pages.di.unipi.it/bigi/dida/rob.html
Class web page

http://pages.di.unipi.it/bigi/dida/rob.html
Updated: 31/07/2020 12:01