Постановка одномерной задачи максимального покрытия. Графическое представление для задачи одномерного раскроя и максимального покрытия. Суть однопроходных простых эвристик, на примере задачи упаковки. Метод решения, структограмма и пошаговый алгоритм.
Аннотация к работе
Простые однопроходные эвристики для решения одномерной задачи покрытияДля проблемы одномерного максимального покрытия имеем следующую задачу: Задана: длинна L покрываемого материала (формы) и имеется m исходных элементов (деталей) заданной длинны li, и в заданном количестве bi, . Требуется найти план покрытия максимального количества форм исходными деталями, т.е. найти матрицу А=[ ], компоненты которой указывают число i-х предметов j-ой упаковке и максимизирующую количество N покрытых форм: , , , , , . Для офф-лайн алгоритмов важно, чтобы задачи были статическими, онлайн алгоритмы могул применятся, когда предметы динамически прибывают на место упаковки или имеют случайные параметры веса (длины). В контейнере емкости L=100 требуется упаковать 7 предметов, веса которых заданы вектором w=(40, 9, 21, 37, 20, 53, 17).Определить с помощью алгоритма NF необходимое количество контейнеров для размещения всех предметов. Далее в зависимости от выбранной эвристики мы следуем алгоритмам и покрываем форму деталями, в последовательностях определенных выбранной эвристикой.