یک روش عملی برای آنالیز حساسیت در برنامه ریزی خطی تحت زوال برای تصمیم گیری مدیریت

Linear programming (LP) is a widely used tool in management decision making. Theoretically, sensitivity analysis of LP problems provides useful information for the decision maker. In practice, however, most LP software provides misleading sensitivity information if the optimal solution is degenerate. The paper shows how sensitivity analysis of LP problems can be done correctly when the optimal solution is degenerate. A production planning example is presented to illustrate the incorrect sensitivity analysis results automatically provided by most LP solvers. The general characteristics of the misleading results and the possible effects of this incorrect information on management decisions are also discussed.

One of the most important management decision making problems is, when limited amount of resources must be assigned to decision alternatives and an objective function helps to evaluate the result of the assignment. Profit maximizing product mix decisions, cost minimizing production planning problems are typical examples of this situation. If the objective function is linear and the limits on resource usage are expressed with linear inequalities, furthermore, the decision variable is continuous, a continuous linear programming problem (LP) is obtained.

This paper presents a method for calculating the proper sensitivity ranges of LP problems, when the optimal solution is degenerate. A small example is used to illustrate the difference between the results of some commercially available LP solvers and the suggested method. A production planning case study was used to illustrate the advantage of management oriented sensitivity analyses results in decision making. If management decisions are based on the erroneous results of standard LP solvers, three types of problem can be found: (1) Most of the LP solvers provide a narrower validity range for OFCs than the real range. A narrow range may direct unnecessarily the attention of managers to such parameters (costs, prices, etc.) which are difficult to control or expensive to change. (2) Most of the LP solvers provide unreliable information about the shadow price. Sometimes either the marginal decrease or the marginal increase of the objective function is provided. Sometimes the shadow price has a zero validity range, and the left and right shadow prices as well are different from the provided one. If managers want to get correct information about the effect of decrease and about the effect of increase as well, additional calculations are required. (3) Most of the LP solvers provide a narrower validity range for the RHS parameters than the real range. In this case managers may easily underestimate or overestimate the effect of the change of some constraints (capacity, manpower). To get the proper ranges, however, requires additional calculations. The erroneous sensitivity results of most commercial LP solvers are obtained by simply solving the LP problem once, and read sensitivity information from the results of the last iteration step (for example from the optimal simplex tableau). For an LP problem with I variables and J constraints the correct ranges are obtained by solving 2I+6J additional LP problems. With the development of information technology the solution of the additional LP problems to get proper ranges can be done quickly, especially, when sensitivity information is not required for all OFCs and RHS parameters. If, however, the LP problem is large, filtering those parameters, which are relevant for management decision making can help to reduce the computational burden.