AN OUT-OF-KILTER METHOD FOR MINIMAL COST FLOW PROBLEMS

Abstract

A method of solving minimal cost network flow problems is described. This method begins with any circulation, feasible or not, and an arbitrary pricing vector. A labeling procedure is then used to adjust 'out-of-kilter' arcs, that is, arcs that fail to satisfy the optimality properties. It is shown that the method terminates in a finite number of steps, and that in so doing, the status of no arc of the network (as measured by certain 'kilter numbers') is worsened at any step.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 05, 1960
Accession Number
AD0615884

Entities

People

  • D. R. Fulkerson

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Combinatorial Analysis
  • Computations
  • Contrast
  • Corporations
  • Equations
  • Heuristic Methods
  • Inequalities
  • Linear Programming
  • Notation
  • Sequences
  • Simplex Method
  • Terminals
  • Transportation
  • Verification

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Aerodynamics.
  • Economics