# LINEAR AND STATISTICAL OPTIMIZATION (UNIT 1)

## Learning outcomes of the course unit

The goal of this course is to introduce linear programming as a

mathematical technique to model decision and optimization problems

relevant in engineering, management science and other applications, as

well as methods for solving the resulting models and interpret the

solutions.

## Prerequisites

Basic knowledge of linear algebra and geometry.

## Course contents summary

This course introduces Linear Programming and applications. The focus is

on economic and geometric interpretations of linear programs, the

formulation of engineering and management problems in terms of linear

programs, as well as on the methods for solving the resulting models and

interpret their solutions. Topics include: formulation and interpretations

of linear programs, the geometry of linear programs, linear programming

algorithms, including the simplex method, duality theory, optimization of

network flows, applications to problems of production, transportation,

diet, product specifications and satisfaction of demand.

## Course contents

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

## Recommended readings

- Course notes.

Other books:

- 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,

## Teaching methods

The theoretical topics of the course are presented during class lectures

and illustrated with significant examples, applications and several

exercises. Homework assignments are proposed during the course, which

are then discussed in recitation sessions during class time.

## Assessment methods and criteria

The final exam consists of a written part, where students are required to

solve some exercises, and of an oral part about the theoretical topics and

the applications discussed during the course.