Linear programming with interval coefficients
- PDF / 280,816 Bytes
- 12 Pages / 595 x 842 pts (A4) Page_size
- 27 Downloads / 265 Views
#2000 Operational Research Society Ltd. All rights reserved. 0160-5682/00 $15.00 http://www.stockton-press.co.uk/jors
Linear programming with interval coef®cients JW Chinneck1* and K Ramadan2 1
Carleton University, Ottawa, Ontario, Canada, and 2Export Development Corporation, Ottawa, Ontario, Canada
In order to solve a linear programme, the model coef®cients must be ®xed at speci®c values, which implies that the coef®cients are perfectly accurate. In practice, however, the coef®cients are generally estimates. The only way to deal with uncertain coef®cients is to test the sensitivity of the model to changes in their values, either singly or in very small groups. We propose a new approach in which some or all of the coef®cients of the LP are speci®ed as intervals. We then ®nd the best optimum and the worst optimum for the model, and the point settings of the interval coef®cients that yield these two extremes. This provides the range of the optimised objective function, and the coef®cient settings give some insight into the likelihood of these extremes. Keywords: linear programming; interval coef®cients; approximate model
Introduction Formulating of a model as a linear program (LP) requires that speci®c values be chosen for the model coef®cients, such as objective function costs and constraint coef®cients and right-hand sides. In practice, however, the values of many of these coef®cients are only approximately known. For example, the pro®t per unit of production of an item is likely estimated from knowledge of average component costs, labour costs, and wholesale sales prices over the preceding months. How then is a manager to treat the results of an LP solution in which the coef®cients are known to be uncertain? In practice, a manager would like to know the range of optimum solutions that could be returned by the LP model with various settings of the uncertain coef®cients. Unfortunately, the current state of the art provides little help. Classical sensitivity analysis allows a study of the effect on the solution of changes to single coef®cients or very small groups of coef®cients, but only to the extent that the optimal basis is not changed. Wendell's1 tolerance approach determines the maximum fractional change in any coef®cient before the basis changes, and the 100% rule (see for example, Bradley et al2) also considers simultaneous coef®cient alterations that do not change the basis. There are no effective tools for examining the effects of many simultaneous changes to the coef®cients that may change the basis. In any case, a hit-and-miss approach to the variation of the uncertain coef®cients is unlikely to uncover the complete range of possible optimum objective function values.
*Correspondence: Department of Systems and Computer Engineering, 4462 Mackenzie Building, 1125 Colonel By Drive, Ottawa, ON K1S 5B6 Canada
Our goal in this paper is the development of practical algorithmic tools for dealing with LPs in which the coef®cients are known only approximately. Our only serious assumption is that any unknown co
Data Loading...
