Math 340 Section 201
Linear Programming
Online Course Material

NEWS

The final exam schedule has been posted and our exam is Thursday April 12 3:30-6:30 (we have a 3 hour exam) in MATH ANNEX 1100. We will be writing a different exam from the other section.

I will be available Wednesday April 11 from 10-12 in MATH ANNEX 1118 and I will also be available 3-5 in MATH ANNEX 1100 and will be around 2-3 as well. I will also be available when students request time; I do expect to be in on Tuesday April 10. I will certainly be unavailable for questions after noon on Thursday April 12.

The practice finals tell you a great deal about the exam. A complete two phase method question is to be expected (with no fractions). Quiz 2 and the first question on Midterm are similar. A question that tests the basic duality theory given either a solution to primal or dual use this, with complementary slackness, to determine an optimal solution to the dual or primal respectively. Note that this procedure will not always work. Quiz 3 and the second question of the the midterm are similar. The revised simplex method seems to figure in the final. Quiz 4 and the third question on the midterm are similar. A multiquestion sensitivity analysis question is typically 4 on the final. Quiz 5 was an abbreviated version. You are expected to be able to use the dual simplex method in both its applications. Maybe I will come up with a special question that seems more difficult. My advice is to read the question carefully to see what is being asked, particularly I fmore than one thing is being asked.
Question 5 on the last two finals has had some application and questions that often utilize LINDO output. You have had assignment questions as well. Who knows what I'll dream up this time. Playoff hockey as an LP? The remainder of the questions are theory type questions. Perhaps there will be a theorem about inequalities that will involve you setting up a primal/dual pair and arguing from there. Perhaps there will be a Game theory question or two. Perhaps some theory question involving sensitivity analysis. Perhaps you will be asked to state one of OUR theorems (isted below in a handout). Perhaps you will be asked to describe why we use the Revised simplex method. What are those eta matrices for?
My advice to you is to always make sure you can do the basics (questions 1-4).

This course would be more properly called Linear Optimization, optimizing a linear objective function subject to linear constraints. The word `programming' is not used in the sense of computer programming. My best reading of Dantzig's description of the term is that the word programming refers to the program of activities given by a solution. There will be no computer programming in this course although for certain assignments you will be asked to use LINDO, a fairly user friendly software package for Linear Programming.

For Section 201, January 2012 in MATH 104.

My office is Mathematics Annex 1114. I will be in most days by 9:00 For office hours I have booked MATH ANNEX 1118 for Wednesday 4-5 (I will be unavailable several Wednesdays but will schedule alternate hours) and most assignments/quizzes/midterm will be set for Thursdays. You could review some linear algebra concepts particularly the basics of matrix multiplication and change of basis.

The basic course material will be covered in about 9 weeks allowing 3 weeks to do applications and a topic of students choice (Game Theory? Karush-Kuhn-Tucker conditions useful in Economics and Non-Linear Optimization? More Applications?)

George Dantzig, who invented the Simplex method died May 13, 2005 at age 90. An obituary is at Obituary

I will be putting some course materials on the web in pdf format. I would not recommend printing them up too far in advance of lectures since they may change. They look authoritative when typed so be wary. They may look perfect but still contain errors! The text by Vasek Chvatal is an excellent reference but it can be short on examples and the problems in the text are not very good for our course. In addition we cover several topics that are not covered in much depth in the text. Hence we have our own supplementary notes. You will enjoy the later chapters on applications in the text e.g. Chapter 11 and on.

There is a computer lab in LSK 310 (and maybe LSK 121) (LSK is the Klinck Building) whose doors are open at various hours during the day. You either should choose a time with no labs or, because we are fairly far through the term, you could 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. You want to access the windows system and click on LINDO.

• Course Outline: grading scheme etc.
• Practice for Quiz 1, for Thursday Jan 12 starting at 10:30am at the end of class.
• Practice for Quiz 2, for Thursday Jan 19 starting at 10:30am at the end of class. There are two examples of the two phase method, one becoming unbounded and one finding the optimal solution. The quiz will go to an optimal solution. If you discover an LP is unbounded,remember to report the parametric set of feasible solutions whose objective function values go off to infinity. I will be available 3-4 for office hours on Wednesday in MATH ANNEX 1118 but my 4:00 meeting is still happening.
• Assignment 1, due Thursday Jan 26 at the beginning of class.
• Assignment 1 Solutions,
• Practice for Quiz 3, for Thursday Feb 2 starting at 10:30am at the end of class. I will be available 4-5 for office hours on Wednesday in MATH ANNEX 1118.
• Assignment 2, due Thursday Feb 9 at the beginning of class.
• Assignment 2 Solutions,
• Practice for Quiz 4, for Tuesday Feb 14 starting at 10:30am at the end of class. I will be available 4-5 for office hours on Monday FEB 13 in MATH ANNEX 1118.
• Quiz 4 Solutions,
• Sample midterm from fall 2011. I will not post solutions to these questions. Most of them can ve checked using your existing tools. I will be able to discuss the midterm during possible office hours on Tuesday 14 or Wednesday 15. At that time I can look over your work. The idea of a practice midterm is to indicate the format of a midterm and give you a practice test for you to write after you have studied. Posted solutions are essentially no help.
• Midterm Solutions.
• Assignment 3, due Thursday March 8 at the beginning of class.
• Assignment 3 Solutions,
• Practice for Quiz 5, for Thursday Mar 15 starting at 10:30am at the end of class. I will be unavailable for usual office hours (Senate business) and so encourage you to visit me on Tuesday after class from 11-1. The quiz is a little long (but not as long as the practice!) and typically will have one question requiring the dual simplex algorithm. The final exam will have a greater variety of such sensitivity questions.
• Assignment 4, due Thursday March 22 at the beginning of class. I will be available for office hours Wednesday March 21 in MATH ANNEX 1118 from 4-5 but other times as well.
• Assignment 4 Solutions,
• Assignment 5, due Thursday March 29 at the beginning of class. I will be available for office hours Wednesday March 28 in MATH ANNEX 1118 from 4-5 but other times as well including 11-12.
• Assignment 5 Solutions,

• Supplementary Course Notes.
• Aviation fuel blending problem (handout only)
• First pivoting example from class with a variation with more than one optimal solution.
• An unbounded example. Always give the parametric set of solutions that show the LP is unbounded. This file is set up to be a pdf slideshow that you click through.
• A cycling example. This is an example where our Anstee's rule (the standard pivot rules) results in no termination. This file is set up to be a pdf slideshow that you click through.
• Pivots preserve the set of solutions proved without the matrix approach. .
• Linear Programming Theorems as we use them in this course.
• Revised Simplex Formulas derived.
• Magic Coefficients as coefficient of slack variables in z row at optimality.
• Example of obtaining optimal dual solution as coefficients of slack variables in z row at optimality.
• Proof of Strong Duality as well as Complementary Slackness and Marginal Value Interpretation.
• Outline of Simplex algorithm indicating why it terminates. We use this termination to prove the Fundamental Theorem of Linear Programming and Strong Duality. Note that we could prove these theorems by other techniques but I think it is interesting for you to see some Mathematical Theorems proven using an algorithm.
• A Theorem about inequalities applying duality theory to get results about inequalities. We will have a number of questions of this sort on assignments, midterm and final.
• Revised Simplex Method done in parallel with the standard simplex method so you can compare and figure out what is being done. In this course I will not expect you to update the inverse of B but I do expect you to be able to produce the eta matrix that updates B.
• Eta Matrix. This contains examples of the eta matrix that updates B for the above example. Hopefully this will help you to understand how to find the eta matrix and also appreciate its simple form.
• Bland's Rule and a proof that it avoids cycling.
• Trucking Example with great sensitivity.
• Another Sensitivity Analysis Example with similar examples. You will see that I typically give a selection of such problems (including the dual simple method) on the final exam.
• Branch and Bound This is a different example from the one done in class but the main steps are the same. This example is given in the course MATH 441, a project course that considers `applied' problems often Linear Programs or Integer Linear Programs.
• Game Theory some brief notes. The text in Chapter 15 is quite helpful.
• Cones and how they arise in sensitivity analysis for the objective function. The main result is that if we have a feasible solution x to a primal (typical inequalities but all variables free) then x is optimal if and only if the gradient of the objective function lies in the cone generated by the gradients of the active constraints for x. This is a lovely result but wouldn't be on the final; you don't have to memorize it! We do have the possibility on the exam of sensitivity analysis for the objective function.
• Karush-Kuhn-Tucker Conditions for optimal solutions to non-linear optimization problems.

• Matrix multiplication This has a refresher on matrix multiplication. Matrices and matrix multiplication figure prominently in this course and should be reviewed. The examples are for 2x2 and 3x3 matrices but can generalize to multiplying pxq and qxr matrices. Change of basis is the key concept we use from your Linear Algebra class.
• You can find copies of old MATH 340 exams here.
• December 2010 Final Exam
• December 2011 Final Exam
• Alexis Guigue alerted me to this interesting contest being run in France. It is a type of Operations Research/Probablility that may interest you. Traffic Problem.

• The following are some LINDO files the first from a problem in the text.

New Forest problem

max 204x10+287x11a+215x11b+228x12+293x13
+148x20+207x21a+135x21b+148x22+212x23
+112x30+157x31a+85x31b+98x32+162x33
+371x40+487x41a+415x41b
+264x50+337x51a+265x51b
+61x60+87x61a+15x61b
subject to
hivolhd)x10+x11a+x11b+x12+x13=2754
mdvolhd)x20+x21a+x21b+x22+x23=850
lovolhd)x30+x31a+x31b+x32+x33=855
conifhi)x40+x41a+x41b=1598
mixedhi)x50+x51a+x51b=405
barelnd)x60+x61a+x61b=1761
conifer)x11a+x21a+x31a+x41a+x51a+x61a+x40<3845
treatmnt)x11a+x11b+x12+x13+x21a+x21b+x22+x23
+x31a+x31b+x32+x33+x41a+x41b+x51a+x51b+x61a+x61b<5000
felledhd)2000x11a+2000x11b+2000x12+2000x13
+1200x21a+1200x21b+1200x22+1200x23
+700x31a+700x31b+700x32+700x33<2440000
felledcm)4000x41a+4000x41b+2500x51a+2500x51b<4160000
x12<357
x22<197
x32<39
x13<500
x23<130
x33<170
end

x11b+x21b+x31b+x41b+x51b+x61b>500

Battleship

max z
z+x1-x2-x3-x4+x5-x6-x7<0
z+x1-x2+x3-x4-x5+x6-x7<0
z-x1-x2+x3-x4-x5-x6+x7<0
z-x1+x2-x3-x4+x5-x6-x7<0
z-x1+x2-x3+x4-x5+x6-x7<0
z-x1-x2-x3+x4-x5-x6+x7<0
x1+x2+x3+x4+x5+x6+x7=1
end
free z

max w
w+y1+y2-y3-y4-y5-y6>0
w-y1-y2-y3+y4+y5-y6>0
w-y1+y2+y3-y4-y5-y6>0
w-y1-y2-y3-y4+y5+y6>0
w-y1+y2-y3-y4+y5-y6>0
w-y1-y2+y3-y4-y5+y6>0
y1+y2+y3+y4+y5+y6=1
end
free w

Morra

max z
subject to
z +2x2-3x3 <0
z-2x1 +3x4<0
z+3x1 -4x4<0
z -3x2+4x3 <0
x1+x2+x3+x4 =1
end
free z

max z
subject to
z +2x2-3x3 +2x6-3x7 <0
z-2x1 +3x4 -2x6+3x7 <0
z+3x1 -4x4+3x5 -4x8<0
z -3x2+4x3 -3x5 +4x8<0
x1 +x2 +x3 +x4 +x5+x6 +x7+x8=1
end
free z

Tollbooth problem

min x1+x2+x3+x4+x5+x6+x7+x8+x9+x10
+x11+x12+x13+x14+x15+x16+x17+x18+x19
+x20+x21+x22+x23+x24
subject to
12:00am)x1+x17+x18+x19+x20+x22+x23+x24>2
1:00am)x1+x2+x18+x19+x20+x21+x23+x24>2
2:00am)x1+x2+x3+x19+x20+x21+x22+x24>2
3:00am)x1+x2+x3+x4+x20+x21+x22+x23>2
4:00am)x2+x3+x4+x5+x21+x22+x23+x24>2
5:00am)x1+x3+x4+x5+x6+x22+x23+x24>2
6:00am)x1+x2+x4+x5+x6+x7+x23+x24>8
7:00am)x1+x2+x3+x5+x6+x7+x8+x24>8
8:00am)x1+x2+x3+x4+x6+x7+x8+x9>8
9:00am)x2+x3+x4+x5+x7+x8+x9+x10>8
10:00am)x3+x4+x5+x6+x8+x9+x10+x11>4
11:00am)x4+x5+x6+x7+x9+x10+x11+x12>4
12:00pm)x5+x6+x7+x8+x10+x11+x12+x13>3
1:00pm)x6+x7+x8+x9+x11+x12+x13+x14>3
2:00pm)x7+x8+x9+x10+x12+x13+x14+x15>3
3:00pm)x8+x9+x10+x11+x13+x14+x15+x16>3
4:00pm)x9+x10+x11+x12+x14+x15+x16+x17>6
5:00pm)x10+x11+x12+x13+x15+x16+x17+x18>6
6:00pm)x11+x12+x13+x14+x16+x17+x18+x19>5
7:00pm)x12+x13+x14+x15+x17+x18+x19+x20>5
8:00pm)x13+x14+x15+x16+x18+x19+x20+x21>5
9:00pm)x14+x15+x16+x17+x19+x20+x21+x22>5
10:00pm)x15+x16+x17+x18+x20+x21+x22+x23>3
11:00pm)x16+x17+x18+x19+x21+x22+x23+x24>3
end