# 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.