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.

Supplementary Course Notes.

Additional resources

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