M510 Linear Programming Syllabus

ENGR 510 Linear Programming (Cont. Ed. Distance)

Fall 2008

 

 

Welcome to the M510 course website.  (Note that this course is also cross listed as ENGR 510.   This semester it is being taught by the Math Department.)  This course serves as a first course in Optimization and will cover

 

  • An Introduction to Optimization
  • Linear Programming
  • Network Flow Algorithms
  • Interior Point Methods
  • Quadratic Programming
  • Applications

 

This course focuses primarily on Linear Optimization.  The first course in Nonlinear Optimization is M520.

 

Prerequisites: M261.  Basic knowledge of linear algebra also expected.   Previous programming experience will also be helpful.

 

Required Text: Linear Programming, Foundations and Extensions, Third Ed., Robert Vanderbei. 

 

Suggested Reading: Model Building in Mathematical Programming, H. Paul Williams serves as an excellent source of applications.

 

Required Software: Matlab with Optimization Toolbox.    For on-campus students all the required software will be available in Weber 205/206.  Off campus students must purchase a Matlab license as well as a license for the Optimization Toolbox from Mathworks.  (Exceptions:  The textbook has C programs that can be used in place of Matlab but these will not be covered in class and are used at your own risk.  Additionally, other linear programming software such as LINDO may be used at your own risk.   Only questions concerning MATLAB and its Optimization Toolbox are supported in this class and it is strongly recommended that unless you have strong programming skills you work only with Matlab.)

 

Instructor: Professor Michael Kirby, Kirby@math, Weber 211.

Office Hours: M, W 3:00-3:50.

Homework Assignments: posted on RamCT.

Homework will be assigned weekly and is due on Wednesdays.  Each day late will result in a 10% deduction unless a CSU sanctioned event or health issues interfere.   Homework not handed in by 5pm Friday of the week its due will not be graded and will count as a zero.

Final Project: 

The last two weeks of the course will be dedicated to a final project.  This project is an integral part of the course and will provide students with an opportunity explore a particular application in more depth.  We will meet in the Computer Lab 205 for each class period and students will work in groups on a problem of their choosing that has been approved for breadth and depth by the instructor.  Distance students will also be required to complete a final project and will receive feedback via email over the project period.

Grading policy:

The final grade will be determined the evaluation of

  • Homework 25%
  • Final Project 15%
  • Midterm Examination 25%
  • Final Examination 35%

Policy on Group Work:

You may collaborate with other students in this class on homework assignments and are even encouraged to do so as this can be an excellent way to learn.  However, if you choose to collaborate the following rules apply: You must write-up your solutions on your own and identify who you collaborated with.  Copying of solutions is not allowed. So, basically, talking about assignments, and even working as a team is OK, but understand the material yourself as evidenced by your independent write-up.  If you do not identify your collaborators it will be assumed that your work was completed by yourself.

 

Syllabus (Video lectures and lecture notes posted on RamCT)

 

Week                                                   Topic

 

  1. Examples of Linear Programming Problems, The Simplex Method I
  2. Labor Day, Simplex Method II
  3. Initialization of Linear Programs, Degeneracy, Cycling
  4. Fundamental Theorem of Linear Programming, Weak and Strong Duality Theorems
  5. The Dual Simplex Method, Resource Allocation
  6. Sensitivity Analysis (via Geometry), The Simplex Method in Matrix Notation
  7. Ranging, Parametric Analysis, Application to Game Theory
  8. Regression, Application to Portfolio Selection
  9. Application to Option Pricing, Mid-term Examination
  10. Network Flows
  11. Interior Point Methods
  12. Integer Programming
  13. Quadratic Programming, Discussion of Projects
  14. Happy Thanksgiving
  15. Applications: Class Project
  16. Applications: Class Project
  17. Final Examination December 17, 7-9AM

 

Note that this syllabus is approximate and we may take more or less time on certain topics.