Задачи ЛП и методы их решения

159

Можно показать, что решение такой целочисленной задачи существует[22]. Так как кратности элементов остатка вектора требований b[M ] – небольшие и мы знаем число съемов в оптимальном решении, то комбинаторный метод не займет много времени.

Задача о минимальном количестве перенастроек ПРС

Как уже упоминалось, для получения решения задачи линейного раскроя применяется модифицированный симплекс метод, и оптимальным решением является нецелочисленная линейная комбинация, состоящая из m линейно независимых способов раскроя. Как правило, в этой линейной комбинации векторов все коэффициенты отличны от нуля и большинство из них не целочисленные, т.е. в решении, полученном на втором шаге, будет использовано большое количество съемов (максимальное количество съемов на втором шаге m −1). Как показало тестирование комбинированного метода, все способы раскроя, полученные на втором шаге, различны и не совпадают со способами раскроя полученными в МСМ. Это приводит к тому, что в конечном оптимальном целочисленном решении используется число различных способов раскроя, как правило, превосходящее число раскроев в базисном решении нецелочисленной задачи.

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

Поэтому возникает следующая задача: среди всех оптимальных решений целочисленной задачи раскроя выбрать то, которое содержит наименьшее число различных способов раскроя, т.е. минимизировать число перенастроек ПРС.

Итак, пусть f * оптимальное значение целевой функции ЗЛР. Рассмотрим набор векторов x[N] такой, что

f (x[N]) = f *

A[M, N] x[N] = b[M ] x[N] ≥ 0[N]

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

Каждая положительная компонента x[i] вектора интенсивностей x[N] означает использование в решении i -го способа раскроя. Следовательно, задача минимизации числа различных способов раскроя участвующих в решении равносильна минимизации положительных компонент вектора x[N], т.е. нам необходимо найти самое вырожденное решение исходной задачи. Обычно складывается кардинально противоположная ситуация – вырожденных решений стараются избегать.

Как говорилось выше, решение, получаемое на втором шаге комбинированного метода, состоит из различных способов раскроя, поэтому оптимизацию по числу различных способов раскроя имеет смысл вести только на первом шаге решения задачи, который представляет собой МСМ.

Различным оптимальным решениям МСМ соответствуют различные базисные подматрицы, в которых все столбцы имеют нулевую оценку. Если мы переберем все возможные такие подматрицы, то, очевидно, мы переберем все решения и выберем наилучшее.

Добавим, к уже имеющимся ограничениям еще одно 1[N] x[N] ≥ K

Это условие означает, что значение целевой функции не опустится ниже оптимального целочисленного значения. Так как целевая функция непрерывна и ее минимальное значение без дополнительного условия меньше либо равно K , то оптимальным значением целевой функции в новой задаче будет K , т.е. обязательно целое значение.

160

Следовательно, среди решений этой задачи могут быть и полностью целочисленные, и, если они существуют, то при полном переборе решений мы обязательно их найдем и выберем наилучшее. Базисность целочисленного решения рассматривается в[22].

Добавление одного дополнительного условия, увеличивает размерность решаемой задачи на единицу. Т.е. размерность задачи уже не m , как было раньше, а m +1. Также, при решении этой задачи с помощью МСМ добавится еще одна переменная x[n +1] с нулевым коэффициентом в целевой функции и один «пустой» способ раскроя rn+1 = A[M,n +1] = (0,0,...,0,−1).

Таким образом, приходим к следующей расширенной задаче линейного

X[N] ≥ 0[N]

Среди решений этой задачи, необходимо найти то, которое дает самое вырожденное решение исходной целочисленной задачи.

Рациональная загрузка ПРС

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

Форматный раскрой бумажного полотна, осуществляется на продольно-резательных станках (ПРС), которые могут иметь различные технические характеристики (основными из которых являются производительность ( m ) и время перенастройки(t )). Пусть буммашину обслуживают два ПРС со следующими характеристиками:

Необходимо распределить между этими двумя ПРС для разрезания S съемов, среди которых имеется R различных съемов (равно общему числу перенастроек ПРС). Выбранное распределение съемов между ПРС и условия, которые должны выполняться приведены в таблице

161

Покажем, что минимум в (*) равен нулю и достигается при t(p1) = t(p2) = T0 . Для простоты, будем считать, что T1 = T2 = 0 . При уменьшении t(p1) за счет уменьшения x , величина y на столько же увеличится, и может (не обязательно) увеличиться v. Следовательно, увеличится и t(p2) , и станет больше T0 . При уменьшении t(p1) за счет изменения u , t(p2)

увеличится за счет увеличения хотя бы на один съем y ( v может и не увеличиться, если такой съем режется и на 2-м ПРС). Таким образом, при выполнении условия t(p1) = t(p2) = T0

минимум в (*) равен нулю.

Подсчитаем распределение отрезаемых съемов между ПРС в частном случае, когда все съемы различны и имеются в одном экземпляре. Тогда:

1). x + y = S ; 2). u + v = R ; 3). S = R ; 4). u = x, v = y

Алгоритм решения задачи

Итак, пусть имеются два станка, на которых обрабатываются n различных типов деталей (раскладок) в количестве S = α[N] 1[N] ( N = n) штук съемов. Время обработки деталей на станках пропорционально их (деталей) количеству ( x t1 и y t2 соответственно). Время перенастройки станков на обработку деталей другого типа линейно зависит от количества деталей разных типов, обрабатываемых на станке (u τ1 и v τ2 соответственно).

Напомним, что требуется найти загрузку станков, дающую минимум модуля разности общего времени работы ПРС-1 и ПРС-2, т.е.

163

и начнем работу алгоритма с варианта «ноль-всё» (все детали обрабатываются на одном из станков). Теперь перебрасываем детали с небольшими кратностями (сначала с единичными) из нижней части списка деталей. Это обеспечивает большие значения скачка целевой функции f . Когда в (**) левая и правая части станут примерно одинаковыми, начинаем перебрасывать детали с большими кратностями (из верхней части списка деталей). Теперь (**) не изменяется, а обе части в (*) подравниваются.

В соответствие с описанным алгоритмом рассчитан нижеследующий пример:

ПРИМЕР 1.

Рассмотрим оптимальные раскладки (номер раскладки и количество вырезаемых съемов по ней см. столбцы 12 и 13) по заявке 034 от 27.09.04 БМ21, подлежащие распределению между ПРС-1 и ПРС-7.