240 CHAPTER 11. LINEAR PROGRAMMING
0,x3 = 1/3,x4 = 0,x5 = 0,x6 = 5. Now as explained in the above observation, this is a basicfeasible solution for the original system 11.18.
Now consider a maximization problem associated with the above constraints.
Example 11.4.3 Maximize x1−x2 +2x3 subject to the constraints, 2x1 +x2−x3 ≥ 3,x1 +x2 + x3 ≥ 2,x1 + x2 + x3 ≤ 7 and x≥ 0.
From 11.20 you can immediately assemble an initial simplex tableau. You begin withthe first 6 columns and top 3 rows in 11.20. Then add in the column and row for z. Thisyields
1 23 0 − 1
3 − 13 0 0 5
30 1
3 1 13 − 2
3 0 0 13
0 0 0 0 1 1 0 5−1 1 −2 0 0 0 1 0
and you first do row operations to make the first and third columns simple columns. Thusthe next simplex tableau is
1 23 0 − 1
3 − 13 0 0 5
30 1
3 1 13 − 2
3 0 0 13
0 0 0 0 1 1 0 50 7
3 0 13 − 5
3 0 1 73
You are trying to get rid of negative entries in the bottom left row. There is only one, the−5/3. The pivot is the 1. The next simplex tableau is then
1 23 0 − 1
3 0 13 0 10
30 1
3 1 13 0 2
3 0 113
0 0 0 0 1 1 0 50 7
3 0 13 0 5
3 1 323
and so the maximum value of z is 32/3 and it occurs when x1 = 10/3,x2 = 0 and x3 = 11/3.
11.5 DualityYou can solve minimization problems by solving maximization problems. You can also gothe other direction and solve maximization problems by minimization problems. Some-times this makes things much easier. To be more specific, the two problems to be consid-ered are
A.) Minimize z = cx subject to x≥ 0 and Ax≥ b andB.) Maximize w = yb such that y≥ 0 and yA≤ c,(
equivalently AT yT ≥ cT and w = bT yT ) .In these problems it is assumed A is an m× p matrix.I will show how a solution of the first yields a solution of the second and then show
how a solution of the second yields a solution of the first. The problems, A.) and B.) arecalled dual problems.