UP | HOME

Math 340: Linear Programming

Table of Contents

This course took place Sep-Dec 2016

News

  • All assignments, quizzes and exams have been taken offline.

About

Linear Programming means maximizing or minimizing linear functions of variables subject to linear equations or inequalities (so maybe “Linear Optimization” would be a more descriptive name).

  • Classes: Monday, Wednesday and Fridays from 2pm to 3pm in Mathematics Annex 1100.
  • Office Hours for final exam (all in LSK 300):

    [Mon Dec 05] 11am-12pm
    [Wed Dec 07] 4pm-5pm
    [Fri Dec 09] 11am-12pm
    [Tue Dec 13] 2pm-3pm

Textbook

We will use Linear Programming by Vašek Chvátal. This text explains the simplex method using the dictionary format that we will use in class.1

Notes

You can get the course notes in a single PDF or each topic in a separate web page:

Quizzes

Quizzes will be held in class from 2:25pm to 2:50pm on the indicated dates. I will post links to practice quizzes about a week before each quiz.

Practice for… Date of Quiz
Quiz 1 [Mon Sep 19]
Quiz 2 (final dictionaries) [Fri Sep 30]
Quiz 3 [Fri Oct 14]
Quiz 4 [Fri Oct 28]
Quiz 5 (solutions) [Mon Nov 14]

Midterm

There will be an in-class midterm on [Mon Oct 31]. Here is a practice midterm. It is important to really try the problems before looking at the solutions! You can get solutions to the practice midterm if you’re sure you’re ready to look at them.

Course Outline

Each of the following topics will take approximately 2 weeks (the chapters listed are from Chvátal’s book):

  • Simplex Method (chapters 1–4 & 8)
  • Duality Theory (chapters 5,9)
  • Revised Simplex Method (chapters 6,7)
  • Sensitivity Analysis (chapter 10)

After that we will cover some of the following topics:

  • Applications and some modeling techniques (chapters 11-14)
  • Branch and Bound
  • Game theory (chapter 15)
  • Non-linear Programming and the Karush-Kuhn-Tucker conditions
  • General Upper Bounding (chapter 25)

Computer Software

On some problems you will be asked to use computer software to solve linear programming problems. I recommend the Classic LINDO application for Microsoft Windows. You can obtain a free evaluation copy from that link to install on your own computer, or use the computer lab in LSK 310. You either should choose a time with no labs or, you can work quietly at the back of the lab even if a lab is scheduled (assuming there are some empty computers). Your ID is the first 8 characters in lower case of your name as recorded first name, middle name (if you have one), final name. The password is set to capital S followed by the first 7 numbers of your student ID. You can change your password. Access the Windows system and click on LINDO.

You don’t need to use LINDO, specially if you have prior programming experience. Other options include:

  • Glpk.js and online-optimizer. These are websites, you don’t need to install anything on your own computer! The second also does sensitivity analysis (for the constraints).
  • The MixedLinearIntegerProgram class in SageMath. Sage can be used without installing any software at SageMathCell. If you chose the GLPK solver, it can also do sensitivity analysis.
  • The scipy.optimize.linprog function from SciPy.

Grading

The grade will be computed as 55% final; 15% midterm; 15% quizzes and 15% assignments.

Quizzes
These will be mostly computational problems. There will be 5 quizzes of 25 minutes in length. Practice questions will be given in advance.
Assignments
There will be 5 assignments. They will have an emphasis on theory. Some assignments will give computational questions and you will be able to utilize the computer Lab and the LINDO and LINGO software for Linear programming (available in the computer lab in LSK 310; you will be given accounts) or software of your choosing. Students may work together on assignments but must write up their solutions independently.
Midterm and Final
There will be one 50 minute midterm, it will be during class on Monday, October 31st. The final will be 3 hours long.

1

Feel free to look at any other comparable text, but beware that the simplex method might look fairly different, even while it performs the same computations.

2

This refers to chapters from the textbook.

3

Not a typo! This is covered in Chapter 7.

by Omar Antolín Camarena