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