INTRODUCTION TO LINEAR PROGRAMMING

MATH 340

The final takes place in room ESB 1012. Time: Dec. 7, 12:00 (noon).

The Final Exam for this course is cumulative; you will be tested on everything we have covered throughout the semester. First midterm + second midterm + Maximum Flows (Chapters 20 and 22 in your book). Note that for network problems we used the augmented path method only.

Here is the practice final. It has no LINDO question. For a detailed LINDO example follow the link below the practice final. Also review the examples from class, HWs, and practice questions. (scroll down for more) I will post the solutions on of the practice final on Wednesday evening.

Practice Final

Solutions

The link above contains most of the problems and give a good hint for the solutions. There are some typos, so be careful. See the corrections below. (For the theorem of duality check your book.)

The Simplexme software has a bug. The last part of the solution is plain wrong. If you solve the problem correctly then you will see that the correct answer is x1=8, x2=1, and the optimum is -11.

There is a typo in the solution of Question 3. We know that A=y1 and later we learned that B=y2. Accidentally I used x1 and x2 for the final solution instead of y1 and y2. Everything is correct, but in the conclusion A= 2 and B=1/2.

The solution of the revised simplex question is x1 = 9/19, x2 = 25/19, x3 = 0. The optimum is 77/19. For the detailed solution check the link below.

Rev.Simplex solution

For the network question the solution (which you can read from the picture) A-W3, B-W2, D-W4, is just one of the possible optimal solutions. Your matching might be different if you selected another augmenting path.

If you don't understand some of the solutions then practice similar problems and come to the office hour tomorrow.

LINDO UWO

MATH 340:

Linear programming problems, dual problems, the simplex algorithm, solution of primal and dual problems, sensitivity analysis.

The core material for the course is covered in Chapters 1-10 of the textbook. After dealing with it, we can branch out in several directions. Here is this term's plan:

week #1 intro to linear programming; objective function, constraints, feasible solutions, standard form of an LP.

week #2 dictionary; the simplex method; slack variables, (non-)basic variables, pivoting.

week #3 tableau format; pitfalls in the simplex method, the Fundamental Theorem of Linear Programming.

week #4,5 duality; the Duality Theorem, applications.

week #5 Test #1.

week #6 Complementary Slackness, economic signiÞcance of dual variables.

week #7 LINDO

week #8 the Revised Simplex Method, matrix description of dictionaries.

week #9 the Duality Theorem, review

week #10 sensitivity analysis, Test #2

week #11+ applications

The final examination counts for 50% of the course grade. Each midterm counts for 15%, and the homework counts for 20%. (The instructor may scale grades or adjust this formula. If that happens, the same scheme will be applied to each student in the class. Each student's grade will be the maximum of the formula result and the output of the scaling scheme.)

Policies:

All midterms and the final examination will be strictly closed book: no notes, formula sheets, or calculators will be allowed.

¥

There is no supplemental examination in this course.

Late homework assignments receive a grade of 0. Homework copied from another student will produce a grade of 0 for both the original solver and the copyist.

¥

Missing a midterm normally results in a mark of 0. Exceptions may be granted in two cases: prior consent of the instructor or a medical emergency. In the latter case, the instructor must be notified within 48 hours of the missed test, and presented with a doctor's note immediately upon the student's return to UBC.

The final takes place in room ESB 1012. Time: Dec. 7, 12:00 (noon).

The Final Exam for this course is cumulative; you will be tested on everything we have covered throughout the semester. First midterm + second midterm + Maximum Flows (Chapters 20 and 22 in your book).

Instructor:

Prof. Jozsef Solymosi

Mathematics Building, room 220

Office hours (MATH 340): Dec. 5, Thursday, 1pm-3pm

solymosi@math.ubc.ca

Homework

-HW1.

-HW2.

HW3: From Chvatal?s book 3.9 a, b, and c. (Page 44) and 1.8 (Page 11).

Due date: Friday September 27.

HW4: Use LINDO to solve Question 1 in HW#1 (Blood transfusion problem) and Question 3 in HW#2 (aviation fuel and heating oil) For the first question you can use the solution I provided and for the second use your own LP formulation of the problem. Print out the formulation and the solution pages for both problems and attach the printout to the HW. Ask LINDO to do sensitivity analysis.

For the second problem answer the following questions based on the LINDO output;

a, How much are you willing to pay (max) for an extra hour of catalytic cracker time availability? Explain your answer. (If you can't answer this question based on the LINDO output then explain why)

b, Would you buy additional 1,000 barrels of oil for \$40/barrel? Explain!

Due date: Friday October 18.

HW 5. Game Theory.

For this assignment you should read Chapter 15. (Matrix Games) from Chvatal's book.

Question 1, Formulate the LP problem to solve Problem 15.4 on page 237. Use LINDO to actually solve the problem. Attach the printouts from LINDO.

Question 2, Problem 15.5. For the proof you have to write down the sum which describes the payoff and rearrange it so the inequalities and equations lead you to the statement you want to show. Check the similar arrangements of sums in the textbook.

The due date is next Monday, the 28th of October. (Note the unusual date!)

The next HW is also a practice midterm. Print out the pages and present your solutions in the booklet. The due date is next Wednesday, Nov. 6.

-HW6.

Seventh HW. The due date is Monday, the 25th of November.

Check the network in exercise 22.1 in your book. Ignore the text, use the picture only.

Question 1. Find a Minimum Cut. Explain your steps, how did you find the cut.

Question 2. Change the capacity of each arc to 17-x where x was the (old) capacity of the arc. For example the first edge from the Source pointing to the Sink had capacity 5 which will become 12 after the change. The edge arriving to the Sink from below will have capacity 1. Find the Maximum Flow of the modified network using the augmented path method.

The final takes place in room ESB 1012. Time: Dec. 7, 12:00 (noon).

The Final Exam for this course is cumulative; you will be tested on everything we have covered throughout the semester. First midterm + second midterm + Maximum Flows (Chapter 22 in your book).

Answers: Due to some recent negotiations the shipping cost from warehouse 1 to customer 4 is reduced by \$2 per unit. What will be the new optimum?

In general, if you change the coefficients of the objective function, then the present solution is still feasible since we did not change the constraints. So, here we can say that the new minimum is at most the old one. The value of XWH1C4 was 0 in the optimal solution, so changing \$7 to \$5 has no effect on the current solution. Also, changing by \$2 is in the range where the basis remains unchanged so the optimum is the same.

Bad news! Costumer 2 has cancelled the contract, you won't transport there any longer. What will be the new optimum?

The change is in the range where the basis remains unchanged so the dual prize will tell us the new optimum. We won't transport to costumer 2, so the shipping cost will decrease. The new optimum will be old min. - 17*2= 127.

Good news! Costumer 2 is back and even increased the order to 30. What will be the new optimum?

This change is out of range where the basis remains unchanged. So, we don't know the answer from this output. (In fact if you check then you can see that the problem is not even feasible now.)

Due to some problems, warehouse 2 can not supply more than 22 units. What will be the new optimum?

The change is in the range where the basis remains unchanged so the dual prize will tell us the new optimum. This is a restriction in one of the constraints, so the new shipping cost will be higher. The new optimum will be the old min. + 3*2 = 167.

(With solution)

Practice questions for the mindterm (I will post the solutions by Wednesday):

1, A contractor is planning to build a new housing development consisting of colonial, split-level, and ranch-style houses. A colonial house requires one-half acre of land, \$60,000 capital and 4,000 labor-hours to construct, and returns a profit of \$20,000. A split-level house requires one-half acre of land \$60,000 capital, and 3000 labor-hours to construct and returns a profit of \$18,000. A ranch house requires 1 acre of land, \$80,000 capital, and 4,000 labor-hours to construct, and returns a profit of \$24,000. The contractor has available 30 acres of land, \$3,200,000 capital, and 180,000 labor-hours.

How many houses of each type should be constructed to maximize the contractorÕs profit? What is the maximum profit?

Write down the LP problem and solve it by the simplex method.

2. Solve the following LP problem using the two-phase method.

maximize z = 2x1 + 3x2 + x3

subject to

x1 + x2 + x3 <= 40

2x1 + x2 - x3 >= 10

- x2 + x3 >= 10

x1; x2; x3 >= 0

3. Complementary Slackness

Maximize 7x1 + 6x2 + 5x3 - 2x4 + 3x5

Subject to the constraints

x1 + 3x2+ 5x3- 2x4 + 2x5 <= 4

4x1 + 2x2- 2x3 + x4 + x5 <= 3

2x1 + 4x2 + 4x3 - 2x4 + 5x5 <= 5

3x1 + x2 + 2x3 - x4 - 2x5 <= 1

x1, ... , x5 >= 0.

The solution x1* = 0, x2* = 4/3, x3* = 2/3, x4* = 5/3, x5 = 0 has been proposed as an optimal solution of the LP. Check it using complementary slackness.

solutions