On the Stability of Solutions Under Error in Stochastic Linear Programming

J. K. Sengupta, C. Millham, and Gerhard Tintner’s 1965 journal article examines two related meanings of stability in linear programming: whether a selected optimal basis remains optimal when coefficients change, and whether the highest attainable objective value fluctuates more than lower-ranked alternatives. Its argument moves from a continuity theorem through a numerical sensitivity analysis to a comparison of the variances of “truncated maxima,” concluding with an agricultural application. The central distinction is between preserving the identity of the best operating policy and limiting the variability of its returns. A policy can remain best throughout a region of coefficient uncertainty without either its payoff or the ranking of inferior alternatives remaining unchanged.

The authors introduce random errors into the constraint matrix, resource vector, and objective coefficients. These errors are unobservable, but samples of the resulting coefficients are available. Their analysis is restricted to an admissible sample space: problems must have finite, bounded, nondegenerate basic feasible solutions and objective values. Error distributions have bounded domains; the later variance comparison additionally restricts objective coefficients to nonnegative values. These assumptions delimit the analysis rather than establish stability for arbitrary stochastic programs.

The first theorem supplies a local persistence result. If coefficient errors are sufficiently small to preserve the linear independence of the relevant columns, objective values associated with basic selections depend continuously on the coefficients. A selection strictly better than every competitor at the reference point therefore remains better throughout some neighborhood. The authors translate this mathematical statement into an interpretation of operational decisions:

If the linear programming problem is interpreted as one of selecting an operating policy in some sense, one interpretation of this result is the following: if the conditions of the theorem are fulfilled, then an operating policy which is selected at its optimum under the assumption that the coefficient matrix is fixed, nonstochastic and known, will still remain the best operating policy even though there might be some error made in determining the coefficients, or even though the value of the coefficients might change after the policy is put into effect.

Stability here means persistence of an optimal selection, not constancy of the decision quantities or objective value. Strict superiority and nonsingularity make the continuity argument possible; the theorem establishes the existence of a neighborhood without determining its practical size.

The numerical example addresses that second question. With two activities, two resource constraints, and errors confined to the constraint matrix, the authors enumerate basic selections and compare their objective values. They derive inequalities preserving nonsingularity and the superiority of the fourth selection, which is optimal without error. A boundary combination within a twenty-percent coefficient-error range violates an optimality condition:

Thus, the fourth selection is not stable with respect to optimality under 20 percent error for all coefficients.

The authors report that a ten-percent range does preserve this optimum. Yet two inferior selections exchange places within that same region. This is the example’s crucial conceptual payoff: a neighborhood protecting the winner need not protect the complete ordering of feasible alternatives. Sensitivity analysis must therefore specify whether it concerns the optimal basis, its value, or the relative merits of other policies.

The second theoretical movement makes those alternatives explicit:

Now we want to characterize the set of basic feasible solutions apart from the optimum solution and the corresponding values of the objective function.

For each admissible sample, the authors define the regular maximum and then successive maxima obtained by excluding higher-ranked selections. These are the truncated maxima of orders zero, one, and two: best, second-best, and third-best objective values. Tied selections are grouped at the same level. Two geometric lemmas seek to connect this truncation with bounded convex feasible regions obtained by eliminating extreme points. The stochastic comparison concerns sample-wise ranks, however, rather than necessarily following one fixed policy across every realization.

For strictly positive ranked values, expected returns inherit their ordering. The authors then express the best value as the second-best multiplied by a random ratio greater than one. Theorem 2 argues that, under additional conditions, the best value also has greater variance. The proposed economic implication is a return–stability trade-off: sacrificing the highest attainable return may reduce variability. The independence corollary provides the clearest sufficient case, since independence of the ratio and the second-best value gives a positive variance difference directly.

The broader proof warrants qualification. Positivity alone does not establish its asserted inequality between the expectation of a product and the product of expectations; that comparison depends on covariance. Its Taylor-expansion argument also treats omitted terms as having zero expectation without establishing this from the stated assumptions. The general variance ordering should consequently be read as the article’s conditional claim, not as an unrestricted consequence of ranking positive returns.

The concluding application uses annual data from a Hancock County, Iowa, farm for 1928–52. Corn, flax, and oats compete for land, labor, and capital. Prices and resources are fixed, while input coefficients vary; estimated means and standard deviations generate perturbations used in twelve admissible samples. Reported variances decrease from the regular maximum to the second- and third-best levels. The authors also observe:

Further, it holds that the coefficient of variation of the objective function corresponding to the truncated maximum of zero order exceeds those corresponding to the truncated maxima of orders one and two.

The example illustrates the proposed trade-off without establishing its universality. The article’s lasting analytical contribution is its separation of local optimal-policy persistence, changes among inferior alternatives, and statistical dispersion of ranked returns—distinct questions that an undifferentiated appeal to “stability” can obscure.