UNIVERSITY OF UDINE

Degree in Mathematics

Course Syllabus

Operations Research

a.y. 1998-99

instructors: Franca Rinaldi and Paolo Serafini

Aims: The first module is the completion of the previous course on Optimization. It provides the mathematical background and the algorithmic knowledge for many operations research models. Eventually students should be able to identify the mathematical model which best fits a real problem and to solve it. In the second module typical stochastic operation research techniques are presented like queueing theory and Markov Decision processes. More emphasis is given to the modelistic aspects of Operations Research and topics providing a rigorous foundation to the modellistic phase are presented like Decision Theory, Multi Objective Decision Making and Game Theory. Moreover, examples of Operations Research applications are presented.

MODULE # 1

(F. Rinaldi)

BASICS OF CONVEX ANALYSIS (6)

Definitions. Separation theorem. Supporting planes. Convex functions. Subgradients.

DUALITY (14)

Dual problem. Optimality Conditions. Examples. Duality and convexity. Differential properties of duality. Duality and sensitivity.

NETWORK FLOWS (14)

Optimality conditions: Gamma curve. Residual network. Max Flow and Shortest Path. `Out of kilter' method. Scaling algorithms. Bipartite matching.

DETERMINISTIC DYNAMIC PROGRAMMING (10)

Optimality principle. Bellman's equation. Optimal control. Combinatorial problems.

APPROXIMATE ALGORITHMS (8)

Definitions. Polynomial approximation schemes. Algoritmhs for Delta-TSP, Knapsack and Bin packing.

LOCAL SEARCH (6)

Definitions. Application to TSP. Simulated annealing. Other techniques.

MODULE # 2

(P. Serafini)

QUEUEING THEORY (12)

Markov chains and Markov processes with finite states. Birth-death processes. Poisson processes. M/M queues. Embedded Markov chains. Queues M/G/1, M/D/1 and M/Er/1. Pollaczek-Khinchin formula.

MARKOV DECISION PROCESSES (12)

Finite horizon formulation. Policy evaluation and optimal policy computation. Infinite horizon formulation, discounted and average cases. Use of dynamic programming and linear programming.

DECISION THEORY (6)

Criteria in presence of uncertainty. Criteria in presence of risk. Expected value of information. Use of Bayes' theorem to recompute probabilites. Decision trees. Lotteries and value function evaluation. Lotteries and subjective probability.

MULTI OBJECTIVE DECISION MAKING (6)

Pareto optimality. Order structures. Utility functions. Arrow's impossibility theorem. Multi attribute decision making. Multi objective programming. Scalarization techniques. Interactive techniques.

GAME THEORY (12)

Extended and normal forms. Zero-sum games. Pure and mixed strategies. Non constant sum games. Nash equilibrium. n-person games. Coalitions and imputations. Core of a game. Shapley value.

MODELS IN OPERATIONS RESEARCH (24)

Staffing. Deterministic and stochastic PERT, crashing. Determistic and stocahstic. Multiperiod models. Multicommodity flows. Integer Linear Programming models. Scheduling.

Evaluation:

The student may choose to be evaluated in one of the two alternative ways: an oral examination or (recommended procedure) a certain number of homeworks.

Information on Operations Research may be found at INFORMS (Institute for Operations Research and Management Science) or at CIRO (Centro Interuniversitario in Ricerca Operativa)