Урахування оцінок мінімуму цільової функції при розв’язуванні дробово-лінійних безумовних задач комбінаторної оптимізації на розміщення: Fìz.-mat. model. ìnf. tehnol. 2021, 32:32-36

• Datum: 2021
• 1. Verfasser: Barbolina, Tetiana
• Format: Artikel
• Sprache: Ukrainisch
• Veröffentlicht: Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2021
• Schlagworte: евклідова комбінаторна оптимізація; дробово-лінійна оптимізація; задачі комбінаторної оптимізації; поліноміальний алгоритм
• Online Zugang: https://www.fmmit.lviv.ua/index.php/fmmit/article/view/155
• Назва журналу: Physico-mathematical modeling and informational technologies

The paper is devoted to the study of one class of Euclidean combinatorial optimization problems — combinatorial optimization problems on the general set of arrangements with linear fractional objective function and without additional (non-combinatorial) constraints. The paper substantiates the improvement of the polynomial algorithm for solving the specified class of problems. This algorithm foresees solving a finite sequence of linear unconstrained problems of combinatorial optimization on arrangements. The modification of the algorithm is based on the use of estimates of the objective function on the feasible set. This allows to exclude some of the problems from consideration and reduce the number of problems to be solved. The numerical experiments confirm the practical efficiency of the proposed approach. References Papadimitriou, C. H., Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Courier Corporation. Korte, B. H., Vygen, J. (2008). Combinatorial optimization: theory and algorithms, Berlin Heidelberg: Springer. Stoyan, Yu. G., Iemets, O. O. (1993). Theory and methods of Euclidean combinatorial optimization. Kyiv: Instytut systemnykh doslidzhen osvity. Iemets, O. A., Barbolina, T. N. (2017). Polynomial method for solving unconditional linear-fractional problem of combinatorial optimization on arrangements. Journal of Automation and Information Sciences, 49(3), 46-56. DOI doi.org/10.1615/jautomatinfscien.v49.i3.60 Barbolina, T. (2020). Improvement of the polynomial method for solving unconstrained linear-fractional combinatorial optimization problems on arrangements. Collection of researcher works of teachers, students, graduate students of the faculty of physics and mathematics, Poltava: Astraya Iemets, O. A., Barbolina, T. N. (2017). Properties of combinatorial optimization unconstrained problems on arrangements with linear and linear-fractional objective functions. Journal of Automation and Information Sciences, 49(1), 41 – 52. DOI doi.org/10.1615/jautomatinfscien.v49.i1.40