Ch 3: The Simplex Method

Converting LPP to Standard Form

General Form:
Objective function: Max Z = f(x)
Subject to: Axi ≤ B
Standard Form:
Objective Function: Max Z – f(x) = 0

Slack Variable: Surplus Variable: Artificial Variable:

When the conditions are When the conditions are When the equations are
≤ Type, we have to add ≥ Type, we have to add = type, add artificial
slack variable (S) on surplus variable on RHS. variable on LHS
LHS.
So, the subject to the conditions will be as follows
Axi + Si = B
Simplex Algorithm
1. Check whether the objective function is maximization or minimization. If
minimum change it to maximum by following rule:
Min Z = - Max (-Z)
2. Check whether RHS is > 0. If not, multiply the constraints by (-1) and make it
to positive.
3. Convert all inequalities into equalities by adding corresponding variables.
4. Formulate the initial basic feasible solution table.
5. Check for most negative number in Z. Select that variable as entering
variable.

6. Find Ratio = , where P.C.E is entering variable column values.

7. Check for the least positive ratio, Choose that row as leaving row.
8. Now,
Leaving Variable Row
E.V = ----------------------------
Pivot Element
9. For other rows,
New Row = Old row + (- P.C.E) * (E.V)
10. Go to step 5. Repeat the same till all the values in objective function are
positive or Zero.
By: [Link] Page 1 of 5
 Ch 3: The Simplex Method
Example:
1) Max Z = 3x + 2y
Subject to
2x + y ≤ 10
x+y≤8
x, y ≥ 0
Solution:
Standard Form:
Max Z – 3x – 2y = 0
Subject to
2x + y + S1 = 10
x + y + S2 = 8 max (- number)
E.V.
x y S1 S2 RHS Rati
o
Z - - 0 0 0 -- Least
3 2 Positive
Number
S1 2 1 1 0 10 5 (L.V)

S2 1 1 0 1 8 8

Calculations:

E.V x = =

= 1 0 5
New Z = Old Z + -(-3)*x
-3 -2 0 0 0
3 *x = 3 1.5 1.5 0 15
----------------------------------
0 -0.5 1.5 0 15
----------------------------------
New S2 = Old S2 + (-1) * x
1 1 0 1 8
-x -1 -0.5 -0.5 0 -5
----------------------------------
0 0.5 -0.5 1 3
-----------------------------------
By: [Link] Page 2 of 5
 Ch 3: The Simplex Method

Table 2:
E.V
x y S1 S2 RHS Rati
o
Z 0 - 1.5 0 15 --
0.5
x 1 0.5 0.5 0 5 10

S2 0 0.5 -0.5 1 3 6 L.V

Calculations:

E.V y = =

= 0 1 -1 2 6
New Z = Old Z + -(-0.5)*y
0 -0.5 1.5 0 15
0.5*y 0 0.5 -0.5 1 3
-------------------------------------
0 0 1 1 18
-------------------------------------
New x = Old x + -(0.5)*y
1 0.5 0.5 0 5
-0.5y 0 -0.5 0.5 -1 -3
-----------------------------------
1 0 1 -1 2
-----------------------------------
Table 3:
x y S1 S2 RHS Rati
o
Z 0 0 1 1 18 --
x 1 0 1 -1 2

y 0 1 -1 2 6

As all the values in Z are positive and Zero, optimum solution is

obtained.

By: [Link] Page 3 of 5

 Ch 3: The Simplex Method
Max Z = 18
At x = 2; y = 6

Try:
1) Max Z = 3x + 2y 3) Max Z = 8x + 7y
Subject to Subject to
x+y≤6 2x + y ≤ 9
2x + y ≤ 6 2x + 3y ≤ 12
x, y ≥0 x, y ≥0
2) Max Z = 5x1 + 3x2 4) Max Z = 2x1 + 5x2
Subject to Subject to
x1 + x 2 ≤ 2 x1 + 2x2 ≤ 5
5x1 + 2x2 ≤ 10 2x1 + 3x2 ≤ 8
3x1 + 8x2 ≤ 12 x1, x2
x1, x2 ≥ 0
Convert into standard form:
1) Max Z = 4x + 3y
4) Max Z = 11x + 25y
Subject to
Subject to
2x + 3y ≤ 12
4x - 9y ≥ -15
3x + 2y ≥ 15
2x + 5y ≤ 12
2) Max Z = 2x1 + 3x2 + 7x3
x + 3y = 10
Subject to:
x, y ≥ 0
7x1 + 5x2 + x3 ≥ 9
5) Min Z = 3x + 2y
2x1 + 6x2 + 3x3 ≤ 11
Subject to
3) Max Z = 7x1 + 8x2 + 5x3
x + 2y ≤ 8
Subject to
-3x - 5y ≥ -21
2x1 + 3x2 + 4x3 ≥ 12
x, y ≥ 0
4x1 + 2x2 + x3 = 10
x1 + 3x2 + 2x3 ≤ 13
By: [Link] Page 4 of 5
 Ch 3: The Simplex Method

Note: Refer to your prescribed text book for further reading.

By: [Link] Page 5 of 5