Department of Mathematical Sciences CARNEGIE MELLON UNIVERSITY

OPERATIONS RESEARCH II 21-393

Professor A.M.Frieze, Wean Hall 7202, x8476, alan@random.math.cmu.edu

1. COURSE OBJECTIVES

(i) To develop and extend the students knowledge of mathematical techniques underlying the application of Operations Research. (ii) To give experience of working in a group on a project.

2. COURSE TEXT There is no required book for the course. There are a number of books which cover much of the material, none of which are recommended.

1. Introduction to Operations Research, by F.S.Hillier and G.J.Liebermann, (published by McGraw-Hill).

2. Operations Research: Applications and Algorithms, by W.L.Winston, (published by P.W.S. Kent).

3. Principles of Operations Research, by H.M.Wagner, (published by Prentice-Hall).

3. TOPICS I will make a selection from the following:

1. Linear Programming Duality and Dual Simplex, Sensitivity Analysis and Parametric Programming, Simple Upper Bounds, Interior Point methods, Two-Person Zero-Sum Games.

2. Integer Linear Programming Formulations, 0-1 Programming, Cutting Planes and Branch and Bound.

3. Combinatorial Optimisation Shortest Paths, Assignment, Minimum Spanning Trees, Network Flows, PERT/CPM, Machine Scheduling, NP-Completeness, Heuristics.

4. Non-Linear Programming Karush, Kuhn-Tucker Conditions, Quadratic Programming.

5. Inventory Theory

6. Markov Decision Processes

7. Markowicz Model in Mathematical Finance 4. THE PROJECT The class will be partitioned into working groups of three/four students. These groups should be formed voluntarily. If necessary, I will make assignments. Each group will work together on a short project which it will research, write a paper on and make a presentation to the class near the end of the semester. Examples of previous projects are obtainable from Dr. Walker. It will be your responsibility to think of a project. I will vet your ideas for suitability and practicality. The evaluation of the project will be based on the following factors:

• the degree to which the project demonstrates the group’s ability to abstract a problem into mathematical form and to employ the appropriate solution techniques.

• the degree to which the group demonstrates professional writing and presentation skills.

Suggested schedule for carrying out project:

Activity  Target Date for Completion
Form small group 3/4 students September 4
Settle on idea for project  September 29
Finish research  November 17
Finish write-up  December 1

5. GRADING SYSTEM There will be an initial set of homeworks, amounting to approxmately one quarter the normal load for a one semester course. There will also be two tests.

Project  50%
2 Tests  20% each
Homework 10%

There will be no written final. The tests will be open book and notes.

6. CLASS SCHEDULE Lectures MWF 10.30 - 11.20 in DH 1211. Tests September 30, October 21.

7. OFFICE HOURS MTWThF 9.30 - 10.00 in WEH7202.