Accession Number:

AD0609586

Title:

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

Descriptive Note:

Corporate Author:

BOEING SCIENTIFIC RESEARCH LABS SEATTLE WA

Personal Author(s):

Report Date:

1964-11-01

Pagination or Media Count:

24.0

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, mn - 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

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE