The mathematical field of optimization divides into linear optimization( a.k.a. linear programming ) and nonlinear optimization( a.k.a nonlinear programming ). This course focuses on linear programming. We have a two-fold goal. Theoretically, we want to learn the Simplex algorithm, its variations and the duality theory. Practically, we want to learn how to set up models similar to those used in business and engineering that can be solved by linear programming. Typical models include "allocation problem", "knapsack problem", "travelling salesman problem", etc.

The "programming" in "linear programming" is not the "programming" in "computer programming". This course stresses the ability to formulate a Math problem and the deep understanding of the algorithms. As for implementing the algorithms (and debugging), it's not our concern since there exist many many commercial software having done that, such as LINDO . So, computer programming is NOT required in this course though you are encouraged to adventure with Simplex algorithm in any language or software you want.

Latest news

• Semester is Over. You can have your final back next week. I'll be on campus. So, just email me. Take care.
  
  
• No makeup of the final exam will be given unless some official documentation is shown. Absence of the final exam score will lead to "fail" in the course automatically.
  
  
• HW6 is complete, due back on June 29th, Friday.
  
  
• HW5 is complete, due back on June 25th, Monday . Angeline reported that in sec 7.4: Problem 3, the third row entry of the "s₃" column should be 1/5 instead of 1 in the book. Please make correction.
  
  
• FINAL will be held in class on Thursday and Friday, June 28th and 29th. The first part of it on Thursday will cover section 3.7, 3.8, 4.2, 7.3 and the second part on Friday will cover 4.3, 7.2, 7.3(again), 7.4, 7.5. Unavoidably, the basics of the Simplex algorithm will also be tested.
  
  
• HW4 is complete, due back on June 20th. HW5 will be due not on Weds, but on Monday, June 25. And the last HW6 will be due on Friday, June 29.
  
  
• MIDTERM will be held in class on Thursday and Friday, June 7th and 8th. The first part of it on Thursday will cover section 1.4, 3.2, 3.3 and the second part on Friday will cover 3.4, 3.5, 3.6. The best way to prepare is to go over the homework problems AND examples from your notes. Make sure you can reproduce the full solution from the beginning to the end by yourself. Most exam problems will be similar. So, don't worry about anything else. We'll finish 3.6 for sure by Wednesday (hopefully by Tuesday), so that you have until Friday afternoon to practice and ask questions about it.
  
  

Textbook

Russell C. Walker, Introduction to Mathematical Programming

We'll mainly cover chapter 1,3,4,7. Part of chapter 2 will be presented as a quick review of matrix algebra. If time permits, we may add some of chapter 8.

Prerequisite knowledge

Students should be familiar with elementary matrix algebra, such as row operation, Gaussian elimination, matrix multiplication, vector space, etc. Other than that, no prerequisite knowledge is assumed. We'll also give a quick review of the part of matrix algebra that's used in this course.

Hours

Lecture hours: (MTWRF) 01:30PM - 02:50PM at WEH 6423
Office hours: Mainly by appointment (pyu@andrew.cmu.edu) at WEH 6403

Grade

There will be weekly homework assignments, a midterm and a final. The midterm is divided into two parts given on two days (probably Thursday and Friday), so we can have a 3-hour miderm in total. Final will be 3 hours as usual. For the overall score, HW takes 20%, midterm takes 30% and final takes 50%. The final will be comprehensive, with at most 30% of the problems focusing on the material covered before midterm. (Notice the material is accumulative, so there's no way to avoid stuff done in the early stage of the course while testing the later stuff.) The final grade is determined according to the following scale:

• A: 90-100
  
• B: 80-89
  
• C: 70-79
  
• D: 60-69
  
• Fail: 0-59
  

Homework assignments

Homework is usually due on Wednesdays in class.

• HW1 (Due: May 30)

  sec 1.4: 4, 7 (try both the level-line method and test-all-corner-points method) sec 2.3: 1, 3 sec 2.4: 1(b), 2(b) sec 2.5: 6, 7 sec 2.6: 1(a), 5 sec 3.2: 1, 4 (hint:x2 and s3 are nonbasic variables and should be set to zero. Why?) sec 3.3: 3, 4 (answer (c) for the given tableau and the next tableau)

• HW2 (Due: June 6) ( Check the latest news!!! Midterm is coming. )

  sec 3.3: 5, 7 sec 3.3: 11 (this problem is optional because it's a little hard. But think about it. It's a very good exercise and it's doable with the knowledge we have so far.) sec 3.4: 4, 9, 8(a geometric argument that's general enough is fine. Of course, a rigorous proof is the best.) ( Check the latest news!!! Midterm is coming. )

• HW3 (Due: June 13)

  sec 3.5: 1, 8(hint: it may be easier to use percentages as the variables instead of the amounts, # of tons = 500*percentage.) sec 3.6: 2, 4(no need to solve), 5, 6 ( It's wise to start doing this hw by midterm because it's a good preparation. )

• HW4 (Due: June 20)

  Read sec 3.7 sec 3.7: 8, 9, 2, 5, 11 (For problem 8, s1=2 and s2=0 are not the solution y1 and y2 to the dual problem. The solution is the COEFFICIENTs of s1 and s2 in the objective row of the optimal Simplex tableau, not s1, s2 themselves. So, you have to use complementary slackness to figure out the solution. There's no simpler way.) sec 3.8: 4(answer (b)(c) only), 6(Hint: (b) is tricky, you have to use the "reasoning" I stated in class.) sec 4.2: 1, 5

• HW5 (Due: June 25, Monday ) ( Check the latest news!!! Final is coming. )

  Read section 7.2 sec 4.3: 1, 3, 4 (Defintion for "float" can be found on page 214. As a critical path is a path of zero slack, a critical activity is an activity with zero float.) sec 7.2: 1 sec 7.3: 1, 5 sec 7.4: 2, 3(Angeline reported that in 3, the third row entry of the "s3" column should be 1/5 instead of 1 in the book. Please make correction.) ( Check the latest news!!! Final is coming. )

• HW6 (Due: June 29)

  sec 7.5: 3, 4

This page

http://www.math.cmu.edu/~pyu/21-257

The material on this page is subject to change during the semester. I'll inform you in class in case a significant change is made.