A CLASS OF LINEAR PROGRAMMING PROBLEMS REQUIRING A LARGE NUMBER OF ITERATIONS

Abstract

A coordinate-free description of the simplex algorithm (for nondegenerate linear programming problems) is supplied, and is used to show that the number of iterations can be larger than was previously known. For 0 < m < n, there is constructed a nondegenerate linear programming problem whose bounded (n - m)-dimensional feasible region is defined by means of m linear equality constraints in n nonnegative variables, and in which, after starting from the worst choice of an initial feasible vertex, m(n - m - l) + 1 simplex iterations are required in order to reach the optimal vertex. It is conjectured that this is the maximum possible number of iterations (for arbitrary 0 < m < n), but the conjecture is proved only for n < m + 4. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1964
Accession Number
AD0609586

Entities

People

  • Victor Klee

Organizations

  • Boeing

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Programs
  • Identities
  • Inequalities
  • Iterations
  • Linear Programming
  • Mathematical Analysis
  • Mathematics
  • Numbers
  • Numerical Analysis
  • Permutations
  • Real Numbers
  • Sequences
  • Simplex Method

Fields of Study

  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.
  • Operations Research