An Introduction to Nearly Optimal Programming an Extension of Sensitivity Analysis in Linear Programming

Article excerpt

Introduction

Linear programming (LP) is one the most significant mathematical tools used in solving problems of practical importance. For example, in a survey of Fortune 500 companies, it was reported that 85% of the firms responding used LP (Winston) 1991). It has been applied to a wide variety of fields and numerous applications can be found in management science textbooks. For instance, one especially effective use of LP cited by Eppen et al. (1987) is an LP model developed for fuel allocation of a major airline during the 1973 fuel crisis. Utilizing the results from this model helped provide a savings of 12% in fuel consumption for the company, while the overall savings were in the millions of dollars. Since LP modelling is so widespread, LP is often also included in first-year college mathematics books, besides the standard operations research and management science texts.

In conventional quantitative analysis courses, LP can often comprise a majority of the course work, especially when sensitivity analysis or post optimality analysis is addressed. According to a recent survey of 20 top ranked business schools, the average time devoted to LP in a quantitative methods course is over 50%. In fact it ranges from 30% to 100% (Carraway and Freeland 1989). Despite the prevalent role of LP in undergraduate and graduate quantitative studies, there is an aspect of sensitivity analysis that is often overlooked. Standard approaches to sensitivity analysis such as right-hand side and objective function coefficient ranging are generally covered. However, another technique which can be incorporated into sensitivity analysis is to examine nearly optimal solutions as opposed to generating one global optimal solution. This idea of Nearly Optimal Programming (NOP) has been investigated in academic research, though it is rarely discussed in textbooks written for quantitative analysis courses (e.g., Burton et al. 1987; Cocklin 1989a, 1989b; Fiering 1984; Quinn and Harrington 1992). In NOP a number of alternative solutions are easily generated, which lie within a small range of the global optimal value of the objective function.

NOP has many advantages which would be of interest to the business oriented college student. First of all, it is quite simple to formulate an LP model as an NOP model and generate solutions by the simplex method. The students can understand the modifications since they are typically few in number. Most importantly, NOP has significant implications for problems where there is more than one decision maker or more than one party that would be affected by the solution. The basic idea of NOP is that it is often more important to provide the interested parties with different types of solutions from an LP model than to produce only one optimal solution.

It is obvious that the global optimal solution from an LP model is only as good as the original model. Since any model is an abstraction of a real world process, it is subject to imprecision. For example, cost or profit data are typically estimated and not exact. Also there can be objectives or constraints that are difficult to quantify, either political or social, and therefore they are difficult to include in the model. Another problem is that the methods of data collection are not completely reliable. As Rogers and Fiering (1986) state:

The reason for searching this domain (nearly optimal region) is enrichment for the array of potential solutions from which to construct a solution acceptable to all the competing parties. It might be more valuable to retreat from the best possible solution, whereupon nearly optimal solutions become attractive. There might be political or institutional constraints which are better unstated. Mathematical formalisms then are useful for identifying the negotiation set from among which the political process selects the decision.

NOP is a method which is especially useful for a business oriented class of students. …