We present a new form of the station cone approach for solving linear programming problems in this study. It determines the entering variables using a succession of inside points Ok. The number of these interior points is limited, and they all tend to gravitate toward the best option. A simplex pivot is used to calculate the new vertex at each step. If the number of points Ok is limited by a polynomial function, the proposed technique will run in polynomial time. The paper's second goal is to do experimental computations and compare them to simplex and dual simplex approaches. The number of pivots in the station cone method is fewer than 30 to 50 times that of the dual method, according to the data. The number of pivots in the dual algorithm grows significantly faster than the number of pivots in the station cone algorithm as the number of variables n and constraints m increase. The computational trials with n 500 and m 2000 led to this conclusion. We look for situations with n = 2, m = 100 000, and n = 3, m = 200 000, in particular. The station cone method is given no more than 16 pivots in the scenario when n = 2 and m = 100 000. The station cone algorithm contains 23 pivots for n = 3 and m = 200 000. The test validated the pattern that the number of pivots in the simplex algorithm grows faster than the number of pivots in the station cone method as the number of variables and constraints grows.
Author(s) DetailsC. N. Nguyen
Hanoi Institute of Mathematics, 18 Hoang Quoc Viet, Hanoi, Vietnam.
H. T. Le
Faculty of Informatics Technology, University of Mining and Geology, Hanoi, Vietnam.
View Book :- https://stm.bookpi.org/TPMCS-V10/article/view/1082
No comments:
Post a Comment