
Accession Number : AD0631810
Title : BLOCK TRIANGULARIZATION OF MULTISTATE 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 nstage 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