Simplex Method

2. Simplex Method
When decision variables are more than 2, we always use
Simplex Method
Slack Variable: Variable added to a £ constraint to
convert it to an equation (=).
A slack variable represents unused resources
A slack variable contributes nothing to the objective
function value.
Surplus Variable: Variable subtracted from a ³
constraint to convert it to an equation (=).
A surplus variable represents an excess above a
constraint requirement level.
Surplus variables contribute nothing to the calculated
value of the objective function.

3. Cont….
Basic Solution(BS) : This solution is obtained by setting
any n variables (among m+n variables) equal to zero and
solving for remaining m variables, provided the
determinant of the coefficients of these variables is non-
zero. Such m variables are called basic variables and
remaining n zero valued variables are called non basic
variables.
Basic Feasible Solution(BFS) : It is a basic solution
which also satisfies the non negativity restrictions.

4. Cont…..
BFS are of two types:
Degenerate BFS: If one or more basic
variables are zero.
Non-Degenerate BFS: All basic variables are
non-zero.
Optimal BFS: BFS which optimizes the
objective function.

5. Example
Max. Z = 13x
1
+11x
2
Subject to constraints:
4x
1
+5x
2 << 1500 1500
5x5x
11+3x+3x
2 2 << 1575 1575
xx
11+2x+2x
2 2 << 420 420
xx
11, x, x
2 2
> 0

6. Solution :
Step 1: Convert all the inequality constraints into equalities
by the use of slack variables.
Let S
1
, S
2
, S
3
be three slack variables.
Introducing these slack variables into the inequality constraints
and rewriting the objective function such that all variables are
on the left-hand side of the equation. Model can rewritten as:
Z - 13x
1
-11x
2
= 0
Subject to constraints:
4x
1
+5x
2
+ S
1
= 1500 1500
5x5x
11+3x+3x
2 2 +S+S
22= 1575= 1575
xx
11+2x+2x
2 2 +S+S
33 = 420 = 420
xx
11, x, x
22, S, S
11, S, S
22, S, S
3 3 > 0

7. Cont…
Step II: Find the Initial BFS.
One Feasible solution that satisfies all the
constraints is: x
1
= 0, x
2
= 0, S
1
= 1500,
S
2
= 1575, S
3
= 420 and Z=0.
Now, S
1
, S
2
, S
3
are Basic variables.
Step III: Set up an initial table as:

8. Cont…
D1
C1
B1
A1
Row
NO.
0000-11-131Z
420
315
375
Rati
o
420100210S
3
1575010350S
2
1500001540S
1
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
Step IV: a) Choose the most negative number from row A1(i.e Z row). Therefore,
x
1
is a entering variable.
b) Calculate Ratio = Sol col. / x
1
col. (x
1 > 0)
c) Choose minimum Ratio. That variable(i.e S
2
) is a departing
variable.

9. Cont….
Step V: x
1
becomes basic variable and S
2
becomes non basic
variable. New table is:
75
525
92.3
Ratio
1051-1/507/500S
3
D1
31501/503/510x
1
C1
2400-4/5113/500S
1
B1
4095013/50-16/501ZA1
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Varia
ble
Row
NO.

10. Cont…
Next Table is :
755/7-1/70100x
2
D1
270-3/72/70010x
1
C1
45-13/7-3/71000S
1
B1
433516/715/70001ZA1
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Varia
ble
Row
NO.
Optimal Solution is : x
1
= 270, x
2
= 75, Z= 4335

11. Example
Max. Z = 3x
1
+5x
2
+4x
3
Subject to constraints:
2x
1
+3x
2 << 8 8
2x2x
22+5x+5x
3 3 << 10 10
3x3x
11+2x+2x
22+4x+4x
3 3 << 15 15
xx
11, x, x
22, x, x
3 3
> 0

12. Cont…
Let S
1
, S
2
, S
3
be the three slack variables.
Modified form is:
Z - 3x
1
-5x
2
-4x
3
=0
2x
1
+3x
2
+S
1
= 8 8
2x2x
22+5x+5x
3 3 +S+S
22= 10= 10
3x3x
11+2x+2x
22+4x+4x
33+S+S
33= 15= 15
xx
11, x, x
22, x, x
33,,

S
1
,
SS
22,,
SS
3 3
> 0

Initial BFS is : x
1
= 0, x
2
= 0, x
3
=0, S
1
= 8,
S
2
= 10, S
3
= 15 and Z=0.

13. Cont…
4
5
0
-4
x
3
15/2
5
8/3
Ratio
15100230S
3
10010200S
2
8001320S
1
0000-5-31Z
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
Therefore, x
2
is the entering variable and S
1
is the
departing variable.

14. Cont…
4
5
0
-4
x
3
29/12
14/15
-
Ratio
29/310-2/305/30S
3
14/301-2/30-4/30S
2
8/3001/312/30x
2
40/3005/301/31Z
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
Therefore, x
3
is the entering variable and S
2
is the
departing variable.

15. Cont…
0
1
0
0
x
3
89/41
-
4
Ratio
89/151-4/52/15041/150S
3
14/1501/5-2/150-4/150x
3
8/3001/312/30x
2
256/1504/517/150-11/151Z
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
Therefore, x
1
is the entering variable and S
3
is the
departing variable.

16. Cont…
0
1
0
0
x
3
89/4115/41-12/41-2/41010x
1
62/414/415/41-6/41000x
3
50/41-10/418/4115/41100x
2
765/4111/4124/4145/41001Z
Sol.
S
3
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
Optimal Solution is : x
1
= 89/41, x
2
= 50/41, x
3
=62/41, Z= 765/41

17. Example
Min.. Z = x
1
- 3x
2
+ 2x
3
Subject to constraints:
3x
1
- x
2
+ 3x
3
<< 7
-2x-2x
1 1 + 4x+ 4x
2 2 << 12 12
-4x-4x
11 + 3x + 3x
22 + 8x + 8x
33 < < 1010
xx
11, x, x
22, x, x
3 3
> 0

18. Cont…
Convert the problem into maximization problem
Max.. Z’ = -x
1
+ 3x
2
- 2x
3
where Z’= -Z
Subject to constraints:
3x
1
- x
2
+ 3x
3
<< 7
-2x-2x
1 1 + 4x+ 4x
2 2 << 12 12
-4x-4x
11 + 3x + 3x
22 + 8x + 8x
33 < < 1010
xx
11, x, x
22, x, x
3 3
> 0

19. Cont…
Let S
1
, S
2
and S
3
be three slack variables.
Modified form is:
Z’ + x
1 - 3x
2 + 2x
3 = 0
3x
1
- x
2
+ 3x
3
+S
1
= 7
-2x-2x
1 1 + 4x+ 4x
2 2 + S + S
22 = 12 = 12
-4x-4x
11 + 3x + 3x
22 + 8x + 8x
33 +S +S
33 = = 1010
xx
11, x, x
22, x, x
3 3
> 0
Initial BFS is : x
1
= 0, x
2
= 0, x
3
=0, S
1
= 7, S
2
= 12, S
3
= 10
and Z=0.

20. Cont…
10/31010083-40S
3
0
0
0
S
3
0
3
2
x
3
3
-
Ratio
12104-20S
2
701-130S
1
000-311Z’
Sol.
S
2
S
1
x
2
x
1
Z’
Coefficients of: Basic
Variable
Therefore, x
2
is the entering variable and S
2
is the
departing variable.

21. Cont…
-11-3/4080-5/20S
3
0
0
0
S
3
0
3
2
x
3
-
4
Ratio
31/401-1/20x
2
101/4105/20S
1
93/400-1/21Z’
Sol.
S
2
S
1
x
2
x
1
Z’
Coefficients of: Basic
Variable
Therefore, x
1
is the entering variable and S
1
is the
departing variable.

22. Cont…
111-1/2111000S
3
0
0
0
S
3
3/5
6/5
13/5
x
3
53/101/5100x
2
41/102/5010x
1
118/101/5001Z’
Sol.
S
2
S
1
x
2
x
1
Z’
Coefficients of: Basic
Variable
Optimal Solution is : x
1
= 4, x
2
= 5, x
3
= 0,
Z’ = 11 Z = -11

23. Example
Max.. Z = 3x
1
+ 4x
2
Subject to constraints:
x
1
- x
2
<< 1
-x-x
1 1 + x+ x
2 2 << 2 2
xx
11, x, x
2 2
> 0

24. Cont…
Let S
1
and S
2
be two slack variables
.
Modified form is:
Z -3x
1
- 4x
2
= 0
x
1
- x
2
+S
1
= 1
-x-x
1 1 + x+ x
2 2 +S+S
2 2 = 2= 2
xx
11, x, x
22, S, S
11, S, S
2 2
> 0
Initial BFS is : x
1
= 0, x
2
= 0, S
1
= 1, S
2
= 2
and Z=0.

25. Cont…
2
-
Ratio
2101-10S
2
101-110S
1
000-4-31Z
Sol.
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
Therefore, x
2
is the entering variable and S
2
is the
departing variable.

26. Cont…
-
-
Ratio
2101-10x
2
311000S
1
8400-71Z
Sol.
S
2
S
1
x
2
x
1
Z
Coefficients of: Basic
Variable
x
1
is the entering variable, but as in x
1
column every no. is less
than equal to zero, ratio cannot be calculated. Therefore given
problem is having a unbounded solution.

28. Introduction
LPP, in which constraints may also have > and = signs, we
introduce a new type of variable , called the artificial
variable. These variables are fictitious and cannot
have any physical meaning. Two Phase Simplex
Method is used to solve a problem in which some
artificial variables are involved. The solution is
obtained in two phases.

29. Example
Min.. Z = 15/2 x
1
- 3x
2
Subject to constraints:
3x
1
- x
2
- x
3
> 3 3
xx
11 - x - x
22 + x + x
33 > 2
xx
11, x, x
22, x, x
3 3
> 0

30. Cont…
Convert the objective function into the maximization form
Max. Z’ = -15/2 x
1
+ 3x
2
where Z’= -Z
Subject to constraints:
3x
1
- x
2
- x
3
> 3 3
xx
11 - x - x
22 + x + x
33 > 2
xx
11, x, x
22, x, x
3 3
> 0

31. Cont…
Modified form is :
Introduce surplus variables S
1
and S
2
, and artificial variables
a
1 and a
2
Z’ + 15/2 x
1
- 3x
2
= 0

Subject to constraints:
3x
1
- x
2
- x
3
–S
1
+ a
1
= 3 3
xx
11 - x - x
22 + x + x
33 –S –S
22 + a + a
22 = = 2
xx
11, x, x
22, x, x
3 3 , , S
1
, SS
22, , a
1
, aa
22 > 0

32. Cont…
Phase I : Simplex method is applied to a specially constructed
Auxiliary LPP leading to a final simplex table containing a BFS
to the original problem.
•Step 1: Assign a cost –1 to each artificial variable and a cost
0 to all other variables in the objective function.
•Step 2: Construct the auxiliary LPP in which the new
objective function Z
*
is to be maximized subject to the given
set of constraints.

33. Cont…
Max. Z
*
= -a
1
–a
2
Z
*
+ a
1
+ a
2
= 0
Subject to constraints:
3x
1
- x
2
- x
3
–S
1
+ a
1
= 3 3
xx
11 - x - x
22 + x + x
33 –S –S
22 + a + a
22 = = 2
xx
11, x, x
22, x, x
3 3 , , S
1
, SS
22, , a
1
, aa
22 > 0
Auxiliary LPP is:
Initial solution is a
1
= 3, a
2
= 2 and Z
*
= 0

34. Cont…
•Step 3: Solve the auxiliary problem by simplex method until either
of the following three possibilities arise:
•Max Z
*
< 0 and at least one artificial variable appear in the
optimum basis at a positive level. In this case given problem
does not have any feasible solution.
•Max Z
*
= 0 and at least one artificial variable appear in the
optimum basis at a zero level. In this case proceed to Phase II.
•Max Z
*
= 0 and no artificial variable appear in the optimum
basis. In this case also proceed to Phase II.

35. Cont…
1
0
1
a
2
0
1
1
a
1
1
-1
0
x
3
2-10-110a
2
30-1-130a
1
000001Z
*
Sol.
S
2
S
1
x
2
x
1
Z
*
Coefficients of: Basic
Variable
This table is not feasible as a
1
and a
2
has non zero coefficients in
Z
*
row. Therefore next step is to make the table feasible.

36. Cont…
2
1
Ratio
1
0
0
a
2
0
1
0
a
1
1
-1
0
x
3
2-10-110a
2
30-1-130a
1
-5112-41Z
*
Sol.
S
2
S
1
x
2
x
1
Z
*
Coefficients of: Basic
Variable
Therefore, x
1
is the entering variable and a
1
is the
departing variable.

37. Cont…
3/4
-
Ratio
1
0
0
a
2
4/3
-1/3
-4/3
x
3
1-11/3-2/300a
2
10-1/3-1/310x
1
-11-1/32/301Z
*
Sol.
S
2
S
1
x
2
x
1
Z
*
Coefficients of: Basic
Variable
Therefore, x
3
is the entering variable and a
2
is the
departing variable.

38. Cont…
1
0
0
x
3
3/4-3/41/4-1/200x
3
5/4-1/4-1/4-1/210x
1
000001Z
*
Sol.
S
2
S
1
x
2
x
1
Z
*
Coefficients of: Basic
Variable
As there is no variable to be entered in the basis, this table is
optimum for Phase I. In this table Max. Z
*
= 0 and no artificial
variable appears in the optimum basis, therefore we can proceed
to Phase II.

39. Cont…
Phase II: The artificial variables which are non basic at the end of
Phase I are removed from the table and as well as from the
objective function and constraints. Now assign the actual costs to
the variables in the Objective function. That is, Simplex method is
applied to the modified simplex table obtained at the Phase I.
1
0
0
x
3
3/4-3/41/4-1/200x
3
5/4-1/4-1/4-1/210x
1
000-315/21Z’
Sol.
S
2
S
1
x
2
x
1
Z’
Coefficients of: Basic
Variable
Again this table is not feasible as basic variable x
1
has a non zero
coefficient in Z’ row. So make the table feasible.

40. Cont…
1
0
0
x
3
3/4-3/41/4-1/200x
3
5/4-1/4-1/4-1/210x
1
-75/815/815/83/401Z’
Sol.
S
2
S
1
x
2
x
1
Z’
Coefficients of: Basic
Variable
Optimal Solution is : x
1
= 5/4, x
2
= 0, x
3
= 3/4,
Z’ = -75/8 Z = 75/8

41. Example
Min.. Z = x
1
- 2x
2
–3x
3
Subject to constraints:
-2x
1
+ x
2
+ 3x
3
= 2 2
2x2x
11 + 3x + 3x
22 + 4x + 4x
33 = = 1
xx
11, x, x
22, x, x
3 3
> 0

42. Cont…
Phase I:
Introducing artificial variables a
1
and a
2
Auxiliary LPP is: Max. Z* = -a
1
- a
2

Z* + a
1
+ a
2
= 0
Subject to constraints:
-2x
1
+ x
2
+ 3x
3
+ a
1
= 2 2
2x2x
11 + 3x + 3x
22 + 4x + 4x
33 + a + a
2 2 == 1
xx
11, x, x
22, x, x
3 3
> 0

43. Cont…
1
0
1
a
2
0
1
1
a
1
4
3
0
x
3
1320a
2
21-20a
1
0001Z
*
Sol.
x
2
x
1
Z
*
Coefficients of: Basic
Variable
This table is not feasible as a
1
and a
2
has non zero coefficients in
Z
*
row. Therefore next step is to make the table feasible.

44. Cont…
1/4
2/3
Ratio
1
0
0
a
2
0
1
0
a
1
4
3
-7
x
3
1320a
2
21-20a
1
-3-401Z
*
Sol.
x
2
x
1
Z
*
Coefficients of: Basic
Variable
Therefore, x
3
is the entering variable and a
2
is the
departing variable.

45. Cont…
0
1
0
a
1
1
0
0
x
3
1/43/41/20x
3
5/4-5/4-7/20a
1
-5/45/47/41Z
*
Sol.
x
2
x
1
Z
*
Coefficients of: Basic
Variable
As there is no variable to be entered in the basis, therefore
Phase I ends here. But one artificial variable is present in the
basis and Z
*
< 0. Therefore we cannot proceed to Phase II.
Given problem is having a non-feasible solution.

46. Example
Min.. Z = 4x
1
+ x
2
Subject to constraints:
3x
1
+ x
2
= 3 3
4x4x
11 + 3x + 3x
22 > 6
x
1
+2x
2
< < 44
xx
11, x, x
22 > 0

47. Cont…
Phase I:
Introducing artificial variable a
1
and a
2
, surplus variable S
1
and
slack variable S
2
Auxiliary LPP is:
Max. Z* = -a
1
- a
2

Z* + a
1
+ a
2
= 0
Subject to constraints:
3x
1
+ x
2
+a
1
= 3 3
4x4x
11 + 3x + 3x
22 –S –S
11 + a + a
22 = 6
x
1
+2x
2
+S
2
= 44
xx
11, x, x
22 > 0

48. Cont…
40010210S
2
0
0
0
S
2
1
0
1
a
2
0
1
1
a
1
-1
0
0
S
1
6340a
2
3130a
1
0001Z
*
Sol.
x
2
x
1
Z
*
Coefficients of: Basic
Variable
This table is not feasible as a
1
and a
2
has non zero coefficients in
Z
*
row. Therefore next step is to make the table feasible.

49. Cont…
4
3/2
1
Ratio
40010210S
2
0
0
0
S
2
1
0
0
a
2
0
1
0
a
1
-1
0
1
S
1
6340a
2
3130a
1
-9-4-71Z
*
Sol.
x
2
x
1
Z
*
Coefficients of: Basic
Variable
Therefore, x
1
is the entering variable and a
1
is the
departing variable.

50. Cont…
9/5
6/5
3
Ratio
30105/300S
2
0
0
0
S
2
1
0
0
a
2
-1
0
1
S
1
25/300a
2
11/310x
1
-2-5/301Z
*
Sol.
x
2
x
1
Z
*
Coefficients of: Basic
Variable
Therefore, x
2
is the entering variable and a
2
is the
departing variable.

51. Cont…
111000S
2
0
0
0
S
2
-3/5
1/5
0
S
1
6/5100x
2
3/5010x
1
0001Z
*
Sol.
x
2
x
1
Z
*
Coefficients of: Basic
Variable
As there is no variable to be entered in the basis, this table is
optimum for Phase I. In this table Max. Z
*
= 0 and no artificial
variable appears in the optimum basis, therefore we can proceed
to Phase II.

52. Cont…
Phase II:
Original Objective function is:
Min.. Z = 4x
1
+ x
2
Convert the objective function into the maximization form
Max. Z’ = -4 x
1
- x
2
where Z’= -Z
111000S
2
0
0
0
S
2
-3/5
1/5
0
S
1
6/5100x
2
3/5010x
1
0141Z
*
Sol.
x
2
x
1
Z
*
Coefficients of: Basic
Variable
Again this table is not feasible as basic variable x
1
and x
2
has a non zero
coefficient in Z’ row. So make the table feasible.

53. Cont…
1
-
3
Ratio
111000S
2
0
0
0
S
2
-3/5
1/5
-1/5
S
1
6/5100x
2
3/5010x
1
-18/5001Z
’
Sol.
x
2
x
1
Z
’
Coefficients of: Basic
Variable
Therefore, S
1
is the entering variable and S
2
is the
departing variable.

54. Cont…
111000S
2
3/5
-1/5
1/5
S
2
0
0
0
S
1
9/5100x
2
2/5010x
1
-17/5001Z
’
Sol.
x
2
x
1
Z
’
Coefficients of: Basic
Variable
Optimal Solution is : x
1
= 2/5, x
2
= 9/5,
Z’ = -17/5 Z = 17/5

56. Introduction
At the stage of improving the solution during Simplex
procedure, if a tie for the minimum ratio occurs at least
one basic variable becomes equal to zero in the next
iteration and the new solution is said to be Degenerate.

57. Example
Max.. Z = 3x
1
+ 9x
2
Subject to constraints:
x
1
+ 4x
2 << 8 8
xx
11 + 2x + 2x
22 << 4
xx
11, x, x
22 > 0

58. Cont…
Let S
1
and S
2
be two slack variables.
Modified form is:
Z - 3x
1
- 9x
2
= 0
x
1
+ 4x
2
+ S
1
= 8 8
xx
11 + 2x + 2x
2 2 +S+S
22 = = 4
xx
11, x, x
22, S, S
11, S, S
22 > 0
Initial BFS is : x
1
= 0, x
2
= 0, S
1
= 8, S
2
= 4 and Z=0.

59. Cont…
2
2
Ratio
410210S
2
0
0
S
2
1
0
S
1
8410S
1
0-9-31Z
Sol.
x
2
x
1
Z
Coefficients of: Basic
Variable
In this table S
1
and S
2
tie for the leaving variable. So
any one can be considered as leaving variable.
Therefore, x
2
is the entering variable and S
1
is the
departing variable.

60. Cont…
0
8
Ratio
01-1/201/20S
2
0
0
S
2
1/4
9/4
S
1
211/40x
2
180-3/41Z
Sol.
x
2
x
1
Z
Coefficients of: Basic
Variable
Therefore, x
1
is the entering variable and S
2
is the
departing variable.

61. Cont…
02-1010x
1
-1/2
3/2
S
2
1/2
3/2
S
1
2100x
2
18001Z
Sol.
x
2
x
1
Z
Coefficients of: Basic
Variable
Optimal Solution is : x
1
= 0, x
2
= 2
Z = 18
It results in a Degenerate Basic Solution.