AN ALGORITHM FOR THE SOLUTION OF LINEAR PROGRAMMING PROBLEMS USING STEP-BY-STEP ADDITION OF CONSTRAINTS.

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)

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1967
Accession Number
AD0828258

Entities

People

  • Michael Robert Fenn

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Computers
  • Evolutionary Algorithms
  • Heuristic Methods
  • Linear Programming
  • Mathematics
  • Simplex Method
  • Standards

Fields of Study

  • Computer science

Readers

  • Computational Modeling and Simulation
  • Operations Research