www.getmyuni.com
CHAPTER-6: SIMPLEX & DUAL SIMPLEX METHOD
1. © Simplex method
Introduction
Simplex method = Simplex technique = Simplex algorithm.
It is an iterative procedure for solving a linear programming problem in a
finite no. of steps. This method provides an algorithm which consist in moving
from one vertex of the region of feasible solution to another in such a way that
the value of the objective function at the succeeding vertex is less (or more)
than the preceding vertex so as to reach finally in the optimum solution.
The following important definitions are necessary to understand the
simplex method.
(a) Basic solution
Given a system 'm' simultaneous linear equations in 'n' unknowns (m<n).
Ax = b,
Where A is a m×n matrix of rank m. Let B be any m×m submatrix
formed by m linearly in dependent columns of A. Then a solution obtained by
setting n – m variable not associated with the columns of B equals to zero and
solving the resulting system is called a basic solution to the given system of
equations.
This can be explained with the following example.
Ex: Obtain basic solution to x1+2x2+x3 = 4 ---------------(1)
2x 1+x2+5x3 = 5 ---------------(2)
In this case m = 2 (i.e., Eq. (1) & Eq. (2))
n = 3 (i.e., x1, x2, x3) = m<n
the above system of equation can be written as:
,www.getmyuni.com
1
1 2 1 4
2 =
2 1 5 5
3
A x b
(2×3) ×(3×1) = (2×1)
The different sub matrix from matrix A are:
1 2 1 1 2 1
. , &
2 1 2 5 1 5
The basic solutions are obtained from the following equations:
1 2 1 4
(I) = -------(1) setting x3 = 0
2 1 2 5
2 1 2 4
(II) = -----------(2) setting x1 = 0
1 5 3 5
1 1 1 4
(III) = -------------(3) setting x2 = 0
2 5 2 5
Considering Eq (1)
[x1+2x2 = 4] ×2
2x1+x2 = 5
4x 2-x2 = 8 - 5 = 3
= 3x2 = 3 = x2 = 1
2x 1+1 = 5 = x1 = 2
So basic x1 = 2, x2 = 1 & non basic x3 = 0
Similarly solving other 2 equations :
Basic x2 = 5/3, x3 = 2/3 non basic x1 = 0
Basic x1 = 5, x3 = -1 non basic x2 = 0
, www.getmyuni.com
(b) Degenerate solution
A basic solution to the system is called Degenerate of one or more of the
basic variables vanish.
Ex: Show that the following system of linear equations has a degenerate
solution.
2x1+x2-x3 = 2
3x1+2x2+x3 = 3
Solution
The given system of linear equations can be written as:
1
2 1 −1 2
. 2 =
3 2 1 3
3
A x b
The basic solution can be obtained as:
2 1 1 2
. = -------------(1) by setting x3 = 0
3 2 2 3
1 −1 2 2
. = ------------(2) by setting x1 = 0
2 1 3 3
2 −1 1 2
. = ------------(3) by setting x2 = 0
3 1 3 3
Solving (1) Basic → x1 = 1, x2 = 0; non basic x3 = 0
(2) Basic → x2 = 5/3, x3 = -1/3; non basic x1 = 0
(3) Basic → x1 = 1, x3 = 0; non basic x2 = 0
In each is 2 basic solutions at least one of the basic variables is zero.
Hence two of the basic solutions are degenerate solutions.
CHAPTER-6: SIMPLEX & DUAL SIMPLEX METHOD
1. © Simplex method
Introduction
Simplex method = Simplex technique = Simplex algorithm.
It is an iterative procedure for solving a linear programming problem in a
finite no. of steps. This method provides an algorithm which consist in moving
from one vertex of the region of feasible solution to another in such a way that
the value of the objective function at the succeeding vertex is less (or more)
than the preceding vertex so as to reach finally in the optimum solution.
The following important definitions are necessary to understand the
simplex method.
(a) Basic solution
Given a system 'm' simultaneous linear equations in 'n' unknowns (m<n).
Ax = b,
Where A is a m×n matrix of rank m. Let B be any m×m submatrix
formed by m linearly in dependent columns of A. Then a solution obtained by
setting n – m variable not associated with the columns of B equals to zero and
solving the resulting system is called a basic solution to the given system of
equations.
This can be explained with the following example.
Ex: Obtain basic solution to x1+2x2+x3 = 4 ---------------(1)
2x 1+x2+5x3 = 5 ---------------(2)
In this case m = 2 (i.e., Eq. (1) & Eq. (2))
n = 3 (i.e., x1, x2, x3) = m<n
the above system of equation can be written as:
,www.getmyuni.com
1
1 2 1 4
2 =
2 1 5 5
3
A x b
(2×3) ×(3×1) = (2×1)
The different sub matrix from matrix A are:
1 2 1 1 2 1
. , &
2 1 2 5 1 5
The basic solutions are obtained from the following equations:
1 2 1 4
(I) = -------(1) setting x3 = 0
2 1 2 5
2 1 2 4
(II) = -----------(2) setting x1 = 0
1 5 3 5
1 1 1 4
(III) = -------------(3) setting x2 = 0
2 5 2 5
Considering Eq (1)
[x1+2x2 = 4] ×2
2x1+x2 = 5
4x 2-x2 = 8 - 5 = 3
= 3x2 = 3 = x2 = 1
2x 1+1 = 5 = x1 = 2
So basic x1 = 2, x2 = 1 & non basic x3 = 0
Similarly solving other 2 equations :
Basic x2 = 5/3, x3 = 2/3 non basic x1 = 0
Basic x1 = 5, x3 = -1 non basic x2 = 0
, www.getmyuni.com
(b) Degenerate solution
A basic solution to the system is called Degenerate of one or more of the
basic variables vanish.
Ex: Show that the following system of linear equations has a degenerate
solution.
2x1+x2-x3 = 2
3x1+2x2+x3 = 3
Solution
The given system of linear equations can be written as:
1
2 1 −1 2
. 2 =
3 2 1 3
3
A x b
The basic solution can be obtained as:
2 1 1 2
. = -------------(1) by setting x3 = 0
3 2 2 3
1 −1 2 2
. = ------------(2) by setting x1 = 0
2 1 3 3
2 −1 1 2
. = ------------(3) by setting x2 = 0
3 1 3 3
Solving (1) Basic → x1 = 1, x2 = 0; non basic x3 = 0
(2) Basic → x2 = 5/3, x3 = -1/3; non basic x1 = 0
(3) Basic → x1 = 1, x3 = 0; non basic x2 = 0
In each is 2 basic solutions at least one of the basic variables is zero.
Hence two of the basic solutions are degenerate solutions.
