Курсовая работа: Оптимальный раскрой материала с максимальной прибылью
Для решения поставленной задачи рассмотрим функцию
(4)
xÎXl
где через Xi обозначено множество неотрицательных векторов х, отвечающих раскроям, в которых общая длина заготовок не превосходит длины l. Пустьl0 = min li , где i =1…m.
Тогда при всех lÎ[0,l0 ] соответствующие множества Xl состоят из одного нулевого элемента и, следовательно, f(l) = 0 для всех таких l. Для lÎ[0,L0 ], справедливы следующие рекуррентные соотношения:
,(5)
iÎIl
где через Il обозначено множество тех i, при которых li £l.
Опираясь на рекуррентные соотношения (5), можно для решения задачи предложить простой численный метод, представляющий собой перебор всех допустимых раскроев. Реализация всего процесса основывается на двух этапах:
Первый этап
На первом этапе осуществляется так называемый прямой ход: по формулам (5) для всех l =
последовательно вычисляются функции f(l) и при этом фиксируются индексы i(l), при которых достигается максимум в выражении (5). Получаемая при этом информация l, f(l) и i(l) запоминается и построчно записывается в таблицу:
| l | l0 | l0 + 1 | l0 + 2 | … | L |
| f(l) | f(l0 ) | f(l0 + 1) | f(l0 + 2) | … | f(L) |
| i(l) | i(l0 ) | i(l0 + 1) | i(l0 + 2) | … | i(L) |
Второй этап
На втором этапе осуществляется так называемый обратный ход: для получения искомого вектора х (1), для которого выполняется равенство m(x) = f(L), в раскрой в первую очередь включаются заготовка с номером i(l1 ), где l1 = L, и подсчитывается значение l2 = l1 -li ( l 1) .
Если l2 ³l0 , то в раскрой включается заготовка с номером i(l2 ) и подсчитывается значениеl3 =l2 -li ( l 2) и т.д. Так как при каждом k³1 очевидно, что lk +1 £lk -l0 , то через конечное число описанных шагов окажется, что lk +1 < l0. На этом генерирование искомого раскроя заканчивается и выводится результат.
3. Описание алгоритма
1. Определяется текущее значение длины раскроя l от минимальной длины детали до длины материала.
2. Вычисляется максимальный индекс (номер) детали, добавление которой возможно.
3. Если нет деталей, которые можно добавить в раскрой, то проверяется не достигнут ли максимум цены раскроя для текущего значения длины раскроя l.
Если максимум достигнут, то он запоминается. Последняя добавленная деталь удаляется из раскроя и добавляется следующая (п. 4). Если нет деталей которые можно добавить в раскрой, происходит выход из цикла.
4. Запоминается текущий раскрой. Длина раскроя уменьшается на длину детали. Цена раскроя увеличивается на цену детали. Определяются детали, добавление которых в раскрой возможно (п. 2).
5. Берется начальная длина раскроя, равная длине материала. Берется деталь, на которой был достигнут максимум для данной длины материала. Из длины материала вычитается длина детали, к стоимости раскроя прибавляется цена детали. П.5 повторяется, пока есть детали, добавление которых к раскрою не превысит длины материала.
6. Зная количество деталей для каждого их вида, составляющих рациональный раскрой, формируется искомый вектор х.
//процедура вычисления рационального раскроя
procedure searchRationalCut(
materialLength: integer;
detailAmount: integer;
var details: array of TDetail;
var x: array of integer);
var
l0, l, i: integer;
currCut: TCutRecord;