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

170

Наличие люфта в векторе требований на форматы

Постановка задачи

Пусть вектор требований на форматы «размыт» допусками. т.е.

в2[M] ≤ в[M] ≤ в1[M]

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

в2[M ] ≤ A[M,N] x[M] ≤ в1[M]

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

Данная задача, по сути дела, есть целочисленная задача линейного раскроя с дополнительными ограничениями. Переходим к ее постановке.

Пусть имеется одномерное сырье длины l0 (ширина тамбура), из которого необходимо нарезать заготовки (форматы в заявке) различных типов из множества M ( M = m– число

элементов в множестве M , в нашей задаче m – число различных форматов в заявке). Длины заготовок задаются вектором l[M ]. Требуется, удовлетворив требования на заготовки по каждому типу (по количеству рулонов каждого формата) b[ M ] , достичь этого, израсходовав минимальное количество штук сырья. Пусть теперь N – множество номеров всех возможных способов раскроя тамбура (множество номеров всех возможных раскладок, включая и нетехнологичные, либо по количеству вырезаемых заготовок, либо с большим отходом). N = n – число всех возможных способов раскроя. Составим из способов раскроя целочисленную неотрицательную матрицу A[M , N], где A[M , j] – способ раскроя с номером j . A[i, j] – количество заготовок i -го типа, вырезаемых j -м способом раскроя (число рулонов i -го формата в j – ой раскладке). Неотрицательный вектор способа раскроя A[M , j], очевидно, удовлетворяет ограничению

(1)A[M, j] l[M ] ≤ l0

так как суммарная длина вырезаемых в способе заготовок не должна превышать длины сырья.

Введем целочисленный неотрицательный вектор неизвестных x[N] – интенсивности

A[M, N] x[N]+ x[M1] = b1[M ]

(*).

A[M, N] x[N]− x[M2 ] = b2[M ]

Вычитая из первой системы вторую, получаем вместо (*)

171

Ясно, что однократное использование способа раскроя приводит к израсходованию одной штуки сырья длиной l0 . Тогда линейная функция f (x) = 1[N] x[N]l0 − l[M ]b[M ]

выражает суммарные отходы при вырезании всех требуемых заготовок. Данную функцию можно преобразовать, удалив из нее константы

f(x) = 1[N] x[N]l0 −l[M ]b[M ] =

=1[N] x[N]l0 − l[M ](b1[M]− x[M1]) =

=1[N] x[N]l0 − l[M ](b2[M ]+ x[M2 ])

Таким образом, приходим к следующим линейным целевым функциям: f1 = 1[N] x[N]l0 + l[M ] x[M1]

f2 = 1[N] x[N]l0 − l[M ] x[M2 ]

Беря первую из них, рассматриваем в качестве системы ограничений систему (+) в которой столбцы матрицы A[M , N] удовлетворяют ограничению (1).

Если добавить к ограничению (1) еще два ограничения (соответствующих максимуму концевого отхода и максимальному количеству вырезаемых в способе раскроя заготовок)

приходим к следующей задаче целочисленного программирования, реализующей нахождение оптимальных раскладок и числа съемов по ним вырезаемым.

Алгоритм решения

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

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

173

Минимизация попутчиков и люфт

Постановка задачи

Вектор требований b[M ] жестко задан и люфта не имеет. Минимизация суммарного

отхода достигается за счет выбора оптимальных раскладок (ЦЗЛР) и ввода дополнительных форматов – «попутчиков» ( M0, l0 [M0 ]). Как правило, в «попутчики»

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

Пусть x* [N ] - оптимальное решение ЗЛР

1[N ] x* [N ]+ x[n+1]= f * +1

новую задачу ЛР.

В качестве начального базиса возьмем N '' = N ' {n +1}. Тогда базисная матрица и обратная к ней будут выглядеть следующим образом:

ε1[ j0 ]=−v[M, j0 ] A[M, j0 ]+1=−ε[ j0 ]≥0 (решение неоптимально) Начальная симплекс таблица имеет вид

Если в оптимальном решении ЗЛР f * - целое, то в правой части вводимого ограничения

f * − минимальное число съемов

x* [N ]− оптимальные интенсивности использ. раскл.

L0 − минимальный суммарный отход

имела бы минимальное значение целевой функции f0* = f * .

176

(| N '' |= M0 )

Начальное базисное решение

x0Б =(B[N ',M ] b[M ], −E[N '',M0 ] 0[M0 ])=(x* [N '],0[N ''])

Значение целевой функции

g0 (x0 )= L0

соответствует минимальному суммарному отходу L0 (без попутчиков). Подсчитаем вектор двойственных переменных v[M1 ]=c[N1 '] B[N1 ',M1 ]

v[M1 ]=(0[M ], l0 [M0 ]).

Тогда начальная симплекс-таблица МСМ для задачи (−) будет выглядеть следующим

образом:

Пусть теперь A1[M1, j]=(A* [M1, j], A0 [M0, j]), так что A0 [M0, j]>0[M0 ] (в один из «старых» раскроев помещается попутчик)

Подсчитаем его оценку.

ε [ j]=0[M ] A* [M, j]+l [M ] A [M , j]−0 =l [M ] A[M , j]>0

1 0 0 0 0 0 0 0

=0

Решение неоптимально и его можно улучшить в рамках МСМ.

1. Если вводимый в базис раскрой имеет вид