Interior Point Approach to Postoptimal and Parametric Analysis in LinearProgramming

摘要

Problems in the simplex based approach to understanding the solution behavior ofthe linear programming problem are discussed and proposals are made to resolve the difficulties. Postoptimal analysis in linear programming is analyzed from an interior point of view. Use is made of the partition of the variables induced by a pair of strictly complementary solutions; this partition will be called the optimal partition and is unique. It is well known that many interior point methods generate such a pair of solutions in the interiors of the optimal faces. Changes in a single coefficient of the right hand side or the objective function are considered. The corresponding optimal value functions are known to be piecewise linear functions. The ranges where these functions change linearly are shown to be exactly the intervals where the optimal partition does not change. Examples are given to compare the information obtained from both the classical approach and the given approach. Results can straightforwardly be extended to parametric linear programming.