Basic solution and basic feasible solution, these two things can be considered as concepts invented to solve linear programming problems. How to solve linear programming without drawing? The answer is to find it according to the multiple linear equations.
We know that linear programming can be transformed into a standard form (the specific transformation method will not be described in detail), and the standard form written in matrix form is as follows:
X is a column vector, and its number of elements is the number of unknown variables in the topic. If there are n, ..
The objective equation z is actually the result of weighted summation of unknown variables (that is, multiplied by the value coefficient).
AX=b is the resource limit. If there are m constraints, then AX=b has m equations. In order to find the value of each unknown quantity in x, we only need to solve this set of equations. Junior high school should have learned how to use gauss elimination for multivariate linear equations. The only solution is that the number of unknowns is just equal to the number of equations (n=m), but it is often n > in linear programming problems; M-shaped
What about this situation? Very simple, find a method to make n=m, this method uses the concept of base B, and the description in general operational research textbooks is "B is m×n nonsingular submatrixes of A". Anyone who is good at linear algebra must understand it. What about those that don't? That depends on how we understand how to bypass the concept of "nonsingular submatrix" In fact, A is divided into N column vectors, from which M is randomly selected. Of course, these M column vectors must be linearly independent, that is to say, none of them can be expressed by the remaining m- 1, or take one less. These M column vectors are base B, also called base matrix. If B is removed from A, the matrix composed of the remaining n-m column vectors is non-base N or non-base matrix. The variable [formula] corresponding to radix b is called radix variable, and the variable [formula] corresponding to non-radix n is called non-radix variable. The first constraint is as follows:
At this time, as long as we set all the variables in [formula] to 0, the above formula becomes: [formula], which is an equation group composed of m linear independent m-ary linear equations, and the [formula] can be obtained by elimination method. Combined with the above [formula], [formula] is the solution of the above constraint condition, of course, it is also a solution of the original constraint condition AX=b, and this solution is the basic solution.