BLOCK TRIANGULARIZATION OF MULTI-STATE LINEAR PROGRAMS.
OPERATIONS RESEARCH CENTER UNIV OF CALIF BERKELEY
Pagination or Media Count:
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 1n 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
- Operations Research