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