Accession Number : AD0828258
Title : AN ALGORITHM FOR THE SOLUTION OF LINEAR PROGRAMMING PROBLEMS USING STEP-BY-STEP ADDITION OF CONSTRAINTS.
Descriptive Note : Master's thesis,
Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Personal Author(s) : Fenn, Michael Robert
Report Date : DEC 1967
Pagination or Media Count : 51
Abstract : As linear programming techniques find applications in more diverse fields, the problem of solution time becomes increasingly important. A variation of the revised simplex algorithm, in which the constraints are added in a step-by-step fashion, is investigated as a potentially faster solution technique. A computational procedure, coded for the IBM 360 computer, is developed to compare this algorithm with the standard two-phase revised simplex algorithm. A limited number of problems, including several randomly generated problems, is solved by each of the two methods. The resulting comparison of solution times indicates that a significant improvement is obtained by the use of the procedure of step-by-step addition of constraints. (Author)
Descriptors : (*LINEAR PROGRAMMING, PROBLEM SOLVING), (*COMPUTER PROGRAMMING, LINEAR PROGRAMMING), SIMPLEX METHOD, NUMERICAL ANALYSIS, MATRICES(MATHEMATICS), STATISTICAL TESTS, DIGITAL COMPUTERS, COMPUTER PROGRAMS, FLOW CHARTING, ALGORITHMS, EFFICIENCY, THESES.
Subject Categories : Operations Research
Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE