Math 340: Introduction to Linear Programming, Fall 2017

Lecture schedule — Homework/Quiz/Exam info

Lecture: MWF 2:00-3:00, Math Annex 1100
Instructor: Dan Collins
Office Hours: Monday 3:00-4:00 and Thursday 2:00-3:00 in LSK 300

Textbook: Linear Programming, by Vašek Chvátal

We'll cover the following topics, listed with the corresponding chapters of the book. (We won't follow the book precisely, and will supplement it with some other notes. One thing we'll do differently from the book is work with matrix notation from much earlier on in the course.)

• The simplex method - Chapters 1-4 and the first section of chapter 7
• Duality theory - Chapters 5 and 9
• The revised simplex method - Chapters 7 and 8
• Sensitivity analysis - Chapter 10
• Applications and advanced topics (depending on time and class interests)
Another good reference is Linear Programming by Robert Vanderbei (electronic copy available to download through the UBC library!). Nearly any book on linear programming will cover the main topics above, but the notation used for the simplex method may be quite different (and take some effort to translate to the notation we'll use).

Homework and Quizzes: Each week there will be either a quiz (on Friday at the beginning of class), or a homework assignment (due on Friday at the beginning of class). There will be a total of five quizzes and five assignments throughout the term.

Exams: There will be a 50-minute in-class midterm (date TBA) during the semester, and a final exam during the exam period we're assigned.

Grading: Grades in this class will be computed with the following weights:
• Quizzes: 15%
• Assignments: 15%
• Midterm: 15%
• Final Exam: 55%
See the assignment/quiz/exam page for policies about missed or late work.

Computer software: Many software packages have the simplex method implemented and can solve linear programs. Computational examples will come up in class, and homework assignments may ask you to solve linear programs using a computer. The software I'll be using for the purposes of this class is called LINDO; you're free to use any other software package you'd like, but any example code will be done in LINDO's syntax. To use LINDO, you have two options:

• You can download and install a trial version of LINDO from their website. The one that I'll be using is "Classic LINDO" at the bottom.
• UBC has computer labs located in the Leonard S. Klinck building (room 310); the hours for this lab is here (and be sure to check the lab schedule linked there to make sure there isn't a class that's reserved it at the time you want).
• If you're registered for the course, an account on these computers has been generated for you (or will be created within a few days if you've just been added). You can email me for your login info, or (hopefully) figure it out from the following ways they use to generate it:
• Your username will most likely either come from putting your full name together (including middle names, with no spaces) and taking the first 8 letters (or the whole thing if it's shorter) - my name is "Daniel Jack Collins" so my username would be "danielja" under this rule. Alternatively, it may be obtained by taking the first 8 letters of just your last name, or (if your last name is shorter than 8 letters) taking your full last name and putting as much of your first name before it as will fit in an 8-letter limit, so my alternate username would be "dcollins" under this rule. If you've tried these ways and neither work it may have been generated another way, so you'd need to email me to check.
• Your password is always a capital S followed by the first seven letters of your student ID number; so if your ID number is 12345678, your password is "S1234567". (It's probably a good idea to change this if you start using your account, though not to a password you use elsewhere since I may be able to see it in plain text).
Also, Vanderbei has an online pivoting tool that lets you choose entering and exiting variables and performs the pivot automatically. This is a good way to get an idea of how the simplex method will work on larger problems without having to do all of the algebra by hand!