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.