# Simplex Method - Solve Standard Maximization Problem

by Lucy
(Dallas )

Maximum value of a linear objective function

Given the initial simplex tableau for the maximization linear programming problem with variables x , y, z and slack variables r, s, t, find the optimal solution using the simplex method:

_ x y z r s t P
4 1 1 1 0 0 0 30
2 3 1 0 1 0 0 60
1 2 3 0 0 1 0 40
-3-2-1 0 0 0 1 0

### Comments for Simplex Method - Solve Standard Maximization Problem

 Aug 03, 2012 Simplex Method – Maximize Objective Function by: Staff Answer: Part I of IV Note: the solution process for this problem is exceptionally long. The final solution is given at the end of Part IV.    • Standard maximization problems – two variables – Graphical Solutions:        You are, no doubt, familiar with determining the maximum value of a linear objective function involving only two variables (say x and y).        When only two variables are involved, the constraints (represented by inequalities) can be plotted on two dimensional x-y coordinates. The corner values can be computed to find a solution.        The process of finding a solution is visual, straightforward, and easy – but, it is generally limited to problems involving two variables.    • Standard maximization problems – more than two variables – Simplex Method:        The Simplex Method is a linear programming technique used to determine the maximum value of a linear objective function involving more than two variables (say, the variables x, y, and z in your problem statement).        The Simplex Method can be used to solve the entire class of “Standard Maximization Problems”.    • The definition of a Standard Maximization Problem is: Determine the maximum value of a linear objective function which is subject to various linear restrictions.        The Standard maximization problem has three restrictions:           1. It is limited to finding the “maximum” value of the objective function (not the minimum value).           2. All variables must be non-negative (0 or greater than 0)           3. All constraints must have the form: Ax + By + Cz + . . . ≤ N (where N ≥ 0)        When these conditions are met, the Simplex Method will compute the maximum value of the objective function.    • Initial simplex tableau        The initial simplex tableau in your problem statement is the “augmented matrix” for a the system of linear equations. ------------------------------------

 Aug 03, 2012 Simplex Method – Maximize Objective Function by: Staff ------------------------------------ Part II However, let’s back up and look at the problem the simplex tableau represents: Although it is not shown in your problem statement, this is your problem (the problem represented by the Initial Simplex Tableau in your problem statement): Maximize the objective function P = 3x + 2y + z subject to the following constraints 4x + y + z ≤ 30 2x + 3y + z ≤ 60 x + 2y + 3z ≤ 40 where x, y, and z are non-negative. The slack variables r, s, and t are introduced to convert the inequalities into equations: 4x + 1y + 1z + 1r + 0 + 0 + 0 = 30 2x + 3y + 1z + 0 + 1s + 0 + 0 = 60 1x + 2y + 3z + 0 + 0 + 1t + 0 = 40 -3x - 2x - 1z + 0 + 0 + 0 + 1P = 0 The four equations are converted into the augmented matrix (Initial simplex tableau) shown below: ___x y z r s t P R [ 4 1 1 1 0 0 0 30 ] S [ 2 3 1 0 1 0 0 60 ] T [ 1 2 3 0 0 1 0 40 ] P [-3-2-1 0 0 0 1 0 ] Row reduction of tableau Look at the bottom row P [-3-2-1 0 0 0 1 0 ] Pick the most negative number (the furthest to the left on the number line) -3 This column is the pivot column (in this case, the first column) Divide the constant (far right) in each row by the number in the pivot column ___x y z r s t P R [ 4 1 1 1 0 0 0 30 ] 30/4 = 7.5 S [ 2 3 1 0 1 0 0 60 ] 60/2 = 30 T [ 1 2 3 0 0 1 0 40 ] 40/1 = 40 --------------------------------------- P [-3 -2 -1 0 0 0 1 0 ] Take the smallest number you calculated: 7.5 The 4 located in the pivot column for that row will be the pivot The pivot number is the 4 located in row 1, column 1 Change the 4 into the number 1 ¼ * Row 1 = the new Row 1 ___x y z r s t P R [ 1 ¼ ¼ ¼ 0 0 0 7.5 ] S [ 2 3 1 0 1 0 0 60 ] T [ 1 2 3 0 0 1 0 40 ] --------------------------------------- P [-3-2-1 0 0 0 1 0 ] The goal is to make everything above and below the pivot element (1, far left, first row) into 0’s -2*(Row 1) + (Row 2) = new (Row 2) ___x y z r s t P R [ 1 ¼ ¼ ¼ 0 0 0 7.5 ] S [ 0 2.5 0.5 -0.5 1 0 0 45 ] T [ 1 2 3 0 0 1 0 40 ] --------------------------------------- P [-3-2-1 0 0 0 1 0 ] ------------------------------------

 Aug 03, 2012 Simplex Method – Maximize Objective Function by: Staff ------------------------------------ Part III -1*(Row 1) + (Row 3) = new (Row 3) ___x y z r s t P R [ 1 ¼ ¼ ¼ 0 0 0 7.5 ] S [ 0 2.5 0.5 0 1 0 0 45 ] T [ 0 1.75 2.75 -¼ 0 1 0 32.5 ] --------------------------------------- P [-3-2-1 0 0 0 1 0 ] 3*(Row 1) + (Row 4) = new (Row 4) ___x y z r s t P R [ 1 ¼ ¼ ¼ 0 0 0 7.5 ] S [ 0 2.5 0.5 0 1 0 0 45 ] T [ 0 1.75 2.75 -¼ 0 1 0 32.5 ] --------------------------------------- P [0 -1.25 -0.25 0.75 0 0 1 22.5 ] All the values under the first pivot value are now 0. At this point, determine whether there are any negative numbers in row 4 in columns x, y, or z. If there are no negative values, the problem is solved. Since there are negative values, a second pivot point must be selected. The second column, 4th row has the greatest negative value. Therefore, the second column is the new pivot column. +++Replace the row for the slack variable “R” with “x” 2nd pivot element ___x y z r s t P x [ 1 ¼ ¼ ¼ 0 0 0 7.5 ] 7.5/.25 = 30 S [ 0 2.5 0.5 0 1 0 0 45 ] 45/2.5 = 18 T [ 0 1.75 2.75 -¼ 0 1 0 32.5 ] 32.5 /1.75 = 18.5714 --------------------------------------- P [0 -1.25 -0.25 0.75 0 0 1 22.5 ] The new pivot point is 2.5, located in the second column, the second row 0.4*(Row 2) = new (Row 2) ___x y z r s t P x [ 1 ¼ ¼ ¼ 0 0 0 7.5 ] S [ 0 1 0.2 -0.2 0.4 0 0 18 ] T [ 0 1.75 2.75 -¼ 0 1 0 32.5 ] --------------------------------------- P [0 -1.25 -0.25 0.75 0 0 1 22.5 ] -1.75*(Row 2) + (Row 3) = new (Row 3) ___x y z r s t P x [ 1 ¼ ¼ ¼ 0 0 0 7.5 ] S [ 0 1 0.2 -0.2 0.4 0 0 18 ] T [ 0 0 2.4 0.1 -0.7 1 0 1 ] --------------------------------------- P [0 -1.25 -0.25 0.75 0 0 1 22.5 ] 1.25*(Row 2) + (Row 4) = new (Row 4) ___x y z r s t P x [ 1 ¼ ¼ ¼ 0 0 0 7.5 ] S [ 0 1 0.2 -0.2 0.4 0 0 18 ] T [ 0 0 2.4 0.1 -0.7 1 0 1 ] P [0 0 0 0.5 0.5 0 1 45 ] +++Replace the row for the slack variable “S” with “y” ___x y z r s t P x [ 1 ¼ ¼ ¼ 0 0 0 7.5 ] y [ 0 1 0.2 -0.2 0.4 0 0 18 ] T [ 0 0 2.4 0.1 -0.7 1 0 1 ] P [0 0 0 0.5 0.5 0 1 45 ] -(1/4)*(Row 2) + (Row 1) = new (Row 1) ___x y z r s t P x [ 1 0 3/20 7/20 -2/20 0 0 3 ] y [ 0 1 2/5 -0.2 0.4 0 0 18 ] T [ 0 0 2.4 0.1 -0.7 1 0 1 ] P [0 0 0 0.5 0.5 0 1 45 ] ------------------------------------

 Aug 03, 2012 Simplex Method – Maximize Objective Function by: Staff ------------------------------------Part IVAll the values above and below the second pivot value are now 0.At this point, determine whether there are any negative numbers in row 4 in columns x, y, or z.Since there are no negative values, the problem is solved. >>>> THE FINAL SOLUTION IS:Objective function maximized: P = 45Variable x = 3Variable y = 18Variable z = 0----------------------------------------------------------------check the solution:Maximize the objective functionP = 3x + 2y + z subject to the following constraints 4x + y + z ≤ 302x + 3y + z ≤ 60x + 2y + 3z ≤ 40x ≥ 0y ≥ 0z ≥ 0P = 3x + 2y + z P = 3* 3 + 2*18 + 0 = 45, OK4x + y + z ≤ 304*3 + 18 + 0 ≤ 30, OK2x + 3y + z ≤ 602*3 + 3*18 + 0 ≤ 60, OKx + 2y + 3z ≤ 403 + 2*18 + 3*0 ≤ 402x + 3y + z ≤ 602*7.5 + 3*18 + z ≤ 60, OKThanks for writing.Staff www.solving-math-problems.com