Homework 5

P= 3x+4y -> max, 2x+2y <= 200, x+3y <= t, x,y >=0, t a given number.

Solution by simplex method.

We introduce two slack variables
u=100-x-y >= 0 and v= t-x-3y >= 0.
We write the problem in a standard row tableau

x y 1

-1 -1 100 =u

-1 -3 t =v

-3 -4 0 =-P->min

When t < 0, the v-row is bad, so the problem is infeasible.
Assume now that t >0. The tableau is feasible, so we go to Phase 2.
We chose the y-column as the pivot column.

When t >= 300, then we pivot on -1 and obtain

x u 1

-1 -1 100 =y

2 3 t-300 =v

1 4 -400 =-P->min

which is an optimal tableau, hence max = 400 at x= 0, y=100.

Assume now that 0 < t < 300. Then according to the simplex method we pivot on -3 and obtain

x v 1

-2/3 1/3 100-t/3 =u

-1/3 -1/3 t/3 =y

-5/3 4/3 -4t/3 =-P->min

Now the x-column is the pivot column. We have to compare (100-t/3)/(-2/3) and (t/3)/(-1/3) to choose a pivot entry.
When 0 < t <=100, we pivot on -1/3 and obtain

y v 1

2 1 100-t =u

-3 -1 t =x

5 3 -3t =-P->min

hence max=3t at x=t, y = 0.
When 100 <= t <=300, we pivot on -2/3 and obtain

u v 1

-3/2 1/2 150-t/2 =x

1/2 -1 t/2-50 =y

5/2 1/2 -t/2-250 =-P->min

hence max=t /2+250 at x = 150-t/2, y= t/2-50.

Note that the slope is decreasing (the law of diminishing return):

interval 0<=t<=100 100 <= t <= 300 300 <= t

slope 3 1/2 0

The last tableau is optimal when t = 200 (the case in the film), and the slope is the last entry in the v-column.
If we start to change the first limit 200 (instead of the second limit 200), then the slope would be 5/4.

Graphical solution.

When t <0, the feasible region is empty, so the problem is infeasible.
When 0 <= t <= 100, the first constraint is redundund, the feasible region is a triangle, max = 3t at x=t, y = 0.
When 100 <=t <= 300, the optimal solution is the intersection of the lines corresponding to the first two constraints:
2x+2y = 200, x+3y = t, hence x= 150-t/2, y=t/2 -50, max = 250+t/2.
When t >=300, the second constraint is redundand, the feasible region is a triangle, max = 400 at x=0, y = 100.