11.3.3. Половинное деление

При поиске множителя Лагранжа можно использовать метод би-секции (половинного деления): на каждом шаге определять такой интервал [Ol , Оц) , чтобы внутри него происходила смена знака функции

г=1j=0

Затем интервал делится пополам и определяется, в какой из половин меняется знак. После этого процедура применяется к ней. Условием завершения процесса служит близость к нулю модуля вышеприведенной разности. В [191] отмечается хорошая сходимость метода: при допуске в 0.5% бюджета (а с учетом погрешности исходных данных вряд ли стоит стремиться к большей точности) требовалось не более 10 итераций.

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

Процедура Фокса - Лэнди и бисекция требуют хороших оценок диапазона для множителя Лагранжа.

11.3.4. ]У[етод ]Мукштадта

Мукштадт [180] предложил решать исходную задачу (11.3.1) с помощью двух аппроксимаций: для запасов в депо и множителя Лагранжа. Метод опирается на тот факт, что числодефицитов в каждом пункте в практически интересных ситуациях хорошо приближается экспоненциальной функцией максимального запаса Sij .

Ожидаемое число «низовых» дефицитов по детали i может быть

Фокс и Лэнди предложили выбирать значения множителя Лагранжа из диапазона [во, Ом] . разбив его на М равных частей. Построение этого интервала - главная проблема при реализации алгоритма. В примере из [191] первоначальный диапазон множителя Лагранжа охватывал четыре порядка, а в дальнейшем суживался до двух порядков. В процессе поиска диапазон делился на 64 равных отрезка.

вычислено как функция суммарного запаса этих деталей Ni - Sij :

J оо

Bi{Ni) = Yl е i-Sij)pbAXijrij{Sio)]. (11.3.14)

i=ln=5.j4-l

В целях аппроксимации Bi{Ni) экспонентой

Bi{Ni) = aiexp{-biNi) (11.3.15)

предлагается для всех г решить задачу вычисления

J оо

Zi{Ni) =ттТ, е i-Sij)p[n\Xijrij{Sio)] (11.3.16)

при дополнительном условии J

J2Sij = Ni, Sij = Ojri-

Пусть она решена для К наборов {Л,} и получены оптимальные значения = Zi(N-) , к= 1,А. Коэффициенты {а,-, 6,} получаются как параметры регрессии, именно

Г Е (Af) Е In - EAf ЕА/ In Z " ""1 AE(7Vf)2-(EiV/)2

Здесь все суммы берутся по к .

Оптимальные решения задачи (11.3.16) получаются решением Ni -h 1 задач минимизации

J оо

Zi{Ni,Sio) = min е е - Sij)p[n\XijTij(Sio)] (11.3.17)

при ограничениях

J2Sij = Ni-Sio, Sij =0,1,..., 5io = ra.

Zi(Ni)= min Zi{Ni,Sio). (11.3Л8)

Тогда

Эта задача решается «рюкзачным» методом: начиная с Sjj = О , j = 1, J , увеличивают на единицу те значения Sij , которые дают наибольшее уменьшение ожидаемого числа дефицитов, пока не будет достигнуто ограничение. Хотя алгоритм прост и эффективен, он должен

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

Sio , т.е. + 1) Рз точки зрения вычислений задача нетриви-

альна. Значительная экономия достигается, если мы оценим оптимальное значение 5*0 • Тогда вместо (Ni -h 1) раз задачу (11.3.17) нужно решить лишь несколько раз в окрестности 5*q .

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

Sio=:-\n(-\-] , (11.3.19)

Ьо \aobo J

где ао,6о - параметры экспоненты, аппроксимирующей ожидаемое число недостач в депо. Эти параметры также определяются посредством регрессионного анализа, основанного на данных Sio и Bo(Sio\XioTio) . Полезность аппроксимации возрастает при увеличении оптимальных значений Sio .

Определение параметров {af,6i}, i = 1,7, представляет первую фазу предлагаемых аппроксимационных алгоритмов. В первом алгоритме она сопровождается оценкой оптимального значения множителя Лагра-нжа

==ехр () , (11.3.20)

а = c,c/i/6b /? = J2ci/bi, di = Haibila). (11.3.21)

i=l i-l

После этого поставленная проблема решается описанными выше методами.

Важнейшее достоинство этого подхода - не требуется знать диапазон для множителя Лагранжа. Время счета оказывается много меньше. Уменьшаются также число проходов и объем хранимых данных.