What Is Regulation M?
The big M method is a method to find the initial basis feasible solution of the linear programming problem when the constraint condition (=) equation or () is greater than the type, after using the artificial variable method.
Big M Method
- After adding artificial variables to the constraints of the linear programming problem, it is required to add the term that M or M is a coefficient to the objective function accordingly. In the maximization problem, one M is assigned to the artificial variable as its coefficient; in the minimization problem, one M is assigned to the artificial variable as its coefficient, and M is a positive number that is arbitrarily large (not infinite). Think of M as an algebraic symbol to participate in the operation, use
- In the process of applying the simplex method to improve the objective function, if there is an optimal solution to the original problem, the artificial variable will inevitably be gradually changed to a non-base variable, or its value will be zero. Otherwise, the objective function value will not reach the minimum or maximum. In the process of iteration, if all artificial variables become non-basic variables, the column where the artificial variables are located can be deleted from the simplex table, and then an initial basis feasible solution to the original problem is found. If the basic feasible solution is not the optimal solution of the original problem, iterate iteratively until all the test numbers are less than or equal to 0, and the optimal solution is obtained.
- Solve linear programming problems using the simplex method:
- First reduce it to a standard form.
- In this case, two unit column vectors P 6 and P 7 can be added, together with the vector P 4 in the constraint condition to form the identity matrix:
- P 6 and P 7 are artificially added. It is equivalent to adding the variables x 6 , x 7 , and the variables x 6 and x 7 to the artificial variables. Because the constraint conditions are already equations before the artificial variables are added, in order for these equations to be satisfied, the value of the artificial variables must be zero in the optimal solution. After adding artificial variables, the mathematical model form becomes:
- In this model, the variables x 4 , x 6 , and x 7 corresponding to P 4 , P 6 , and P 7 are the base variables. Let the non-base variables x 1 , x 2 , x 3 , and x 5 be equal to 0 to obtain the initial basis feasible solution. X (0) = (0,0,0,4,0,1,9) T and list the initial simplex table. In the simplex iterative operation, M can participate in the operation as a mathematical symbol. If the test number contains the M symbol, when the coefficient of M is positive, the test number is positive; when the coefficient of M is negative, the test number is negative. The process of solving by the simplex method is shown in the following table:
| C j (objective function coefficient) | -3 | 0 | 1 | 0 | 0 | -M | -M | ||
| C B | base | b | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 |
|
| 0 | x 4 | 4 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| -M | x 6 | 1 | -2 | [1] | -1 | 0 | -1 | 1 | 0 |
| -M | x 7 | 9 | 0 | 3 | 1 | 0 | 0 | 0 | 1 |
| c j -z j (test number) | -2M-3 | 4M | 1 | 0 | -M | 0 | 0 | ||
| 0 | x 4 | 3 | 3 | 0 | 2 | 1 | 1 | -1 | 0 |
| 0 | x 2 | 1 | -2 | 1 | -1 | 0 | -1 | 1 | 0 |
| -M | x 7 | 6 | [6] | 0 | 4 | 0 | 3 | -3 | 1 |
| c j -z j (test number) | 6M-3 | 0 | 4M + 1 | 0 | 3M | -4M | 0 | ||
| 0 | x 4 | 0 | 0 | 0 | 0 | 1 | -1/2 | 1/2 | -1/2 |
| 0 | x 2 | 3 | 0 | 1 | 1/3 | 0 | 0 | 0 | 1/3 |
| -3 | x 1 | 1 | 1 | 0 | 2/3 | 0 | 1/2 | -1/2 | 1/6 |
| c j -z j (test number) | 0 | 0 | 3 | 0 | 3/2 | -M-3 / 2 | -M + 1/2 | ||
| 0 | x 4 | 0 | 0 | 0 | 0 | 1 | -1/2 | 1/2 | -1/2 |
| 0 | x 2 | 5/2 | -1/2 | 1 | 0 | 0 | -1/4 | 1/4 | 1/4 |
| 1 | x 3 | 3/2 | 3/2 | 0 | 1 | 0 | 3/4 | -3/4 | 1/4 |
| c j -z j (test number) | -9/2 | 0 | 0 | 0 | -3/4 | -M + 3/4 | -M-1 / 4 | ||
The simplex table of the large M method can be compared with the two-stage method, and it can be found that the two are largely the same.