Решение условной задачи оптимизации дробно-линейной целевой функции на множестве размещений методом ветвей и границ

Abstract

Розглянуто точний комбінаторний метод розв’язування задачі оптимізації на розміщеннях з дробово-лінійною функцією цілі та додатковими лінійними обмеженнями. Побудований алгоритм гілок та меж для розв’язування такої задачі ґрунтується на ідеях А. Ленд та A. Дойг. Наведено приклад розв’язування оптимізаційної задачі з дробово-лінійною цільовою функцією на розміщеннях запропонованим алгоритмом.

The exact combinatorial method of solving the problem of optimization on arrangements with a linear-fractional objective function and additional linear constraints is considerd. The branch and bound algorithm constructed is based on the ideas of Land and Doig. An illustrative example of solving the optimization problem with a linear-fractional objective function on arrangements with the algorithm is presented.