Operations Research I - 0365.2302

Lecturer: Prof. Marc Teboulle ( teboulle@math.tau.ac.il )
Office: Schreiber Bldg. 227, Phone: 8896
School of Mathematical Sciences,
Tel-Aviv University

Time and Place : Winter Semester, 2008 - Sunday 12-13, Tuesday 8-10
Bldg: Schreiber -- Classroom 006

Intended Audience

This is an Undergraduate Course. Students majoring in Mathematics & Statistics, Computer Science, Finance , Economics and Engineering are strongly encouraged to register. The course will provide the basic and modern treatment of linear optimization, that is linear programming and related problems. The main objectives of the course will be to cover the key ideas and principles in this field, including classical topics as well as more recent developments achieved in the last decade.

Course requirements/Exams

Homeworks will be assigned by the teaching assistant during the "targil" session and usually will be due the following week, unless otherwise specified. It is mandatory to submitt at least 2/3 of the assigned homeworks to attend the final exam. The final grade will be determined by the final exam. Submission of homeworks may be used to improve final grades.

Textbooks and References

There is no required textbook for the course, and the Lectures will be comprehensive. However, the students are strongly encouraged to consult the following texts, which reflect the level of most of the material which will be covered in the course.

Some Sample of Exams + Review Problems

Later on ...

Approximate syllabus

1. Linear programming: formulation, examples, LP models, Graphical solutions. 2. Geometry and Algebra of LP: polyhedral sets, convex sets, extreme points. 3. The Simplex method: Optimality, Basic feasible solutions, the method, anticycling, finding a BFS, the two phase and big-M methods. 4. Duality theory: Motivation, dual problems, duality theorem, marginal costs, the dual simplex, Farkas' lemma. 5. Sensitivity analysis: solutions of LP under perturbations of the parameters (cost, righthanside, additional constraints). + ONE (or more) of the following topics ( time being permitted): 6. Complexity of LP: efficient algorithms and computational complexity issues. Key ideas of the ellipsoid method. 7. Interior point methods: Affine scaling, potential reduction and path following algorithms. 8. Network flows: Introduction to Graphs and network flows, the max flow problem, shortest path problems, the minimum spanning tree problem. 9. Integer Programming: Models, cutting plane methods, Branch and Bound. 10. Introduction to dynamic programming.