Work Through the Simplex Method (In Algebraic Form)step by Step

Question

Examlex · Accepted Answer

The Answer is 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₂_.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.

Work Through the Simplex Method (In Algebraic Form)step by Step

Definitions: