--%>
Assignment Help - homework help

  Simplex Method Assignment Help

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 = 3x1 + 2x2

    Subject to

            x1 + x2 ≤ 4

            x1 - x2 ≤ 2

    &     x1 ≥ 0, x2  ≥ 0

Answer

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

Maximize Z = 3x1 + 2x2 + 0s1 + 0s2

            Subject to

                        x1 + x2+ s1= 4

                        x1 - x2 + s2= 2

                        x1 ≥ 0, x2  ≥ 0, s1 ≥ 0, s2 ≥ 0

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

x1 + x2+ s1= 4

                        x1 - x2 + s2= 2

            251_Simplex Method.png

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

 

                                         Cj →     3                2              0               0

Basic Variables

CB       XB

 X1              X2                S1                   S2

Min ratio

 XB /Xk

  s1

 

 s2

 0         4

 

 0         2

  1                1              1                0

 

  1               -1              0               1

 

 

Z= CB XB

  Δj

 

 

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

Z= CB XB

     = 0 *4 + 0 * 2 = 0

 

Δj = Zj - Cj

       = CB Xj - Cj

Δ1 = CB X1 - Cj = 0 * 1 + 0 * 1 - 3 = -3

Δ2 = CB X2 - Cj = 0 * 1 + 0 * -1 - 2 = -2

Δ3 = CB X3 - Cj = 0 * 1 + 0 * 0 - 0 = 0

Δ4 = CB X4 - Cj = 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 Xj are negative or zero, then the solution under examination will be unbounded.  

 

In this problem it is seem that Δ1 and Δ2 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 Xk 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

Basic Variables

CB       XB

 X1              X2                S1                   S2

(Xk)

Min ratio

 XB /Xk

  s1

 

 s2

 0         4

 

 0         2

  1                1              1                0

 

  1               -1              0               1

4 / 1 = 4

 

2 / 1 = 2 → outgoing

 

 

Z= CB XB = 0

  ↑incoming

Δ1= -3      Δ2= -2        Δ3=0        Δ4=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 Xk.

 

 

Basic Variables

CB       XB

 X1            X2                S1                   S2

                    (Xk)

Min ratio

 XB /Xk

 

 s1

 

 x1

 

 0         2

 

 3         2

(R1=R1 - R2) 

0                2              1                -1

 

1               -1              0                 1

2 / 2 = 1 → outgoing

 

2 / -1 = -2 (neglect in case of negative)

 

 

Z=0*2+3*2= 6

                  ↑incoming

Δ1=0        Δ2= -5       Δ3=0        Δ4=3

 

 

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

 

Basic Variables

CB       XB

 X1          X2                S1                       S2

 

Min ratio

 XB /Xk

 

 x2

 

 x1

 

 2         1

 

 3         3

(R1=R1 / 2)   

 0             1            1/2                -1/2

(R2=R2 + R1) 

 1             0            1/2                 1/2

 

 

Z = 11

Δ1=0      Δ2=0      Δ3=5/2        Δ4=1/2

 

 

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

 

Thus the solution is Max Z = 11, x1 = 3 and x2 = 1

 

Worked Examples

 

Solve with the help of simplex method

 

Example 1

Maximize Z = 80x1 + 55x2

    Subject to

            4x1 + 2x2 ≤ 40

            2x1 + 4x2 ≤ 32

    &     x1 ≥ 0, x2  ≥ 0

 

Answer

SLPP

Maximize Z = 80x1 + 55x2 + 0s1 + 0s2

            Subject to

                        4x1 + 2x2+ s1= 40

                        2x1 + 4x2 + s2= 32

                        x1 ≥ 0, x2  ≥ 0, s1 ≥ 0, s2 ≥ 0

 

 

   Cj →    80               55            0                0

Basic Variables

CB       XB

 X1              X2                S1                   S2

 

Min ratio

 XB /Xk

  s1

 

 s2

 0         40

 

 0         32

  4                2              1                0

 

  2                4              0                1

40 / 4 = 10→ outgoing

 

32 / 2 = 16

 

 

Z= CB XB = 0

  ↑incoming

Δ1= -80      Δ2= -55      Δ3=0        Δ4=0

 

 

  x1                 

 

 

  s2    

 

 

 80       10              

 

 

 0         12 

 

 (R1=R1 / 4)  

  1                1/2          1/4              0

 

(R2=R2- 2R1)

  0                 3           -1/2             1

 

 10/1/2 = 20            

 

 

 12/3 = 4→ outgoing

 

 

 

Z = 800

                    ↑incoming

Δ1=0       Δ2= -15      Δ3=40        Δ4=0

 

 

  x1                 

 

 

  x2    

 

 

 80         8              

 

 

 55         4 

 

(R1=R1- 1/2R2) 

1                0             1/3              -1/6

 

(R2=R2 / 3)

 0                1            -1/6              1/3

 

 

Z = 860

Δ1=0      Δ2=0       Δ3=35/2       Δ4=5

 

As all Δj ≥ 0, optimal basic feasible solution is achieved. Hence the solution is Max Z = 860, x1 = 8 and x2 = 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.