朝闻道

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 vertex of the convex set, and the feasible region of the linear programming problem is a convex set, which is the set of feasible solutions. Therefore, to find the optimal solution, we need to find a basic feasible solution.

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

1. First, transform the linear programming problem into a standard mathematical model.
2. Next, find an initial basis and verify that it is a feasible basis.
   • Find a basis: Find a maximum full-rank submatrix of the coefficient matrix ($m \times m$ order).
   • Find a basic solution: Let the 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-negativity constraint, 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 a $σ_j = 0$, then there are infinitely many optimal solutions.
   • If there exists $σ_j > 0$, and all coefficients $a_{ij} < 0$ corresponding to the non-basic variable $x_j$, then there is no optimal solution.
   • If there exists $σ_j > 0$, and among the coefficients corresponding to the non-basic variable $x_j$, there exists $a_{ij} > 0$, then iteration can continue.
4. If iteration can continue, perform a basis transformation.
   • Determine entering variable: Select the non-basic variable $x_j$ that achieves the maximum positive value of $σ_j$ as the entering variable.
   • Determine leaving variable: Select the basic variable $x_i$ corresponding to $i$ that achieves the minimum positive value of $θ_j=\frac{b_i}{a_{ij}}$ as the leaving variable.
   • Basis transformation: Let $x_j=θ, x_i=0$, and transform the coefficient matrix $B$ of the new basic variables into the identity matrix to obtain the new basis.
   • Re-verification: Re-"find a basic solution - verify if it is a basic feasible solution - verify if it is the optimal solution..." for the new basis, until iteration can no longer continue.

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