The parallel simplex-method achievements for errorless solving of linear programming problems

Бесплатный доступ

Techniques of obtaining exact solutions of linear programming problems are subjects of this paper. Absolute accuracy are arrived at implementation of simplex-algorithm with exact rational-fractional computation. In this case if m is minimal of problem dimensions, and 1 is number of bits for a source data item then space complexity are no more 41m4 + o(m3), one iteration time complexity are no more O(1m4), and paralleling efficiency (i.e. ratio of acceleration to number of processors) asymptotical estimate are 100%.

Linear programming, simplex method, distributed computing, parallel computing, rational computations, optimization, arbitrary precision, interval arithmetic

Короткий адрес: https://sciup.org/147159094

IDR: 147159094

Статья научная