# Proof of Strong Duality via Simplex Method

I am study the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis. The proof of strong duality (Theorem 4.4)

Theorem 4.4 (Strong duality) If a linear programming problem has an optimal solution, so does its dual, and the respective optimal costs are equal.

uses the fact that the simplex method has finite termination using the lexicographic pivoting rule, takes an optimal BFS $$x$$, and constructs a dual feasible solution $$p'=c_B'B^{-1}$$ that has the same cost as the primal optimal solution.

I wonder why the simplex method is used in this proof. Why not just use the fact that a standard form LP which has an optimal solution must have an optimal BFS? Is it because the reduced costs are not guaranteed to be nonnegative?

1. To prove the dual feasibility of $$c'_B B^{-1}$$, we need them to be nonnegative, and the clearest argument I can see for that is "well, if one of them is negative, do a pivot step of the simplex method to improve the objective value". We can rephrase that without talking about pivoting - something like "the corresponding nonbasic variable can be increased slightly with a compensating slight decrease in all the basic variables by such-and-such formula, getting a better feasible solution". But at some point, you're avoiding the obvious.