The Simplex Method for Dynamic Linear Programs

Propoi, A.I. & Krivonozhko, V.E. (1978). The Simplex Method for Dynamic Linear Programs. IIASA Research Report. IIASA, Laxenburg, Austria: RR-78-014

Preview

Text RR-78-014.pdf Download (1MB) | Preview

Abstract

This paper presents an extension of the simplex method, the basic method for solution of dynamic linear programming problems. The paper consists of three parts. Part I, "dual systems of DLP", concerns theoretical properties of the problem, primarily, duality relations; Part II, "the dynamic simplex method: general approach" describes the idea and the theory of the method; and Part III, "a basis factorization approach", gives a complete description of the algorithm, as well as the connection with the basis factorization approach. Part III also includes a numerical example that is not trivial for a general LP algorithm but is solved very easily by using the dynamic simplex method. Part II is written in a language more familiar to control theory specialists, Part III is closer to linear programming. All parts are written as independent papers with their own references and thus can be read independently. However, the whole paper comprises a theory of finite-step methods for DLP. The next development of the research might be first numerical tests on the behavior of the method and thus a judgement of its efficiency, and second extensions of the approach to other classes of strucured linear programming (for example, to DLP problems of the transportation type).

Actions (login required)

View Item