Course Description:

Solution of linear programming problems by simplex method, duality theory, transportation problems, assignment problems, network analysis, dynamic programming

Instructor:

Aaron Nung Kwan Yip

Department of Mathematics

Purdue University

Contact Information:

Office: MATH 432

Email and Phone: click here

Lecture Times and Places:

Section 001 (CRN 26170): T, Th 12:00 PM - 1:15 PM, LILY G401

Office Hours:

M, W: 2:45pm-4:00pm, MATH 432, or by appointment

Occasionally, due to unexpected events, there might be a need for online meetings and lectures. These will be conducted in Zoom.
You can also find this link in Brightspace MA421 course homepage: Content/Zoom (upper left corner, second tab).
This link will also be used in case you need to see me online.

Textbook:

Main Text (required):
[V] Linear Programming, Foundations and Extensions, 5th edition, Robert J. Vanderbei, Springer.
Accessible online from Purdue Library page, using Career account.
Additional resources

You are highly encouraged to make good use of the textbook by reading it.

References (recommended reading):
[FMW] Linear Programming with Matlab, Michael C. Ferris, Olvi L. Mangasarian, Stephen J. Wright, SIAM
Available online from Purdue Library page, using your Career account.

[MG] Understanding and Using Linear Programming, Jiri Matousek and Bernd Gartner, Springer.
Accessible online from Purdue Library page, using Career account.

[E] Mathematical Methods for Optimizations - Finite Dimensional Optimization, L. C. Evans
Accessible online

[C] Linear Programming, Vasek Chvatal,
Available in Brightspace, Content/Course Materials

Homework:

Homeworks will be assigned weekly, due usually on Thursday in class. They will be gradually posted as the course progresses. Please refer to the course announcement below.

Steps must be shown to explain your answers. No credit will be given for just writing down the answers, even if it is correct.

As a rule of thumb, you should only use those methods that have been covered in class. If you use some other methods for the sake of convenience, at our discretion, we might not give you any credit. You have the right to contest. In that event, you might be asked to explain your answer using only what has been covered in class up to the point of time of the homeworks or exams.

Please staple all loose sheets of your homework to prevent 5% penalty.

Please resolve any error in the grading within one week after the return of each graded assignment.

No late homework will be accepted (in principle).

You are encouraged to discuss the homework problems with your classmates but all your handed-in homeworks must be your own work. Submitting identical work constitutes one form of cheating.

Examinations:

Tests: Midterm (in class, Oct 23)

Final Exam: During Final Exam Week

No books, notes or electronic devices are allowed (nor needed) in any of the tests and exam.

Grading Policy:

Homeworks (40%)

Midterm (20%)

Final Exam (40%)

The following is departmental policy for the grade cut-offs:
97% of the total points in this course are guaranteed an A+,
93% an A,
90% an A-,
87% a B+,
83% a B
80% a B-,
77% a C+,
73% a C,
70% a C-,
67% a D+,
63% a D, and
60% a D-.
For each of these grades, it's possible that at the end of the semester a lower percentage will be enough to achieve that grade.

You are expected to observe academic honesty to the highest standard. Any form of cheating will automatically lead to an F grade, plus any other disciplinary action, deemed appropriate.

Nondiscrimination Statement:

This class, as part of Purdue University's educational endeavor, is committed to maintaining a community which recognizes and values the inherent worth and dignity of every person; fosters tolerance, sensitivity, understanding, and mutual respect among its members; and encourages each individual to strive to reach his or her own potential.

Student Rights:

Any student who has substantial reason to believe that another person is threatening the safety of others by not complying with Protect Purdue protocols is encouraged to report the behavior to and discuss the next steps with their instructor. Students also have the option of reporting the behavior to the Office of the Student Rights and Responsibilities. See also Purdue University Bill of Student Rights and the Violent Behavior Policy under University Resources in Brightspace.

Accommodations for Students with Disabilities and Academic Adjustment:

Purdue University strives to make learning experiences accessible to all participants. If you anticipate or experience physical or academic barriers based on disability, you are also encouraged to contact the Disability Resource Center (DRC) at: drc@purdue.edu or by phone at 765-494-1247.

If you have been certified by the DRC as eligible for accommodations, you should contact me to discuss your accommodations as soon as possible. See also Courses: ADA Information for further information from the Department of Mathematics.

Campus Emergency:

In the event of a major campus emergency or circumstances beyond the instructor's control, course requirements, deadlines and grading percentages are subject to change. Check your email and this course web page for such information.

See also Emergency Preparedness and Planning for campus wide updates.

Course Outline (tentative):

I will at least cover sections from [V] Chapters 1-15, which touch upon simplex methods, duality, sensitivity and parametric analysis, network flows and various applications.

Additional materials will be covered based on time and interests.

Course Progress and Announcement:

You should consult this section regularly, for homework assignments, additional materials and announcements.
You can also access this page through BrightSpace.

---

Some tips and comments.

NOTATION MATTERS!!!!!!!!!!!!!!!
A clear understanding of notations is one of the keys to fullly appreciate mathematics.

READ THE TEXTBOOK!
Get used to how mathematics are formulated and presented.

My MOTTO on the use of technology (which I use often):
IF TECHNOLOGY HELPS YOU UNDERSTRAND, BY ALL MEANS USE IT. OTHERWISE, USE IT AT YOUR OWN RISK!
For the homework, I believe all the problems should be and can be done by hand. In order to get full credit, sufficient steps must be shown. You are welcome to use technology to check your answers.

BEWARE THAT DURING THE TESTS AND EXAM, NO TECHNOLOGY WILL BE ALLOWED.

---

Week 1 (Aug 26, 28):
[E, Chapter 1][V, Chapter 1][C, Chapter 1]
General concepts of optimization and linear programming (LP).
3-in-1 example: dietary problem:

solution by graphical method (in R^2);

changing of parameters;

dual problem.
Standard form of LP.
Geometry of LP: hyperplane, half-space, polyhedron/polytope, corner/vertex.

Note: Intro. to Optimization
Note: Intro. to Linear Programming
Ref: Examples and applications of Linear Programming (Beck, Guttmann-Beck, First Course in Linear Optimization)
(See also [FMW, Chapter 1], [MG, Chapter 1, 2, 3] for many more examples and applications)

Homework 1, due: Thursday, Sept 4th, in class.

---

Week 2 (Sept 2, 4):

[V, Chapter 2][C, Chapter 2]
Simplex method: going through vertices
slack, basic and non-basic variables;
feasible solutions, basic feasible solutions (vertices);
entering and leaving variables;
dictionary;
Variations of simplex method:
Phase I and II.
Unboundness
Non-uniqueness
Fundamental Theorem of LP:
[V] Theorem 3.4; [C] Theorem 3.4.
(Types of solutions: feasible/basic feasible/optimal/optimal basic)

Note: Examples of simplex method
Note: Variations of simplex method

Homework 2, due: Thursday, Sept 11th, in class.

---

Week 3 (Sept 9, 11):

[V, Chapter 3][C, Chapter 3]
Degeneracy, cycling, perturbation/lexicographic method, Bland Rule.
[V, Chapter 4][C, Chapter 4][MG Section 5.9]
Efficiency of simplex method: average vs worst case analysis;
Klee-Minty example;
[MG, Section 5.7]
Pivoting rules: Largest coefficient, largest increase, steepest slope, random, etc

[V, Chapter 9]
LP in general form;
formulation using auxiliary variables.

Note: Degeneracy in Simplex Algorithm
Note: Efficiency of Simplex Algorithm
Note: LP in general form

Homework 3, due: Thursday, Sept 18th, 11:59pm, in Gradescope.

---

Week 4 (Sept 16, 18):

[V, Chapter 5][C, Chapter 5][MG, Chapter 6]
Duality, primal (P) and dual (D) problems;
Upper and lower bounds, duality gap, Weak Duality Theorem [V, Thm. 5.1].
Complementary variables: x_j vs z_j, and w_i vs y_i;
Matrix representation of (P) and (D): preservation of negative transpose of matrices during simplex iterations;
Stong Duality Theorem [V, Thm. 5.2];
Dual simplex method, dual based Phase I.
Complementary Slackness [V, Thm. 5.3];
Certificate of Optimality.
Given (optimal) X, how to find (optimal) Y?

Note: Duality
Note: Complementary slackness

Homework 4, due: Thursday, Sept 25th, 11:59pm, in Gradescope.

---

Week 5 (Sept 23, 25):

[V, Chapter 5.8, 9.1] Duality in general form
(Economic) Interpretation of duality: cost vs profit;
[V, Chapter 5] Matrix form of LP and simplex method.

Note: Duality-II
Note: Matrix form of Simplex method
Ref: The Theory of Linear Economic Models (Chapter 1), by David Gale
Ref: Mathematical Methods of Economics, paper by Joel Franklin
Ref: Methods of Mathematical Economics, book by Joel Franklin

Homework 5, due: Thursday, Oct 2nd, 11:59pm, in Gradescope.

---

Week 6 (Sept 30, Oct 2):

---

Week 7 (Oct 7, Oct 9):

---

Week 8 (October Break, Oct 16):

---

Week 9 (Oct 21, 23):
Midterm: in class, Thursday, Oct 23

---

Week 10 (Oct 28, 30):

---

Week 11 (Nov 4, 6):

---

Week 12 (Nov 11, 13):

---

Week 13 (Nov 18, 20):

---

Week 14 (Nov 25, Thanksgiving):

---

Week 15 (Dec 2, 4):

---

Week 16 (Dec 9, 11):

---

Week 17 (Final Exam Week):