Комбинаторный подход к решению одного класса задач размещения

Гуляницкий Л.Ф., Малышко С.А.

Киев, 1988. – 19 с. – (Препр/ АН УССР. Ин-т кибернетики им. В.М. Глушкова; 88-32).

Анотація:

Рассмотрен класс задач размещения прямоугольников одинаковой ширины на полубесконечной ленте, раздененной на полосы и содержащей запрещенные области. Предложена формализация этих задач в виде задач оптимизации на перестановках, доказана адекватность возникающих математических моделей. Предложены два подхода к определению достижимой нижней границы целевой функции построенных задач на перестановках. Разработан и исследован локально-оптимальный метод, который позволяет получать приближенные рещения с оценкой их точности и распознавать глобальный оптимум. На основании разработанной общей схемы метода предложеноо четыре алгоритма оптимизации. Приведены результаты обширного численного эксперимента.

Завантажити файл публікації