MA 421: Linear Programming And Optimization Techniques
Fall 2025, Purdue University
http://www.math.purdue.edu/~yipn/421
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.
Note: Examples of simplex method
Note: Variations of simplex method
Homework 2,
due: Thursday, Sept 11th, in class.
Week 3 (Sept 9, 11):
Week 4 (Sept 16, 18):
Week 5 (Sept 23, 25):
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):