Полиномиальный метод решения безусловной дробно-линейной задачи комбинаторной оптимизации на размещениях

Abstract

Розглянуто розв’язування дробово-лінійної задачі комбінаторної оптимізації на загальній множині розміщень. Запропоновано й обґрунтовано метод, який передбачає розв’язування скінченної послідовності лінійних безумовних задач комбінаторної оптимізації на розміщеннях. Отримано теоретичні оцінки сформульованого алгоритму, доведено його поліноміальність.The article deals with the solving of a linear fractional problem of combinatorial optimization on the general set of arrangements. Authors propose and substantiate the method which provides solving of finite sequence of linear unconditional problems of combinatorial optimization on arrangements. Theoretical estimates of the formulated algorithm are received, its polynomiality is proved.