DEGENERACY AND THE (MIS)INTERPRETATION OF SENSITIVITY ANALYSIS IN LINEAR PROGRAMMING

Under conditions of degeneracy, sensitivity analysis information such as cost and right-hand-side ranges, which are produced by standard linear programming procedures used in commercial codes, can be misleading. From a managerial perspective, the interpretation of such information can be erroneous. In this paper we present these problems, explain their occurence with elementary examples, and discuss procedures for their resolution.     

Notes and Communications ON SENSITIVITY ANALYSIS IN DECISION THEORY*

This note points out a crucial flaw in Evans's recent article [1] on decision sensitivity analysis which was published in this journal. This flaw leads to errors in the majority of his formulae and examples. Correct distance formulae in “probability space,” easily computed from the problem data, are provided. After a critical discussion of some of the concepts Evans employed, we bring to the reader's attention a body of prior work in this area that apparently was overlooked.     

A MATHEMATICAL PROGRAMMING APPROACH TO SENSITIVITY ANALYSIS IN SINGLE-STAGE DECISION MAKING

This paper presents sensitivity analyses for a single-stage decision problem where an action which will maximize the expected payoff must be chosen from a finite number of actions given the states of nature, their probabilities, and the payoffs corresponding to each action and state of nature. Three types of sensitivity analysis are developed: (1) sensitivity analysis on the probabilities keeping the payoff numbers fixed, (2) sensitivity analysis on the payoffs keeping the probabilities fixed, and (3) joint sensitivity analysis on the payoffs and the probabilities. The approach is illustrated with an example. Quite often the sensitivity analysis can be conducted by solving an appropriate linear or quadratic programming problem.     

THE EFFECTS OF DEGENERACY ON COST-COEFFICIENT RANGES AND AN ALGORITHM TO RESOLVE INTERPRETATION PROBLEMS

The problems of determining valid shadow prices and of performing a valid sensitivity analysis for managerial purposes are considered. For primal degenerate optima, earlier results on finding shadow prices are used to propose a clear and efficient method for finding valid cost-coefficient ranges. An example is used to demonstrate how managerial information can be obtained at degenerate optima.     

Sensitivity Analysis Revisted and Extended

The tolerance approach to sensitivity analysis in linear programming provides a framework for dealing with simultaneous and independent variations of the coefficients and terms. Specifically, the approach yields a maximum tolerance percentage which in turn characterizes a region of variability for the coefficients or terms. This paper shows how to expand this region of variability yielding ordinary sensitivity analysis as a special case of the tolerance approach.     

Notes and Communications RESOLVING CERTAIN DIFFICULTIES AND IMPROVING THE CLASSIFICATION POWER OF LP DISCRIMINANT ANALYSIS FORMULATIONS

In certain settings, difficulties arise that limit the effectiveness of LP formulations for the discriminant problem. Explanations and possible remedies have been offered, but these have had only limited success. We provide a simple way to overcome these problems based on an appropriate use and interpretation of normalizations. In addition, we demonstrate a normalization that is invariant under all translations of the problem data, providing a stability property not shared by previous approaches. Finally, we discuss the possibility of using more general models to improve discrimination.     

A Generalization of Wendell's Tolerance Approach to Sensitivity Analysis in Linear Programming

A criticism of linear programming has been that the data which are available in practice are too inexact and unreliable for linear programming to properly work. Managers are therefore concerned with how much actual values may differ from the estimates that were used in the model before the results become irrelevant. Sensitivity analysis emerged to help deal with the uncertainties inherent in the linear programming model. However, the ranges calculated are generally valid only when a single coefficient is varied. An extension of sensitivity analysis, the 100 Percent Rule, allows the simultaneous variation of more than one element in a vector, but does not permit the independent variation of the elements. A tolerance approach to sensitivity analysis enables the consideration of simultaneous and independent change of more than one coefficient. However, the ranges developed are unnecessarily restricted and may be reduced in width to zero when primal or dual degeneracy exists. This paper presents an extension of the tolerance approach which reduces the limitations of both the traditional and tolerance approaches to sensitivity analysis.     

Sensitivity of Linear Programs to Related Changes in Multiple Inputs*

In a 1991 paper in Decision Sciences, Camm and Burwell presented smart modeling techniques for obtaining the sensitivity of linear programs to simultaneous common changes in common inputs. This note addresses sensitivity analysis of simultaneous related changes in multiple inputs, and shows how related multi-parametric analysis can be performed with software that has no or only limited parametric programming capability.     

A UNIFIED APPROACH TO THE PRICE-BREAK ECONOMIC ORDER QUANTITY (EOQ) PROBLEM*

In many developing countries where supply is limited, a premium rather than a discounted price is paid for buying in larger amounts. In order for management science/operations research solutions to be relevant to developing economies, such realities need to be explicitly recognized and any decisions evaluated from that perspective. To illustrate this point, a typical inventory-purchasing problem is solved. In the process, formulae are developed that introduce simultaneous price and quantity sensitivity into the inventory equation. A systematic procedure is suggested to locate the optimal order quantity for a given schedule of discounts or premiums.     

RATIONING DISCRETIONARY ECONOMIC RESOURCES: A MULTIOBJECTIVE APPROACH

Prior research involving capital rationing has focused on capital budgeting issues: given a limited resource pool, which major long-lived fixed assets should be acquired? However, capital rationing can be extended to include not only new fixed-asset purchases but also expenditures for any other discretionary activity such as advertising, research and development, or maintenance. In this broader situation, measuring the contributions of certain discretionary activities to a single objective (e.g., maximize profits) or to multiple objectives often is hindered by a lack of reliable revenue estimates. This problem severely hampers the usefulness of traditional mathematical programming approaches to capital rationing. In this paper, we modify the usual multiobjective capital rationing procedures by treating each discretionary activity as an objective in itself. In this manner, we can mitigate the difficulties associated with revenue measurement problems and allow a decision maker systematically to explore the various trade-offs between competing discretionary investments.     

EVALUATING ALTERNATIVE LINEAR PROGRAMMING MODELS TO SOLVE THE TWO-GROUP DISCRIMINANT PROBLEM

The two-group discriminant problem has applications in many areas, for example, differentiating between good credit risks and poor ones, between promising new firms and those likely to fail, or between patients with strong prospects for recovery and those highly at risk. To expand our tools for dealing with such problems, we propose a class of nonpara-metric discriminant procedures based on linear programming (LP). Although these procedures have attracted considerable attention recently, only a limited number of computational studies have examined the relative merits of alternative formulations. In this paper we provide a detailed study of three contrasting formulations for the two-group problem. The experimental design provides a variety of test conditions involving both normal and nonnormal populations. Our results establish the LP model which seeks to minimize the sum of deviations beyond the two-group boundary as a promising alternative to more conventional linear discriminant techniques.     

SOME DIFFICULTIES AND IMPROVEMENTS IN APPLYING LINEAR PROGRAMMING FORMULATIONS TO THE DISCRIMINANT PROBLEM

In this paper, we discuss some disturbing features of two linear programming (LP) approaches to the discriminant problem. Specifically, we show that both approaches are sensitive to the choice of origin for the data although, intuitively, placement of origin should have no effect on the method of assigning cases to groups. In addition, we show that these LP approaches may lead to discriminant functions which assign all cases to the same group. We show that the usual statistical approach to this problem does not share these difficulties, and we make recommendations for implementing these LP approaches which help to alleviate the difficulties.     

MODIFIED STEPPING-STONE METHOD AS A TEACHING AID FOR CAPACITATED TRANSPORTATION PROBLEMS

This paper extends the standard stepping-stone method to the case of capacitated transportation problems. The purpose is to offer an alternative to network-oriented or simplex-based methods (such as the out-of-kilter and upper-bounding techniques) often used in handling the capacitated transportation problem but generally beyond the scope of introductory decision sciences courses. The proposed procedure is based on the simple stepping-stone method and requires only a few modifications in the cost/assignment matrix and some alterations in the pivoting rules. As such, it is much easier to understand and apply than the above-mentioned solution algorithms. It therefore can serve as an effective tool for teaching capacitated transportation problems. Two numerical examples illustrate applications of the proposed method, procedures for sensitivity analysis, and comparisons with linear programming.     

ESTIMATION OF MISCLASSIFICATION PROBABILITIES IN THE LINEAR PROGRAMMING APPROACHES TO THE TWO-GROUP DISCRIMINANT PROBLEM

Expressions for misclassification probabilities are derived under a contaminated multivariate normal model for the linear-programming approaches to the two-group discriminant problem.     

A MATHEMATICAL PROGRAMMING APPROACH TO THE SELECTION OF ACCESS PATHS FOR LARGE MULTIUSER DATA BASES*

The selection of an efficient set of access paths is critical to the design of large multiuser data bases. This task is formulated as an integer, linear mathematical program, and an approach to its solution is presented. A series of experiments support the assertion that this approach is sufficient for quickly producing an efficient, if not optimal, set of access paths for data-base problems of practical significance.     

FOUR APPROACHES TO THE CLASSIFICATION PROBLEM IN DISCRIMINANT ANALYSIS: AN EXPERIMENTAL STUDY*

Four discriminant models were compared in a simulation study: Fisher's linear discriminant function [14], Smith's quadratic discriminant function [34], the logistic discriminant model, and a model based on linear programming [17]. The study was conducted to estimate expected rates of misclassification for these four procedures when observations were sampled from a variety of normal and nonnormal distributions. In contrast to previous research, data were taken from four types of Kurtotic population distributions. The results indicate the four discriminant procedures are robust toward data from many types of distributions. The misclassification rates for both the logistic discriminant model and the formulation based on linear programming consistently decreased as the kurtosis in the data increased. The decreases, however, were of small magnitude. None of these procedures yielded statistically significant lower rates of misclassification under nonnormality. The quadratic discriminant function produced significantly lower error rates when the variances across groups were heterogeneous.     

ORTHOGONAL INFORMATION STRUCTURES—A MODEL TO EVALUATE THE INFORMATION PROVIDED BY A SECOND OPINION

The paper discusses the value of information when a number of independent sources provide information related to a common set of states of nature. The starting point is the information economic model of information structures. The model is augmented to represent independence of informational sources by means of orthogonality of the information structures. A new mathematical operator, orthogonal product, is defined and its properties are probed. It is shown that this operator maintains some mathematical properties such as closure, association, unity element, null element, and so forth. It is demonstrated how the orthogonal product represents the notion of multisource information. The paper proves that an orthogonal product is generally more informative than its multipliers, namely, if cost is not considered a constraining factor, then there is a nonnegative value to obtaining a second opinion. An appendix to the paper expands this result to a case of partially dependent signals. The paper concludes with a numerical example and a discussion of the model's applicability for practical problems such as cost estimates.     

A UNIVERSITY EXAMINATION-SCHEDULING MODEL TO MINIMIZE MULTIPLE-EXAMINATION DAYS FOR STUDENTS

Scheduling university examinations is often done with the objective of spreading a student's required examinations over an examination week. That is the equivalent of the problem of minimizing the number of examinations a student must take on any one day. An approach to scheduling exams which relates the problem to the classical assignment problem is discussed. The model developed is a symmetry-constrained assignment model, and the solution method requires use of a branch-and-bound algorithm. Results from application of the algorithm to six semesters of actual data are presented.     

MULTIPLE-CRITERIA DECISION MAKING INCLUDING QUALITATIVE FACTORS: THE POST-MODEL ANALYSIS APPROACH

As a method of solving multiple-criteria decision making problems with a single quantitative objective and multiple qualitative objectives, the post-model analysis (PMA) approach is proposed. The essence of PMA is to support the trade-offs between a quantitative objective and multiple qualitative objectives so that the decision maker can find a perceived most preferred nondominated solution. To this end, the optimal solution of a quantitative model is found first, without regard for qualitative factors. The solution is then evaluated in terms of qualitative objectives. When the initial quantitatively optimal solution is adjusted to allow improvement of qualitative goals, opportunity costs of achieving qualitative goals are incurred. In this process, an expert system and/or graphical display can be used. PMA therefore provides a way to incorporate quantitative models into knowledge-based expert systems.