A dual projective pivot algorithm for linear programming

被引：14

作者：

Pan, PQ ^{[1
]}

机构：

[1] SE Univ, Dept Math, Nanjing 210018, Peoples R China

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 2004年 / 29卷 / 03期

基金：

中国国家自然科学基金;

关键词：

linear programming; dual algorithm; pseudo-basis; pivot; projection;

D O I：

10.1023/B:COAP.0000044185.69640.54

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Recently, a linear programming problem solver, called dual projective simplex method, was proposed (Pan, Computers and Mathematics with Applications, vol. 35, no. 6, pp. 119-135, 1998). This algorithm requires a crash procedure to provide an initial (normal or deficient) basis. In this paper, it is recast in a more compact form so that it can get itself started from scratch with any dual (basic or nonbasic) feasible solution. A new dual Phase-1 approach for producing such a solution is proposed. Reported are also computational results obtained with a set of standard NETLIB problems.

引用

页码：333 / 346

页数：14

共 25 条

[1] BEALE EML, 1954, P CAMB PHILOS SOC, V50, P513
[2] EFFICIENT SOLUTION OF LARGE-SCALE LINEAR-PROGRAMMING PROBLEMS - SOME ALGORITHMIC TECHNIQUES AND COMPUTATIONAL RESULTS
BENICHOU, M
GAUTHIER, JM
HENTGES, G
RIBIERE, G
[J]. MATHEMATICAL PROGRAMMING, 1977, 13 (03) : 280 - 322
[3] Bjorck A., 1996, NUMERICAL METHODS LE, DOI DOI 10.1137/1.9781611971484
[4] Bland R. G., 1977, Mathematics of Operations Research, V2, P103, DOI 10.1287/moor.2.2.103
[5] OPTIMALITY AND DEGENERACY IN LINEAR PROGRAMMING
Charnes, A.
[J]. ECONOMETRICA, 1952, 20 (02) : 160 - 170
[6] Dantzig G.B., 1955, Pacific J. Math., V5, P183
[7] Dantzig G. B., 1951, Activity analysis of production and allocation
[8] STEEPEST-EDGE SIMPLEX ALGORITHMS FOR LINEAR-PROGRAMMING
FORREST, JJ
GOLDFARB, D
[J]. MATHEMATICAL PROGRAMMING, 1992, 57 (03) : 341 - 374
[9] Gay D.M., 1985, MATH PROGRAMMING SOC, V13, P10
[10] Gill P E, 1986, USERS GUIDE LSSOL VE

← 1 2 3 →