Зад лин прогр и мет их решения 16 12 08

180

Выпишем нецелочисленное решение, выделяя целые части

(5 раскладок, 7 попутчиков, отход 2)

(2)Теперь приведем пример, где среди оптимальных раскладок одна имеет отход меньше длины попутчика, но суммарный отход значителен из-за ее (раскладки) большой интенсивности.

Исходные данные: L =13, l =(7,5,3), b =(29,31,11) попутчик длины 2.

1 2 3 4 5 6 7 8 9 10 1112 13 номер

111100000000 0

A =100021111000 0 раскрой

1210102104 321

1 0 3 6 0 3 2 5 8 1 4 7 10 отход

Это матрица всех возможных способов раскроя Оптимальное целочисленное решение

Вводим дополнительное ограничение на число используемых съемов (32).

Решение оптимально.

(+)

Вводим попутчика длины 2 (x0 [M0 ]=0).

181

Изменяем целевую функцию

ε(−1)(−1)(−2)(−2)

Добавить попутчиков не удается.

182

Раскрой с учетом постоянного и случайного брака на тамбуре

Учет заранее выявленного постоянного брака на тамбуре

Исходные данные и предположения

Выработано несколько бракованных тамбуров, из которых можно получить K съемов. При этом, число K может удовлетворять одному из двух альтернативных условий:

a)Указанных K съемов (с учетом брака) хватает для вырезания всех форматов по вектору требований;

b)Имеет место остаток вектора требований, после использования всех K

"бракованных" съемов.

Рассмотрим оба указанных случая по отдельности

Решение ЗЛР при наличие только бракованных съемов

Пусть при выработке очередного тамбура возможен брак шириной l0 , начинающийся на расстоянии L1 от левого края тамбура.

Тогда на все съемы данного тамбура распространяются раскладки, содержащие «бракованного попутчика» шириной l0 , располагающегося на фиксированном месте. Получаемое при этом «псевдосырье» с длинами L1 и L2 раскраивается с максимизацией

вырезаемой ширины и учетом имеющихся форматов в векторе требований. Таким образом, необходима модификация r -задачи с ограничением на число заготовок в векторе требований.

Предстоит выяснить эффективность по материалу двух следующих подходов:

(I)«Не замечая» брака, разрезать тамбур в посъемном режиме, и браковать рулоны, пересекающие выделенную область (не вычитать их из вектора требований).

(II)Использовать (до окончания зоны брака) раскладку с попутчиком, совпадающим по ширине с выделенной областью и максимальным заполнением псевдосырья с длинами L1 и L2 . Далее выполнять задачу в обычном посъемном

режиме.

Надо решить вопрос о том, встраивать ли процедуру генерации раскроя с одним попутчиком на фиксированном месте в r -задачу, или использовать ее автономно. Если использовать ее автономно, то встает вопрос об оптимальности решения (вернее, насколько далеко оно удалится от оптимального). Если же встраивать в r -задачу, то возникает проблема постоянного присутствия в базисе раскроя с «бракованным попутчиком» на фиксированном месте.

183

Будем считать, что выделенная область брака существует всегда т.е.

L = L1 + l0 + L2 .

Тогда в ЗЛР способ раскроя определяется как сумма двух неотрицательных целочисленных векторов

a[M ] = a1[M ]+ a2[M ]

a1[M ] l[M ] ≤ L1 a2[M ] l[M ] ≤ L2

a[M ] l[M ] ≤ L1 + L2

r - задача будет выглядеть следующим образом:

a[M ] v[M ] → max

a1[M ] l[M ] ≤ L1a2[M ] l[M ] ≤ L2

Доказательство. (Reductio ad absurdum)

) Пусть a1[M ] не является решением r1 -задачи, т.е.

aɶ1[M ]: aɶ1[M ] v[M ] > a1[M ] v[M ]. Тогда aɶ[M ] = aɶ1[M ]+ a[M ],

aɶ[M ] v[M ] = aɶ1[M ] v[M ]+ a2[M ] v[M ] > a[M ] не является решением r -задачи.

>a1[M ] v[M ]+ a2[M ] v[M ] = a[M ] v[M ]

) Очевидно.

Начальное решение ЗЛР выглядит так:

и мы остаемся в рамках МСМ.

184

Замечания.

1.Базисные раскладки хранятся в виде двух частей:

•«левая» раскладка a1[M ]: a1[M ] l[M ] ≤ L1

•«правая» раскладка a2[M ]: a2[M ] l[M ] ≤ L2

2.В базис вводится раскладка, являющаяся решением r -задачи

a[M ] = a1[M ]+ a2[M ].

Полученные результаты очевидно распространяются на любое число фиксированных областей брака l0 ,l1,…,lk−1, которым соответствуют длины «псевдосырья» L1, L2 ,…, Lk , и соответственно r1,r2 ,…,rk - задачи.

Оптимальные раскладки, в этом случае, будут состоять из k частей.

a1[M ] l[M ] ≤ L1

Решение ЗЛР для бракованных и обычных съемов

Предположим, что на вырезание всех форматов требуется S бракованных съемов, причем S > K .

Требуется нарезать все форматы из вектора требований, с минимальными отходами, использовав при этом все K бракованных съемов.

f (x) =1[N1] x[N1]+1[N] x[N] → min A[M, N1] x[N1]+ A[M , N] x[N] = b[M ] 1[N1] x[N1] = K

x[N1] ≥ 0[N1] x[N] ≥ 0[N] x[N1], x[N] – целочисленный ,

Здесь

A[M, N1] – раскладки для бракованных съемов (способы раскроя с постоянным "бракованным" попутчиком);

x[N1] – интенсивности использования раскладок для бракованных съемов;

A[M, N] – обычные раскладки (в отсутствие брака);

x[N] – интенсивности использования обычных раскладок;

K– число бракованных съемов;

b[M ] – вектор требований с учетом люфта.

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

185

Итак, рассмотрим оптимальное решение для постоянного брака, считая, что бракованных съемов хватает для вырезания всех форматов по вектору требований

A[M, N1] xɶ[N1] = b[M ] 1[N1] xɶ[N1] = S

Можно считать, что раскладки в A[M, N1] упорядочены по возрастанию отходов.

Выделяем и суммируем раскладки, начиная с наименее отходных, до тех пор, пока их число не станет равным K . Т.е. произведем перегруппировку

A[M, N1] x[N1]+ A[M , N1] (xɶ[N]− x[N1]) = b[M ] 1[N1] x[N1] = K

x[N1] ≥ 0[N1] xɶ[N]− x[N] ≥ 0[N] x[N1], xɶ[N]− x[N] – целочисленный ,

Подсчитаем остаток вектора требований

b1[M ] = A[M , N1] (xɶ[N]− x[N1])

На этом первый этап заканчивается.

Далее решаем следующую задачу минимизации отходов (ЦЗЛР):

g(x) =1[N] x[N] → min A[M, N] x[N] = b1[M ] x[N] ≥ 0[N]

x[N] – целочисленный.

В полученном оптимальном решении удалим (или дополним их до малоотходных) наиболее отходные раскладки с малой интенсивностью использования, уменьшая (или увеличивая, соответственно) вектор требований, и, оставаясь, по возможности, в пределах люфта.

Рассмотрим теперь несколько примеров:

186

Решаем теперь задачу с обычными раскладками и полученным остатком вектора требований. Оптимальная базисная матрица и обратная к ней