Math 340 Section 202
|Online Course Material
Our final exam is scheduled for Wednesday April 11 at 8:30 am in WOOD 2. The exam is 3 hours in length. There are office hours scheduled for Tuesday April 10 from 11-1 in MATH ANNEX 1118. Room for about 20.
Our midterm is scheduled for Friday Feb 16. Arrive early!
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 202, 12-1 MWF January 2016 in BUCH A201. (There is a second section called 201 scheduled for 9:30-11 TTh in MATH 104
that will be run partly coordinated with this section.)
My office is Mathematics Annex 1114. I will be in most days by 9:00. I will schedule office hours in the new year. Most assignments/quizzes/midterm will be set for Fridays.
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
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 Friday Jan 12 starting at 12:30pm to the end of class.
Practice for Quiz 2, for Friday Jan 19 starting at 12:30pm to the end of class.
Assignment 1, due Friday Jan 26 at beginning of class. Solutions,
Practice for Quiz 3, for Friday February 2 starting at 12:30pm to the end of class.
Assignment 2, due Friday February 9 at beginning of class. Solutions,
Practice for Quiz 4, for Wednesday February 14 starting at 12:30pm to the end of class. Solutions for versions of Quiz 4
Sample Midterm. Our midterm is Friday February 16 for 50 (maybe 55 minutes). I will not post solution but you will be welcome to visit me in office hours. I do have office hours Thursdays at 4:30-5:30
Midterm Solutions. Your midterms are available for pickup in MLC (LSK 310)
Assignment 3, due Friday March 2 at beginning of class. Solutions,
Practice for Quiz 5, for Friday March 9 starting at 12:30pm to the end of class.
Assignment 4, due Friday March 16 at beginning of class. Solutions,
Assignment 5, due Wednesday March 28 at beginning of class. This is the last assignment of the term.
Supplementary Course Notes.
Aviation fuel blending problem (handout only)
Obtaining Standard Inequality form
Our first pivoting example
An unbounded example (a slide show)
Two Phase Method with an example
A second example of Two Phase Method
Infeasibility revealed in Phase One. The magic coefficients are revealed.
Degenerate Pivots and why not to fear them.
Pivots preserve the set of solutions a direct proof. We will also appeal to the linear algebra proof from the Revised Simple Formulas.
Chvatal`s example of cycling which has the virtue of being an exact computation in binary. No numerical errors can result.
Revised Simplex Formulas which we use heavily in this course.
Our main Linear Programming Theorems
A Theorem of the Alternative a result about inequalities that uses our Linear Programming Theorems
Bland`s Rule and the proof by contradiction that it works to avoid cycling.
An example of duality and the demonstration that the negatives of the coefficients of the slack variables in the z row of an optimal dictionary yields the dual solution
Revised Simplex Algorithm compared directly with standard Simplex method pivots.
Eta matrices for our example.
Sensitivity Analysis and trucks with many examples of possible changes
Sensitivity Analysis and desks with a similar series of changes
Dual Simplex example leading to an infeasible primal and an unbounded dual.
Parametric sensitivity in the objective function.
Integer Linear Programming. When you need to find optimal solutions with integer values for some of the variables, the problem becomes much harder. One simple technique is Branch and Bound. Two examples are given. The first has variables that are forced to be 0 or 1 while the second example (the one done in class) has variables forced to be positive integers. There are a variety of techniques for integer linear programming including various cutting plane methods which are more useful constraints than the simple constrains used in our examples.
Karush-Kuhn-Tucker conditions for non-linear programming problems. They are a generalization of Lagrange multipliers for inequality constraints.
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 second 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.
Distribution of Goods.
The following are some LINDO files the first from a problem in the text.
New Forest problem
z +2x2-3x3 <0
z -3x2+4x3 <0
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