UNIVERSITY OF UDINE

Degree in Mathematics

Course Syllabus

Operations Research

a.y. 1999-2000

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, Game theory) 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

NONLINEAR PROGRAMMING

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

DECISION THEORY

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

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

GAME THEORY

Extended and normal form. 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.

SCHEDULING

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

ROUTING

Arc routing problems. Capacitated vehicle routing problems.

MODULE # 2

QUEUEING THEORY

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

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

MODELS IN OPERATIONS RESEARCH

Case studies with laboratory practice using packages like Lingo, Mathematica, Cplex.