Obiettivi formativi
Il corso fornisce una prima introduzione all’ottimizzazione lineare e alle sue applicazioni. L'attenzione e' rivolta alle interpretazioni economiche e geometriche dei programmi lineari e alla formulazione e soluzione di problemi decisionali dell'ingegneria in termini di programmi lineari.
Prerequisiti
Geometria e Algebra Lineare
Contenuti dell'insegnamento
1. PROGRAMMAZIONE LINEARE. Problemi di Programmazione Lineare (P.L.) e loro formulazione: modelli di dieta, miscelazione, produzione, trasporto, scelta di investimenti; problemi in due variabili e loro soluzione grafica; terminologia della P.L. Geometria della P.L.: poliedri, insiemi convessi, soluzioni basiche ammissibili e vertici, Teorema Fondamentale della P.L.. Applicazioni ai problemi della produzione: produzione in presenza di risorse limitate e processi produttivi, piani di trasporto, specificazioni dei prodotti, soddisfazione della domanda. Casi generali ed esempi numerici. Tecniche della P.L.: il metodo del simplesso e la sua implementazione; interpretazione geometrica ed economica del metodo del simplesso. Esempi applicativi. Dualita' nella P.L.: il problema duale; relazioni tra i problemi primale e duale: dualita' debole e forte; interpretazione economica del duale; dualita' e metodo del simplesso; analisi di sensibilita’. Esempi applicativi. 2. PROBLEMI DI OTTIMIZZAZIONE SU GRAFI E RETI. Grafi, alberi e reti: definizioni e notazioni. I problemi di flusso massimo e di flusso a costo minimo. Applicazioni al problema dell'assegnazione, del trasporto, del cammino minimo. Alcuni algoritmi di soluzione. Esempi applicativi.
Programma esteso
1. LINEAR PROGRAMMING. Linear programming (LP) problems and their formulation: the diet and blending problem, the activity-analysis (product-mix) problem, the transportation problem, investment problems; two-variables problems and their graphic solution; LP terminology. The geometry ol LP: polyhedra, convex sets, basic feasible solutions and vertices. The Fundamental Theorem of LP. Applications to problems of production: optimum product lines and production processes in presence of limited resources, transportation routing, meeting product specifications, satisfaction of demand. General cases and examples Techniques of LP: the simplex method and its implementation; geometric and economic interpretations of the simplex method. Examples. Duality theory: the dual problem; relations between the primal and the dual problem: weak and strong duality; economoc interpretation of the dual problem; duality theory and the simplex method; sensitivity analysis. 2. NETWORK OPTIMIZATION PROBLEMS. Graphs, trees and networks. The maximum flow problem and the minimum cost flow problem. Applications to the assignment problem, the transportation problem, the shortest path problem. Some network algorithms.
Bibliografia
- Note a cura del docente.
Testi di approfondimento:
- R. Dorfman, P. A. Samuelson, R. M. Solow, Linear programming and economic analysis, Dover Publications, Inc., New York, 1987, reprint of the 1958 edition.
- D. Gale, The theory of linear economic models, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1960.
- F. S. Hillier, G. J. Lieberman, Introduzione alla ricerca operativa, Ottava edizione, McGraw-Hill, Milano, 2006.
- D. G. Luenberger, Linear and nonlinear programming, Second edition, Springer, New York, 2003.
- R. J. Vanderbei, Linear progamming: Foundations and Extensions,
Metodi didattici
Lezioni frontali ed esercitazioni
Modalità verifica apprendimento
Esame scritto e orale
Altre informazioni
- - -
