GENERALIZED UPPER BOUNDING TECHNIQUES FOR LINEAR PROGRAMMING, 2

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1965
Accession Number
AD0614577

Entities

People

  • George Bernard Dantzig
  • Richard M. Van Slyke

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Coefficients
  • Computations
  • Equations
  • Iterations
  • Linear Programming
  • Operations Research
  • Simplex Method
  • United States
  • United States Government
  • Universities
  • Vans

Fields of Study

  • Mathematics

Readers

  • Calculus or Mathematical Analysis
  • Operations Research