|Lecture:||Tu Th 3:30 pm - 4:50 pm at CENTR 115|
|Office Hours:||Tu Th 10:00 am - 11:00 am at AP&M 6444|
A01: W 5:00 pm - 5:50 pm at HSS 1315, Chuqing
A02: W 6:00 pm - 6:50 pm at HSS 1315, Chuqing
A03: W 7:00 pm - 7:50 pm at HSS 1315, Jiajie
A04: W 8:00 pm - 8:50 pm at HSS 1315, Jiajie
|Teaching Assistant:||Chuqing Shi|
|Office Hours:||Tu 5:00 pm - 6:00 pm and F 9:00 am - 10:00 am at AP&M 1240||Teaching Assistant:||Jiajie Shi|
|Office Hours:||F 2:00 pm - 4:00 pm at AP&M 1131|
|Credit Hours:||4 (Credit not allowed for both MATH 171A and ECON 172A.)|
|Prerequisites:||MATH 18 or MATH 20F or MATH 31AH, and MATH 20C. Students who have not completed listed prerequisites may enroll with consent of instructor.|
|Course description:||Math 171A is an upper-division course introducing students to the field of mathematical optimization, in particular,
the area of linear optimization (historically known as linear programming). Topics covered in this course include the geometry of linear programming,
optimality conditions, the simplex method, duality theory.|
Some homework assignments will require the use of the package Matlab, although no prior knowledge of Matlab is assumed. Matlab enables the student to concentrate on the fundamental ideas of linear programming without becoming distracted by the rigors of mental arithmetic.
The aim of the class is for students to
|Textbook:||There is no required textbook for this course. A copy of "Linear Programming Notes" by Philip E. Gill, Walter Murray, and Margaret H. Wright will be made available to enrolled students. Please do not distribute these notes.|
|Syllabus:||This website acts as our syllabus.|
Exams: There will be three exams in the class:
⭢ You may use one 8.5 x 11 inch sheet of handwritten notes (which may be written on both sides, no photocopies!). No books, calculators, phones, or other aids may be used during exams.
Homework: Homework will be assigned weekly, and is due on Fridays at 11:00 am, starting in Week 2.
Homework problems will be uploaded on Canvas and Gradescope.
There will be nine (9) homework assignments in total.
The lowest homework grade will be dropped.
There are two methods to determine your course grade. Your grade will be determined using both methods and then the best grade will be used.
Overview of the Class:
Introduction to Optimization
Properties of Linear Constraints and Geometry of the Feasible Region
Properties of the Feasible Region and of the Objective Function
Two Methods for Toy Linear Programs,
Full-Rank Systems of Linear Equations
Homework 1 due
Martin Luther King, Jr. Holiday
Full-Rank Systems cont'd,
Properties of Incompatible Equations
Prop's of Incompatible Equations cont'd,
Linear Programming with Equality Constraints
Homework 2 due
Optimality Conditions for Equality Constraints,
Feasible Directions for Inequality Constraints
Homework 3 due
Last Day to Drop w/o 'W'
Vertices, Finding a Vertex
Optimality Conditions for Linear Programming
Homework 4 due
Farkas' Lemma and its Implications
The Simplex Method
Homework 5 due
Last Day to Drop w/o 'F'
Mitigating the Ill-Effects of Degeneracy
Finding a Feasible Point
Homework 6 due
LPs with Mixed Constraint Types
Homework 7 due
LPs in Standard Form,
Simplex Method for Standard-Form LPs
Linear Programming Duality Theory
Homework 8 due
More Duality Theory,
Complexity of Simplex Method
Other techniques for solving LPs,
Applications of Linear Programming,
Homework 9 due