( english version )

Geometria e ricerca operativa B ( 4 CFU ) Tel. 0521-032321 - Fax. 0521-032350 E-mail. lorenzo.nicolodi@unipr.it Home page. http://www.unipr.it/~lnicolo9/

Finalità

This course introduces linear programming and applications. The focus is

on economic and geometric interpretations of linear programs and on the

formulation and solution of engineering and management problems in terms

of linear programs.

on economic and geometric interpretations of linear programs and on the

formulation and solution of engineering and management problems in terms

of linear programs.

Programma

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.

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.

Attività d'esercitazione

Discussion and solution of exercises and assignments

Modalità d'esame

Written and oral exam

Testi consigliati

Notes by the instructor.