7.4 The Simplex Method: Maximization Standard Maximum Form A linear programing problem is in standard maximum form if 1. the objective function is to maximized; 2. all variables are nonnegative (x 2 0, i = 1,2,3, --): 3. all constraints involve s; 4. the constants on the right side in the constraints are all nonnegative (b > 0) Example 1: Restate the following lincar programming problem by introducing slack variables: Maximize z = 2xị + 3x2 + X3 Subject to x1 + X2 + 4x3 < 100 x, + 2x, + x3 < 150 3x1 + 2x2 + X3 S 320, with x, 2 0, x2 2 0, x3 2 0. Example 2: Determine the pivot in the simplex tablcau for the problem in Example 1. Pivoting Once the pivot has been selected, row operations are used to replace the initial simplex tableau by another simplex tableau in which the pivot column variable is eliminated from all but one of the cquations. Since this new tableau is obtained by row operations, it represents an equivalent system of equations (that is, a system with the same solutions as the original system). This process, which is called pivoting, is explained in the next example. Example 3: Use the indicated pivot, 2, to perform the pivoting on the simplex tableau of Example 2: 100 150 320 -2 -3 -1 0 0 0 1 0. Example 4: In the simplex tableau obtained in Example 3, select a new pivot and perform the pivoting. Example 5: Solve the linear programming problem introduced in Example 1. 7.4 The Simplex Method: Maximization Example 6: In Example 1 of Section 7.3, the following problem was solved graphically (using x and y instead of x, and x2 , respectively): , 7) Maximize z = 8x, + 12x2 (K, 3) Subject to 40x, + 80x, < 560 6x, + 8x2 < 72 x, 2 0, x2 2 0. 40, + S0 S60 (12, 0 with Graphing the feasible region and evaluating z at cach Corner Point Value of = Kr + 12 (0, 0) comer point shows that the maximum value of z (0, 7) 84 occurs at (8,3) (8, 3) 100 (maximum) (12, 0) 96 To solve the same problem by the simplex method, add a slack variable to cach constraint: (0, 7) (0, 7 (R, 3) (8, 3) (8.3) (0,0) (12.0) (0, 0) (12,0 (0. 0) (12,0 Figure 7.28 Figure 7.29 Figure 7.30