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.
So the answer is
|
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 y3:
y 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