linear programming

Question

Consider an LP problem in Standard form, z = c^Tx. Let x_Bn, x_Nn be the BV, NBV in the n th iteration of the simplex algorithm, c_Bi, c_{N i} be the coefficient vector of x_Bn, x_Nn in the first equation of the i th iteration of the simplex algorithm.

When the LP problem is initialized, the first equation is z − c ^T _B0x_Bn − c ^T _N0x_Nn = 0. At the n th iteration, the first equation is z − c ^T _Bnx_Bn − c ^T _Nnx_Nn = c_n for some c_n ≥ 0. Show that at the n th iteration, c_n = c ^T _B0x_Bn. Interpret the meaning of c_n.

Although it’s not necessary, it might be helpful to work out the following problem and then compare terms.

z − 60x₁ − 30x₂ − 20x₃ = 0 (4)

8x₁ + 6x₂ + x₃ + s₁ = 48 (5)

4x₁ + 2x₂ + 1.5x₃ + s₂ = 20 (6)

2x₁ + 1.5x₂ + 0.5x₃ + s₃ = 8 (7)

x₂ + s₄ = 5 (8)

Answer 1

Hi Sarah,

Here is the solution to Your Simplex Algorithm Question

Key Insight:

At iteration *n*, the constant term cₙ in the objective row equals c_B₀ᵀx_Bₙ because it represents the cumulative improvement in the objective value from all previous pivots. This is essentially how much the objective has improved from its initial value (which was zero in the starting basis).

Step-by-Step Proof:

1. Initialization:
2. Starting tableau has: *z - c_B₀ᵀx_B₀ - c_N₀ᵀx_N₀ = 0*
3. Here x_B₀ are the slack variables, so *c_B₀ = 0* → initial objective is zero.
4. After *n* iterations:
5. The objective row becomes z - c_Bₙᵀx_Bₙ - c_Nₙᵀx_Nₙ = cₙ
6. Through row operations, this cₙ accumulates the objective improvements from each pivot.
7. Why cₙ = c_B₀ᵀx_Bₙ:
8. The current basic variables x_Bₙ are expressed in terms of the original non-basics.
9. When you substitute these into the original objective c_B₀ᵀx_Bₙ + c_N₀ᵀx_N₀, the c_N₀ᵀx_N₀ terms are eliminated (they're non-basic), leaving just c_B₀ᵀx_Bₙ.

Your Example Walkthrough:

For the given problem:

1. Initial basis is slack variables (s₁, s₂, s₃, s₄)
2. After several pivots, if (say) x₁ enters the basis, then:
3. *cₙ = 60x₁* (from original objective coefficients)
4. This shows exactly how much *z* has improved by introducing x₁.

Why This Matters Practically:

1. cₙ is your current objective value - crucial for tracking progress
2. It helps identify when you've reached optimality (c_Nₙ ≥ 0)
3. My students learn to:
4. Track this visually using revised simplex method
5. Debug cycling issues by monitoring cₙ stagnation
6. Accelerate convergence with steepest-edge pricing

Ready to Dive Deeper?

I have:

1. An animated simplex solver that visualizes these relationships
2. Practice problems with known pivot sequences
3. Common pitfall examples (degeneracy, cycling)

I'm available for a session this week to walk through your specific questions!

Best regards,

Aaron