The general form of linear programming model is:
Converting it into standard form requires that all constraints are equality constraints and all decision variables are non-negative.
For example, the following form:
For example:
Then it is easy to write the mathematical model of this linear programming problem:
Similarly, the standard form of linear programming must be the following form:
Regarding the standard type, we have two basic assumptions:
The row vectors of 1. coefficient matrix A are linearly independent.
2. The number of columns of coefficient matrix A is greater than its number of rows, that is, n >；; M. because if n
Back to the example just now, we can write a standard form as follows:
In this example, m = 3 and n = 5. Then we can use three variables to represent all five variables, which we call base variables. In the figure above, the coefficients of x3, x4, x5 and x5 are a identity matrix. We call this form of equality constraint a gauge constraint.
Observing this formula, we can easily see a basic feasible solution: (0,0,15,24,5) t, that is, the non-base variable is equal to 0 and the base variable is equal to the constant on the right side of the equation. This solution, we can imagine it as a vertex of the basic feasible solution region, and we know that the optimal solution is also at this vertex, so we just need to find this optimal vertex along the boundary.
For vertex (0,0,15,24,5) t, its x3, x4, x5, x5 are base variables, so what is the relationship between the base variables of other vertices adjacent to this vertex? In fact, only one of all the base variables of adjacent vertices has changed. This can be verified. So the next work is to select a non-base variable from x 1, x2 as the base variable, and a base variable from x3, x4 and x5 as the base variable.
Then the question comes, how do we choose the base variable and the base variable?
Assuming that we want to take x2 as the base, then according to the expression of the basic feasible solution, x2 must only appear in an equality constraint in the form of elementary line transformation, that is, the coefficient of x2 should be changed to the form of (1, 0,0) t or (0,0, 1) t.
Suppose we change x2 into the form of (0,0, 1)T, and after elementary line transformation, we get:
Now, for example.
We get two basic feasible solutions: x1= (0,0,15,24,5) t, X2 = (0 0,3,0,18,2) t, and the objective function f (x) = 2x/kloc-0.
Then f (x 1) = 0 and f (x2) = 3.
So how do we find the optimal solution?
We know that the expression of the constraint of X2 = (0 0,3,0,18,2) t is:
Did you find anything?
For the feasible solution X2 = (0 0,3,0,18,2) t, x 1, x3 is a non-base variable, and the non-base variable is 0. However, shouldn't we choose the base variable in the next step? Don't we choose base variables from non-base variables? We choose x 1. Why? The coefficient of x 1 is positive 2! Our example is to find the maximum value of Z. If x 1 is denominated, then f(X) will inevitably increase, because our decision variables are all positive numbers, and whether positive numbers are multiplied by positive numbers or not, the increment must be greater than 0. We see that the coefficient of x3 is -0.2. If x3 is added to the radix, the increment must be less than 0.
What if the coefficients of X 1 and X3 are both greater than 0? Then choose at will.
What if the coefficients of x 1 and x3 are both less than 0? Haha, some people may realize that the coefficients of non-radix variables are all less than 0, and choosing who to enter the radix will make f(X) smaller. Aren't we trying to maximize? Then we won't choose anyone. This question is over. We found the optimal solution!
Thus, the problems of selecting base variables and finding the optimal solution are solved.
We usually use simplex table to represent this process visually.
Or the feasible solution X2 = (0 0,3,0,18,2) t, and its corresponding simplex table is as follows:
The leftmost column is the base variable, the rightmost column is the constant term that constrains the right, and the middle column is the coefficient of the decision variable. The bottom line is the objective function z = 2x 1+x2+0x3+0x4+0x5. The coefficient of the decision variable in the bottom row is called the test number.
We change the coefficient in front of the base variable in the last row to 0 through row transformation, and get the following simplex table:
We can get the following information from this table:
Then, by using the method just now, let x3 enter the base and get a new simplex table of basic feasible solutions:
From this table, we can know:
So far, we have got the optimal solution X4 of this problem.
We know that for a basic feasible solution, generally speaking, its base variable is greater than 0 and its non-base variable is equal to 0. In the case of degradation, we have a basic variable that is also equal to 0. Then, this basic feasible solution will correspond to multiple feasible arrays.
For example:
X = (3 3 3,3,0,0 0) t is a feasible solution to this problem.
We can make x3 and X4 non-basic variables or X3, x5 or X4 and X5 non-basic variables.
The problem in the degenerate case is that the same basic feasible solution is obtained after one iteration inside and outside the base, so it is possible that the iterative algorithm will cycle through several base matrices of a basic feasible solution.
Therefore, the sufficient condition to ensure the convergence of simplex method is that the value of the base variable of each basic feasible solution generated in the iterative process is strictly greater than 0.
In the iterative process, if the coefficient of a decision variable is less than 0, what does it mean?
For example:
As shown above, we can put x2 on the right side of the equation. See anything? X2 can tend to infinity.
As shown in the above figure, the test number of non-base variable x4 is 0. According to the optimality condition, it cannot continue to optimize the objective function value by letting the objective function value enter the base. However, a basic feasible solution will still be obtained after x4 enters the base, and the objective function value is the same as the current result. What does this mean?
The goal can no longer be optimized, but there are different basic feasible schemes. What do you mean? It shows that there are infinite optimal solutions to this problem.
Therefore, for the linear programming problem of finding max, if all the test numbers are satisfied,
Simplex method starts from an initial basic feasible solution and proceeds step by step until the optimal feasible solution is found.
The question is, how do we get the initial basic feasible solution?
The most basic method is to add artificial variables
Assume that the constraints of the original problem are as follows:
x 1 + 2x2 + 3x3 = 1
2x + x3 = 2
Then, we add two more variables X4 x4, x5 to make the constraint look like this:
x 1 + 2x2 + 3x3 + x4 = 1
2x + x3 + x5 = 2
We can directly get a basic feasible solution (0, 0, 0, 1, 2)T by changing the constraint into a canonical form, and find that the basic variables of a basic feasible solution are x4 and x5. Then the next work is to change x4 and x5 into non-basic variables from base to base, so that their values can be 0, thus obtaining the feasible solution of the original problem.
Now there is a problem. What does it mean if the basic variables still contain artificial variables in the optimal table?
This shows that the original problem has no solution at all.