Definitions used in Simplex Method for solving Linear Programming Model:
The terminology (important definitions) used in the simplex method for solving the linear programming model (LPP) are as follows:
Basic Solution:
A basic solution to the set of constraints is a solution obtained by setting any ‘n’ variables (among m+n variables) to zero and solving for the remaining ‘m’ variables.
These ‘n’ variables are called the non-basic variables (the variables set to 0) and ‘m’ variables are called the basic variables (the variables which may be all different from zero, that is, the variables obtained by solving the system).
Total number of solutions = m+nCn
Question 1:
Given the system of the linear equations:
x1+ 2x2+ x3 = 4
2x1+ x2+ 5x3 = 5
Obtain all the basic solutions to this system of linear equations.
Solution:
In the matrix form, this system of equations can be written as Ax=b, where,
Since the rank of A is 2, the maximum number of linearly independent columns of A is 2. Thus, we can take any of the following, 2×2 sub-matrices as basis matrix B:
The variables not associated with the column of B are x3, x2 and x1, respectively, in the three different cases.
Case 1: Let us first take,
Set x3 = 0 to obtain a basic solution to the given system of equation, and solve the system as follows:
Thus a basic and non-basic solution to the given system is;
x1 = 2, x2 = 1 (Basic Solution); x3 = 0 (Non-basic solution)
Case 2: Let us now take,
Set x2 = 0 to obtain a basic solution to the given system of equation, and solve the system as follows:
Thus a basic and non-basic solution to the given system is;
x1 = 5, x3 =−1 (Basic Solution); x2 = 0 (Non-basic solution)
Case 3: Let us now take,
Set x1 = 0 to obtain a basic solution to the given system of equation, and solve the system as follows:
Thus a basic and non-basic solution to the given system is;
x2 = 5/3, x3 =2/3 (Basic Solution); x1 = 0 (Non-basic solution)
Note that all three basic solutions obtained above are non-degenerate.
Question 2:
Given a system of the linear equation:
2x1+x2−x3=2
3x1+2x2+x3=3
Obtain all the basic solutions to this system of linear equations.
Solution:
In the matrix form, this system of equations can be written as Ax=b, where,
Since the rank of A is 2, the maximum number of linearly independent columns of A is 2. Thus, we can take any of the following, 2×2 sub-matrices as basis matrix B:
The variables not associated with the column of B are x3, x2 and x1, respectively, in the three different cases.
Case 1: Let us first take
Set x3 = 0 to obtain a basic solution to the given system of equation, and solve the system as follows:
Thus a basic and non-basic solution to the given system is;
x1 = 1, x2 = 0 (Basic Solution); x3 = 0 (Non-basic solution)
Case 2: Let us now take
Set x2 = 0 to obtain a basic solution to the given system of equation, and solve the system as follows:
Thus a basic and non-basic solution to the given system is;
x1 = 1, x3 = 0 (Basic Solution); x2 = 0 (Non-basic solution)
Case 3: Let us now take
Set x1 = 0 to obtain a basic solution to the given system of equation, and solve the system as follows:
Thus a basic and non-basic solution to the given system is;
x2 = 5/3, x3 = −1/3 (Basic Solution); x1 = 0 (Non-basic solution)
Observe that, in each of the two basic solutions, at least one of the basic variables is zero. Hence, two basic solutions are degenerate solutions.
Click here to read more about LPP
Basic Feasible Solution (BFS):
A basic solution is called a basic feasible solution if all basic variables are non-negative (that is, greater than or equal to 0). In other words, a feasible solution to an LPP, which is also a basic solution to the problem, is called a basic feasible solution to the LPP.
BFS (basic feasible solutions) are of two types:
Non-degenerate Basic Feasible solution (Non-degenerate BFS):
It is a BFS (basic feasible solution) in which all ‘m’ basic variables are positive, and the remaining ‘n’ variables will be all zero.
Degenerate Basic Feasible solution (Degenerate BFS):
It is a BFS (basic feasible solution) in which one or more of the ‘m’ basic variables are zero.
Examples:
In Question 1, observe that, the basic solution x1 = 5, x3 =−1, x2 = 0 is not a feasible solution. Only non-degenerate basic feasible solutions are,
- x1 = 2, x2 = 1,
- x2 = 5/3, x3 = 2/3,
In Question 2, observe that, the basic solution x2 = 5/3, x3 = −1/3, x1 = 0 is not a feasible solution. Only degenerate basic feasible solutions are,
- x1 = 1, x2 = 0
- x1 = 1, x3 = 0
Optimal Basic Feasible solution or Optimal BFS:
A BFS (basic feasible solution) is called the optimal BFS (optimal basic feasible solution) if it optimizes the objective function.
(Source – Various books from the college library)
Copyrighted Material © 2019 - 2024 Prinsli.com - All rights reserved
All content on this website is copyrighted. It is prohibited to copy, publish or distribute the content and images of this website through any website, book, newspaper, software, videos, YouTube Channel or any other medium without written permission. You are not authorized to alter, obscure or remove any proprietary information, copyright or logo from this Website in any way. If any of these rules are violated, it will be strongly protested and legal action will be taken.
Be the first to comment