Deck 4: Solving Linear Programming Problems: the Simplex Method

Question 1

Work through the simplex method (in algebraic form)step by step to solve the following problem.Maximize Z = x₁ + 2x₂ + 2x₃,subject to 5x₁ + 2x₂ + 3x₃ ≤ 15 x₁ + 4x₂ + 2x₃ ≤ 12 2x₁ + x₃ ≤ 8 and x₁ ≥ 0,x₂ ≥ 0,x₃ ≥ 0.

Answer 1

We introduce x₄,x₅,and x₆ as slack variables for the respective functional constraints.The augmented form of the problem then is Maximize Z = x₁ + 2 x₂ + 2 x₃,subject to 5 x₁ + 2 x₂ + 3 x₃ + x₄ = 15 x₁ + 4 x₂ + 2 x₃ + x₅ = 12 2 x₁ + x₃ + x₆ = 8 and x₁ $\ge$ 0,x₂ $\ge$ 0,x₃ $\ge$ 0,x₄ $\ge$ 0,x₅ $\ge$ 0,x₆ $\ge$ 0.The simplex method in algebraic form is applied to this augmented form of the problem as follows.Initialization: Let x₁,x₂ and x₃ be the nonbasic variables,so x₁ = x₂ = x₃ = 0.Solving for x₄,x₅ and x₆ from the equations in the constraints: (1)5 x₁ + 2 x₂ + 3 x₃ + x₄ = 15 (2)x₁ + 4 x₂ + 2 x₃ + x₅ = 12 (3)2 x₁ + x₃ + x₆ = 8 we obtain the initial BF solution (0,0,0,15,12,8).The objective function is Z = 1 x₁ + 2 x₂ + 2 x₃.The current BF solution is not optimal since we can improve Z by increasing x₁ or x₂ or x₃.Iteration 1: Z = x₁ + 2 x₂ + 2 x₃.We choose x₂ as the entering basic variable because increasing it (or x₃)increases Z at the fastest rate.(Alternatively,because of the tie,x₃ can be chosen instead to be the entering basic variable,in which case Iteration 2 would lead to x₂ becoming the entering basic variable at that point instead of x₃.)Next,we need to decide how far we can increase x_2. Since we need variables x₄,x₅ and x₆ to stay nonnegative,from the minimum ratio test,we find that x₂ can be increased to 3,at which point x₅ has decreased to 0.Therefore,the variable x₅ is the leaving basic variable,so it becomes a nonbasic variable.To find the new BF solution,we start with the current equations (1),(2),and (3)given above along with (0)Z - x₁ - 2 x₂ - 2 x₃ = 0.Since x₂ now is a basic variable,proper form from Gaussian elimination is restored by dividing Eq.(2)by 4,adding 2 times this new Eq.(2)to Eq.(0),and subtracting 2 times this new Eq.(2)from Eq.(1).This yields the following system of equations: (0)Z - 0.5x₁ - x₃ - 0.5x₅ = 6 (1)4.5 x₁ + 2x₃ + x₄ - 0.5x₅ = 9 (2)0.25 x₁ + x₂ + 0.5 x₃ + 0.25x₅ = 3 (3)2 x₁ + x₃ + x₆ = 8 Thus,the new BF solution is (0,3,0,9,0,8)with Z = 6.Iteration 2: The objective function becomes Z = 0.5 x₁ + x₃ - 0.5 x₅ + 6.The current BF solution is not optimal since we can improve Z by increasing either x₁ or x₃ .Since x₃ has the larger coefficient,increasing it gives the larger rate of improvement in Z (1).Hence,we choose x₃ as the entering basic variable.From the minimum ratio test,we find that x₃ can be increased to 4.5,at which point x₄ has decreased to 0.Thus,the variable x₄ becomes the leaving basic variable.Using elementary algebraic operations to restore proper form from Gaussian elimination,we obtain the following system of equations: (0)Z + 1.75 x₁ + 0.5 x₄ + 0.25 x₅ = 10.5 (1)2.25 x₁ + x₃ + 0.5 x₄ - 0.25 x₅ = 4.5 (2)- 0.875 x₁ + x₂ - 0.25 x₄ + 0.375 x₅ = 0.75 (3)- 0.25 x₁ - 0.5 x₄ + 0.25 x₅ + x₆ = 3.5 The new form of the objective function is Z = -1.75 x₁ - 0.5 x₄ - 0.25 x₅ + 10.5,which has no positive coefficients.Therefore,the new BF solution (0,0.75,4.5,0,0,3.5)is optimal with Z = 10.5.

Question 2

Consider the following problem.Minimize Z = 3x₁ + 2x₂,subject to 2x₁ + x₂ ≥ 10 -3x₁ + 2x₂ ≤ 6 x₁ + x₂ ≥ 6 and x₁ ≥ 0,x₂ ≥ 0.
(a)Solve this problem graphically.
(b)Using the Big M method,construct the complete first simplex tableau for the simplex method and identify the corresponding initial (artificial)BF solution.Also identify the initial entering basic variable and the leaving basic variable.
(c)Work through the simplex method step by step to solve the problem.

Answer 2

(a)
Thus,the optimal solution is (x₁,x₂)= (4,2)with Z = 16.
(b)We introduce the surplus variables x₃,x₄,slack variable x₆, and artificial variables x₅ and x_7. (Note that these supplementary variables can be numbered in any order.)Using the Big M method,the introduction of these supplementary variables gives the following form of the problem.Minimize Z = 3 x₁ + 2 x₂ + M x₅ + M x₇,subject to 2x₁ + x₂ - x₃ + x₅ = 10 -3x₁ + 2x₂ + x₆ = 6 x₁ + x₂ - x₄ + x₇ = 6 and x₁ $\ge$ 0,x₂ $\ge$ 0,x₃ $\ge$ 0,x₄ $\ge$ 0,x₅ $\ge$ 0,x₆ $\ge$ 0,x₇ ≥ 0.Converting from minimization to maximization,we next have Maximize Z = - 3 x₁ - 2 x₂ - M x₅ - M x₇,subject to (1)2x₁ + x₂ - x₃ + x₅ = 10 (2)-3x₁ + 2x₂ + x₆ = 6 (3)x₁ + x₂ - x₄ + x₇ = 6 and x₁ $\ge$ 0,x₂ $\ge$ 0,x₃ $\ge$ 0,x₄ $\ge$ 0,x₅ $\ge$ 0,x₆ $\ge$ 0,x₇ ≥ 0.Let x₅,x₆ and x₇ be the basic variables.The above objective function gives the following Equation (0).(0)Z + 3x₁ + 2x₂ + Mx₅ + Mx₇ = 0 Proper form from Gaussian elimination requires that the basic variables x₅ and x₇ be eliminated from this equation.This is accomplished by subtracting both M times Eq.(1)and M times Eq.(3)from Eg.(0),which yields (0)Z + (-3M + 3)x₁ + (-2M + 2)x₂ +Mx₃ +M x₄ = -16 M The corresponding initial simplex tableau is as follows.
The initial (artificial)BF solution is (0,0,0,0,10,6,6).The entering basic variable is x₁; the leaving basic variable is x₅.(c)Iteration 1: The negative coefficients of x₁ and x₂ in Eq.(0)of the above initial simplex tableau indicates that the initial BF solution is not optimal.After choosing the initial entering basic variable x₁ and leaving basic variable x₅ as noted above,proper form from Gaussian elimination is restored by dividing Eq.(1)by 2,adding (3M-3)times this new Eq.(1)to Eq.(0),adding 3 times the new Eq.(1)to Eq.(2),and subtracting the new Eq.(1)from Eq.(3).This yields the simplex tableau shown below.
The resulting BF solution is (5,0,0,0,0,21,1),which is not optimal because of the negative coefficients of x₂ and x₃ in Eq.(0).Iteration 2: Comparing the negative coefficients of x₂ and x₃ in the above Eq.(0),(-0.5M + 0.5)is slightly larger in absolute value than (-0.5M + 1.5),so x₂ is chosen as the entering basic variable and x₇ as the leaving basic variable,as indicated in the boxes in the above simplex tableau.After restoring proper form from Gaussian elimination,the following simplex tableau is obtained.
The current BF solution (4,2,0,0,0,14,0)is optimal,since all the coefficients in Eq.(0)are nonnegative.The resulting optimal solution for the decision variables of the problem is (x₁,x₂)= (4,2)with Z = 16.

Question 3

Consider the following problem.Maximize Z = 2x₁ - x₂ + x₃,subject to x₁ - x₂ + 3x₃ ≤ 4 2x₁ + x₂ ≤ 10 x₁ - x₂ - x₃ ≤ 7 and x₁ ≥ 0,x₂ ≥ 0,x₃ ≥ 0.(a)Work through the simplex method step by step in algebraic form to solve this problem.(b)Work through the simplex method step by step in tabular form to solve the problem.

Answer 3

(a)Initialization: After introducing slack variables,the initial system of equations is (0)Z - 2 x₁ + x₂ - x₃ = 0 (1)x₁ - x₂ + 3 x₃ + x₄ = 4 (2)2 x₁ + x₂ + x₅ = 10 (3)x₁ - x₂ - x₃ + x₆ = 7 Thus,the initial BF solution is (0,0,0,4,10,7),which is not optimal since Z = 2x₁ - x₂ + x₃ can be incresed by increasing either x₁ or x₃.Iteration 1: Choosing x₁ as the entering basic variable (since increasing x₁ increases Z at the fastest rate)and x₄ as the leaving basic variable (by the minimum ratio test),using elementary algebraic operations to restore proper form from Gaussian elimination then leads to the following system of equations.(0)Z - x₂ + 5 x₃ + 2 x₄ = 8 (1)x₁ - x₂ + 3 x₃ + x₄ = 4 (2)3 x₂ - 6 x₃ - 2 x₄ + x₅ = 2 (3) - 4 x₃ - x₄ +x₆ = 3 Thus,the current BF solution is (4,0,0,0,2,3),which is not optimal since Z = x₂ - 5x₃ - 2x₄ + 8 can be increased by increasing x₂.Iteration 2: Choosing x₂ as the entering basic variable and x₅ as the leaving basic variable (by the minimum ratio test),using elementary algebraic operations to restore proper form from Gaussian elimination then leads to the following system of equations.(0)Z + 3 x₃ + 4/3 x₄ + 1/3 x₅ = 8.667 (1)x₁ + x₃ + 1/3 x₄ + 1/3 x₅ = 4.667 (2)x₂ - 2 x₃ - 2/3 x₄ + 1/3 x₅ = 0.667 (3)- 4 x₃ - x₄ + x₆ = 3 From Eq.(0),Z = -3 x₃ - 4/3 x₄ - 1/3 x₅ + 8.667,so Z cannot be increased by increasing any of the nonbasic variables.Therefore,the current BF solution (4.667,0.667,0,0,0,3)is optimal with Z = 8.667.(b)Using the same logic as described above,the simplex method in tableau form is shown below. The current BF solution (4.667,0.667,0,0,0,3)is optimal with Z = 8.667.

Question 4

Consider the following problem: Maximize Z = 2x₁ + 4x₂ - x₃,subject to 3x₂ - x₃ ≤ 30 (resource 1)2x₁ - x₂ + x₃ ≤ 10 (resource 2)4x₁ +2x₂ - 2x₃ ≤ 40 (resource 3)and x₁ ≥ 0,x₂ ≥ 0,x₃ ≥ 0.(a)Work through the simplex method step by step to solve the problem.(b)Identify the shadow prices for the three resources and describe their significance.