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
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE