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

149

139510

Если обозначить через u[i] - путь максимальной доходности из вершины i в вершину 0 и положить u[0]=0 , то можно записать соотношение

u[i]= max{v[k]+u i−l[k] k Ni } (*)

( Ni - множество дуг, выходящих из вершины i )

Это соотношение называется функциональным уравнением Р.Беллмана или функциональным уравнением динамического программирования.

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

В данной задаче имеется простой способ решения уравнения Беллмана: достаточно вычислять v[i] последовательно от v[1] до v[L], запоминая управление (номер заготовки)

на котором достигался максимум. Будем формировать список, каждый элемент которого состоит из размера сырья, получаемого из этого сырья дохода, и заготовки, которую следует отрезать от сырья этого размера. Список должен быть упорядочен по возрастанию размеров сырья и строго упорядочен по доходам. Будем говорить, что запись с размером сырья λ1 и доходом γ1 доминирует ( α ) запись λ2 , γ2 , если λ1 ≤λ2 и γ1 ≥γ2 . Собственно списков будет два – рабочий (текущий) список и архивный список. На каждом шаге к самой первой из имеющихся в рабочем списке записей будет прибавляться каждая из заготовок: размер сырья будет при этом равен сумме размера в исходной записи и длины прибавляемой детали, доход будет равен сумме имеющегося дохода и цены прибавляемой заготовки, в качестве отрезаемой заготовки будет указана эта прибавляемая заготовка. Полученный набор новых записей вливается в рабочий список с соблюдением условий упорядочения: по длине и по доходу. Записи, которые доминируются другими, исключаются из списка. Записи, в которых размер сырья превосходит L , в список также не включается. Использованная таким образом первая запись рабочего списка, передается в архивный список, а процесс повторяется до исчерпания рабочего списка.

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

На шаге 2 запись (20, 20, 20) исключается из рабочего списка, так как доминируется кандидатом (18, 20, 9). На шаге 3 из рабочего списка удаляется запись (29, 30, 20), доминируемая кандидатом (27, 30, 9), а кандидат (38, 40, 20) не включается в рабочий список, так как доминируется записью рабочего списка (37, 40, 37). На четвертом шаге, по этой же причине, кандидат (58, 63, 37) не включается в рабочий список (доминируется записью рабочего списка (58, 65, 40)). Продолжаем перерабатывать рабочий список.

150

После исчерпания рабочего списка остается следующий архивный список:

Искомый раскрой получается обратным просмотром архивных записей:

Искомый способ раскроя (2, 0, 2, 0, 1) с доходом 111.

В процедуре, приведенной ниже, используется более удобный в вычислительном отношении вариант уравнения Беллмана

Его решение реализуется способом, использующим вместо матрицы u вектор, в котором последовательно получаются все строки этой матрицы:

Процедура r -задачи методом динамического программирования

{v[0:l0]– вектор в котором получаются последовательно все строки матрицы.

Dec[0:l0]– целочисленный массив решений

(номер отрезаемой детали), принимаемых в состояниях процесса }

for I:=0 step 1 until l0 do begin v[i]:=0; dec[i]:=0 end;

{начальные установки}

for k:=1 step 1 until n do {цикл по номерам деталей} begin ck:=c[k]; lk:=l[k]; x[k]:=0;

{текущие доход и длина}

for I:=lk step 1 until l0 do

{цикл по длине сырья от текущей до l0} if v[I-lk]+ck>v[I] then

begin v[i]:=v[I-lk]+ck; dec[i]:=k end

{Если встретился рекорд, то принимается решение отрезать деталь с номером k}

end k; d:=l0;

{Начало восстановления раскроя. Индекс устанавливается равным l0}

for I:=dec[d] while I>0

{при I=0 достигнем нулевой части вектора dec} begin x[i]:=x[i]+1; d:=d-l[i] end

{Элемент массива x (раскрой) с индексом, равным номеру очередной отрезаемой детали увеличивается на единицу. После окончания цикла в нем получается искомый Наилучший способ раскроя}.

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

152

выделенные типы заготовок: «только в середине», «только с края» и т. д.). В этом случае, по-видимому, предпочтительнее алгоритм метода ветвей и границ.

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

Базисную матрицу, отвечающую начальному базисному решению, можно выбрать диагональной

A[M, N ']=diag( L/l[i] , i M )

Тогда

v[M ]=1[N '] B[N ', M ]=(L/l[i]−1 , i M ).

Общая схема модифицированного симплекс-метода выглядит следующим образом:

Пусть теперь x* [N ] - оптимальное решение задачи линейного раскроя. f * =1[N ] x* [N ] -

минимальное значение целевой функции. В [22] показано, что существует целочисленное решение задачи раскроя со значением целевой функции

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

b[M ]=b[M ]− A[M, N ] x* [N ]

и разобьем его на

k = f −1[N ] x* [N ]

раскроев. Для этого можно использовать часть процедуры bestpartition[9] в режиме r-

имеем оптимальное целочисленное решение исходной задачи линейного раскроя.

153

Рассмотрим пример с исходными данными, приведенными выше ( L =35,l =(9,5,3)) и

вектором требований b =(101,101,102).

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