BLOCK TRIANGULARIZATION OF MULTI-STATE LINEAR PROGRAMS.
Abstract
In this work a variant of the Revised Simplex Method is developed for solving a Multistage Linear Program in which the output of one stage is an input to the next. The method is devised to use the special staircase structure of the original basis. It essentially reduces this basis into a block triangular working basis by a set of elementary column operations. The use of the working basis in place of the original now involves the inversion of the diagonal blocks which are considerably smaller in size (of the order of 1/n th of the original in an n-stage problem). Thus the work involved and the storage required is considerably less. An efficient procedure is developed for updating the working basis. The method consists of interchanging the dropping column to the last stage effected by the pivot on a diagonal block. The updated diagonal blocks are then obtained by a cascade pivot in which the dropping column of each stage is entered into the next until the column leaving the basis is dropped. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1966
- Accession Number
- AD0631810
Entities
People
- Romesh Saigal