#### 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, x≥ 0

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, x≥ 0, s1 ≥ 0, s2 ≥ 0

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

x1 + x2+ s1= 4

x1 - x2 + s2= 2

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 Δ≥ 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, x≥ 0

SLPP

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

Subject to

4x1 + 2x2+ s1= 40

2x1 + 4x2 + s2= 32

x1 ≥ 0, x≥ 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.