Accession Number:

AD0614577

Title:

GENERALIZED UPPER BOUNDING TECHNIQUES FOR LINEAR PROGRAMMING, 2

Descriptive Note:

Corporate Author:

CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER

Report Date:

1965-02-01

Pagination or Media Count:

26.0

Abstract:

A variant of the simplex method is given for solving linear programs with M L equations, L of which have the property that each variable has at most one nonzero coefficient. Special cases include transportation problems, programs with upper bounded variables, assignment and weighted distribution problems. The algorithm described uses a working basis of M rows for pivoting, pricing, and inversion which for large L can result in a substantial reduction of computation. This working basis is only M x M and is a further reduction of the size found in an earlier version, see AD0610950. Unfortunately, to achieve this reduction, row as well as column transformations must now be made.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE