Interior Point Method and Sensitivity Analysis

In linear programming (LP), shadow prices play an importante role in sensitivity analysis. While the Simplex Method is commonly used to compute them, and typically, they are identical to the optimal solution of the dual problem. However, in cases of degeneracy, where multiple optimal bases exist, shadow prices may vary with changes in the right-hand side (RHS) of constraints, either increasing or decreasing accordingly. This variability can introduce inaccuracies in commercial solvers that rely on the Simplex Method. This study aims to highlight these discrepancies and propose the use of the Interior Point Method as an alternative approach for computing shadow prices. The objective is to utilize the concept of optimal partitions in primal variables and dual slackness variables, induced by pairs of strictly complementary solutions. Finally, we present an illustrative example comparing the results obtained using the optimal basis approach of the Simplex Method with those obtained using the Interior Point Method and optimal partitions.