全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

The Pivot Adaptive Method for Solving Linear Programming Problems

DOI: 10.4236/ajor.2018.82008, PP. 92-111

Keywords: Optimization, Linear Programming, Simplex Method, Adaptive Method

Full-Text   Cite this paper   Add to My Lib

Abstract:

A new variant of the Adaptive Method (AM) of Gabasov is presented, to minimize the computation time. Unlike the original method and its some variants, we need not to compute the inverse of the basic matrix at each iteration, or to solve the linear systems with the basic matrix. In fact, to compute the new support feasible solution, the simplex pivoting rule is used by introducing a matrix that we will define. This variant is called “the Pivot Adaptive Method” (PAM); it allows presenting the resolution of a given problem under the shape of successive tables as we will see in example. The proofs that are not given by Gabasov will also be presented here, namely the proofs for the theorem of the optimality criterion and for the theorem of existence of an optimal support, and at the end, a brief comparison between our method and the Simplex Method will be given.

References

[1]  Dantzig, G.B. (1951) Minimization of a Linear Function of Variables Subject to Linear Inequalities. John Wiley, New York.
[2]  Minoux, M. (1983) Programmation mathématique, Théorie et al gorithmes, Tome 1, Dunod.
[3]  Culioli, J.C. (1994) Introduction à l’optimisation, Elipse.
[4]  Dantzig, G.B. (1963) Linear Programming and Extensions. Princeton University Press, Princeton. https://doi.org/10.1515/9781400884179
[5]  Gabasov, R. and Kirillova, F.M. (1977, 1978, 1980) Method of Linear Programming. Vol. 1, 2 and 3, BGU Press, Minsk. (In Russian)
[6]  Bland, R.G. (1977) New Finite Pivoting Rules for the Simplex Method. Mathematics of Operations Research, 2, 103-107.
[7]  Klee, V. and Minty, G.J. (1972) How Good Is the Simplex Algorithm? In: Shisha III, O., Ed., Inequalities, Academic Press, New York, 159-175.
[8]  Khachiyan, L.G. (1979) A Polynomial Algorithm in Linear Programming. Soviet Mathematics Doklady, 20, 191-194.
[9]  Karmarkar, N.K. (1984) A New Polynomial-Time Algorithm for Linear Programming. Combinatorica, 4, 373-395.
[10]  Kojima, M., Megiddo, N., Noma, T. and Yoshise, A. (1989) A Unified Approach to Interior Point Algorithms for Linear Programming. In: Megiddo, N., Ed., Progress in Mathematical Programming: Interior Point and Related Methods, Springer Verlag, New York, 29-47.
[11]  Ye, Y. (1997) Interior Point Algorithms, Theory and Analysis. John Wiley and Sons, Chichester.
[12]  Vanderbei, R.J. and Shanno, D.F. (1999) An Interior-Point Algorithm for Nonconvex Nonlinear Programming. Computational Optimization and Applications, 13, 231-252.
[13]  Peng, J., Roos, C. and Terlaky, T. (2001) A New and Efficient Large-Update Interior-Point Method for Linear Optimization. Journal of Computational Technologies, 6, 61A-80.
[14]  Cafieri, S., Dapuzzo, M., Marino, M., Mucherino, A. and Toraldo, G. (2006) Interior Point Solver for Large-Scale Quadratic Programming Problems with Bound Constraints. Journal of Optimization Theory and Applications, 129, 55-75.
[15]  Gabasov, R.F. (1994) Adaptive Method for Solving Linear Programming Problems. University of Bruxelles, Bruxelles.
[16]  Gabasov, R.F. (1994) Adaptive Method for Solving Linear Programming Problems. University of Karlsruhe, Institute of Statistics and Mathematics, Karlsruhe.
[17]  Gabasov, R., Kirillova, F.M. and Prischepova, S.V. (1995) Optimal Feedback Control. Springer-Verlag, London.
[18]  Gabasov, R., Kirillova, F.M. and Kostyukova, O.I. (1979) A Method of Solving General Linear Programming Problems. Doklady AN BSSR, 23, 197-200. (In Russian)
[19]  Kostina, E. (2002) The Long Step Rule in the Bounded-Variable Dual Simplex Method: Numerical Experiments. Mathematical Methods of Operation Research, 55, 413-429.
[20]  Radjef, S. and Bibi, M.O. (2011) An Effective Generalization of the Direct Support Method. Mathematical Problems in Engineering, 2011, Article ID: 374390.
[21]  Balashevich, N.V., Gabasov, R. and Kirillova, F.M. (2000) Numerical Methods of Program and Positional Optimization of the Linear Control Systems. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 40, 838-859.
[22]  Bentobache, M. and Bibi, M.O. (2012) A Two-Phase Support Method for Solving Linear Programs: Numerical Experiments. Mathematical Problems in Engineering, 2012, Article ID: 482193.
[23]  Bibi, M.O. and Bentobache, M. (2015) A Hybrid Direction Algorithm for Solving Linear Programs. International Journal of Computer Mathematics, 92, 201-216.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133