Общие сведения
Опишем общую задачу линейного (одномерного) раскроя материала.
Необходимо из кусков материала длиной d i ( i = 1, 2, …, m ) выкроить заготовки длиной a j ( j = 1, 2, …, n ) в указанном ассортиментном наборе, заданном вектор-столбцом [b jo]. Требуется определить оптимальный план раскроя материала, т.е. получить максимум ассортиментных наборов m с минимальными отходами т.е. найти матрицу [x i j ] ( количество j - х заготовок в i - х кусках).
Рассмотрим в качестве основного критерий максимума ассортиментных наборов при заданном ограничении по минимуму отходов (для всех видов раскроя есть норматив отходов Z). Эта разница в критериях приводит к разнице в методах решения задачи.
На практике, если из кусков материала выкроить заготовки одного вида (одной длины), то критерий максимума ассортиментных наборов совпадает с минимумом отходов и задача решается быстро без компьютера. Если имеется один кусок материала и на нем можно разместить один-два ассортиментных набора, то критерий минимума отходов является определяющим. Наиболее часто встречается другой случай, когда имеется много кусков материала и требуется выкроить много ассортиментных наборов. В этом случае критерий максимума ассортиментных наборов является определяющим.
Пусть Δ i - отходы, получаемые от i - го куска материала. Тогда сумма отходов равна
= 
- 
(2.1)
Итак, требуется найти матрицу оптимального решения [xijо], максимизирующую линейную форму L при условиях
L = m (2.2)
aj x i j 
d i (2.3)
x i j ³ b jo m (2.4)x i j ³ 0 (2.5) j > 0 , b j o > 0 (2.6) Δ i = d i - £ Z (2.7)
В принципе это задача линейного программирования. Однако большинство реальных задач раскроя имеют нелинейные эффекты, которые резко усложняют задачу.
Например, заготовки после разреза дополнительно обрабатываются. С тем, чтобы при разрезе не допустить брака, между заготовками при раскрое вводятся перемычки (припуски, зазоры и т.п.) между заготовками с определяющим размером p.
Таким образом, сумма длин перемычек q i в кусках материала равна
q i = 0 , если S x i j £ 1; q i = p (x i j - 1) , если x i j > 1 (2.8)
Кстати размер перемычек достигает несколько процентов и более от размера заготовки и может оказывать весьма существенное влияние на итоги раскроя.
Неравенство (2.3) будет выглядеть следующим образом:
a j x i j + q i £ d i (2.9)
Неравенство (2.7) будет:
Δ i = d i - £ Z (2.10)
Задача (2.2), (2.4) - (2.6), (2.8) -(2.10) является принципиально нелинейной, область изменения переменных невыпукла и представляет собой форму "ежа".
Существенным моментом в рассматриваемом методе решения задачи является следующее.