Open Access Open Access  Restricted Access Subscription Access

Augmentation of Simplex Algorithm for Linear Programming Problem to Enhance Computational Performance

N.A.A.N. Azlan, A. Saptari, E. Mohamad


Linear programming (LP) has been seen as a tool to solve problem in mathematical way with various methods to perform the solution. Simplex method is one of pioneer methods in dealing with linear problem in LP. It involves step-by-step works towards the solution in its algorithm. Due to this distinctiveness, it has brought up interest in others and few studies were done by researchers to come out with augmentation study in enhancing computational performance of Simplex method in terms of initialization, iteration and termination. In this paper, three studies were recognized in augmenting Simplex algorithm namely Basic Line Search Algorithm (BLSA),

Full Text:



X. Wang, “Review on the Research for Separated Continuous Linear Programming: With Applications on Service Operations”, Hindawi Publishing Corporation, Mathematical Problems In Engineering, 2013.

G. Ambrus, “Linear Programming Duality for Geometers”, University of Toulouse, 2013.

K. Al-Kuhali, Z. M., Zain, and M. I. Hussein, “Production planning of LCDS: Optimal linear programming and sensitivity analysis”, Industrial Engineering Letters, Vol. 2, No.9, 2012.

S. Zhu, G. Ruan, and X. Huang, “Some Fundamental Issues of Basic Line Search Algorithm for Linear Programming Problems”, Taylor & Francis Publisher, Optimization, Vol. 59, No. 8, pp. 1283-1295, 2010.

I. M. Srour, C. T. Haas, and D. P. Morton, “Linear Programming Approach to Optimize Strategic Investment in the Construction Workforce”, Journal of Construction Engineering And Management, Vol. 132, No. 11, pp. 1158-1166, 2006.

S. Karagiannis and D. Apostolou, “Regional Tourism Development Using Linear Programming and Vector Analysis”, Regional Science Inquiry Journal, pp. 25-32, 2010.

A. Goudarzi, M. Kazemi, A.G. Swanson, and M. H. Nabavi, “DC Optimal Power Flow Through The Linear Programming – In Context of Smart Grid”, 24th Southern African Universities Power Engineering Conference, Vereeniging, South Africa, 2016.

D. Bienstock, “Potential Function Methods For Approximately Solving Linear Programming Problems: Theory And Practice”, Columbia University, 2001.

O. Guler, C. Roos, T. Terlaky, and J. –Ph. Vial, “A Survey of the Implications of the Behavior of the Central Path for the Duality Theory of Linear Programming”, Management Science, 1995.

N. T. Vinh, D. S. Kim, N. N. Tam, and N. D. Yen, “Duality Gap Function in Infinite Dimensional Linear Programming”, Journal of Mathematical Analysis and Applications, pp. 1-15, 2016.

N. A. Suleiman and M. A. Nawkhass, “A New Modified Simplex Method to Solve Quadratic Fractional Programming Problem and Compared it to a Conventional Simplex Method by Using Pseudoaffinity of Quadratic Fractional Functions”, Applied Mathematical Sciences, Vol. 7, No. 76, pp. 3749-3764 , 2013.

M. J. Todd, “The Many Facets of Linear Programming”, Math. Program., Ser. B, 2001.

H. A. Taha, “Operations Research- An Introduction Ninth Edition”, Pearson Education, Inc., Prentice Hall Publishing, 2011.

M. Imtiaz, N. Touheed and S. Inayatullah, “Artificial Free Clone of Simplex Method for Feasibility”, Publication in Siam Review, 2013.

J. K. T. D. Costa, K. G. Angilelli, K. R. Spacino, E. T. daSilva, L. R. C. Silva, and D. Borsato, “Application of the Multiresponse Optimization Simplex Method to the Biodiesel B100 Obtaining Process”, Semina: Ciências Exatas e Tecnológicas, Londrina, Vol. 37, No. 1, p. 107-118, 2016.

H. Suprajitno and I. Mohd, “Linear Programming with Interval Arithmetic”, Int. J. Contemp. Math. Sciences, Vol. 5, No. 7, pp. 323 – 332, 2010.

M. A. Schulze, “Linear Programming for Optimization”, Perceptive Scientific Instruments, Inc., 2000.

H. Luh and R. Tsaih, “An Efficient Search Direction For Linear Programming Problems”, Computers & Operations Research, No. 29 pp. 195-203, 2002.

N. V. Vaidya and N. N. Kasturiwale, “Application of Quick Simplex Method (A New Approach) on Two Phase Method”, British Journal of Mathematics & Computer Science, Vol. 16(1), pp. 1-15, 2016.

A. Obot, U. M. Anthony and S. Ozuomba “A Novel Tabular Form of the Simplex Method for Solving Linear Programming Problems “, International journal of Computer Science & Network Solutions, 2016-vol. 4, no. 2, 2016.

A. L. Ramírez, O. Buitrago, R. A. Britto and A. Fedossova, “A New Algorithm For Solving Linear Programming Problems”, Ingenieria e Investigación, Vol. 32, No. 2 , pp. 68-73, 2012.

P. A. Ihom, J. Jatau and H. Muhammad, “The Use of LP Simplex Method in the Determination of the Minimized Cost of a Newly Developed Core Binder”, Leonardo Electronic Journal of Practices and Technologies ISSN 1583-1078, pp. 155-162, 2007.

N. V. Stojkovic, P. S. Stanimirovic, M. D. Petkovic and D. S. Milojkovic, “On the Simplex Algorithm Initializing”, Hindawi Publishing Corporation Abstract and Applied Analysis, 2012.

H. Arsham, “A Computationally Stable Solution Algorithm For Linear Programs”, Applied Mathematics and Computation 188, pp. 1549-1561, 2007.

S. Inayatullah, N. Touheed, and M. Imtiaz, “A Streamlined Artificial Variable Free Version of Simplex Method”, PLoS ONE 10(3): e0116156.doi:10.1371/journal.pone.0116156, 2015.

© Journal of Advanced Manufacturing Technology