UNIVERSITY OF UDINE

Degree in Mathematics

Course Syllabus

Operations Research

a.y. 1997-98

instr. Paolo Serafini; t.a. Franca Rinaldi

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

DUALITY (12)

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

NETWORK FLOWS (18)

Optimality conditions: Gamma curve. Residual network. Polynomial algorithms for Shortest Path (Dijkstra) and Max Flow. `Out of kilter' method. Scaling algorithms. Bipartite matching. Network Simplex.

DETERMINISTIC DYNAMIC PROGRAMMING (12)

Optimality principle. Bellman's equation. Bellman-Ford algorithm for general networks. Algorithm for acyclic and layered networks. Floyd-Warshall algorithm. Knapsack problems. Optimal control. Combinatorial problems.

APPROXIMATE ALGORITHMS (10)

Definitions. Algoritmhs for $\Delta$-TSP, Knapsack and Bin packing. Polynomial approximation schemes. Computational complexity and approximability.

LOCAL SEARCH (4)

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

NONLINEAR PROGRAMMING (6)

Line search. Gradient method. Convergence speed. Newton's method. Constrained problems. Nondifferentiable problems.

INTERIOR POINTS MEHODS (6)

Karmarkar's method. Barrier methods.

MODULE # 2

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/E$r/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 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.

MODELS IN OPERATIONS RESEARCH (24)

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