Accession Number : AD0622609

Title :   COVERING PROBLEMS: DUALITY RELATIONS AND A NEW METHOD OF SOLUTION.

Descriptive Note : Technical rept.,

Corporate Author : INFORMATION SYSTEMS LAB UNIV OF MICHIGAN ANN ARBOR

Personal Author(s) : Lawler,Eugene L.

Report Date : MAY 1965

Pagination or Media Count : 33

Abstract : This paper is concerned with 'covering' problems of the following type: Let a strictly positive n-vector c and an mxn matrix A of O's and 1's be given. Let epsilon = (1,1,...,1) be an m-vector of 1's. Find a solution vector y = (y1,y2,...,yn) which will minimize the inner product cy subject to Ay > or = epsilon and y sub j = O or 1 (j=1,2,...,n). There is an interesting duality between the constraints of covering problems and their solutions. This duality is explored in this paper and is found to furnish the basis for a possible new method of solution which is described in detail. (Author)

Descriptors :   (*LINEAR PROGRAMMING, OPTIMIZATION), MATRICES(MATHEMATICS), COMBINATORIAL ANALYSIS, VECTOR ANALYSIS, OPERATIONS RESEARCH, SET THEORY

Distribution Statement : APPROVED FOR PUBLIC RELEASE