INTRODUCTION TO LINEAR PROGRAMMING
UBC Math 340, Section 921 (Summer 2013)
http://www.math.ubc.ca/~loew/m340/

Mathematical optimization is a huge and vital subject, and Linear Programming is an important part of it. In this course we will discuss the surprising variety of problems for which Linear Programming has something useful to contribute. We will translate applied problems into LP form, solve them both by hand and by computer, explore the underlying geometric and algorithmic issues, and extract useful consequences from the solutions we find.

Syllabus

The core material for the course is covered in Chapters 1-10 of the textbook. After dealing with it, we can branch out in several directions. Here is this term's plan:

• The simplex method (Chapters 1-4) — about 7 sessions.
• Duality (Chapter 5) — about 4 sessions.
• Matrix Notation (Chapter 7) — about 2 sessions.
• Sensitivity analysis (Chapter 10) — about 3 sessions.
• Applications — whatever time remains.
  Topics are somewhat flexible; the Prof likes ...
  • Game Theory (Chapter 15)
  • Geometry (Chapter 17)
  • l¹ magic (online)
  • Quadratic and/or Convex Programming (online)

Learning Resources

Lectures:

Tu-Fr 14:00-16:00, room LSK 201. (Early dismissal Wednesdays.)

Course Web Page:

http://www.math.ubc.ca/~loew/m340/

Textbook (Required):

Chvátal, Vašek, Linear Programming, New York: W. H. Freeman, 1980.

Other References:  

• Robert Vanderbei, Linear Programming---Foundations and Extensions, third edition. New York: Springer-Verlag, 2008.
• Schechter, Eric, The most common errors in undergraduate mathematics. http://www.math.vanderbilt.edu/~schectex/commerrs/

Important Dates

• 14 May 2013 (Tue): First class of term.
• 28 May 2013 (Tue): Midterm 1 in class. Closed book, 90 minutes. Bring UBC ID, writing tools, and nothing else.
• 11 Jun 2013 (Tue): Midterm 2 in class. Closed book, 90 minutes. Bring UBC ID, writing tools, and nothing else.
• 20 Jun 2013 (Thu): Last class of term.
• 24–28 Jun 2013 (Mon-Fri): Exam week. We will have a scheduled exam, closed book, 180 minutes, exact time decreed by Enrolment Services. All students are responsible for being available for the entire exam period. Do not make travel plans until we know the date of the exam. Students who miss the final examination risk failing the course, as the Mathematics Department will not allow an alternate sitting outside of truly exceptional circumstances. UBC's definition of an exam conflict will apply to the exam period. Here is the link to UBC's official exam schedule.

Homework

There will be six assignments, one due every Friday. Details are on the course main page.

Grading Scheme

The final examination counts for 50% of the course grade. Each midterm counts for 20%, and the homework counts for 10%. (The instructor may scale grades or adjust this formula. If that happens, the same scheme will be applied to each student in the class. Each student's grade will be the maximum of the formula result and the output of the scaling scheme.)

Policies:

• All midterms and the final examination will be strictly closed book: no notes, formula sheets, or calculators will be allowed.
• There is no supplemental examination in this course.
• Late homework assignments receive a grade of 0. Homework copied from another student will produce a grade of 0 for both the original solver and the copyist.
• Missing a midterm normally results in a mark of 0. Exceptions may be granted in two cases: prior consent of the instructor or a medical emergency. In the latter case, the instructor must be notified within 48 hours of the missed test, and presented with a doctor's note immediately upon the student's return to UBC.

Instructor Contact Information

Last update: 25 Jul 2022 (Mon), 12:30:23. (Verification tools: [HTML]  [CSS].)