Boundedness relations for linear constraint sets

AbstractIn the first three sections, relationships between the feasible sets of primaldual linear programming pairs are developed. A theorem of Clark [2] says that, for a linear programming pair in standard symmetric form, whenever the primal feasible set is nonempty and bounded the dual set is unbounded. We extend this theorem by showing that when the primal feasible set is nonempty it is bounded if and only if, in the dual feasible set, all variables, including slacks, are unbounded. We show, in fact, that, whenever a linear program pair in standard symmetric form has optimal solutions, a primal variable is bounded if and only if its complementary dual variable is unbounded; therefore the total number of bounded variables (primal and dual, including slacks) must always be equal to the total number of unbounded variables, and this common value must be equal to the total number of constraints, primal and dual. Results along similar lines are obtained for the primal-dual programs in the nonstandard form, i,e., when some constraints may be equalities or some of the variables may be unrestricted in sign. The latter results sharpen some of those of Charnes, Cooper, and Thompson [1].In the final section the same methods are used to obtain results concerning the bounded and unbounded variables in the solution sets for linear inequalities when the matrix is “copositive” or “adequate.” This extends the work of Lemke [9] and of Cottle [3]