Introduction to Simplex Method

It was invented by G. Danztig in 1947. The simplex method gives an algorithm, that is, a rule of procedure generally involving repetitive application of a prescribed operation, which is based on the basic theorem of linear programming.

The Simplex algorithm is an iterative method for resolving LP problems in a finite number of steps. It contains

• Having a trial general feasible solution or answer to constraint-equations

• Checking whether it is an optimal solution
• Enhancing the first trial solution by a series of rules and repeating the process till an optimal solution is attained

Benefits

• Simple to crack the problems
• The solution of LPP of two variables or more can be achieved through this method.

 Computational Procedure of Simplex Method

 Take an example

Maximize Z = 3x₁ + 2x₂

    Subject to

            x₁ + x₂ ≤ 4

            x₁ - x₂ ≤ 2

    &     x₁ ≥ 0, x₂  ≥ 0

Answer

 Step 1 - Note down or write the given GLPP in the form of SLPP

Maximize Z = 3x₁ + 2x₂ + 0s₁ + 0s₂

            Subject to

                        x₁ + x₂+ s₁= 4

                        x₁ - x₂ + s₂= 2

                        x₁ ≥ 0, x₂  ≥ 0, s₁ ≥ 0, s₂ ≥ 0

Step 2 - Then present the constraints in the form of matrix

x₁ + x₂+ s₁= 4

                        x₁ - x₂ + s₂= 2

Step 3 - Now construct the starting simplex table with the use of notations

                                         C_j →     3                2              0               0

Step 4 - Calculation of Z and Δ_j and check the basic feasible solution for optimality by the rules known.

Z= C_B X_B

     = 0 *4 + 0 * 2 = 0

Δ_j = Z_j - C_j

       = C_B X_{j -} C_j

Δ₁ = C_B X₁ - C_j = 0 * 1 + 0 * 1 - 3 = -3

Δ₂ = C_B X₂ - C_j = 0 * 1 + 0 * -1 - 2 = -2

Δ₃ = C_B X₃ - C_j = 0 * 1 + 0 * 0 - 0 = 0

Δ₄ = C_B X₄ - C_j = 0 * 0 + 0 * 1 - 0 = 0

Process to check the basic feasible solution for optimality by the rules known

Rule 1 - If all Δ_j  ≥ 0, then the solution under the test will be optimal. Other optimal solution will exist if any non-basic Δ_j is zero as well.

Rule 2 - If at least one Δ_j is negative, then the solution is not optimal and one can proceed to improve the solution in the further step.

Rule 3 - If corresponding to any negative Δ_j, eacjh and every elements of the column X_j are negative or zero, then the solution under examination will be unbounded.  

In this problem it is seem that Δ₁ and Δ₂ are negative. Therefore proceed to enhance or improve this solution

Step 5 - To enhance the basic feasible solution, the vector entering the basis matrix and the vector to be removed from the basis matrix are to be find out.

• Incoming vector

The incoming vector X_k is always chosen parallel to the most negative value of Δ_j. It is signified through (↑).

• Outgoing vector

The outgoing vector is chosen parallel to the minimum positive value of minimum ratio. It is symbolized through (→).

Step 6 - Now mark the key element or pivot element through '1''.The element at the intersection of incoming vector and outgoing vector is the pivot element.

    Cj →     3                2               0               0

• If the number in the marked position is something other than unity, then divide all the elements of that row with the key element.
• Then subtract correct multiples of this new row from the remaining rows, in order to get zeroes in the remaining position of the column X_k.

Step 7 - Then repeat step 4 through step 6 until an optimal solution is attained.

As all Δ_j ≥ 0, optimal basic feasible solution is achieved

Thus the solution is Max Z = 11, x₁ = 3 and x₂ = 1

Worked Examples

Solve with the help of simplex method

Example 1

Maximize Z = 80x₁ + 55x₂

    Subject to

            4x₁ + 2x₂ ≤ 40

            2x₁ + 4x₂ ≤ 32

    &     x₁ ≥ 0, x₂  ≥ 0

Answer

SLPP

Maximize Z = 80x₁ + 55x₂ + 0s₁ + 0s₂

            Subject to

                        4x₁ + 2x₂+ s₁= 40

                        2x₁ + 4x₂ + s₂= 32

                        x₁ ≥ 0, x₂  ≥ 0, s₁ ≥ 0, s₂ ≥ 0

   C_j →    80               55            0                0

As all Δ_j ≥ 0, optimal basic feasible solution is achieved. Hence the solution is Max Z = 860, x₁ = 8 and x₂ = 4

Email based Simplex Method assignment help – homework help 

Are you not finding solution for simplex method problems? Do you need expert’s guide in solving your operation research assignments or homework for simplex method based questions? We at www.tutorsglobe.com offer simplex method assignment help, simplex method homework help, simplex method problems solutions and linear programming assignment help with step by step answers. Our specialized tutors are expert in solving complex level problems in simplex method.