A Forward Simplex Method for Staircase Linear Programs
提出并测试了一种求解阶梯结构线性规划的前向算法，该算法通过逐步求解更长的有限期子问题来找到最优解，计算时间与时期数呈线性关系，远优于标准算法的二次或三次关系。
Modelling planning problems that extend over many time periods as linear programs leads to a special structure called a “staircase” or “dynamic” linear program. In this special structure, the nonzero coefficients of the linear program appear in blocks along the “main diagonal” of the coefficient matrix. Such problems are commonly found in economic planning, structural design, agricultural planning, dynamic traffic assignment, production planning, and scheduling models. Forward algorithms provide an approach to solving these dynamic problems by solving successively longer finite horizon subproblems, terminating when a stopping rule can be invoked (or a decision horizon found). Such algorithms are available for a large number of specific models. Here we discuss the implementation and testing of a forward algorithm for solving general dynamic (staircase) linear programs. Tests reported indicate that the solution time is linear in the number of periods of the staircase problem, as compared to a quadratic or cubic relationship for standard linear programming codes. Computational decision horizons are often found, and are responsible for the good performance of the algorithm.