Course No.：S070105ZJ001
Course Category：Professional Basic Course
Period/Credits：40/2
Prerequisites：Advanced Mathematics, Linear Algebra.
Aims & Requirements：
This is a basic course for graduate students majoring various mathematical sciences, while could also serve as an elective for students of management sciences. Although Operational Research is a broad subject and has many branches, this course concerns mainly the mathematical background of deterministic models. After taken this course, students are expected to acquaint the basic concepts and techniques of deterministic models in Operational Research. We also hope that, through the study of some cases, students can understand the essence of deterministic models in Operational Research, and can lay the foundation for further study in various areas of Operational Research.
Primary Coverage：
Chapter 1 Linear Programming
Cases; Basics of Convex Analysis (Convex Sets); Separation Theorem; Duality Theory; Simplex Algorithm; Ellipsoid Algorithm; Network Flow Models; Maximum Flow Minimum Cut.
Chapter 2 Game Theory
Game Models; Zero-Sum Game; Mini-max Theorem; Non-Zero-Sum Game; Pure Strategy; Mixed Strategy; Saddle Point; Nash Equilibrium.
Chapter 3 Nonlinear Programming
Basics of Convex Analysis (Convex Functions); KKT Condition; Algorithms for Unconstrained and Constrained Nonlinear Programming; Duality Theorem and Saddle Point Theorem.
Chapter 4 Complexity Theory
Deterministic Turing Machine; Nondeterministic Turing Machine; Decision Problem; Combinatorial Optimization Problems; Integer Programming; Cook’s Theorem; Polynomial Algorithms; Categories of Computational Complexity.
Chapter 5 Design and Analysis of Combinatorial Optimization Algorithms
Exact Algorithms; Heuristics; Approximation Algorithms; Divide and Conquer; Branch and Bound; Dynamic Programming; Local Search; Integer Programming; Online Problems and Algorithms; Stochastic Algorithms.
Textbook：
Lecture notes written by lecturer (Can be downloaded from http://www.amt.ac.cn/member/huxiaodong/index.html).
References：
[1] Linear and Nonlinear Programming (2nd Edition), D. G. Luenberger, Addison-Wesley Publishing Com., 1984.
[2] Combinatorial Optimization：Algorithms and Complexity, Christos H. Papadimitriou and Kenneth Steiglitz，Printice-Hall Inc., 1982.
[3] Five Golden Rules: Great Theories of 20th-Century Mathematics--and Why They Matter, John Casti,1995.
Author：Xiaodong Hu (Academy of Mathematics and Systems Science)
Date：June, 2009
