UNIVERSITY OF UDINE

Degree in Mathematics

Course Syllabus

Operations Research

a.y. 2002-2003

instructors: Franca Rinaldi and Paolo Serafini

Aims: The two modules complete the topics of the previous course on Optimization and provide an overview of theoretical (Decision Theory, Multi Objective Programming) and practical (Scheduling, Routing,..) modelling issues. Moreover, stochastic techniques will be presented in the second module to model queueing systems and multistage decision processes. Eventually students should be able to identify the mathematical model which best fits a real problem and to solve it.

MODULE # 1

(F. Rinaldi)

DYNAMIC PROGRAMMING (12 hours)

Optimality principle. Bellman's equation. Bellman-Ford algorithm for generic directed graphs. Algorithm for layered and acyclic directed graphs. Floyd-Warshall algorithm. Knapsack problems. Combinatorial problems.

HEURISTIC AND APPROXIMATE ALGORITHMS (10)

Approximate algorithms. Local search. Greedy methods. Disaggregation. Tabu search. Simulated annealing.

ROUTING (13)

Arc routing problems. Node routing problems. Capacitated vehicle routing problems.

SCHEDULING (13)

Pert. One machine problems. Parallel machines. Job shop models.

MODULE # 2

(P. Serafini)

MARKOV DECISION PROCESSES (15)

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

QUEUEING THEORY (19)

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

DECISION THEORY (6)

Decision trees. Optimla decision evaluation. Lotteries and utilities. Expected value of information. Use of Bayes' theorem to recompute probabilites. Lotteries and subjective probability. Stochastic linear programming.

GAME THEORY (8)

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

Exam: oral examination after each module.

For more information on Operatons Research and Optimization see INFORMS (Institute for Operations Research and Management Science) or CIRO (Centro Interuniversitario in Ricerca Operativa)