Accession Number : AD0631810


Title :   BLOCK TRIANGULARIZATION OF MULTI-STATE LINEAR PROGRAMS.


Descriptive Note : Research rept.,


Corporate Author : OPERATIONS RESEARCH CENTER UNIV OF CALIF BERKELEY


Personal Author(s) : Saigal,Romesh


Report Date : MAR 1966


Pagination or Media Count : 42


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)


Descriptors :   (*LINEAR PROGRAMMING, *MATRICES(MATHEMATICS)), ALGORITHMS, COMBINATORIAL ANALYSIS


Subject Categories : OPERATIONS RESEARCH


Distribution Statement : APPROVED FOR PUBLIC RELEASE