Deck 5: The Theory of the Simplex Method

Question 1

Consider the following problem.Minimize Z = x₁ + 2 x₂,subject to -x₁ + x₂ $\le$ 15 2 x₁ + x₂ $\le$ 90 x₂ $\ge$ 30 and x₁ $\ge$ 0,x₂ $\ge$ 0.
(a)Solve this problem graphically
(b)Develop a table giving each of the CPF solutions and the corresponding defining equations,BF solution,and nonbasic variables.

Answer 1

(a)Thus,the optimal solution is (x₁,x₂)= (15,30)with Z = 75. (b)The above graphical solution reveals that the problem has three CPF solutions,as listed in the first column of the table below.The corresponding defining equations are the equations of the constraint boundaries (the solid lines in the above graph)that pass through the respective CPF solutions,as listed in the second column of the table below.To identify the corresponding BF solutions and nonbasic variables,we need to use the augmented form of the problem.Introducing slack variables,x₃ and x₄,and surplus variable x₅,we have Minimize Z = x₁ + 2 x₂,subject to - x₁ + 2 x₂ + x₃ = 15 2 x₁ + x₂ + x₄ = 90 x₂ - x₅ = 30 and x₁ $\ge$ 0,x₂ $\ge$ 0,x₃ $\ge$ 0,x₄ $\ge$ 0,x₅ $\ge$ 0.Also introducing an artificial variable x₆ into the last constraint is optional,since this variable would be needed only to initiate the simplex method,which we are not concerned with doing here.If x₆ is introduced,it would become an additional nonbasic variable (so its value would be 0)in the last two columns of the table below.For each CPF solution,the corresponding BF solution listed in the third column is obtained by calculating x₃,x₄ and x₅ in the augmented form of the problem.The nonbasic variables listed in the last column are the variables whose values are 0 in the BF solution.

Question 2

Consider the following problem.Maximize Z = 2x₁ + 4x₂ + 3x₃,subject to x₁ + 3x₂ + 2x₃ ≤ 30 x₁ + x₂ + x₃ ≤ 24 3x₁ + 5x₂ + 3x₃ ≤ 60 and x₁ ≥ 0,x₂ ≥ 0,x₃ ≥ 0.You are given the information that x₁ > 0,x₂ = 0,and x₃ >0 in the optimal solution.Using the given information and the theory of the simplex method,analyze the constraints of the problem in order to identify a system of three constraint boundary equations (defining equations)whose simultaneous solution must be the optimal solution (not augmente d).Then solve this system of equations to obtain this solution.

Answer 2

Since x₁ > 0 and x₃ > 0,it follows that x₁ = 0 and x₃ = 0 cannot be part of the three defining equations at the optimal solution.Since x₂ = 0,then x₁ + x₃ $\le$ 24 and 3 x₁ + 3 x₃ $\le$ 60 or,equivalently,x₁ + x₃ $\le$ 24 and x₁ + x₃ $\le$ 20.This implies that the second constraint (x₁ + x₂ + x₃ ≤ 24)must have some slack,so its constraint boundary equation cannot be a defining equation at the optimal solution.We now have ruled out three of the six constraint boundary equations as being part of the defining equations at the optimal solution.For this three-variable problem,each CPF solution including the optimal solution must have three defining equations.Therefore,the three constraint boundary equations not ruled out must be the defining equations for the optimal solution.These defining equations are x₂ = 0,x₁ + 3 x₂ + 2 x₃ = 30,3 x₁ + 5 x₂ + 3 x₃ = 60.Solving this system of equations yields the optimal solution as (x₁,x₂,x₃)= (10,0,10).

Question 3

You are using the simplex method to solve the following linear programming problem.Maximize Z = 6x₁ + 5x₂ - x₃ + 4x₄,subject to 3x₁ + 2x₂ - 3x₃ + x₄ ≤ 120 3x₁ + 3x₂ + x₃ + 3x₄ ≤ 180 and x₁ ≥ 0,x₂ ≥ 0,x₃ ≥ 0,x₄ ≥ 0.You have obtained the following final simplex tableau where x₅ and x₆ are the slack variables for the respective constraints. Use the fundamental insight presented in Sec.5.3 of the textbook to identify Z*, ,and .

Answer 3

The fundamental insight presented in Sec.5.3 of the textbook states in part that Z* =y*b, = S*b,where y* = is the vector of coefficients of the slack variables in Eq.(0),S* = is the matrix of coefficients of the slack variables in the remaining equations,and b is the vector of the original right-hand sides.(Since S = B^-1,where B is the basis matrix,and y* = c_BB^-1,where c_B is the vector of the objective function coefficients of the basic variables,this alternative notation may be used throughout this solution.)Therefore,the final right-hand side is = S* b = = ,and Z^* = y*b = = 315.

Question 4

Consider the following problem.Maximize Z = 2x₁ + 4x₂ + 3x₃,subject to x₁ + 3x₂ + 2x₃ = 20 x₁ + 5x₂ ≥ 10 and x₁ ≥ 0,x₂ ≥ 0,x₃ ≥ 0.Let be the artificial variable for the first constraint.Let x₅ and be the surplus variable and artificial variable,respectively,for the second constraint.You are now given the information that a portion of the final simplex tableau is as follows: (a)Extend the fundamental insight presented in Sec.5.3 of the textbook to identify the missing numbers in the final simplex tableau.Show your calculations.(b)Identify the defining equations of the CPF solution corresponding to the optimal solution in the final simplex tableau.