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, PHYS 202

Office Hours:

T, W: 4:30pm-5:45pm, 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.
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):
[C] Linear Programming, Vasek Chvatal

[CZ] An Introduction to Optimization, 4ed, Chong-Zak
Accessible online from Purdue Library page, using 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

[BV] Introduction to Applied Linear Algebra - Vectors, Matrices, and Least Squares, Stephen Boyd and Lieven Vandenberghe.
Acessible online

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.

Project: detail information

Examinations:

Midterm: Week 9, in class, Oct 22

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 (30%)

Project (20%)

Midterm (20%)

Final Exam (30%)

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.

Last but not least,
SHOW UP IN CLASS!!!!!!!!!!!!!!!
(Some notes or extra materials will be posted. They are not meant to replace my lectures.)

---

Week 1 (Aug 25, 27):

[V, Chapter 1][CZ, Chapter 5]
General concepts of optimization:

first derivative test, critical points

second derivative test, local max/min

constrained optimization and Lagrange multipliers
Linear programming (LP) a 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 vs facets;

convexity.

Note: Some preliminaries in calculus (thanks to Sammith Belur)
Note: Some preliminaries in linear algebra (thanks to Sammith Belur)
Note: Intro. to Optimization
Note: Intro. to Linear Programming
Ref: Examples and applications of Linear Programming (Beck, Guttmann-Beck, First Course in Linear Optimization)
Ref: Mathematical Methods of Economics, paper by Joel Franklin
(See [E Chapter 1][MG, Chapter 1, 2, 3] for many more examples and applications.)

Homework 1, due: Thursday, Sept 3rd, in class.

---

Week 2 (Sep 1, 3):

[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;

Note: Examples of simplex method

---

Week 3 (Sep 8, 10):

---

Week 4 (Sep 15, 17):

---

Week 5 (Sep 22, 24):

---

Week 6 (Sep 29, Oct 1):

---

Week 7 (Oct 6, 8):

---

Week 8 (Oct 15) (Oct 12-13: Fall Break):

---

Week 9 (Oct 20, 22):
Midterm: in class, Thursday, Oct 22

---

Week 10 (Oct 27, 29):

---

Week 11 (Nov 3, 5):

---

Week 12 (Nov 10, 12):

---

Week 13 (Nov 17, 19):

---

Week 14 (Nov 24) (Nov 25-27: Thanksgiving Break):

---

Week 15 (Dec 1, 3):

---

Week 16 (Dec 8, 10):

---

Week 17 (Dec 14-29):
Final Exam Week