Post-optimality analysis of the optimal solution of a degenerate linear program using a pivoting algorithm

摘要

This paper gives a theory and method that specifies how the optimal solution of a linear program changes when the right-hand side of the original problem is changed and when the original optimal solution exhibits primal degeneracy. The method determines an optimal change vector as the resource availabilities change, and it calculates a range for which this vector is valid. Resource availabilities are allowed to change simultaneously in any arbitrary proportion, and the concept of an "efficient resource bundle" is introduced. The geometry of the optimal change vector is presented from which the desired results are derived. The connection between the geometrical results and their algebraic calculation in tableau-form is shown. Our method uses a pivoting algorithm and the relationship with post-optimality results from interior-point methods will be established.