Page 1
Edurev123
4. Simplex Method of Solution
4.1 Maximize :?????????????????????????????????????????? =?? ?? ?? +?? ?? ?? +?? ?? ??
Subject to :
?? ?? ?? +?? ?? ?? ?=?? ?? ?? ?? +?? ?? ?? +?? ?? ?? ?=????
?? ?? ?? +?? ?? ?? ?=????
?? ?? ?=??
(2009 : 30 Marks)
Solution:
Step 1 : Checking whether objective function is to be maximized and all ?? 's are non-
negative. ? These conditions are satisfied. So, proceed to next step.
Step 2 : Express the above problem in standard form. By introducing the slack variables
?? 1
,?? 2
and ?? 3
, the problem in standard form becomes :
Max. ?? =3?? 1
+5?? 2
+4?? 3
+0?? 1
+0?? 2
+0?? 3
subject to
2?? 1
+3?? 2
+0?? 3
+?? 1
+0?? 2
+0?? 3
=8
3?? 1
+2?? 2
+4?? 3
+0?? 1
+?? 2
+0?? 3
=15
0?? 1
+2?? 2
+5?? 3
+0?? 1
+0?? 2
+?? 3
=10
where ?? 1
,?? 2
,?? 3
,?? 1
,?? 2
,?? 3
=0
Step 3 : Find initial basic feasible solution. The basic (non-degenerate) feasible solution
is
?? 1
=?? 2
=?? 3
=0 (non-basic)
?? 1
=8,?? 2
=15,?? 3
=10 (basic)
? Initial basic feasible solution is given by the table below
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
0 ?? 1
2 (3) 0 1 0 0 8
8
3
Page 2
Edurev123
4. Simplex Method of Solution
4.1 Maximize :?????????????????????????????????????????? =?? ?? ?? +?? ?? ?? +?? ?? ??
Subject to :
?? ?? ?? +?? ?? ?? ?=?? ?? ?? ?? +?? ?? ?? +?? ?? ?? ?=????
?? ?? ?? +?? ?? ?? ?=????
?? ?? ?=??
(2009 : 30 Marks)
Solution:
Step 1 : Checking whether objective function is to be maximized and all ?? 's are non-
negative. ? These conditions are satisfied. So, proceed to next step.
Step 2 : Express the above problem in standard form. By introducing the slack variables
?? 1
,?? 2
and ?? 3
, the problem in standard form becomes :
Max. ?? =3?? 1
+5?? 2
+4?? 3
+0?? 1
+0?? 2
+0?? 3
subject to
2?? 1
+3?? 2
+0?? 3
+?? 1
+0?? 2
+0?? 3
=8
3?? 1
+2?? 2
+4?? 3
+0?? 1
+?? 2
+0?? 3
=15
0?? 1
+2?? 2
+5?? 3
+0?? 1
+0?? 2
+?? 3
=10
where ?? 1
,?? 2
,?? 3
,?? 1
,?? 2
,?? 3
=0
Step 3 : Find initial basic feasible solution. The basic (non-degenerate) feasible solution
is
?? 1
=?? 2
=?? 3
=0 (non-basic)
?? 1
=8,?? 2
=15,?? 3
=10 (basic)
? Initial basic feasible solution is given by the table below
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
0 ?? 1
2 (3) 0 1 0 0 8
8
3
0 ?? 2
3 2 4 0 1 0 15
15
2
0 ?? 3
0 2 5 0 0 1 10
10
2
?? =S(?? ?? ????
) 0 0 0 0 0 0
?? ?? =?? ?? -?? ?? 3 5 4 0 0 0
?
As ?? 1
are positive under the columns. But we choose the largest positive, i.e., ' 5 ' under
column of ' ?? 2
'. Now ?? =
8
3
is smallest. So, ?? 2
is the incoming variable and ?? 1
is the
outgoing variable and (3) is the key element. Again producing :
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
5 ?? 2
2
3
1 0
1
3
0 0
8
3
8
3(0)
=8
0 ?? 2
5
3
0 4 -
2
3
1 0
29
3
29
3×4
=
29
12
0 ?? 3
-
4
3
0 (5) -
2
3
0 1
14
3
14
3×5
=
14
15
?? =S(?? ?? ????
)
10
3
5 0
5
3
0 0
?? ?? =?? ?? -?? ?? -
1
3
0 4 -
5
3
0 0
?
Again largest positive ?? ?? =4 under column of ' ?? 3
' and now ?? =
14
15
is smallest. So, ?? 3
is
the incoming variable and ?? 3
is the outgoing variable and (5) is the key element. Again
proceeding:
?? ?? 3 5 4 0 0 0
Page 3
Edurev123
4. Simplex Method of Solution
4.1 Maximize :?????????????????????????????????????????? =?? ?? ?? +?? ?? ?? +?? ?? ??
Subject to :
?? ?? ?? +?? ?? ?? ?=?? ?? ?? ?? +?? ?? ?? +?? ?? ?? ?=????
?? ?? ?? +?? ?? ?? ?=????
?? ?? ?=??
(2009 : 30 Marks)
Solution:
Step 1 : Checking whether objective function is to be maximized and all ?? 's are non-
negative. ? These conditions are satisfied. So, proceed to next step.
Step 2 : Express the above problem in standard form. By introducing the slack variables
?? 1
,?? 2
and ?? 3
, the problem in standard form becomes :
Max. ?? =3?? 1
+5?? 2
+4?? 3
+0?? 1
+0?? 2
+0?? 3
subject to
2?? 1
+3?? 2
+0?? 3
+?? 1
+0?? 2
+0?? 3
=8
3?? 1
+2?? 2
+4?? 3
+0?? 1
+?? 2
+0?? 3
=15
0?? 1
+2?? 2
+5?? 3
+0?? 1
+0?? 2
+?? 3
=10
where ?? 1
,?? 2
,?? 3
,?? 1
,?? 2
,?? 3
=0
Step 3 : Find initial basic feasible solution. The basic (non-degenerate) feasible solution
is
?? 1
=?? 2
=?? 3
=0 (non-basic)
?? 1
=8,?? 2
=15,?? 3
=10 (basic)
? Initial basic feasible solution is given by the table below
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
0 ?? 1
2 (3) 0 1 0 0 8
8
3
0 ?? 2
3 2 4 0 1 0 15
15
2
0 ?? 3
0 2 5 0 0 1 10
10
2
?? =S(?? ?? ????
) 0 0 0 0 0 0
?? ?? =?? ?? -?? ?? 3 5 4 0 0 0
?
As ?? 1
are positive under the columns. But we choose the largest positive, i.e., ' 5 ' under
column of ' ?? 2
'. Now ?? =
8
3
is smallest. So, ?? 2
is the incoming variable and ?? 1
is the
outgoing variable and (3) is the key element. Again producing :
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
5 ?? 2
2
3
1 0
1
3
0 0
8
3
8
3(0)
=8
0 ?? 2
5
3
0 4 -
2
3
1 0
29
3
29
3×4
=
29
12
0 ?? 3
-
4
3
0 (5) -
2
3
0 1
14
3
14
3×5
=
14
15
?? =S(?? ?? ????
)
10
3
5 0
5
3
0 0
?? ?? =?? ?? -?? ?? -
1
3
0 4 -
5
3
0 0
?
Again largest positive ?? ?? =4 under column of ' ?? 3
' and now ?? =
14
15
is smallest. So, ?? 3
is
the incoming variable and ?? 3
is the outgoing variable and (5) is the key element. Again
proceeding:
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
5 ?? 2
2
3
1 0
1
3
0 0
8
3
8×3
3×2
=4
0 ?? 2
(
41
15
) 0 0 -
2
15
1 -
4
15
89
15
89×15
15×41
=
89
41
4 ?? 3
-
4
15
0 1 -
2
15
0
1
5
14
15
14×15
15×(-4)
?? =S?? ?? ?? ????
34
15
5 4
17
15
0
4
5
?? ?? =?? ?? -?? ??
11
15
0 0 -
17
15
0 -
4
5
?
Again
11
15
is the only positive ?? ?? under column of ' ?? 1
' and now ?? =
89
41
is the smallest
positive fraction. So,
?? 1
is the incoming variable and ?? 2
is the outgoing variabie and (
41
15
) is the key element.
Again proceeding :
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
5 ?? 2
0 1 0
15
41
-
10
41
8
41
50
41
3 ?? 1
1 0 0 -
2
41
15
41
-
12
41
89
41
4 ?? 3
0 0 1 -
6
41
4
41
5
41
62
41
?? =S?? ?? ?? ????
3 5 1
45
41
11
41
24
41
?? ?? =?? ?? -?? ?? 0 0 0
-
45
41
-
11
41
-
24
41
Page 4
Edurev123
4. Simplex Method of Solution
4.1 Maximize :?????????????????????????????????????????? =?? ?? ?? +?? ?? ?? +?? ?? ??
Subject to :
?? ?? ?? +?? ?? ?? ?=?? ?? ?? ?? +?? ?? ?? +?? ?? ?? ?=????
?? ?? ?? +?? ?? ?? ?=????
?? ?? ?=??
(2009 : 30 Marks)
Solution:
Step 1 : Checking whether objective function is to be maximized and all ?? 's are non-
negative. ? These conditions are satisfied. So, proceed to next step.
Step 2 : Express the above problem in standard form. By introducing the slack variables
?? 1
,?? 2
and ?? 3
, the problem in standard form becomes :
Max. ?? =3?? 1
+5?? 2
+4?? 3
+0?? 1
+0?? 2
+0?? 3
subject to
2?? 1
+3?? 2
+0?? 3
+?? 1
+0?? 2
+0?? 3
=8
3?? 1
+2?? 2
+4?? 3
+0?? 1
+?? 2
+0?? 3
=15
0?? 1
+2?? 2
+5?? 3
+0?? 1
+0?? 2
+?? 3
=10
where ?? 1
,?? 2
,?? 3
,?? 1
,?? 2
,?? 3
=0
Step 3 : Find initial basic feasible solution. The basic (non-degenerate) feasible solution
is
?? 1
=?? 2
=?? 3
=0 (non-basic)
?? 1
=8,?? 2
=15,?? 3
=10 (basic)
? Initial basic feasible solution is given by the table below
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
0 ?? 1
2 (3) 0 1 0 0 8
8
3
0 ?? 2
3 2 4 0 1 0 15
15
2
0 ?? 3
0 2 5 0 0 1 10
10
2
?? =S(?? ?? ????
) 0 0 0 0 0 0
?? ?? =?? ?? -?? ?? 3 5 4 0 0 0
?
As ?? 1
are positive under the columns. But we choose the largest positive, i.e., ' 5 ' under
column of ' ?? 2
'. Now ?? =
8
3
is smallest. So, ?? 2
is the incoming variable and ?? 1
is the
outgoing variable and (3) is the key element. Again producing :
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
5 ?? 2
2
3
1 0
1
3
0 0
8
3
8
3(0)
=8
0 ?? 2
5
3
0 4 -
2
3
1 0
29
3
29
3×4
=
29
12
0 ?? 3
-
4
3
0 (5) -
2
3
0 1
14
3
14
3×5
=
14
15
?? =S(?? ?? ????
)
10
3
5 0
5
3
0 0
?? ?? =?? ?? -?? ?? -
1
3
0 4 -
5
3
0 0
?
Again largest positive ?? ?? =4 under column of ' ?? 3
' and now ?? =
14
15
is smallest. So, ?? 3
is
the incoming variable and ?? 3
is the outgoing variable and (5) is the key element. Again
proceeding:
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
5 ?? 2
2
3
1 0
1
3
0 0
8
3
8×3
3×2
=4
0 ?? 2
(
41
15
) 0 0 -
2
15
1 -
4
15
89
15
89×15
15×41
=
89
41
4 ?? 3
-
4
15
0 1 -
2
15
0
1
5
14
15
14×15
15×(-4)
?? =S?? ?? ?? ????
34
15
5 4
17
15
0
4
5
?? ?? =?? ?? -?? ??
11
15
0 0 -
17
15
0 -
4
5
?
Again
11
15
is the only positive ?? ?? under column of ' ?? 1
' and now ?? =
89
41
is the smallest
positive fraction. So,
?? 1
is the incoming variable and ?? 2
is the outgoing variabie and (
41
15
) is the key element.
Again proceeding :
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
5 ?? 2
0 1 0
15
41
-
10
41
8
41
50
41
3 ?? 1
1 0 0 -
2
41
15
41
-
12
41
89
41
4 ?? 3
0 0 1 -
6
41
4
41
5
41
62
41
?? =S?? ?? ?? ????
3 5 1
45
41
11
41
24
41
?? ?? =?? ?? -?? ?? 0 0 0
-
45
41
-
11
41
-
24
41
As all ?? ?? are negative. So, the optimal solution is achieved.
Optimal solution is :
?? 1
=
89
41
?? 2
=
50
41
?? 3
=
62
41
and
Max. ?? ?=3×
89
41
+5×
50
41
+4×
62
41
?=
765
41
Max. ?? ?=
765
41
4.2 Solve by Simplex method, the following LP Problem:
Maximize????????????????????????????????????????????????????? =?? ?? ?? +?? ?? ??
Constraints.
?? ?? ?? +?? ?? ?? ?=????
?? ?? ?? +?? ?? ?? ?=????
?? ?? ,?? ?? ?=??
(2011 : 12 Marks)
Solution:
The give, : LPP is
Maximize????????????????????????????????????????????????????? =5?? 1
+3?? 2
Constraints.
3?? 1
+5?? 2
?=15
5?? 1
+2?? 2
?=10
?? 1
,?? 2
?=0
Convert the inequalities by the introduction of slack variables ?? 3
and ?? 4
as follows
3?? 1
+5?? 2
+?? 3
=15
5?? 1
+2?? 2
+?? 4
=10
Page 5
Edurev123
4. Simplex Method of Solution
4.1 Maximize :?????????????????????????????????????????? =?? ?? ?? +?? ?? ?? +?? ?? ??
Subject to :
?? ?? ?? +?? ?? ?? ?=?? ?? ?? ?? +?? ?? ?? +?? ?? ?? ?=????
?? ?? ?? +?? ?? ?? ?=????
?? ?? ?=??
(2009 : 30 Marks)
Solution:
Step 1 : Checking whether objective function is to be maximized and all ?? 's are non-
negative. ? These conditions are satisfied. So, proceed to next step.
Step 2 : Express the above problem in standard form. By introducing the slack variables
?? 1
,?? 2
and ?? 3
, the problem in standard form becomes :
Max. ?? =3?? 1
+5?? 2
+4?? 3
+0?? 1
+0?? 2
+0?? 3
subject to
2?? 1
+3?? 2
+0?? 3
+?? 1
+0?? 2
+0?? 3
=8
3?? 1
+2?? 2
+4?? 3
+0?? 1
+?? 2
+0?? 3
=15
0?? 1
+2?? 2
+5?? 3
+0?? 1
+0?? 2
+?? 3
=10
where ?? 1
,?? 2
,?? 3
,?? 1
,?? 2
,?? 3
=0
Step 3 : Find initial basic feasible solution. The basic (non-degenerate) feasible solution
is
?? 1
=?? 2
=?? 3
=0 (non-basic)
?? 1
=8,?? 2
=15,?? 3
=10 (basic)
? Initial basic feasible solution is given by the table below
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
0 ?? 1
2 (3) 0 1 0 0 8
8
3
0 ?? 2
3 2 4 0 1 0 15
15
2
0 ?? 3
0 2 5 0 0 1 10
10
2
?? =S(?? ?? ????
) 0 0 0 0 0 0
?? ?? =?? ?? -?? ?? 3 5 4 0 0 0
?
As ?? 1
are positive under the columns. But we choose the largest positive, i.e., ' 5 ' under
column of ' ?? 2
'. Now ?? =
8
3
is smallest. So, ?? 2
is the incoming variable and ?? 1
is the
outgoing variable and (3) is the key element. Again producing :
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
5 ?? 2
2
3
1 0
1
3
0 0
8
3
8
3(0)
=8
0 ?? 2
5
3
0 4 -
2
3
1 0
29
3
29
3×4
=
29
12
0 ?? 3
-
4
3
0 (5) -
2
3
0 1
14
3
14
3×5
=
14
15
?? =S(?? ?? ????
)
10
3
5 0
5
3
0 0
?? ?? =?? ?? -?? ?? -
1
3
0 4 -
5
3
0 0
?
Again largest positive ?? ?? =4 under column of ' ?? 3
' and now ?? =
14
15
is smallest. So, ?? 3
is
the incoming variable and ?? 3
is the outgoing variable and (5) is the key element. Again
proceeding:
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
5 ?? 2
2
3
1 0
1
3
0 0
8
3
8×3
3×2
=4
0 ?? 2
(
41
15
) 0 0 -
2
15
1 -
4
15
89
15
89×15
15×41
=
89
41
4 ?? 3
-
4
15
0 1 -
2
15
0
1
5
14
15
14×15
15×(-4)
?? =S?? ?? ?? ????
34
15
5 4
17
15
0
4
5
?? ?? =?? ?? -?? ??
11
15
0 0 -
17
15
0 -
4
5
?
Again
11
15
is the only positive ?? ?? under column of ' ?? 1
' and now ?? =
89
41
is the smallest
positive fraction. So,
?? 1
is the incoming variable and ?? 2
is the outgoing variabie and (
41
15
) is the key element.
Again proceeding :
?? ?? 3 5 4 0 0 0
?? ?? Basis ?? 1
?? 2
?? 3
?? 1
?? 2
?? 3
?? ??
5 ?? 2
0 1 0
15
41
-
10
41
8
41
50
41
3 ?? 1
1 0 0 -
2
41
15
41
-
12
41
89
41
4 ?? 3
0 0 1 -
6
41
4
41
5
41
62
41
?? =S?? ?? ?? ????
3 5 1
45
41
11
41
24
41
?? ?? =?? ?? -?? ?? 0 0 0
-
45
41
-
11
41
-
24
41
As all ?? ?? are negative. So, the optimal solution is achieved.
Optimal solution is :
?? 1
=
89
41
?? 2
=
50
41
?? 3
=
62
41
and
Max. ?? ?=3×
89
41
+5×
50
41
+4×
62
41
?=
765
41
Max. ?? ?=
765
41
4.2 Solve by Simplex method, the following LP Problem:
Maximize????????????????????????????????????????????????????? =?? ?? ?? +?? ?? ??
Constraints.
?? ?? ?? +?? ?? ?? ?=????
?? ?? ?? +?? ?? ?? ?=????
?? ?? ,?? ?? ?=??
(2011 : 12 Marks)
Solution:
The give, : LPP is
Maximize????????????????????????????????????????????????????? =5?? 1
+3?? 2
Constraints.
3?? 1
+5?? 2
?=15
5?? 1
+2?? 2
?=10
?? 1
,?? 2
?=0
Convert the inequalities by the introduction of slack variables ?? 3
and ?? 4
as follows
3?? 1
+5?? 2
+?? 3
=15
5?? 1
+2?? 2
+?? 4
=10
Taking ?? 1
=0,?? 2
=0, we get, ?? 3
=15,?? 4
=10 which is the starting basic feasible
solution. Construct the starting simplex table as follows :
?? ?? 5 3 0 0
Minimum
Ratio
?? ?? ?? 1
?? ?? ?? ?? ?? ?? 1
?? 2
?? 3
?? 4
1/3 0 15 3 5 1 0
15
3
=5
1/4 0 10 5 2 0 1
10
5
=2(Min)
?
??
?
Incoming Vector
?
?? ?=?? ?? -?? ?? ?? ?? ?
?? ?=?? 1
-?? ?? ?? 1
?=5-[(0,0)(3,5)]=5-(0×3+0×5)
?=5-0=5
?
2
?=?? 2
-?? ?? ?? 2
?=3-[(0,0)(5,2)]=3
The values of ?
3
and ?
4
must be zero as they correspond to unit column vectors.
Since all ?
?? are not less than or equal to zero, therefore the solution is not optimal.
Since ?
1
=5 is maximum, ??? 1
is the incoming vector.
Since,
?? ?? 1/1
ratio is minimum against ?? 4
in the table, therefore ?? 4
is the outgoing vector.
The element at the intersection of the minimum ratio arrow and incoming vector arrow is
the pivot element.
We mark this element in ?.
Divide the second row containing the key element (=5) by 5 to get unity at this position
and add 'minus 3 times' the second row to first row to zero at all other positions of the
column containing the pivot element.
Read More