Math 484  Ocober 4, 2007      Mayur Aras corrected by L.V.

 x y z 1. Solve for y, z 0 2 1 =u 1 0 1 =v

Solution:

The second row reads x + z = v  hence
z= v - x.
The first row reads 2y + z = u   hence  2y= u-z = u -(v-x) = u-v+x   and
y = u/2 -v/2 +x/2.

 u v x 1/2 -1/2 1/2 =y 0 1 -1 =z

This tableau can be also obtained from the initial tableau by two pivot steps.

2. x - 2y 3 -> min,

x2 y 3 = 1.

Solution:

Solve the equation for y3y 3 =(1-  x2 ).
Plug into the objective function:

x - 2(1-  x2 ) =   x -2 +2x2 = 2(x+1/4)2 -1/8-2 -> min.

Now it is clear that  min = -17/8 at  x = -1/4, y3 = 15/16.

3.

 x y 1 3. Solve for x, y 1 -1 2 1 x 2x >=  1 <= 2 -2 -1 x - > min

Solution: It is given that  2y + 2x >= 1, x+y <= 2. The objective function, f = -x - y -> min.

The constraints say that -2 <= f <= -1/2.

Now it is clear that  min = -2 at  x =  1, y =1 (there are other optimal solutions).

4. Solve the linear programs given by the following standard tableaux:

 a b 1 Problem 4a -1 0 -1 =d 0 -1 -1 ->min

Solution: The d-row is bad so the LP is infeasible.

 a b c 1 Problem 4b -1 0 -1 1 =d 1 0 1 0 ->min

Solution: Tableaux is already optimal: min=0 at a=b=c=0, d=1

 a b c 1 Problem 4c 1 0 -1 3 =d -2 0 1 -1 ->min

Solution: Tableaux is feasible with column a bad, so LP is unbounded.

5. Find all logical implications between the following 5  constraints on  x, y:

(a)   x3 = y3, (b) x = y= 0, (c)  x >= y , (d) x + y = 0, (e) y > -1.

Solution:

a implies c

b implies a, c, d, e