11.6. EXERCISES 245
Two good books which give more discussion of linear programming are Strang [17]and Nobel and Daniels [14]. Also listed in these books are other references which mayprove useful if you are interested in seeing more on these topics. There is a great deal morewhich can be said about linear programming.
11.6 Exercises1. Maximize and minimize z = x1− 2x2 + x3 subject to the constraints x1 + x2 + x3 ≤
10, x1+x2+x3 ≥ 2, and x1+2x2+x3 ≤ 7 if possible. All variables are nonnegative.
2. Maximize and minimize the following if possible. All variables are nonnegative.
(a) z = x1−2x2 subject to the constraints x1 + x2 + x3 ≤ 10, x1 + x2 + x3 ≥ 1, andx1 +2x2 + x3 ≤ 7
(b) z = x1−2x2−3x3 subject to the constraints x1+x2+x3 ≤ 8, x1+x2+3x3 ≥ 1,and x1 + x2 + x3 ≤ 7
(c) z = 2x1 + x2 subject to the constraints x1− x2 + x3 ≤ 10, x1 + x2 + x3 ≥ 1, andx1 +2x2 + x3 ≤ 7
(d) z = x1 +2x2 subject to the constraints x1− x2 + x3 ≤ 10, x1 + x2 + x3 ≥ 1, andx1 +2x2 + x3 ≤ 7
3. Consider contradictory constraints, x1+x2 ≥ 12 and x1+2x2 ≤ 5,x1 ≥ 0,x2 ≥ 0. Youknow these two contradict but show they contradict using the simplex algorithm.
4. Find a solution to the following inequalities for x,y≥ 0 if it is possible to do so. If itis not possible, prove it is not possible.
(a)6x+3y≥ 48x+4y≤ 5
(b)6x1 +4x3 ≤ 11
5x1 +4x2 +4x3 ≥ 86x1 +6x2 +5x3 ≤ 11
(c)6x1 +4x3 ≤ 11
5x1 +4x2 +4x3 ≥ 96x1 +6x2 +5x3 ≤ 9
(d)x1− x2 + x3 ≤ 2
x1 +2x2 ≥ 43x1 +2x3 ≤ 7
(e)5x1−2x2 +4x3 ≤ 16x1−3x2 +5x3 ≥ 25x1−2x2 +4x3 ≤ 5
5. Minimize z = x1 + x2 subject to x1 + x2 ≥ 2, x1 +3x2 ≤ 20, x1 + x2 ≤ 18. Change toa maximization problem and solve as follows: Let yi = M−xi. Formulate in terms ofy1,y2.