Math 340 Section 202
Linear Programming
Online Course Material 

NEWS


Final Exam scheduled for Tuesday, April 19, 2016 from 7:00-10:00pm in Buchanan A 101. We will be writing the 3 hour exam with the other section.

Our midterm is scheduled for Wednesday Feb 24. 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 A103. (There is a second section called 201 scheduled for 9:30-11 TTh in MATH 104 taught by Omar Antolin Camarena 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 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 Wednesday Jan 13 starting at 12:30pm to the end of class. 
  • Practice for Quiz 2, for Wednesday Jan 20 starting at 12:30pm to the end of class. 
  • Assignment 1, Due Wednesday January 27 at start of class. Solutions,  
  • Practice for Quiz 3, for Wednesday Feb 3 starting at 12:30pm to the end of class. 
  • Assignment 2, Due Wednesday February 10 at start of class. Solutions,  
  • Practice for Quiz 4, for Monday Feb 22 starting at 12:20pm to 12:45pm. We must finish early for the next class.  
  • Sample Midterm, We will be aiming for 70-30 split computation vs theory on the midterm. The final exam split will be more like 60-40.  
  • Solutions to our midterm  
  • Assignment 3, Due Wednesday March 9 at start of class. Solutions,  
  • Practice for Quiz 5, for Wednesday March 16 starting at 12:25pm to 12:45pm.  
  • Assignment 4, Due Wednesday March 23 at start of class. . Solutions,  
  • Assignment 5, Due Friday April 1 at start of class. Solutions,  



  • Supplementary Course Notes.
  • Aviation fuel blending problem (handout only) 
  • Obtaining Standard Inequality form  
  • Our first pivoting example  
  • An unbounded example (a slide show)  
  • Pivots preserve the set of solutions a direct proof. We will also appeal to the linear algebra proof from the Revised Simple Formulas.  
  • Degenerate Pivots and why not to fear them.  
  • Chvatal`s example of cycling which has the virtue of being an exact computation in binary. No numerical errors can result.  
  • An example of infeasibility and our Magic Coefficients.  
  • Overview of Simplex two phase method.  
  • Our main Linear Programming Theorems  
  • Revised Simplex Formulas Try on an example. The ordering of the columns of B (and rows of the inverse of B will be important.  
  • Proof of Strong Duality and Complementary Slackness as well as our Marginal Values interpretation of the dual.  
  • A Theorem of the Alternative . There are many variations that you will see.  
  • Example of Revised Simplex with the standard simplex dictionaries displayed.  
  • Eta matrices examples  
  • Proof of Blands Rule  
  • Sensitivity analysis example of Trucking firm from lectures.  
  • A sensitivity analysis example  
  • An example of the dual simplex method which is shows the dual in unbounded (towards negative infinity) and so the primal is infeasible.  
  • An outline of Game Theory of our two person zero sum games.  
  • Cones in LP and a different perspective on optimality.  
  • Karush-Kuhn-Tucker Conditions This topic wonÕt be on the final.  
  • Branch and Bound example solving an integer programming problem using idea of adding constraints.  



  • Additional resources
  • 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. Sensor Network 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