Computing shadow prices/costs of degenerate LP problems with reduced simplex tables

摘要

In applications of linear programming, shadow prices/costs are as important as the optimal values of decision variables and objective function. When the linear programming problems are primal degenerate, the shadow prices are no longer necessarily equal to optimal value of dual variables. In such cases, the so-called two-sided shadow prices are defined. However, existing approaches for two-sided shadow prices are tedious and unnoticed by decision-makers. The situation for shadow costs in a dual degenerate LP problem is the same. This study will first review and generalize the approaches of shadow prices in related studies, and then propose an easy approach to compute the shadow prices with respect to a resource and/or a resource bundle by using a reduced optimal simplex table. With slight modification, the proposed approach can also find the shadow costs with respect to an activity and/or an activity bundle. Numerical examples are used to illustrate the new approaches. Furthermore, some other important topics are discussed, as: the paradoxical situation, complementary effect between resources, weakly redundant constraint and the optimal change vector. We believe the proposed approaches are efficient and useful not only in classroom teaching but also in software programming of commercial packages.