
Accession Number : AD0658740
Title : DUALITY IN DISCRETE PROGRAMMING.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CALIF OPERATIONS RESEARCH HOUSE
Personal Author(s) : Balas,Egon
Report Date : AUG 1967
Pagination or Media Count : 36
Abstract : A duality theory is proposed for discrete programming. The mixedinteger programming problem is shown to be a special case of a minimax problem with a Lagrangiantype objective function, linear constraints, and some variables constrained to belong to an arbitrary set of real numbers. The dual of this problem is formulated as a problem of the same type, and such that the dual of the dual is the primal. It is shown that the primal has an optimal solution if and only if the dual has one, and in this case the values of their respective objective functions are equal. An optimal solution to the primal and the dual is shown to have the saddlepoint property of optimal solutions to a pair of dual linear (and certain nonlinear) programs. A certain type of complementary slackness is shown to hold. Conditions for the uniqueness of a solution are examined. Finally, an economic interpretation is outlined in terms of a generalized shadowprince system for mixedinteger programs.
Descriptors : (*LINEAR PROGRAMMING, PROBLEM SOLVING), OPTIMIZATION, THEOREMS, STEEPEST DESCENT METHOD, REAL NUMBERS, MINIMAX TECHNIQUE, DECISION MAKING, ECONOMICS, MATHEMATICAL PROGRAMMING, OPERATIONS RESEARCH
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE