关于求解线性规划的单纯形法中转轴操作的技术问询

Great question—let’s break down exactly how pivot operations work, confirm the core principles you’ve noted, and dive into the technical details tied to your problem: min c'x, s.t. Ax ≤ b (where (A) is (m \times n), (m < n)).

First, Confirming the Pole/Base Variable Relationship #

You’re totally right about poles (vertices of the feasible region) corresponding to solutions with at most (m) non-zero variables. To formalize this, we first convert your inequality constraints to standard form by adding non-negative slack variables (s \in \mathbb{R}^m):

Ax + s = b
x ≥ 0, s ≥ 0

Now we have (m) equality constraints with (n + m) variables. A basic feasible solution (BFS)—which is exactly a pole of the feasible region—comes from selecting (m) linearly independent columns of the augmented matrix ([A | I]) (where (I) is the (m \times m) identity matrix for slack variables). These columns form the basis matrix (B), and the corresponding variables are base variables (set to non-zero values by solving (Bx_B = b)). The remaining (n) variables are non-base variables, which we set to 0 to get the BFS.

Why Pivots Swap a Non-Base Variable into the Basis #

The whole point of pivoting is to move from one BFS (pole) to another that improves the objective function. Here’s the core logic:

• For a minimization problem, we look at the reduced cost of each non-base variable. This value tells us how much the objective function will decrease if we increase that non-base variable from 0 (while keeping other non-base variables at 0).
• If a non-base variable has a negative reduced cost, increasing it will make the objective function smaller (better for our minimization goal). We pick this variable as the entering variable—the one moving from non-base to base.

Choosing Which Base Variable to Swap Out (The Minimum Ratio Test) #

When we increase the entering variable, we have to keep all variables non-negative to maintain feasibility. Each base variable’s value depends on the entering variable:

• For each constraint, rearrange the equation to express the base variable in terms of the entering variable.
• Calculate the ratio of the current base variable value to the positive coefficient of the entering variable in that constraint. This ratio tells us the maximum amount we can increase the entering variable before that base variable hits 0.
• We pick the smallest non-negative ratio—this corresponds to the leaving variable (the base variable that becomes 0, moving to non-base). This guarantees all variables stay non-negative in the new BFS.

Technical Details of the Pivot Calculation #

Pivoting is essentially a targeted Gaussian elimination step on the simplex tableau (a compact way to represent constraints and the objective function):

1. Locate the pivot element: the intersection of the entering variable’s column and the leaving variable’s row.
2. Normalize the pivot row by dividing by the pivot element, so the pivot element becomes 1.
3. Eliminate the entering variable from all other rows (including the objective function row) by subtracting multiples of the pivot row. This ensures the entering variable’s column becomes a unit vector (1 in the pivot row, 0 elsewhere).
4. The new tableau now represents the updated BFS: the entering variable is now a base variable, the leaving variable is non-base (set to 0), and all other base variables have updated values.

Why This Moves to Another Pole #

Each pivot swaps exactly one variable between base and non-base. Since a BFS is defined by its set of base variables, changing one base variable gives us a new set of (m) linearly independent columns, which corresponds to a new vertex (pole) of the feasible region. We repeat this process until no non-base variable has a negative reduced cost (for minimization)—at that point, we’ve found the optimal BFS.

内容的提问来源于stack exchange，提问作者朱恆毅