ALGORITHM OF THE BRANCH AND BOUND METHOD FOR SOLVING OPTIMIZATION PROBLEMS WITH A FRACTION-LINEAR OBJECTIVE FUNCTION AND ADDITIONAL COMBINATORY CONSTRAINTS
DOI:
https://doi.org/10.32782/IT/2022-2-9Keywords:
method of branches and bounds, placement, fractional-linear objective function, combinatorial optimizationAbstract
The paper considers a mathematical model of the problem of combinatorial optimization with a fractional-linear objective function on a set of placements. Given that the problem of fractional-linear programming differs from the problem of linear programming only in the form of the objective function, this makes it possible to use known methods of linear programming with a certain modification to solve it. Among the combinatorial methods, the method of branches and limits is important both in practical and theoretical terms. In the work the method of branches and bounds is extended for solving optimization problems on placements with a fractional-linear objective function and additional linear constraints. The main criteria that determined the effectiveness of the method in solving a specific problem were the method of calculating estimates and branching. The algorithm consists of two stages: first, the transition to a relaxed problem (using the appropriate mapping, we move from a fractional-linear optimization problem to a linear one), then a modified method of branches and bounds, based on the ideas of Land and Doig. The combinatorial condition, namely, to be an element of the set of placements, is replaced by a system of constraints describing the general polyhedron of placements. In the work based on the properties of the mapping applied to the problem with a fractional-linear objective function, a number of statements that formed the basis of the method of solving the problem were proved. In particular, the theorem on the equivalence of sets of admissible values of the original and relaxed problems and the theorem on the estimation of admissible areas of problems that are intermediate in the process of solving. The proposed algorithm of the branch-and-bound method for solving optimization problems on a combinatorial set of placements in the case of a fractional-linear objective function seems appropriate to be applied in the future for solving optimization problems with a fractional-linear objective function on other sets.
References
Сергиенко И. В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. К.: Наукова думка, 1981. 288 с.
Стоян Ю. Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. К.: ІСДО, 1993. 188 с.
Ємець О. О., Колєчкіна Л. М. Задачі комбінаторної оптимізації з дробово-лінійними цільовими функціями. К.: Наукова думка, 2005. 117 с.
Емец О. А., Черненко О. А. Оптимизация дробно-линейных функций на размещениях: монография. Київ: Наукова думка, 2011. 154 с.
Донець Г. П., Колєчкіна Л. М. Екстремальні задачі на комбінаторних конфігураціях: монографія. Полтава: РВВ ПУЕТ, 2011. 309 с.
Ємець О.О., Черненко О.О., Чілікіна Т. В., Ольховська О. В. Огляд задач комбінаторної оптимізації визначення рентабельності сільськогосподарського виробництва та методи їх розв’язування. Математичне та комп’ютерне моделювання. Серія: фізико-математичні науки. Випуск 22. 2021. С. 63–74.
Ольховський Д., Ольховська О., Черненко О., Парфьонова Т., Чілікіна Т. Програмний комплекс для розв’язування евклідових комбінаторних оптимізаційних задач точними та наближеними методами. Інформаційні технології та суспільство, 2 (4). 2022. С. 78–87.
Юрій Олексійчук, Дмитро Ольховський, Олена Ольховська, Тетяна Чілікіна, Оксана Черненко, Оксана Оріхівська. Комбінаторна задача про побудову мостів та методи її розв’язання. Вісник Кременчуцького національного університету імені Михайла Остроградського. Кременчук: КРНУ, 2022. Випуск 1(132). С.115–122.
Ємець, О., Черненко, О., Парфьонова, Т., Ольховська, О. Математична модель задачі оптимального розміщення продуктивних сил з врахуванням мінімальної шкоди навколишньому середовищу. Information Technology: Computer Science, Software Engineering and Cyber Security, випуск 1, 2022, С. 14–19.
Корбут А. А., Сигал И.Х., Финкельштейн Ю. Ю. Метод ветвей и границ: обзор теории, алгоритмов, программ и приложений. Math. Operationsch und Statist., Ser. Optimiz. 1977. № 2. P. 253–280.
