A Non-Iterative Basis Selection Algorithm for Linear Programming Using Directional Cosines
DOI:
https://doi.org/10.63746/njtd.v23i2.4261Keywords:
Linear programming, non-iterative algorithm, directional cosine alignment, Dantzig matrix, geometric optimizationAbstract
This paper presents a geometry-based non-iterative method for solving linear programming (LP) problems that have either three constraints or three decision variables. Instead of using iterative procedures like the simplex, Interior-point, and Criss-Cross methods, the method finds a basic feasible solution consistent with optimal results for the class of problems considered. The algorithm measures the directional cosines alignment between each constraint vector and the resource vector, picks the three most aligned constraints to form a 3×3 Dantzig matrix, and solves that small linear system for the decision variables and objective value. The algorithm was tested on standard textbook examples, and the results match conventional solvers exactly, but are obtained without pivoting or tableau updates, just one matrix inversion. The approach is fast and provides a very clear geometric visualization, making it useful as a pedagogical tool or as an initialization step in larger routines.
References
Corriou, J. P. (2021). Linear programming. In Numerical methods and optimization (Vol. 187, pp. 1–24). Springer, Cham. https://doi.org/10.1007/978-3-030-89366-8_10
Dantzig, G. B. (1947). Linear programming. Princeton University Press.
Fábián, C. I., Papp, O., & Eretnek, K. (2013). Implementing the simplex method as a cutting-plane method, with a view to regularization. Computational Optimization and Applications, 56(2), 343–368. https://doi.org/10.1007/s10589-013-9565-9
Golden, B., Schrage, L., Shier, D. Apergi L.A. (2024). The unexpected power of linear programming: an updated collection of surprising applications. Annals of Operation Research, 343, 573–605. https://doi.org/10.1007/s10479-024-06245-5
Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4(4), 373–395. https://doi.org/10.1145/800057.808695
Li, W. (2010). Practical criss-cross method for linear programming. In L. Zhang, B. L. Lu, & J. Kwok (Eds.), Advances in neural networks – ISNN 2010 (Lecture Notes in Computer Science, Vol. 6063, pp. 234–243). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13278-0_29
Loera, J., Kafer, S., & Sanità, L. (2021). On the simplex method for 0/1-polytopes. Mathematics of Operations Research, 50(4), 1398–1420. https://doi.org/10.1287/moor.2021.0345
Ma, Y., Zhang, L., & Pan, P. (2015). Criss-cross algorithm based on the most-obtuse-angle rule and deficient basis. Applied Mathematics and Computation, 268, 439–449. https://doi.org/10.1016/j.amc.2015.06.080
Pan, P. Q. (2014). Interior-point method. In Linear programming computation. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40754-3_9
Sharma, J. K. (2009). Operations research: Theory and applications (4th ed.). Macmillan.
Sokolinsky, L. B., & Sokolinskaya, I. M. (2023). Apex method: A new scalable iterative method for linear programming. Mathematics, 11(7), 1654. https://doi.org/10.3390/math11071654
Srinivasan, R. (2014). Introduction to linear programming. In Strategic business decisions. Springer, New Delhi. https://doi.org/10.1007/978-81-322-1901-9_2
Stroud, K. A. (2011). Advanced engineering mathematics (5th ed.). Palgrave Macmillan.
Vasant, P. M. (2003). Application of fuzzy linear programming in production planning. Fuzzy Optimization and Decision Making, 2(3), 229–241. https://doi.org/10.1023/A:1025094504415
Zionts, S. (1969). The criss-cross method for solving linear programming problems. Management Science, 15(7), 426–445. https://doi.org/10.1287/mnsc.15.7.426
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Nigerian Journal of Technological Development
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
In accordance with the Copyright Act of 1976, which became effective January 1, 1978, the following statement signed by each author must accompany the manuscript submitted: "I, the undersigned author, transfer all copyright ownership of the manuscript referenced above to the Nigerian Journal of Technological Development, in the event the work is published. I warrant that the article is original, does not infringe upon any copyright or other proprietary right of any third party, is not under consideration by another journal, and has not been published previously. I have reviewed and approved the submitted version of the manuscript and agree to its publication in the Nigerian Journal of Technological Development." A copyright transfer form can be downloaded from the NJTD Website (http://njtd.com.ng/index.php/njtd). Author(s) will be consulted, whenever possible, regarding republication of material. All authors must have access to the data presented, and the authors and sponsor (if applicable) must agree to share original data with the editor if requested.
