Move along an improving feasible edge

Try

Maximize 3x+2y subject to x+y≤4, 2x+y≤6 and x,y≥0. Add nonnegative slacks s₁,s₂ to obtain two equalities. Starting with x=y=0 gives the feasible slack basis s₁=4,s₂=6. Increasing x by t changes the slacks to 4−t and 6−2t and increases the objective by 3t. The largest feasible step is the smaller ratio, min(4,3)=3. At that step s₂ reaches zero and x replaces it in the basis.

Predict

Predict whether the largest objective coefficient is always the best entering choice. It can have a small allowable step or lead to many later pivots; a local reduced cost is not a complete forecast of total algorithm work. Predict also why a coefficient that makes a basic variable increase does not limit the step. Nonnegativity constrains decreases toward zero, not increases away from zero. Getting this sign wrong changes both the pivot and the claimed unboundedness status.

Experiment

After the first pivot, express the dictionary using nonbasic y and s₂. The equations are x=3−y/2−s₂/2 and s₁=1−y/2+s₂/2. The objective becomes 9+y/2−3s₂/2.

Entering variable	Reduced cost	Limiting step	Result
y	1/2	2	x=2,y=2,s₁=s₂=0
s₂	−3/2	Not an improving choice	Reject for maximization

The y step adds one unit of objective, reaching ten. Solve for the new dictionary: x=2+s₁−s₂, y=2−2s₁+s₂, and objective=10−s₁−s₂. Since both nonbasic variables are nonnegative, no feasible decision can exceed ten. The final dictionary is a certificate, not just a stopping instruction.

Understand

In equality standard form Ax=b,x≥0 with a feasible basis B, let nonbasic variable j enter at value t while other nonbasic variables remain zero. Then x_B=B⁻¹b−B⁻¹aⱼt. The objective’s slope is the reduced cost rⱼ=cⱼ−c_BᵀB⁻¹aⱼ. For maximization, a positive reduced cost is improving. If u=B⁻¹aⱼ has positive entries, the ratio test takes the minimum of (x_B)ᵢ/uᵢ over those entries. A minimizing coordinate leaves the basis when it reaches zero.

If u≤0 componentwise and rⱼ>0, every basic coordinate stays nonnegative for arbitrarily large t, producing an improving feasible ray and proving unboundedness. If every nonbasic reduced cost is nonpositive, the objective decomposition cᵀx=c_BᵀB⁻¹b+Σrⱼxⱼ bounds all feasible objectives by the current value. This proof does not require enumerating every vertex. It does require a feasible current basis; an infeasible dictionary cannot support the same conclusion.

Apply

Recompute the first pivot by choosing y first. Its initial reduced cost is two, and its maximum step is four. The point (0,4) has objective eight. From there, a later improving pivot reaches (2,2). Compare the paths while preserving exact arithmetic and the same objective. Different pivot paths can lead to the same optimum, but a finite example does not establish complexity or termination for every rule.

Inspect degeneracy: if a limiting basic coordinate starts at zero, the ratio test can return a zero step despite positive reduced cost. The basis changes but the point and objective do not. Therefore strict improvement per pivot cannot be used as a general simplex termination proof.

Continue

Record entering variable, reduced cost, basic direction, ratio candidates, leaving variable and objective gain. This trace makes sign errors and false improvement claims visible. Continue to Phase I and degeneracy to construct an initial feasible basis when slacks alone do not provide one, and to understand why an anti-cycling rule is needed for an exact finite termination guarantee.