朝闻道

According to the theorem of convex sets, the optimal solution of linear programming must be a basic feasible solution, and a basic feasible solution must be at a convex set vertex. The feasible region of the linear programming problem is a convex set, and the feasible region is the set of feasible solutions. Therefore, to find the optimal solution, you need to find basic feasible solutions.

This is why the steps of linear programming are: find base - find basic solution - verify if it is a basic feasible solution - verify if it is the optimal solution - if not the optimal solution, iterate (base transformation).

1. First, transform the linear programming problem into a standard mathematical model.
2. Next, find an initial base and verify that it is a feasible base.
   • Find Base: Find a maximum full-rank submatrix of the coefficient matrix ($m \times m$ order).
   • Find Basic Solution: Let non-basic variables be 0, then the constraint equations form an $m \times m$ order linear system of equations, which must have a unique solution. Solving the current constraint equations gives the basic solution.
   • Verify if it is a basic feasible solution: If all basic variables in the basic solution satisfy the non-negative constraints, then the basic solution is a basic feasible solution.
3. Check if it is the optimal solution:
   • If all $σ_j ≤ 0$, then it is the optimal solution.
   • If all $σ_j ≤ 0$, but there exists one $σ_j = 0$, then there are infinitely many optimal solutions.
   • If there exists $σ_j > 0$, and all coefficients $a_{ij} < 0$ corresponding to non-basic variable $x_j$, then there is no optimal solution.
   • If there exists $σ_j > 0$, and among the coefficients corresponding to non-basic variable $x_j$, there exists $a_{ij} > 0$, then iteration can continue.
4. If iteration can continue, perform base transformation.
   • Determine entering variable: Select the non-basic variable $x_j$ that achieves the maximum positive number $σ_j$ as the entering variable.
   • Determine leaving variable: Select the basic variable $x_i$ corresponding to $i$ that achieves the minimum positive number $θ_j=\frac{b_i}{a_{ij}}$ as the leaving variable.
   • Base transformation: Let $x_j=θ, x_i=0$, and transform the coefficient matrix $B$ of the new basic variables into an identity matrix to obtain a new base.
   • Re-verification: Re-"find basic solution - verify if it is a basic feasible solution - verify if it is the optimal solution..." for the new base, continue iterating until it is no longer possible.

$σ_j$ is the change in the objective function after the base transformation. (All $σ_j≤ 0$ means there is no better choice than the current one).
$θ$ is the smallest positive value for non-basic variables.