Math 340 Section 201
Linear Programming
Online Course Material 

NEWS





Our Final exam is scheduled for April 15 at 8:30am (PDT) for 3 hours using Crowdmark. The students have an additional hour to upload their answers (one question at a time) but can continue working on the exam in this extra time. The link: https://app.crowdmark.com/sign-in/ubc will allow students to sign into Crowdmark using their CWL if they click the "Sign in with Canvas" option. Students maybe prompted to authorize Crowdmark to gain access to their Canvas account, which students should accept.
  • Our final exam . 8:30-12:30 Wednesday April 15, done on Crowdmark  
  • Exam instructions . 8:30-12:30 Wednesday April 15, done on Crowdmark  
  • Our mock exam (to verify your Crowdmark capabilities).  
  • A discussion of the exam and answers to many student questions.  
  • The integrity pledge required to be signed for the online final exam. This was provided by the department.  
  • Partial solutions for 2010 and 2011 exams.  

  • We will also post a very partial set of solutions for the practice exams from 2010 and 2011. What gets posted should enable you to check how you have done.

    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 user friendly software package for Linear Programming.

    For Section 201, 9:30-11 TTh (January 2020) in LSK 200.

    There is another section, Section 202, 12:00-13:00 MWF (January 2020) in BUCH A201 taught by Hugo Lavenant. Section 202 will be run partly coordinated with this section. Our quizzes and assignments will typically be on Thursdays while Section 202 will have quizzes and assignments on Fridays.

    My office is Mathematics Annex 1114. I will be in Tuesdays, Wednesdays and Thursdays by about 9:00, Mondays by about 1:00. Fridays I am unlikely to be at UBC. I will schedule office hours in the new year. Most assignments/quizzes will be set for Thursdays and so I will schedule special office hours 4-5 on Wednesdays assuming I can get a room. 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 recommended 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.


    Certain assignments will ask you to use LINDO software (either LINDO 6.1 or LINGO) which can be downloaded at www.lindo.com. There is a computer lab in LSK 310 (LSK is the Klinck Building) with this software 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 16 starting at 10:30am to the end of class. 
  • Practice for Quiz 2, for Thursday Jan 23 starting at 10:30am to the end of class. 
  • Assignment 1 for Thursday Jan 30 in class. Solutions.  
  • Practice for Quiz 3, for Thursday February 6 starting at 10:30am to the end of class. 
  • Practice for Quiz 4, for Thursday February 13 starting at 10:30am to the end of class. Solutions for versions of Quiz 4  
  • Sample Midterm. Our midterm is Tuesday February 25 for 55 minutes. I will not post solutions to practice tests but you will be welcome to visit me in office hours. I do have office hours Wednesdays afternoon (4-5 in MATH ANNEX 1118)as well as after class and other times in my office (MATH ANNEX 1114) and for the midterm will have an office hour in a bigger room for Monday February 24.  
  • Midterm Solutions  
  • Assignment 2 for Thursday March 5 in class. Solutions.  
  • Practice for Quiz 5, for Thursday March 12 starting at 10:30am to the end of class.  
  • Solutions for Quiz 5, I donÕt usually post this but we are in special times. Hugo Lavenant has kindly provided this file.  
  • Assignment 3 for Tuesday March 24 by noon using electronic submission. No need for submission of sample LINDO or LINGO input or output files Solutions.  
  • Assignment 4 for Thursday April 2 by noon using electronic submission. You will be sent a link from crowdmark (not canvas) for this. Solutions.  
  • There will be no assignment 5
  • There is a link for Hugo Lavenants videos on Game Theory etc that resides on google drive. My webpage didn`t like it so I`ll try as text only

    https://drive.google.com/open?id=1APAKrcB17edMG37C0MuGUefuX8D2mNCy


  • Supplementary Course Notes.
  • Aviation fuel blending problem (handout only) 
  • Linear Programming as Pig Farming  
  • Standard Inequality Form  
  • Modelling a Big Data problem as an LP  
  • Pivoting process essentially in Phase Two.  
  • Pivoting process with non unique optimal solutions and Revised Simplex Formulas .  
  • An example of an unbounded LP Note that you need to give a parametric solution to verify that the LP is unbounded.  
  • Two Phase method and another Two Phase method . This method is tested in Quiz 2 and then again in Midterm and then again on Final. Study it.  
  • Two Phase method as summarized by Hugo Lavenant in section 202.  
  • Two Phase method summary  
  • An example of an infeasible LP discovered in phase one. The magic coefficients provide an independent verification that the LP is infeasible. We would not expect these coefficients in solutions on quiz4.  
  • An example of degeneracy as we explored in class. Note the difference between a degenerate basic feasible solution (some basic variable is 0) and a degenerate pivot (the basic feasible solution doesn`t change from the pivot). Degenerate basic feasible solutions are common enough and degenerate pivots occur but we are only concerned as it affects finite termination of the algorithm.  
  • Pivots are reversible and so preserve the set of solutions to the equations of our dictionary  
  • An example that cycles from Chvatal and the slide show version.  
  • Revised Simplex Formulas.  
  • Our LP theorems. These are the theorems to quote in assignments and tests.  
  • Weak Duality  
  • Complementary Slackness  
  • Magic coefficients arising in dictionary that correspond to dual solution. An explanation that the negative of the coefficients of the slack variables yields the dual solution.  
  • Strong Duality and its proof  
  • Marginal Values and associated proofs  
  • Another example of Marginal Values written by Hugo Lavenant.  
  • Theorem of the Alternative. Versions of this appear on tests. The first step is trying to encode aspects of the inequalities in a primal/dual pair of LP`s.  
  • Revised Simplex Formulas a refresher.  
  • Revised Simplex. A worked example.  
  • Eta matrices.  
  • Bland`s Rule and a proof that the Simplex Algorithm using Bland`s rule has finite termination.  
  • Trucking problem and a variety of sensitivity questions. The Dual Simplex algorithm is introduced.  
  • Sensitivity problem and a variety of sensitivity questions. The Dual Simplex algorithm appears.  
  • Unboundedness in Dual Simplex yielding primal infeasibility.  
  • Branch and Bound which is done by adding constraints. The Dual Simplex algorithm would be helpful here.  
  • New Forest application . Input file to Lindo below.  
  • Battleship .  
  • Two person zero sum Games as LP`s.  
  • Game of Morra . It is very interesting to see how the computational abilities of LP enable you to examine a game more carefully.  
  • A strong connection between Games and LP . We have shown that we can solve Games with LP`s. The reverse is partly true. The MinMax theorem of Von Neumann is interesting in that it was proved long before LP duality but after the Farkas lemma (which is another result related to LP duality). The details of this wonÕt be suitable for the exam.  
  • A reduction strategy . Some games simplify to smaller games if you are lucky.  
  • A geometric view of optimal solutions . This geometric approach allows you to envision what you got a piecewise linear function as you computed the objective function as a function of c1.  



  • 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 second key concept we use from your Linear Algebra class. 
  • You can find copies of some old MATH 340 exams here.  
  • December 2010 Final Exam  
  • December 2011 Final Exam  



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

    New Forest problem (LINDO)


    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



    New Forest problem (LINGO)


    Max= 204*x10+287*x11a+215*x11b+228*x12+293*x13
    +148*x20+207*x21a+135*x21b+148*x22+212*x23
    +112*x30+157*x31a+85*x31b+98*x32+162*x33
    +371*x40+487*x41a+415*x41b
    +264*x50+337*x51a+265*x51b
    +61*x60+87*x61a+15*x61b;
    [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;
    [treatment]x11a+x11b+x12+x13+x21a+x21b+x22+x23
    +x31a+x31b+x32+x33+x41a+x41b+x51a+x51b+x61a+x61b<=5000;
    [felledhd]2000*x11a+2000*x11b+2000*x12+2000*x13
    +1200*x21a+1200*x21b+1200*x22+1200*x23
    +700*x31a+700*x31b+700*x32+700*x33<=2440000;
    [felledcm]4000*x41a+4000*x41b+2500*x51a+2500*x51b<=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 (LINDO)

    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



    Tollbooth problem (LINGO)

    @GIN(x1); @GIN(x2); @GIN(x3); @GIN(x4); @GIN(x5); @GIN(x6); @GIN(x7); @GIN(x8); @GIN(x9); @GIN(x10); @GIN(x11); @GIN(x12); @GIN(x13); @GIN(x14); @GIN(x15); @GIN(x16); @GIN(x17); @GIN(x18); @GIN(x19); @GIN(x20); @GIN(x21); @GIN(x22); @GIN(x23); @GIN(x24);
    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;
    [s1200am]x1+x17+x18+x19+x20+x22+x23+x24>=2;
    [s100am]x1+x2+x18+x19+x20+x21+x23+x24>=2;
    [s200am]x1+x2+x3+x19+x20+x21+x22+x24>=2;
    [s300am]x1+x2+x3+x4+x20+x21+x22+x23>=2;
    [s400am]x2+x3+x4+x5+x21+x22+x23+x24>=2;
    [s500am]x1+x3+x4+x5+x6+x22+x23+x24>=2;
    [s600am]x1+x2+x4+x5+x6+x7+x23+x24>=8;
    [s700am]x1+x2+x3+x5+x6+x7+x8+x24>=8;
    [s800am]x1+x2+x3+x4+x6+x7+x8+x9>=8;
    [s900am]x2+x3+x4+x5+x7+x8+x9+x10>=8;
    [s1000am]x3+x4+x5+x6+x8+x9+x10+x11>=4;
    [s1100am]x4+x5+x6+x7+x9+x10+x11+x12>=4;
    [s1200pm]x5+x6+x7+x8+x10+x11+x12+x13>=3;
    [s1300pm]x6+x7+x8+x9+x11+x12+x13+x14>=3;
    [s1400pm]x7+x8+x9+x10+x12+x13+x14+x15>=3;
    [s1500pm]x8+x9+x10+x11+x13+x14+x15+x16>=3;
    [s1600pm]x9+x10+x11+x12+x14+x15+x16+x17>=6;
    [s1700pm]x10+x11+x12+x13+x15+x16+x17+x18>=6;
    [s1800pm]x11+x12+x13+x14+x16+x17+x18+x19>=5;
    [s1900pm]x12+x13+x14+x15+x17+x18+x19+x20>=5;
    [s2000pm]x13+x14+x15+x16+x18+x19+x20+x21>=5;
    [s2100pm]x14+x15+x16+x17+x19+x20+x21+x22>=5;
    [s2200pm]x15+x16+x17+x18+x20+x21+x22+x23>=3;
    [s2300pm]x16+x17+x18+x19+x21+x22+x23+x24>=3;
    End