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.

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.

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

Supplementary Course Notes.

Additional resources

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