mathematical-optimizationlinear-programmingsimplex-algorithm

Dual values of optimal bases


Suppose that we have a linear program (LP) that has at least two optimal bases B1 and B2. Are the dual values associated with B1 equal the dual values associated with B2? In other words, can we associate to each constraint of LP a unique dual value even if this program admits more then one optimal basis?


Solution

  • No, you cannot. With a degenerate optimal solution, i.e. when there is more than one optimal basis, there can also be different primal and dual solutions. What will always be equal among all optimal bases is the corresponding solution value.