центральный . Горизонтальные связи в системе отсутствуют. Задача: найти минимум

i j j i

B = J2( EEJ 5 = 0,1,2,...

i=lj = l j=0 i=l

(11.3.1)

Ожидаемое число дефицитов по детали i на базе j

Bij{Sij,Sio)= (n-Sij)p(n\\ijtij). (11.3.2)

n=5.,--l

При этом tij = tij{Sio) . Точнее,

tij = njTij -f (1 - r,-,)[L,o + (5(5,o)]. (11.3.3)

В этой формуле

Tij - среднее время ремонта детали г на базе j , rij - вероятность ремонта детали г на базе j , Ljo - среднее время доставки детали с базы j в депо. Дополнительно отметим равенства для средней задержки в депо

1 ~

S(Sio)Tij = - У2 - Sio)p(n\\ioTio) (11.3.4)

п=5.о + 1

и интенсивности потока заявок на ремонт в депо

A,o=(l-n,)A,-j. (11.3.5)

11.3.2- Процедура Фокса и Лэнди

Эта процедура [142] адаптирует к поставленной задаче метод множителей Лагранжа. Разыскиваются {Sij}, которые минимизируют лагранжиан

j i j i

L = YJ2iiSiJ,Sio) + eJ2T.<iSij. (11.3.6)

j=l1=1 j=0i=l

При разработке алгоритма использованы сепарабельность целевой функции по г, строгое убывание Bij(Sij, Sio) по обоим своим аргументам, дискретная выпуклость и рекурсивность по первому аргументу.

Вследствие сепарабельности по г оптимальное решение задачи (11.3.6) находится последовательным решением / подзадач вида

w\(в) = mill ( Т Bij(Sij, 5,0) + е Т aSij ]

(11.3.7)

с учетом требования целочисленности. Разделяя далее переменные 5,о и Sij , перепишем эту задачу как

Wi{e) = min (eciSio + min Ij Bij{Sij, Sio) + OciSij] \ (11.3.8)

(при вычислении внутреннего минимума переменная 5,0 считается фиксированной). Обозначим содержимое фигурных скобок

Zi{Sio,0) = Ci5io + min

Y,Bij{Sij,Sio) + OciSi

(11.3.9)

Теперь подзадача (11.3.8) может быть поставлена как нахождение для всех г

Wi(0) = min ZiiSioJ). (11.3.10)

Введем оператор минимума в (11.3.9) под знак суммы:

Zi{SioO)eciSio + Vmm

Bij(Sij,Sio) + eciSij

(11.3.11)

Чтобы определить Z,(5,o,) . мы должны для каждого 5,0 найти

mm S.J I

Bij{Sij,Sio)-\-eciSij

(11.3.12)

Так как эта функция монотонно убывает, дискретно выпукла и рекурсивна по аргументу Sij , нахождение минимума в (11.3.12) сводится к нахождению первого целого Sij , начиная с нуля, для которого выполняется

Bij(Sij,Sio) - BijiSij -f 1,5,0) < ва. (11.3.13)

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

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

г=1j=0

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

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

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

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

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

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

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