Accession Number : AD0737647

Title :   Polyhedral Sets Having a Least Element.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH

Personal Author(s) : Cottle,Richard W. ; Veinott,Arthur F. , Jr

Report Date : 20 AUG 1971

Pagination or Media Count : 15

Abstract : For a fixed m x n matrix A, the authors consider the family of polyhedral sets X(sub b) = (x : Ax > or = b), b belongs to R(sup m), and prove a theorem characterizing in terms of A, the circumstances under which every nonempty X sub b has a least element. In the special case where A contains all the rows of an n x n identity matrix, the conditions are equivalent to A sup T being Leontief. Among the corollaries of the theorem, the authors show the linear complementarity problem always has a unique solution which is at the same time a least element of the corresponding polyhedron if and only if its matrix is square, Leontief, and has positive diagonals. (Author)

Descriptors :   (*DECISION THEORY, DYNAMIC PROGRAMMING), SET THEORY, MATRICES(MATHEMATICS), OPTIMIZATION

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE