В.И. БОДРОВ, Т.Я. ЛАЗАРЕВА, Ю.Ф. МАРТЕМЬЯНОВ МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ ПРИ ПРИНЯТИИ РЕШЕНИЙ Издательство ТГТУ Министерство образования и науки Российской Федерации Тамбовский ...
-- [ Страница 2 ] --dPsn = -nPsn (t) + n+1Psn+1(t), n = 0, 1, 2, K dt при условии 0 0, s,s +1 и начальных условиях Рsn(0) = 0, n = 0, 1, 2, Е, s - 1, s + 1, Е, Pss(0) = 1. Опуская индекс s в этих урав нениях, получают модель чистой гибели при sn 0 в виде dP = 1P1(t);
dt (4.21) dP n = -nPn (t) + n+1Pn+1(t), n = 1, 2;
dt Рn(0) = 0, n = 0, 1, 2, Е, s - 1, s + 1, Е, Ps(0) = 1.
Рассмотрим частный случай общей модели рождения и смерти (4.19), когда при t = 0 состояние сис темы n = 0, параметры и - const. Этот случай соответствует очереди с одним клиентом, пуассонов ским входным потоком и экспоненциальным временем обслуживания. В уравнениях модели (4.19) можно оставить в этом случае лишь один индекс, т.е.
dP = -P0(t) + P1(t);
dt (4.22) dP n = Pn-1(t) - ( + )Pn(t) + Pn+1(t), n = 1, 2, K dt Система дифференциальных уравнений (4.22) описывает изменение во времени вероятностей со стояния Pn(t), n = 0, 1, 2, Е, которые называются неустановившимися вероятностями состояния.
Начальные условия для (4.22) P0(0) = 1, Pn(0) = 0, n = 1, 2, Е (4.23) Cистему уравнений (4.22) с начальными условиями (4.23) можно решить, его решение будет схо дится к статистически стационарному процессу Pn = lim Pn (t), n = 0, 1, K t только при условии / < 1.
Интуитивно это понятно, поскольку статистическая стационарность наступает только тогда, когда средний интервал 1/ между появлениями новых требований меньше среднего интервала 1/ обслуживания.
Обозначим отношение параметра входного потока (интенсивности) к параметру обслуживания (ин тенсивности) или, что тоже самое, отношение среднего времени обслуживания 1/ к среднему ин тервалу между появлениями новых требований как = 1/:1/ = 1/.
Эту величину называют трафик-интенсивностью.
Если < 1, то всегда существуют статистические стационарные состояния. Уравнения для их опре деления получают из (4.22), приравнивая нулю производные 0 = -P0 + P1;
(4.24) 0 = Pn-1 - ( + )Pn + Pn+1, n = 1, 2, K Эти уравнения называют уравнениями в конечных разностях.
Можно показать, что при < 1 система массового обслуживания входит в стационарный режим, при этом установившиеся или стационарные вероятности Рn, n = 0, 1, Е, удовлетворяют системе урав нений (4.24).
Решение этой системы дает Pn = lim Pn(t) = n (1- ), n = 0, 1, K (4.25) t Из (4.25) следует, что P0 = 1-, т.е. (4.26) = 1- P0 = P. (4.27) Так как Р0 является вероятностью отсутствия очереди, P = 1- P0, а, следовательно, и - вероятно стью наличия очереди. Другими словами, трафик-интенсивность можно трактовать, как долю време ни, в течение которого прибор обслуживает требование (работает). Поэтому величина = / называ ется также коэффициентом загруженности обслуживающего устройства или коэффициентом использо вания.
4.4.3 ОЦЕНОЧНЫЕ ХАРАКТЕРИСТИКИ Имея выражения (4.25), (4.26) для расчета Рn, легко рассчитать другие оценочные характеристики, сре ди которых выделяют следующие.
1 Вероятность нахождения в системе не более n требований n n i i F(n) = P0 + P1 +K + Pn = (1- ) = (1- ).
i =1 i= Сумма в последнем выражении составляет геометрическую прогрессию и определяется по формуле n i, = 1- n+ 1- i= откуда F(n) = Вер( n) = 1- n-1. (4.28) 2 Вероятность (n) = Вер{ > n} является дополнительной к F(n):
(n) = Вер{ > n}= n+1. (4.29) Вероятность (0) является вероятностью существования очереди и из (4.29) следует, что для n = (n) = Вер{ > n}= P =.
3 Среднее число требований в системе n определяется как d n n-1 n n = = (1- ) = (1- ) nPn n n = (1- ) d ( ).
n=0 n=0 n=0 n= Так как сумма геометрической прогрессии равна n = 1-, n= то n =. (4.30) 1- Таким образом, между коэффициентом загруженности (трафик-интенсивностью) и средним чис лом требований n в системе существует однозначная связь (рис. 4.9).
4 Среднее число требований в очереди m равно m = -1)Pn = - + P0 = n -1+ P (n nPn Pn n=0 n=0 n= или m =. (4.31) 1- 8 n 0,2 0,4 0,6 0, Рис. 4.9 Зависимость среднего числа требований от трафик-интенсивности Вероятность Р0 иногда называют коэффициентом простоя прибора kпр:
kпр = Р0 = 1 Ц, отсюда m = n -1+ P0 = n -.
Сравнивая выражения (4.30) и (4.31), можно записать m = n или m n =.
5 Время ожидания в очереди tf связано с временем ожидания в системе ts соотношением ts = t + t0, f где t0 - время обслуживания.
Такое же соотношение, очевидно, справедливо и для средних величин ts = t + t0.
f Значения средних времен ожидания в системе и в очереди определяются соответственно по форму лам ts = n / = n / ;
t = m / = n / .
f С учетом (4.30) последние соотношения преобразуются к виду 1 1 ts = = ;
(4.32а) 1- 1- 1 2 t = =, (4.32б) f 1- 1- откуда t = ts.
f Разность между ts и t равна, с одной стороны,, а с другой f 1 = ts - t = ( - ) = 1/ .
f 1- 1- 6 Распределение времени ожидания в очереди F(t f), т.е. распределение вероятности того, что вре мя ожидания в очереди меньше t f: Вер{ t }.
f t f Очевидно, что F(ts ) = f ()d, где f () - плотность распределения времени ожидания в очереди.
Предположим, что в момент времени 0 в систему поступает требование у0 (рис. 4.10). Спустя неко торое время, требование проходит очередь и попадает в цех на обслуживание.
Время ожидания в очереди зависит от того, сколько требований уже было в очереди в момент вре мени 0.
Цех у0 x x x x x x x x x х n а) Цех х х х х х х х у0 х б) Рис. 4.10 Ожидание в очереди:
а - момент времени 0;
б - момент времени = 0 + tf Если обозначить P(t ) - вероятность того, что время ожидания лежит в пределах [t f, t f + dt];
т.е. tf f t f + dt;
P(n, t ) - вероятность того, что время ожидания лежит в пределах [t f, t f + dt] и в момент f времени 0 в системе было n требований, то, очевидно, по теореме сложения вероятностей можно запи сать P(t ) = ).
f P(n,t f n= При отсутствии очереди (n = 0) требования сразу поступают на обслуживание, поэтому вероятность того, что лежит в пределах [tf, tf + dt], равна нулю, и Р(tf) определяется по формуле P(t ) = ). (4.33) f P(n, t f n= Вероятность P(n, tf) определяется по формуле произведения вероятностей P(n, t ) = Pn(0)P(n -1/ n)P(n / n -1, n), f где Рn(0) - вероятность того, что в момент 0 в системе было n требований;
Р(n - 1/n) - условная веро ятность того, что к моменту времени 0 + tf (т.е. за время tf) (n - 1)-е требование уже обслужено (т.е. на чато обслуживание n-го требования) при условии, что в момент времени 0 в системе было n требова ний;
P(n/n - 1, n) - вероятность того, что за время dt n-е требование закончит обслуживаться при усло вии, что в момент времени 0 в системе было n требований и к моменту времени 0 + t f обслуживание (n - 1)-го требования закончили.
Так как рассматривается установившийся процесс, то Pn(0) = Pn = n(1- ). (4.34) Вследствие стационарности процесса вероятность обслуживания (n - 1)-го требования за время tf не зависит от числа требований в системе и определяется по формуле (4.12) (t )n-1e-t f f P(n -1/ n) =. (4.35) (n -1)!
Вероятность того, что за время t будет обслужено одно n-е требование, пропорциональна интерва лу dt, поэтому согласно (4.15) P(n / n -1, n) = G1(dt) = dt. (4.36) Из (4.33) - (4.36) следует, что (t )n-1e-t f f n P(t ) = (1- ) dt = f (n -1)!
n= (t )n- f = (1- )e-t f dt (4.37) 1)!.
(n n= Обозначив P(tf) = f (tf)dt, где f (tf) - плотность распределения вероятности того, что время ожидания лежит в пределах [tf, tf + dt], и приняв k = n - 1, можно записать (t )k f f (ts)dt = (1- )e-t f dt.
k!
k = С учетом (t )k f = et f k!
k = окончательно получают f (ts )dt = (1- )e-t f (1-)dt. (4.38) Таким образом, распределение времени ожидания в очереди будет t F(ts ) = )e-(1-)d = 1- e-t f (1-).
(1 Вероятность (t ) = Вер{ > t }определяется по формуле f f (t ) = 1- F(t ) = e-t f (1-).
f f Вероятность того, что время ожидания tf будет равно нулю, т.е. ждать не придется совсем, будет равна F(0) = 1 Ц. Это же соотношение можно получить и из (4.29) при n = 0, как вероятность того, что в системе не находится ни одно требование.
4.4.4 РАСЧЕТ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ОЧЕРЕДЬЮ БЕЗ ПОТЕРЬ M M 4.4.4.1 Система T1 1 Трафик-интенсивность = / или = n /(1- n).
2 Вероятность нахождения в системе точно n требований Pn = n (1- ), n = 0, 1, 2, K или P0 = 1-, Pn = Pn-1, n = 1, 2,...
3 Вероятность, что в системе находится не более n требований F(n) = 1- n+1.
4 Среднее число требований в системе n = /(1- ).
5 Среднее число требований в очереди m = 2 /(1- ) = n = n -.
6 Вероятность, что время ожидания в очереди меньше t f F(t ) = 1- e-t f (1-).
f 7 Среднее время ожидания в очереди 1 t = = ts = ts -1/.
f 1- 8 Среднее время ожидания в системе 1 ts = = ts +1/ .
1- 9 Коэффициент простоя (вероятность простоя) обслуживающего устройства (прибора) пр k = P0 = 1-.
10 Вероятность существования очереди P = 1- P0 =.
M D 4.4.4.2 Система T1 Рассматриваемая система отличается от предыдущей тем, что время обслуживания t0 является по стоянной величиной: t0 = 1/ = const. Такими системами могут быть аэропорты, железнодорожные во кзалы, морские и речные порты, отпуск товаров с заводов оптовым покупателям и др.
Основными расчетными соотношениями для этой системы являются следующие:
1 Трафик-интенсивность = / .
2 Среднее время нахождения в очереди t =.
f 2(1- ) 3 Средняя длина очереди 2 n = + = -.
2(1- ) 1- 2(1- ) Таким образом, при равномерном обслуживании среднее время ожидания в очереди сокращается в два раза, средняя длина очереди уменьшается. Можно показать, что среднее время ожидания в очереди и средняя длина очереди в этом случае минимальны.
M G 4.4.4.3 Система T1 В этой системе время обслуживания распределено не по экспоненциальному, а по произвольному закону с математическим ожиданием t = 1 и дисперсией Dt.
Расчетные соотношения следующие:
1 Средняя длина очереди + 2Dt 2 - 2Dt n = + = -.
2(1- ) 1- 2(1- ) При Dt = 0, т.е. когда обслуживание постоянно 2 n = + = -.
2(1- ) 1- 2(1- ) Таким образом, с увеличением дисперсии (разброса) времен обслуживания очередь увеличивается.
При Dt = 1/2 имеет место экспоненциальное распределение и следовательно 2 - n = - =, 1- 2(1- ) 1- ЧТО СОВПАДАЕТ С (4.30).
2 Время ожидания в очереди 1 2 + 2Dt t =.
f 2(1- ) В случае пуассоновского закона Dt = 1/2 и тогда 2 + 2( ) 1 1 t = =, f 2(1- ) 1- ЧТО СОВПАДАЕТ С (4.32Б).
3 Среднее время ожидания в системе ts = t +1/ .
f M M 4.4.4.4 Система n T 1 Данная система характеризуется тем, что параметр потока не является постоянной величиной, а пропорционален числу требований в системе: = 0n, где 0 = const. Примером подобной системы мо жет быть столовая, где скорость обслуживания обычно пропорциональна числу ожидающих клиентов.
Вообще говоря, в системах массового обслуживания процесс обслуживания интенсифицируется при росте очереди.
Основные расчетные соотношения имеют вид.
1 Вероятность нахождения точно n требований в системе ( / 0)n e- / Pn =.
n!
2 Среднее число требований в системе n = / .
3 Дисперсия Dn = /.
4 В переходном процессе среднее число требований изменяется по закону n(t) = (1- e-t ).
Таким образом, среднее число требований увеличивается от нуля до числа n(t) = / . При этом, чем меньше значение параметра , тем дольше длится переходный процесс.
M M 4.4.4.5 Система N T1 Система отличается от предшествующей тем, что число требований в системе ограничено. Схема этой системы представлена на рис. 4.11.
Пусть максимальное число требований, которые могут находиться в системе массового обслужива ния, равно N. Эта ситуация имеет место, например, при ремонте станков в цехе. Общее число станков равно N. Поэтому число N и есть максимально возможное число станков, которые потенциально могут сломаться и находиться в системе массового обслуживания. Ремонт станков производится одной брига дой.
Другим примером могут быть студенты, обслуживающиеся в студенческой поликлинике, спортсмены, тре нируемые одним тренером и т.д.
Если n - число станков в системе массового обслуживания, то в очереди будет станков 0, если n = 0;
m = K, n -1, если n = 1, 2, N, Система обслуживания Очередь Цех х х х х х х х х х х х х х m n = m + x x x x x x x x x l Рис. 4.11 Система с ограниченным числом требований предельное число которых не может быть равно n и тем более m:
n m, m N - 1.
Очевидно, что реальная интенсивность появления в очереди требований зависит от того, сколько требований уже находится в очереди и сколько осталось "свободных" (не находящихся в системе). Если все требования уже стоят в очереди, то нового требования поступить уже не может, т.е. N = 0. В общем случае можно считать, что n = (N - n), 0 n N, интенсивность обслуживания n = , для 0 < n N ;
n = 0, для n = 0.
Расчетные формулы для данной системы имеют вид:
1 Трафик-интенсивность = / .
2 Вероятность нахождения в системе точно n требований Pn = (N - n +1)Pn-1, n = 1, 2, K, N или N!
Pn = nP0, n = 1, 2, K, N;
(N - n)!
P0 =.
N!n 1+ (N - n)!
n= 3 Среднее число требований в системе nn n = = N!P0 = N - (1- P0) = 1- l.
nPn (N - n)!
n=0 n= 4 Среднее число требований в очереди N N n - m = -1)Pn = N!P0 n = (n (N - n)!
n=2 n= 1+ = N - (1- P0) = (N - n)t.
f 5 Среднее число требований, не находящихся в системе l = N - n.
6 Среднее время нахождения в очереди N t = 1- -.
f (n -1)Pn = 1 N 1+ (N - n) P n= 7 Среднее время нахождения в системе n 1 N ts = = 1- -.
(N - n) P 8 Вероятность существования очереди P = 1- P0.
9 Вероятность отсутствия очереди Вер{n = 0}= P0.
M M L 4.4.4.6 Система T1 В отличие от других рассмотренных ранее систем в данном случае число каналов (приборов) не равно единице. Пусть в системе функционирует L параллельно работающих приборов. В этом случае, если число требований в системе n L, то очереди нет - все требования обслуживаются. Очередь воз никает, если n > L.
Примерами подобных систем могут быть аэропорты с несколькими посадочными площадками, ав тозаправочные станции, железнодорожные вокзалы с несколькими кассами, мастерские с несколькими работающими станками, швейные мастерские и др.
Схема такой системы изображена на рис. 4.12.
В таких системах массового обслуживания для того, чтобы наступил статический стационарный режим, должно выполняться соотношение < 1.
L Если трафик-интенсивность = /, как и раньше, то для рассматриваемых систем с каналами для на ступления статического стационарного режима, следовательно, должно выполняться соотношение / < 1 (4.39) Цех х х х х х х х х х х х х х L 1442443 x m х Рис. 4.12 Система c L каналами В противном случае очередь будет бесконечно расти. Действительно, так как - среднее число тре бований, поступающих в систему в единицу времени;
- среднее число требований, которые обслужи ваются одним прибором в единицу времени;
L - среднее число требований, обслуживаемых прибо рами в единицу времени, то для того, чтобы очередь не росла бесконечно, необходимо, чтобы < L или / < L.
Отсюда и вытекает (4.39).
Расчет системы ведется по следующим формулам.
1 Коэффициент использования каждого канала (трафик-интенсивность) = / .
2 Вероятность нахождения в системе точно n требований n Pn = P0, 1 n < L ;
n!
n Pn = P0, n L L!Ln- или ;
Pn = Pn-1, 1 n L n Pn = Pn-1, n L.
3 Вероятность отсутствия требований в системе P0 = L L-1 n + L!(1- / L) n!
n= или P0 =.
2 3 n- +1+ + + + K+ L!(1- / L) 2! 3! (L -1)!
4 Среднее число требований в очереди n L+1 PL m = (n - L)Pn = P0 =.
LL!(1- / L)2 L(1- / L) n= L+ 5 Среднее число незанятых каналов L s = - n)Pn = m + L - n = M -.
(L n= 6 Среднее число требований в системе n = = m + L - s = m +.
nPn n= 7 Вероятность существования очереди P = Вер{n > L}= = P0.
Pn L!(1- / L) n= Эта вероятность может быть определена также по формуле Эрланга L!(1- / L) P =.
2 2 L- +1+ + + K + L!(1- / L) L! (L -1)!
8 Вероятность того, что время ожидания в очереди для одного требования не превышает tf - Lt (1- / L) L f F(t ) = 1- e P0.
f L!(1- / L) 9 Среднее время ожидания в очереди L t = m / = P0.
f LL!(1- / L) Для определения t можно воспользоваться номограммой, позволяющей определить t по значе f f ниям N и / N.
M M L 4.4.4.7 Система N T Система характеризуется тем, что число требований, находящихся в ней, ограничено. Условная схема этой системы изображена на рис. 4.13.
Цех x x x x x x x x x m x Система x массового x обслуживания n ххххххххххххх 1u2u l Рис. 4.13 Система с ограниченным максимальным числом требований и с L каналами Здесь обозначено: m - число требований в очереди;
n - число требований в системе;
l - число тре бований вне системы массового обслуживания;
N - общее число требований;
L - общее число приборов (устройств обслуживания);
s - число незанятых каналов (простаивающих устройств).
Примерами такой системы могут быть N станков, обслуживаемых L механиками;
группа нефтепе рерабатывающих заводов, обслуживаемых группой нефтедобывающих предприятий;
топливозаправщи ки, обслуживающие эскадрилью бомбардировщиков и т.п.
Между переменными данной системы, очевидно, справедливы следующие соотношения n - l = N;
0, если n L;
0, если n > L;
m = s = n - L, если n > L;
L - n, если n L.
Процесс же массового обслуживания имеет в этом случае следующие реальные значения парамет ров n, n, зависящие от числа требований в системе 0 при n = 0;
N при n = 0;
n = (N - n) при 1 n N;
n = n при 1 n < L;
L при L n N.
Можно показать, что 1 при n = 0;
N - n + an = an-1 при n = 1, 2, K, L -1;
n N - n + an-1 при n = L, K, N, N где an = Pn / P0.
Расчет системы производится по следующим формулам:
1 Вероятность отсутствия требований в системе P0 =.
N 1+ an n= 2 Вероятность нахождения в системе точно n требований Pn = P0an.
3 Коэффициент интенсивности обслуживания = / .
4 Среднее число требований в очереди N m = - L)Pn.
(n n=L+ 5 Коэффициент простоя требований тр kпр = m / N.
6 Среднее число простоев приборов (оборудования) L s = - n)Pn.
(L n= 7 Коэффициент простоя приборов (оборудования) пр kоб = s / L.
8 Среднее число требований в системе L n = = m + L - s.
nPn n= 9 Среднее число требований, не находящихся в системе l = N - n.
10 Вероятность существования очереди N L- P = = 1-.
Pn Pn n=L n= 11 Среднее время ожидания в очереди m m t = =.
f (N - n) (L - s) 4.5 Системы с нетерпеливыми клиентами (системы без очередей) M M L 4.5.1 СИСТЕМА H Рассматриваемая система массового обслуживания характеризуется тем, что, если число находя щихся в цехе клиентов равно L и клиент уходит, то система его теряет. Таким образом, число клиентов всегда не больше обслуживающих устройств n L, т.е. очереди в такой системе быть не может.
Примером такой системы может служить перехват сообщений по радио, которые осуществляет группа приемников. Если в момент передачи все радиоприемники уже принимают сообщения, то данное сообщение будет потеряно. Другой пример, если на междугородной телефонной станции все кана лы линии связи заняты, то соединение не возможно, а также, если в гостинице все места заняты, прием нового гостя не возможен и т.п.
Условная схема системы изображена на рис. 4.14.
В системе массового обслуживания без очередей основным показателем эффективности служит ве роятность ухода требования (вероятность, что все устройства обслуживания заняты), которая обознача ется V и определяется как V = PL, где L - число обслуживающих устройств.
Эта вероятность характеризует соотношение входного потока требований и потока обслуженных требований. Кроме того, основным характерным показателем для этой системы является среднее число простоя (среднее число свободных устройств) s, характеризующее загруженность цеха в среднем.
Расчет системы производится по следующим формулам.
1 Трафик-интенсивность = / .
2 Вероятность того, что все обслуживающие устройства свободны P0 =.
L n n!
n= 3 Вероятность того, что в обслуживающей системе занято n аппаратов P Pn = n, n = 1, 2, K, L.
n!
Это так называемая формула Эрланга.
Цех x x x x x x х х х х х х х х х L Рис. 4.14 Система без очередей Вероятности Pn могут быть определены по рекуррентным формулам Pn = Pn-1,n = 1,2,K, L.
n 4 Вероятность отказа очередному требованию в обслуживании L L!
V = PL =.
L n n!
n= 5 Среднее число занятых обслуживающих устройств L L n = = nP (n -1)!n P0.
n=0 n= 6 Среднее число простоев оборудования s = L - n.
7 Коэффициент простоя оборудования об kпр = s / L.
8 Коэффициент занятости оборудования об kзан = n / L.
M M 4.5.2 СИСТЕМА H В данной системе в отличие от предыдущих число приборов бесконечно велико. Такой предельный случай часто используется в расчетах, когда число обслуживающих устройств велико. Подобная идеализация позволяет получить более простые расчетные формулы. При таком варианте, как и в предыдущем случае, очереди нет, но здесь потеря требования невозможна. Число требований в сис теме всегда равно числу занятых обслуживающих устройств.
Расчет системы ведется по следующим формулам.
1 Неустановившаяся вероятность того, что в момент времени t заняты n приборов при условии, что в начальный момент времени они свободны Pn (t) = n (1- e-t )n e-(1-t), n = 0, 1, 2, K n!
2 Среднее число обслуживающих устройств в момент времени t, если при t = 0 они все свободны n(t) = (1- e-t ).
3 Установившаяся вероятность, что в системе будут работать n аппаратов, каково бы ни было на чальное состояние системы Pn = ne-.
n!
4 Вероятность того, что в установившемся режиме все аппараты свободны P0 = e-.
4.6 Системы с очередями и частичными потерями M M L 4.6.1 СИСТЕМА H Возможными вариантами такой системы могут быть системы с условиями:
- n N, где N - предельное число требований в системе (требование не встает в очередь, т.е. теряет ся для обслуживающей системы, если число таких требований, находящихся в системе, равно N);
- m M, где M - предельное число требований в очереди (здесь требование не встает в очередь, т.е.
теряется для обслуживающей системы, если число требований в очереди уже равно M);
- t0 T0, где T0 - предельное время ожидания в очереди (в этом случае требование выходит из оче реди, если его время ожидания начала обслуживания уже равно T0);
- tс Tс, где Tс - предельное время пребывания в системе (требование покидает систему, если оно находится в ней уже время Tс) Могут быть и любые другие условия, при которых требование покидает систему или вообще не встает в очередь.
Частным случаем рассматриваемой системы является система, где требование встает в очередь только в том случае, если эта очередь меньше предельного значения N:
m < M, где m - длина очереди.
Если m = M, то требование в очередь не встает. Очевидно, что 0, если n L;
m = n - L, если L < n N, где L - число приборов;
n - число требований в системе.
Обслуживающая система отказывает в обслуживании при n = L + M, т.е. L требований обслуживается и M требований стоит в очереди.
Схема системы массового обслуживания с очередью и потерями представлена на рис. 4.15.
Расчетные формулы системы имеют вид:
1 Трафик-интенсивность = / .
2 Вероятность нахождения в системе n требований n n! P0, 1 n < L;
Pn = P n, L n L + M.
L!Ln- L 3 Вероятность того, что в системе работают n приборов n n! P0, 1 n < L;
Pn = P nP0, L n L + M.
L!Ln- L x x х х х х х х х х х х L M x x Рис. 4.15 Система с очередью и потерями 4 Вероятность того, что в очереди стоит m = n - L требований 0, если 1 n < L;
Pm = n, L n L + M.
L!Ln- L 5 Вероятность, что все обслуживающие аппараты свободны P0 =, L- 1 n + n[1- ( / L)M +1] n! L!(1- / L) n= где L - максимальное число аппаратов;
M - наибольшая допустимая длина очереди.
6 Вероятность того, что поступившее требование получит отказ, т.е. не будет принято на обслужи вание:
P PL+M = L+M.
L!LM 7 Вероятность того, что все аппараты будут заняты (вероятность образования очереди) 1- ( / L)M + П = PL.
1- / L 8 Вероятность того, что время ожидания в очереди будет больше tf -Lt M f - (Lt )n пe f (t ) = [( / L)n - ( / L)M ]..
f n!
1- ( / L)M + n= 9 Средняя длина очереди PL m = - (M +1)( / L)M +1 + M ( / L)M +2.
L (1- / L) 10 Среднее число свободных приборов L- L - s = nP0.
n!
n= 4.7 Пример расчета системы массового обслуживания с несколькими каналами и ограниченным числом клиентов M M L Эта система по принятой классификации изображена на рис. 4.12. и описана в п. 4.4.4.7.
N T Пусть в цехе имеется N = 16 ткацких станков и L = 4 механиков. Таким образом, максимальное чис ло требований в системе может быть n = 16, если же их число n L, возникает очередь. Параметр пуассо новского входного потока = 10 1/сут, а параметр обслуживания = 100 1/сут, следовательно, трафик интенсивность = 0,1.
Для последующих расчетов необходимо определить коэффициенты an, n = 0, 1, Е, 20, по формуле 1 при n = 0;
N - n + an = an-1, 1 n ;
n N - n + an-1, 5 n.
N В результате расчетов получено a0 = 1;
a1 = 2;
a2 = 1,9;
a3 = 1,14;
a4 = 0,48;
a5 = 0,178;
a6 = 0,067;
a7 = 0,023;
a8 = 0,0074;
a9 = 0,0022;
a10 = 0,000605;
a11 = 0,00015;
a12, a13, a14, a15, a16 < 0,0001.
= 2 +1,9 +1,14 + 0,48 + 0,178 + 0,067 + 0,023 + 0,0074 + 0,0022 + an n= + 0,000605 + 0,00015 + K = 5,791.
ВЕРОЯТНОСТЬ, ЧТО СТАНКИ НЕ БУДУТ РАБОТАТЬ (ОТСУТСТВИЕ ТРЕБОВАНИЙ В СИСТЕМЕ) 1 P0 = = = 0,147.
1 + 5, 1 + n a n= Вероятности работы n станков (нахождения в системе n требований) Pn = anP0 :
P1 = P0a1 = 0,294;
P2 = P0a2 = 0,279;
P3 = P0a3 = 0,168;
P4 = P0a4 = 007;
P5 = Pa5 = 0,026;
P6 = P0a6 = 0,0098;
, 0,007;
P7 = P0a7 = 0,0033;
P8 0 a8 = 0,0010 ;
;
P9 = P0a9 = 0,0003, K = P 0,00109;
Среднее число станков, ждущих работу (требований в очереди) m = - 4)Pn = P5 + 2P6 + 3P7 + 4P8 + 5P9 + 6P10 + 7P11 + (n + 8P12 + 9P13 +10P14 +11P15 +12P16;
m = 0,026 + 2 0,0098 + 3 0,00339 + 4 0,00109 + 5 0,0003 + K = 0,057.
Среднее число простоев ткацких станков s = - n)Pn = 4P0 + 3P1 + 2P2 + P4;
s = 2,196.
( n= Среднее число работающих станков (требований в системе) n = L + m - s;
n = 4 + 0,057 - 2,196 = 1,861.
Коэффициент простоя механиков (приборов) об об kпр = s / L;
kпр = 0,549.
Коэффициент простоя станков (требований) тр тр kпр = m / N;
kпр = 0,0036.
Вероятность существования очереди P = 1- ;
P = 1- 0,147 - 0,279 - 0,168 = 0,112.
Pn n= Среднее время ожидания в очереди m 0, t = ;
t = 0,000403 сут = 5,8 мин.
f f (N - n) 10(16 -1,861) 4.8 Моделирование процессов массового обслуживания Системы массового обслуживания далеко не исчерпываются теми проанализированными случаями, которые были рассмотрены, но, к сожалению, только эти случаи и поддаются пока аналитическому ре шению. Более сложные случаи могут быть исследованы лишь с помощью методов моделирования с ис пользованием вычислительной техники.
На рис. 4.16 представлена схема моделирования системы массового обслуживания.
Расчет ведется через малый промежуток времени t, который задается счетчиком времени 1. Этот счетчик определяет также текущее время t.
Генератор случайных чисел 2 генерирует интервал времени между появлениями очередных требований.
При этом плотность распределения интервалов времени должна соответствовать реальной плотно сти распределения системы реально функционирующей или гипотетической системы.
Как только прошло время t, появляется новый клиент. При этом блок 4 проверяет, есть ли очередь или нет, другими словами есть ли свободный прибор.
Если такой прибор есть, то немедленно начинается обслуживание, если же свободных приборов нет, клиент решает, встать ли ему в очередь или уйти.
Если очередь велика (n = N), проверку этого осуществляет блок 5, то клиент попадает в очередь.
При этом он решает, возвратится ли ему снова на обслуживание в эту систему или уйти в другую (блок 6). Если клиент покидает систему, то он навсегда теряется для нее, и в этом случае система несет эко номические убытки.
Если же очередь не велика, то в блоке 7 проверяются другие возможные причины, препятствующие клиенту встать в очередь. Например, это может быть отсутствие нужного мастера. В блоке 8 снова решается вопрос о повторном в будущем использовании этой же самой системы массового обслу живания для удовлетворения заявки на обслуживание.
Если клиент решил встать в очередь, то последняя увеличивается на единицу (блок 9).
Блок 10 моделирует ожидание в очереди. Здесь для каждого клиента подсчитывается время ожида i ния в очереди t0. Через каждый маленький интервал времени t блок 11 проверяет, не освободился ли прибор. В случае положительного решения этого вопроса очередь уменьшается на единицу (блок 12) и требование поступает на обслуживание в цех. Если же свободного прибора нет, блок 13 проверяет, це лесообразно ли продолжать стоять в очереди. Чаще всего это означает, не превышает ли уже ожидание предельного времени. Очевидно, могут быть и любые другие условия.
Если в блоке 13 принимается решение покинуть очередь, то эта очередь уменьшается на одного клиента (блок 14), затем в блоке 15 решается вопрос о целесообразности в будущем снова попасть в данную обслуживающую систему.
Блок 16 уменьшает число свободных приборов на единицу, и клиент попадает в цех на обслужива ние.
Счетчик времени t t 2 t Плотность интервалов между клиентами НЕТ 3 Время НЕТ t 23 возврата прошло наступило 5 6 возврат в ДА n=N систему НЕТ будет Есть НЕТ 4 свободный ДА прибор 7 8 будет встать в возврат в ДА 16 ДА очередь систему Уменьшение числа свободных приборов плотность времени ДА НЕТ обслуживания t0 18 Процесс обслуживания Увеличение Определение текущего Процесс обслуживания очереди на времени обслуживания ti Определение текущего 10 ожидание в очереди 19 прошло клиент обслужен Уменьшение i 20 t0 очереди на 1 ДА Увеличение числа свободных 21 условие НЕТ условия НЕТ приборов продолжения 13 ожидания на 1 обслуживания очереди ДА выполнены 22 НЕТ Увеличение Уменьшение свободной очереди НЕТ прибыли на 15 возврат ДА в систему будет НЕТ клиент потерян Рис. 4.15 Моделирование системы массового обслуживания Блок 18 имитирует процесс обслуживания. Сюда поступает время обслуживания очередного требо вания, которое выдает генератор 17.
Генератор реализует тот закон распределения вероятности, который может быть тождественен плотно сти распределения времени обслуживания реального (анализируемого) или гипотетического произ водства.
Через каждый интервал времени t0 блок 19 проверяет, не окончилось ли обслуживание одного из клиентов. Если обслуживание окончилось, то число свободных приборов увеличивается и это делает блок 20. Если же обслуживание не окончилось, то в блоке 21 решается вопрос о продолжении нахожде ния в системе обслуживания. Чаще всего проверяется, не превосходит ли суммарное время нахождения в системе (в очереди и в цехе) предельно допустимого для клиента времени. Если клиент уходит, то число свободных приборов увеличивается на единицу (блок 22).
Генератор 24 генерирует продолжительность времени (случайную величину), спустя которое очередное требование возвращается в систему на обслуживание. Наступление момента возвращения каждого требования контролируется блоком 23.
Рассмотренная блок-схема (рис. 4.16) является блок-схемой имитационного функционирования системы массового обслуживания. Имитация осуществляется следующим образом. Датчик случайных чисел 2 через одинаковые промежутки времени генерирует либо 0, либо 1, что означает, появилось ли за данный промежуток времени новое требование или нет. Образующийся поток требований такой же, как и на реальном объекте, естественно, в статическом смысле, т.е. вероятность появления того или иного числа требований в единицу времени одинакова, что на реальном объекте, что на имитационной моде ли.
Датчик случайных чисел 17 каждому требованию, "поступающему" в цех, ставит в соответствие время, которое он будет обслуживаться в цеху. При этом значения этих времен в статистическом смыс ле такие же, как и на реальном объекте.
Чем точнее заданы распределения вероятностей датчиков 2 и 17 с соответствующими реальными законами распределения вероятностей появления новых требований и времен обслуживания, получен ными на имитационной модели, тем больше совпадают с реальными процессами обслуживания на ис следуемой системе.
Теперь рассмотрим вопросы расчета операционных показателей по данным имитационного экспе римента. Пусть этот эксперимент длится время Тобщ. Далее замеряются время Т0, когда в системе не бы ло ни одного требования, и времена Тn, n = 1, 2, Е, когда в системе было соответственно 1, 2, Е требо ваний. Тогда вероятность того, что в системе будет n требований Pn = Tn/Tобщ.
Вероятность F(n), что в системе будет не больше n требований, определяется формулой n F(n) =.
Pi i= Вероятность (n), что в системе будет более n требований (n) = 1- F(n).
Вероятность того, что в системе не будет ни одного требования P0 = T0 / Tобщ.
Среднее число требований в системе равно n =.
nPn n= Пусть L - число обслуживающих клиентов. Тогда среднее число клиентов в очереди N m = - L)Pn, (n n=L+ где N - предельное число клиентов в системе, при превышении которого клиент не встает в очередь.
L Среднее число простоев приборов: s = - n)Pn.
(L n= тр Коэффициент простоя требования: kпр = m / N.
об Коэффициент простоя приборов (оборудования): kпр = s / L.
L- Вероятность существования очереди: P = 1-.
Pn n= Время ожидания в очереди определяется по данным имитационного эксперимента. На рис. 4. представлены два варианта обслуживания требований в системе массового обслуживания.
В обоих вариантах рис. 4.17, а и рис. 4.17, б в момент 1 поступает требование n, в момент 3 посту пает требование (n + 1). В это время прибор все еще обслуживает требование n - 1, обслуживание кото рого заканчивается в момент 2.
Начиная с момента 2, требование n поступает в систему и начинает обслуживаться. Таким образом n - это время ожидания требования n в очереди.
tn n n + 1 t n 1 2 3 (n - 1) (n) (n + 1) t n n+ a) tn 1 2 4 3 t n (n - 1) (n) (n + 1) t n б) Рис. 4.17 К расчету времени ожидания:
a - время обслуживания велико;
б - время обслуживания мало В момент 3 поступает следующее требование n + 1. На рис. 4.17, а время обслуживания n велико, и требование n + 1 также ожидает в очереди время n прежде, чем начнет обслуживаться. Это время рас считывается по формуле n+1 = n + n - tn, где tn - время между последовательными поступлениями тре бований.
На рис. 4.17, б время обслуживания n мало, и время ожидания (n + 1)-го требования в очереди рав но нулю. Требование начинает обслуживаться сразу. Таким образом n + n - tn, если n + n > tn;
n+1 = 0, если n + n 0, n = 1, 2, K Начальные условия для этой рекуррентной формулы 1 0, т.е. первое требование начинает об служиваться без задержки.
Время нахождения в системе определяется формулой c tn = tn + n.
Среднее время ожидания в очереди R t = / R.
f n n= Среднее время пребывания в системе R c ts = / R.
tn n= 4.9 Оптимизация процессов массового обслуживания Оптимизация систем массового обслуживания, как и всякая оптимизация, заключается в выборе варьируемых параметров (называемых управлением), при которых целевая функция принимает мини мальное (максимальное) значение и удовлетворяется система ограничений и условий.
В системах массового обслуживания в качестве варьируемых параметров обычно принимают: L - число обслуживаемых приборов;
1/ - среднее время обслуживания клиента одним прибором.
Выбор более дорогого прибора с меньшим временем обслуживания удорожает простой прибор, но уменьшает время ожидания клиента в очереди.
Иногда в качестве варьируемого параметра может быть использована структура s системы (число очередей в системе, последовательное или параллельное расположение приборов и др.).
Также в качестве варьируемого параметра иногда используется число М - максимально допустимое число клиентов, после которого клиент получает отказ в обслуживании и др.
Пусть U - вектор варьируемых параметров, U = (L, , s, M). Очевидно, каждая из варьируемых пе ременных вектора U изменяется в определенных пределах:
Lmin L Lmax;
min max;
(4.40) s A;
M M M.
min max Причем Mmax может быть и бесконечностью.
Теория массового обслуживания устанавливает связь (математическую модель) между варьируемыми переменными и вектором операционных показателей у. Эта связь в операторной форме может быть представлена в виде y = A(U ). (4.41) Оператор А представляет собой как систему аналитических формул, так и может быть задан в алго ритмической форме (в виде имитационных алгоритмов моделирования).
Целевая функция Q(y) оценивает численно, насколько операционные показатели хороши.
Задача оптимизации ставится как задача отыскания такого вектора U*, при котором целевая функ ция Q(y) примет минимальное (максимальное) значение, при этом у определяется по (4.41), а варьируе мые переменные удовлетворяют (4.40).
Иногда накладываются дополнительные технологические ограничения, которые также должны удовлетворяться, что сужает область возможных изменений вектора U.
В качестве целевой функции часто выбирается некоторый экономический критерий, который учи тывает средние потери от ожидания в очереди клиентами и средние потери от простоя оборудования:
Q(y) = (C1m + C2s)T, где mT - среднее время, потерянное в очереди клиентами за время имитации Т;
sT - среднее время, по терянное из-за простоев приборов;
С1, С2 - стоимости единицы времени из-за ожидания клиентов в оче реди и простоя приборов соответственно.
Если С1 и С2 постоянны, то обычно рассматривают целевую функцию в виде Q(y) = С1m + С2s.
Величины С1 и С2 могут вычисляться довольно сложно, зависеть от многих факторов, быть нели нейными функциями многих переменных (времени непрерывной работы, субъективных факторов уста лости обслуживающего персонала и т.д.).
Особенно трудно адекватно учесть величину С1, так как из-за простоев в очереди клиенты могут те ряться (заходить в другую систему обслуживания, не обращаться в будущем к данной системе обслу живания, получать меньше, чем они намеривались и т.п.).
5 УПРАВЛЕНИЕ ЗАПАСАМИ Запас обозначает ресурсы, готовые к употреблению, но временно не используемые.
Если количество ресурсов можно регулировать, то возникает проблема управления запасами.
5.1 Задачи управления запасами Основная задача управления запасами заключается в том, что необходимо принять некоторое управляющее воздействие относительно запасов, заключающееся в решении вопроса, сколько и когда надо иметь этих запасов. Имеющиеся запасы, как правило, хранятся на складах, поэтому задачи управ ления запасами называют еще задачами работы и управления складов. Решение этих задач должно быть таковым, чтобы минимизировалась некоторая целевая функция, которая характеризует эффективность работы склада.
Обычно целевой функцией является экономическая функция, включающая следующие составляю щие:
1 Затраты на хранение запаса. Эти затраты пропорциональны объему запасa и времени хранения.
Здесь, как правило, учитываются:
а) затраты на складские операции (погрузка, разгрузка, портальные краны и т.п.);
б) стоимость хранения (плата за аренду помещения);
в) страхование;
г) потери, порчи продукции;
д) затраты на учет.
2 Затраты на компенсацию потерь от недостатка запасов (потери от дефицита).
Учет этих потерь ведется одним из двух способов:
а) потери пропорциональны объему недостающих ресурсов и времени, в течение которого сущест вует дефицит;
б) потери оцениваются постоянным штрафом, например, в размере потери прибыли и компенсации морального ущерба, нанесенного предприятию.
В принципе могут быть и другие составляющие работы склада. Так, можно учитывать затраты на размещение заказа на найм и обучение рабочих при изменении характера производства, от объема заку пок может зависеть цена ресурсов и т.п.
В качестве управляющих воздействий (варьируемых переменных) выбирают либо объем посту пающих ресурсов, либо периодичность или моменты времени поступления ресурсов.
Задачи управления запасами возникают всегда и повсеместно, при любом производстве и коммер ческой организации. Так, энергетики должны решить, сколько ввести в систему электростанций, какой мощности включить генератор;
университет должен решить, сколько готовить тех или иных специали стов;
тренер должен решить, сколько готовить запасных игроков;
режиссер - сколько нужно дублеров на спектакль;
военные - сколько необходимо военных запасов;
финансист - каков должен быть резерв ный капитал в банке и т.п.
Задачи теории управления запасами подразделяются на следующие категории: детерминированные;
случайные, статически устойчивые (стационарные);
случайные, но статически неустойчивые (нестацио нарные);
с неизвестным характером спроса.
С другой точки зрения, задачи теории управления запасами можно подразделить по:
а) характеру пополнения запасов (отсрочка, непрерывный, периодический, осуществляется через некоторые интервалы времени);
б) характеру ограничений (максимальный или минимальный объемы, вес, время изготовления, на личие финансовых средств, стоимость перевозок и др.).
5.2 Алгоритмы (характер) пополнения запасов Пополнение и расходование запасов часто изображают графически (рис. 5.1).
На рис. 5.1 изображен процесс расходования запасов на производство со склада. Начальный запас товара в момент t0 составляет Sн. Рассматривается промежуток времени T, в течение которого в момен ты t1, t2, t3, t4 запасы отпускаются со склада. Ломаная линия показывает изменение запасов на складе. В конечный момент времени запасы равны Sк. Соединив Sк и Sн, получают линию, которая показана пунк тиром. Чаще всего считается, что именно эта идеализированная линия отражает отпуск товара со скла да. Этот прием отвечает математическому описанию задачи складирования при достаточно малых по требностях.
S Sн Sк t0 t1 t2 t3 t4 t5 t Т Рис. 5.1 Процесс расходования запасов Smax б б б б б б S1 S2 S3 S4 S S6 S Smin t0 T t1 T t2 T t3 T t4 T t5 T t a) Smax б б б S S S Smin t0 T1 t1 T2 t2 T3 t3 T4 t4 T5 t б) Рис. 5.2 Мгновенное (дискретное) пополнение запасов:
а - тип I (периодический), Т = const;
б - тип II (релаксационный), S = const Два основных алгоритма управления запасами при дискретном характере пополнения этих запасов изображены на рис. 5.2.
Первый тип (рис. 5.2, а) называется периодическим и обозначается тип I, второй (рис. 5.2, б) - ре лаксационным, тип II. Первый тип характеризуется периодическим пополнением запасов. В этом случае склад пополняется запасами до предельной величины Smax через равные промежутки времени, интерва лы времени Т одинаковы, пополнения Si разные.
Во втором случае склад пополняется каждый раз на величину S, когда запасы на нем достигают нижнего критического уровня Smin. Здесь интервалы времени Тi разные, величина пополнения одинакова (S = Smax - Smin).
Непрерывная система пополнения запасов показана на рис. 5.3, она также может быть двух типов:
тип I - периодический (рис. 5.3, а), тип II - релаксационный (рис. 5.3, б).
Первый тип соответствует случаю, когда весь диапазон изменения времени делится на равные уча стки Т/2. При этом ветвь "б" кривой изменения запасов (рис. 5.3, а) соответствует потреблению запасов, а ветвь "а" на участке Т/2 - пополнению запасов на складе, причем может одновременно происходить расходование запасов на производство. В данном случае интервалы T/2 постоянны, а изменения запасов на складе Si разные.
S Smax б а а S1 а S3 б а б б S2 S Smin t Т Т/2 T/2 T T a) S Smax а б а б а б S S S Smin t Т1 T2 T б) Рис. 5.3 Непрерывное пополнение запасов:
а - тип I (периодический), Т = const;
б - тип II (релаксационный), S = const При релаксационном характере пополнения склада (рис. 5.3, б, участок "а") непосредственное его пополнение начинается, если запас на нем достигает минимальной величины. При этом S = Smax - Smin является постоянной величиной, а интервалы времени Тi разные.
Очевидно, движение товаров на складе при дискретном характере пополнения запасов является идеализированным, так как мгновенное пополнение склада невозможно. Задержка в пополнении товара может привести к серьезным последствиям в производстве. В связи с этим приказ о пополнении запасов на складе должен отдаваться заранее, когда еще не известно точно, какое именно количество товара не обходимо будет приобрести (для управления типа I) или через какое время запас точно достигнет мини мального уровня Smin (для управления типа II). Все это приводит к тому, что необходимо построить "опе режающий" алгоритм, т.е. алгоритм пополнения склада с прогнозом.
Пусть - интервал времени между решениями о приобретении ресурсов (заключение договора) до момента прихода товара на склад, являющийся постоянной величиной, не зависящей от объема постав ленного товара.
Характер периодического алгоритма управления типа I с прогнозом изображен на рис. 5.4.
В рассматриваемом алгоритме интервалы времени Т между поставками известны. Задача заключа ется в том, что в момент времени tk, называемый контрольным моментом времени, отстоящем на интер вал от момента привоза товара, необходимо спрогнозировать величину Si, т.е. сколько товара требу ется привезти. При прогнозе надо учитывать скорость уменьшения товара на складе.
Smax K K S S1 S Smin K tk tk tn t T T T Рис. 5.4 Периодический алгоритм с прогнозом Smax S K K S K S Smin tk tk tk t T1 T2 T Рис. 5.5 Релаксационный алгоритм прогноза Релаксационный алгоритм управления с прогнозом запасами на складе (тип II) изображен на рис.
5.5.
В рассматриваемом алгоритме необходимо, наблюдая за скоростью изменения запасов на складе, спрогнозировать контрольный момент времени такой, чтобы через интервал запас на складе достиг минимального уровня Smin. Именно в этот момент нужно заключить договор на поставку товара в одном и том же количестве S.
Таким образом, в периодическом алгоритме прогнозируется количество товара Si, в релаксацион ном - интервалы времени Тi (моменты закупки товара).
На практике довольно часто применяется алгоритм, при котором запасы пополняются, если уровень запасов достиг некоторого критического значения Sкр. Характер этого алгоритма изображен на рис. 5.6.
Согласно рассматриваемому алгоритму, решение о пополнении запасов (договор на поставку ре сурсов) принимается в момент времени tкp, когда уровень запасов на складе достиг критического значе ния Sкp. Через некоторое время - время задержки товар поступает на склад. Пополнение S всегда одинаково, поэтому уровень товара на складе может после пополнения оказаться как выше, так и ниже предельного уровня Smax.
S Smax S S S Sкр K K Smin T1 T2 T Рис. 5.6 Алгоритм по достижению уровня пополнения Расположение склада Склад резервов может иметь двойное назначение. В одном случае (рис. 5.7) склад служит хранили щем сырья, ресурсов, полуфабрикатов, которые идут дальше на производство (или перепродажу). Такой склад называется складом на входе. При этом вертикальный участок (рис. 5.2) соответствует закупке товаров, участок "б" - отпуску ресурсов со склада на производство.
На рис. 5.3 участок "а" соответствует закупке, а участок "б" - отпуску на производство. На участке "а" может одновременно быть и закупка и отпуск на производство.
Под производством понимается перепродажа, оптовая или розничная торговля и т.д.
Затраты на хранение включают в этом случае в себя постоянную составляющую (собственно закуп ку) и переменную (затраты на охрану, аренду, рабочую силу), обычно пропорциональную времени и количеству хранящихся ресурсов.
Закупка Отпуск на Склад производство Производство Рис. 5.7 Блок-схема склада на входе Поступление Отпуск Производство Склад ГОТОВОЙ ПРОДУКЦИИ ПОТРЕБИТЕЛЯМ Рис. 5.8 Блок-схема склада на выходе Склад готовой продукции располагается на выходе производства (рис. 5.8).
На таком складе поступления - это выход продукции с завода, выход со склада - отпуск товара по требителям.
На рис. 5.3 участок "а" соответствует поступлению готовой продукции (производству), участок "б" - отпуску товара со склада. Естественно, что и на участке "а" и на участке "б" отпуск товара и поступ ление на склад могут быть одновременными. Однако, участок "а" в случае варианта склада на выходе соответствует интенсивному производству, а участок "б" - интенсивному отпуску. В случае склада на входе смысл этих участков противоположен.
Рис. 5.2 при рассмотрении склада на выходе соответствует случаю, когда производство очень бы строе (мгновенное). Это весьма идеализированный склад. Обычно для склада на выходе характерно из менение запасов на нем в соответствии с рис. 5.3, для склада на входе - с рис. 5.2.
Задачи управления запасами можно классифицировать по ряду признаков, которые характеризуют их со всех сторон. Основными характеристиками являются следующие:
- сбыт, который может быть детерминированным (Д) и случайным (С);
- поступление товаров - дискретное (Д), непрерывное (Н);
- алгоритм управления запасами - периодический (П), непериодический (Н);
- количество продукции - одна ("1"), много (n);
- затраты на хранение - есть ( + ), нет ( - );
- затраты на дефицит - есть ( + ), нет ( - ).
В соответствии с принятыми характеристиками задача управления запасами может быть записана как = сбыт поступление алгоритм количество продукции затраты хране- дефи- ние цит 5.3 Детерминированная задача управления запасами с единственным видом продукции Рассмотренная задача имеет несколько вариантов.
5.3.1 ПЕРИОДИЧЕСКИЙ ТИП АЛГОРИТМА.
ЗАТРАТЫ НА ХРАНЕНИЕ ПРОПОРЦИОНАЛЬНЫ РАЗМЕРУ ПАРТИИ (СЕРИИ). СКЛАД НА ВХОДЕ.
ДЕФИЦИТ ОТСУТСТВУЕТ По принятой классификации задача обозначается как = / Д / Д / П / 1 / + / - /.
Данную задачу удобно рассмотреть на примере работы склада по периодическому типу алгоритма на протяжении достаточно большого времени.
При этом считают, что а) продукция однородна;
б) максимальный уровень запасов фиксирован;
в) ресурсы поступают на склад партиями (дискретно) или сериями. Также считают, что а) стоимость дос тавки партии Сp;
б) стоимость хранения единицы продукции в единицу времени (например, сутки) Сs;
в) общее потребление товара за время равно N.
Задача управления запасами состоит в том, чтобы найти уровень пополнения запасов S и период пополнения Т, при которых затраты на создание и хранение N ресурсов были бы минимальны.
Пусть расход ресурса (например, деталей) равномерен. Тогда в единицу времени расходуется n = N/ ресурсов.
Не уменьшая общности, можно считать, что Smin = 0. В этом случае изменение запаса на периоде Т будет выглядеть в соответствии с тем, как изображено на рис. 5.9.
S S S/ t 0 T/2 T Рис. 5.9 Изменение запаса на периоде Искомая величина S называется иногда экономической партией или серией. Этот термин особенно удобен при дискретном характере ресурсов, например, если ресурсы - детали.
Число серий (периодов) на интервале можно определить либо по формуле N = /, (5.1) либо по формуле n = /S. (5.2) Целевая функция, представляющая собой затраты на серию, для рассматриваемой задачи является аддитивной и включает в себя затраты на доставку партии S - q1, затраты на хранение - q2. Таким об разом, целевая функция записывается в виде q = q1 + q2, где очевидно q1 = Ср;
q2 = (S/2)ТСs.
Здесь обозначено: Ср - стоимость доставки партии S;
S/2 - средний за период Т запас на складе;
Сs - стоимость хранения единицы продукции за единицу времени.
Общие затраты на хранение за время равны S Q = C n + TCsn.
p Используя (5.1), (5.2), выражение для общих затрат преобразуется к виду N S Q = C + TCs p S 2 T или C N Cs p Q = + S. (5.3) S Таким образом, общие затраты (5.3) состоят из суммы двух составляющих, одна из которых обрат но пропорциональна уровню пополнения запасов S: Q1 = C N / S, другая же пропорциональна этому p уровню: Q2 = CsS / 2.
Минимум общих затрат на хранение, т.е. минимум целевой функции Q находится из условия Q / S = 0 :
C N Cs p - + = 0, (5.4) S откуда C N p S = 2. (5.5) Cs Выражение (5.4) определяет уровень пополнения склада или оптимальное число деталей в эконо мической партии (серии), из него видно, что C N / S = Cs = S / 2, т.е. составляющие общих затрат равны p между собой Q1 = Q2.
Это свидетельствует о том, что минимум затрат при решении задачи управления запасами имеет место тогда, когда общие затраты Q1 = C N / S равны общим затратам Q2 = CsS / 2 на хранение этих p запасов (рис. 5.10).
Оптимальное число серий (периодов) n* согласно (5.2) равно n* = N / S*.
Оптимальный интервал цикла * T = / n* = S*.
N Cs * Оптимальное значение целевой функции Q* = 2Q2 = 2 S*.
С учетом (5.5) Q* = 2NС Cs.
р Интерес представляет оценка влияния погрешности в определении S на целевую функцию.
Средняя погрешность при ошибке в определении S на 10 % дает следующую погрешность целевой функции Q = [Q(S + 0,1S ) - Q(S ) + Q(S - 0,1S ) - Q(S)]= [Q(1,1S) - 2Q(S) + Q(0,9S)].
= Q Cs Q2 = S Q* C N p Q1 = S Рис. 5.10 Графическое определение оптимальной партии S Отсюда можно получить S* S Q 1 Q(1,1S*) + Q(0,9S*) = -1.
Q* Q* 5.3.2 ПЕРИОДИЧЕСКИЙ ТИП АЛГОРИТМА. СКЛАД НА ВХОДЕ. НАЛИЧИЕ ДЕФИЦИТА.
= Д Д П1+ +.
Для данной задачи полагают, что а) продукция однородна;
б) максимальный уровень запасов фиксирован;
в) ресурсы поступают на склад партиями (или сериями);
г) максимальный уровень де фицита фиксирован.
Изменение запаса на складе для периода Т представлено на рис. 5.11.
В момент времени t = 0 уровень запаса равен Smax, в момент t = tкр уровень запаса на складе достига ет условного нуля (нуля или минимального уровня), после чего производство невозможно вследствие дефицита ресурсов.
На интервале времени Т2 (от tкр до Т) дефицит растет и в момент t = Т достигает максимального значе ния Sдеф. После этого на склад поступают ресурсы в размере S, которые перекрывают дефицит, и уро вень ресурсов на складе снова становится Smax:
S = Smax - Sдеф.
Общие затраты в этом случае складываются из Q1 - затрат на доставку ресурсов, Q2 - затрат на хранение на интервале времени Т1, а также Q3 - потерь из-за дефицита на интервале времени Т2:
Q = Q1 + Q2 + Q3.
Очевидно Q1 = C n, где C - стоимость доставки партии, а n - число партий, которые определяют p p ся, как и раньше S Smax а S 0 tкр Т T T t Sдеф c b Рис. 5.11 Изменение запасов на складе N n = =. (5.6) T S Здесь - общий интервал времени, в течение которого должно быть израсходовано на производст во N ресурсов.
Затраты на хранение, как и раньше, пропорциональны треугольнику "0аtкр":
Q2 = SmaxT1Csn, (5.7) где Cs - стоимость хранения единицы продукции в единицу времени.
Убытки из-за дефицита пропорциональны треугольнику "tкрbТ", т.е. пропорциональны дефициту и времени дефицита с коэффициентом пропорциональности Cд Q3 = SдефT2Cдn или Q3 = (S - Smax )T2Сдn, где Cд - цена дефицита единицы продукции в единицу времени.
Из подобия треугольников "а0tкр" и "аbс" можно записать T1 Smax = T S или T1 = TSmax / S. И тогда затраты на хранение, определяемые по (5.7) с учетом (5.6), можно рассчитать по выражению 2 1 Smax 1 SmaxCs Q2 = CsTn =.
2 S 2 S Из подобия треугольников "аbс" и "tкрТb" следует, что T2 Sдеф = T S и соответственно Sдеф S - Smax T2 = T = T. (5.9) S S Стоимость убытков (5.8) с учетом (5.9) определяется соотношением (S 1 (S - Smax )2 1 - Smax )2Cд Q3 = TСдn =.
2 S 2 S Таким образом, общие затраты определяются целевой функцией С N (S SmaxСs 1 - Smax )2Сд p Q(S, Smax ) = + +.
S 2S 2 S * Оптимальные значения S*и Smax определяются из условий Q Q = 0;
= 0.
S Smax Решение этой системы дает С Сs + Сд 2N p S* = ;
Сs Cд (5.10) C Cд Cд 2N p * = = S*.
Smax Cs Cs + Cд Cs + Cд Отношение * Smax = (5.11) S* называется плотностью убытков.
* Smax T1 T1 Т Так как =, то =, а 1- =, T T Т S* откуда и вытекает физический смысл плотности убытков, который заключается в том, что в течение (1 - ) доли от Т будет дефицит товара - Т2 = (1 - )Т. Из (5.10) плотность убытков можно определить так же, как Cд =.
Cs + Cд Таким образом, плотность убытков зависит от соотношения цены хранения товаров Ср и цены пла ты за дефицит товаров Cд. Она изменяется в пределах 0 1. Если плата за дефицит товаров равна нулю, то = 0, если эта плата стремится к бесконечности, то = 1.
Используя (5.6), получают выражение для оптимального времени цикла * T = / n* = S* / N, а, используя (5.10) - следующее выражение C Cs + Cд p * T =.
N Cs Cд В соответствии с выведенными соотношениями оптимальное значение целевой функции имеет вид Cд * Q* = Q(S*, Smax ) = 2NCsC.
p Cs + Cд В заключении следует еще раз выписать основные расчетные формулы алгоритма:
Cд 1 Плотность убытков =.
Cs + Cд * 2 Максимальный уровень ресурсов Smax = S*.
C 2N p 3 Оптимальное поступление на склад S =.
Cs C 2 p * 4 Оптимальное время периода T =.
N Cs * 5 Оптимальное число серий n* = / T = N / *.
6 Оптимальное значение целевой функции Q* = 2NCsC.
p При отсутствии дефицита, т.е. когда = 1 перечисленные формулы совпадают с формулами разде ла 5.1, т.е.
* Smax = Smax;
S* = S11 ;
* T = T1 1 * = 1, ;
где Smax, S1, T1, 1 - соответствующие величины при отсутствии дефицита.
Как видно, с увеличением дефицита потери увеличиваются, как и. При заданной величине = * в соответствии с (5.11) должно соблюдаться соотношение Smax = S*.
5.3.3 ПЕРИОДИЧЕСКИЙ ТИП АЛГОРИТМА.
СКЛАД НА ВЫХОДЕ. НАЛИЧИЕ ДЕФИЦИТА При рассмотрении этой задачи полагают, что а) продукция однородна;
б) максимальный уровень запаса и дефицита не фиксирован.
Изменение запасов на складе для периода Т изображается графиком, представленным на рис. 5.12.
Уровень запасов в начальный момент времени t = 0 равен нулю, затем в течение времени Т1 он воз растает до максимальной величины Smax, после чего в течение периода времени Т2 убывает до нуля. По следнее свидетельствует о том, что в течение Т2 производства либо не было, либо его темп был недоста точен и запасы на складе уменьшились. Начиная с момента С (рис. 5.12), запасов на складе нет, поэтому растет дефицит продукции (на рисунке это отображается увеличением отрицательного "запаса" за время Т3 - на отрезке СF). Производство начинает работать и на склад поступают изделия, что свидетельству ет об уменьшении дефицита на участке FД (рис. 5.12). В конце интервала Т4 дефицит исчезает.
Для решения поставленной задачи считают, что а) стоимость производства одной партии Ср;
б) стоимость хранения единицы продукции в единицу времени Сs;
в) потери от дефицита единицы про дукции в единицу времени Cд ;
г) спрос на продукцию из склада постоянен и равен единице продукции в единицу времени: = /.
S Smax B S A E C F Д T1 T2 T3 T S деф T G Рис. 5.12 Изменение запасов на складе Кроме того, считают, что производство продукции осуществляется со скоростью k на участках АЕ и FД и не производится вообще на участке EF (рис. 5.12).
В этом случае величина запасов S определяется соотношениями:
(k - )t при 0 t T1;
S - (t - T1) при T1 t T1 + T2;
max S = - (t - T1 - T2) при T1 + T2 t T1 + T2 + T3;
-Sдеф + (k - )(t - T1 - T2 - T3) при T1 + T2 + T3 t T1 + T2 + T3 + T.
Для временных точек E, C, F, Д соответственно имеют (k - )T1 = Smax;
Smax - T2 = 0;
(5.13) - T3 = -Sдеф;
- Sдеф + (k - )T4 = 0.
Общие затраты на одном цикле, как и в предыдущих случаях, складываются из затрат на изготовле ние продукции q1, затрат на хранение q2, потерь из-за дефицита q3 и составляют q = q1 + q2 + q3.
Затраты на изготовление продукции равны q1 = Ср, где n = / T = N / S, S = Smax - Sдеф.
Затраты на хранение q2 = Smax (T1 + T2)Cs.
Убытки из-за дефицита пропорциональны треугольнику СДG (рис. 5.12) и определяются как q3 = Sдеф (T3 + T4)Cд.
Таким образом, общие затраты составят 1 q = [C + Smax (T1 + T2)Cs + Sдеф (T3 + T4)Cд]. (5.14) p 2 Неизвестными в (5.14) являются Smax, Т1, Т2, Sдеф, Т3, Т4. Однако условие (5.13) устанавливает четы ре связи и, следовательно, степень свободы системы (5.13), (5.14) равна двум.
Рассматриваемую задачу управления запасами удобно решать методом неопределенных множите лей Лагранжа. Для этого составляется вспомогательная функция q(T1, T2, Sдеф, T3, T4, Smax ) = q + i, (5.15) i i= где i = 0 - условия (5.13).
Дифференцируя (5.15) по переменным Smax, Т1, Т2, Sдеф, Т3, Т4 и используя (5.13), определяют значе ния переменных, минимизирующих целевую функцию. Расчетные формулы для определения основных показателей приводятся ниже.
1 Плотность убытков Cд =. (5.16а) Cs + Cд 2 Оптимальные значения Ti*, i = 1, 2, 3, 2C Cд (1 р * k) 2C р(1- k) T2 = = ;
(Cд + Cs )Cs Cs Cs * T3* = T2 ;
Cд (5.16б) * T1* = T2 ;
k - * T4 = T3*.
k - 3 Оптимальное значение времени цикла * * * T = T1* + T2 + T3* + T4. (5.16в) 4 Общий объем производства (равен объему спроса) * V = T. (5.16г) 5 Максимальный уровень запасов 2C (1 p * k) Smax = T2 =. (5.16д) Cs 6 Максимальный уровень дефицита Cs * Sдеф = T3* = T2. (5.16е) Cд 7 Оптимальное значение целевой функции 2CsC Cд (1 р k) q* = = 2C Cs (1- (5.16ж) p k).
Cд + Cs 8 Оптимальное число циклов * n* = / T = N /V. (5.16з) Примером рассмотренной задачи управления запасами может быть случай, когда производство имеет слишком большой темп. В этом случае приближенно можно считать, что темп заполнения склада бесконечно большой (k = ), и на рис. 5.12 участки АВ и GД вертикальны. Расчетные формулы (5.16) при k совпадут с формулами (5.12), а рис. 5.12 - с рис. 5.13.
Таким образом, при бесконечно быстром производстве ситуация со складом на выходе тождествен на ситуации склада на входе производства при бесконечно быстром заполнении склада сырьем и посто янной скорости потребления продукции производством.
В том случае, если дефицит не допускается, Cд =, = 1 и k =, расчетные формулы (5.16) превраща ются в расчетные формулы раздела 5.3.1.
5.3.4 ПЕРИОДИЧЕСКИЙ ТИП АЛГОРИТМА. СКЛАД НА ВЫХОДЕ. ПРОИЗВОДСТВО БЕСКО НЕЧНОЙ ИНТЕНСИВНОСТИ.
ОТСУТСТВИЕ ДЕФИЦИТА. СТОИМОСТЬ ХРАНЕНИЯ ПРОПОРЦИОНАЛЬНА СЕБЕСТОИМОСТИ ИЗДЕЛИЙ (ДЕТАЛЕЙ) Так как дефицита нет, а скорость пополнения склада равна бесконечности, то при работе производ ства склад заполняется мгновенно. Изменение запаса на нем иллюстрируется рис. 5.9, где вертикальные участки характеризуют заполнение склада при работе производства. Уменьшение запасов на складе происходит в результате отпуска готового товара (изделий потребителю).
Целевая функция в данном случае Q = Q1 + Q2, где Q1 - себестоимость изделий, поступивших на склад в результате работы производства за время ;
Q2 - затраты на хранение изделий, пропорциональные времени и суммарной себестоимости деталей, все еще остающихся на складе.
Себестоимость Q1 изготовленных деталей определяется по формуле Q1 = (SCa + Cе )n, (5.17) где Се - постоянные затраты на серию;
Са - себестоимость единицы продукции;
n - число серий, опре деляемых, как и раньше:
N n = =.
T S Стоимость хранения продукции на складе пропорциональна количеству этой продукции S(t), ме няющейся во времени по закону, изображенному на рис. 5.9.
S S(t) = S - t.
T Следовательно, можно определить затраты на хранение T SCa + Cе S - S Q2 = t dt, S T где - коэффициент пропорциональности.
Интегрирование выражения для Q2 дает T T T Се S S Q2 = Ca + St - t2 - t2 n = S 0 2T 0 2T Cе T CaT Cе = (Ca + )S n = S + T n.
S 2 2 Общие затраты составляют CaT Cе Q = + Cе + S + T n = SCa 2 Ca Cе N = + Cе + S + S SCa 2N 2 N S или Cе CеN Ca Q = + + + S. (5.18) NCa 2 S Расчетные формулы находятся из соотношения, полученного в результате записи необходимого ус ловия оптимальности целевой функции Q по S, т.е. Q / S = 0. Минимум функции Q достигается при равенстве NCе S Ca =.
2 S Графическая иллюстрация представлена на рис. 5.13.
Основными расчетными формулами являются следующие:
1 Оптимальное значение экономической партии серии Cе N S* = 2.
Cа 2 Оптимальное значение числа серий n* = N / S*.
3 Оптимальный интервал цикла T T = S*.
N 4 Оптимальные затраты на хранение Q* = NCa + Cе + 2NCаCе.
Q Q* CaS Сa NCе Се S NCa + CЙ Сa Се S* S Рис. 5.13 Графическое определение оптимальной партии S* 5.3.5 ПЕРИОДИЧЕСКИЙ ТИП АЛГОРИТМА. СКЛАД НА ВЫХОДЕ. ПРОИЗВОДСТВО БЕСКО НЕЧНОЙ ИНТЕНСИВНОСТИ.
ОТСУТСТВИЕ ДЕФИЦИТА. ЗАВИСИМОСТЬ СЕБЕСТОИМОСТИ ОТ РАЗМЕРА ПАРТИИ Ранее себестоимость S единицы продукции определялась соотношением 0, если S = 0;
qS = е C + CаS, если S > 0, где Се - постоянные затраты на серию;
Са - себестоимость единицы продукции.
При этом себестоимость единицы продукции была величиной постоянной. Однако, часто себестои мость изготовления (закупки) единицы продукции зависит от размеров изготавливаемой партии. Часто бывает ситуация, когда для маленьких партий себестоимость Ca велика, а для больших - Ca мала, т.е.
Ca > Ca. При этом 0, если S = 0;
qS = Cе + CаS, если 0 S < S ;
C + CаS, если S S, е и целевая функция с учетом (5.18) записывается как 0, если S = 0;
Cе CеN Ca Q(S) = + + + S, если 0 S < S ;
NC а 2 S Cе CеN Ca а NC + + + S, если S S.
2 S Если обозначить кривую Q (S) при 0 S S через QI (S) (при этом Ca = Ca ), то минимальное * * значение QI для Q1 (S) достигается в точке S1 (рис. 5.14). При S S кривая Q (S) рассчитывается * по (5.19) при Ca = Ca и обозначается как QII (S). Минимальное значение QII (S) будет Q2 и оно достига * ется в точке S2 (рис. 5.14).
В соответствии с рис. 5.14 переход с кривой QI на кривую QII происходит при S S (рис. 5.14).
Q Ca" QII Ca' QI Q2* Q1* a) S2* S* = S1* S S Q Ca" Ca' QII QI Q2* Q1* S =S* S2* S1* S б) Рис. 5.14 Графическое решение задачи определения оптимальной партии:
а - S* = S1*;
б - S* = S;
в - S* = S2* Q Ca" Ca' QII Q2* QI Q1* S S S* = S2* S1* в) Рис. 5.14 Окончание Оптимальное решение в соответствии с графическим решением задачи (рис. 5.14) определяется следующим образом:
* a) если S1 S (рис. 5.14, а), то Cе N * S* = S1 = 2 ;
Cа * Q* = Q1 = NCa + Cе + 2NCaCе ;
* * S2 S < S1 (рис. 5.14, б), то S* = S ;
* * б) если S2 S S1 (рис. 5.14, б), то S* = S ;
Cе CеN Ca Q* = Q1(S ) = NCa + + + S ;
2 S * S > S2 (рис. 5.14, в), то в) если * S* = arg min(Q1(S ),Q2(S2 )), * Q* = min(Q1(S ),Q2(S2 )).
Аналогичным образом исследуется задача с конечными разрывами целевой функции при различных условиях в постановке задачи.
5.4 Детерминированная задача управления запасами при различных видах продукции 5.4.1 ПЕРИОДИЧЕСКИЙ ТИП АЛГОРИТМА, ЗАТРАТЫ НА ХРАНЕНИЕ ПРОПОРЦИОНАЛЬНЫ РАЗМЕРУ ПАРТИИ (СЕРИИ). СКЛАД НА ВХОДЕ Работа склада рассматривается на достаточно большом интервале времени. При этом считают, что а) имеется n видов продукции;
б) максимальный уровень запасов на складе фиксирован;
в) ресурсы по ступают на склад одновременно партиями (сериями). Также считают, что а) стоимость доставки i-й пар тии Cрi;
б) стоимость хранения единицы продукции в единицу времени Csi;
в) общее потребление товара за время равно Ni.
Задача управления состоит в том, чтобы найти уровень пополнения Si и периоды пополнения Ti, при которых затраты на хранение Ni ресурсов, i = 1, 2, Е, n, на периоде были бы минимальны и при этом n (5.19) i S I, i= где Si = Simax - Simin - уровень пополнения i-го ресурса;
Simax - максимальный запас i-го ресурса;
Simin - минимальный запас i-го ресурса;
I - объем склада, предназначенного для хранения запасов и ресурсов.
Пусть расходы ресурсов равномерны, тогда в единицу времени расходуется i-го ресурса hi = Ni/.
Затраты на хранение за период Т i-го сырья составят i i qi = q1 + q2, i i где q1 - затраты на доставку S i-го сырья;
q2 - затраты на собственно хранение.
Si qi = Ci + TCi. (5.20) p s Очевидно Ni hi =, ni =, T Si отсюда T = Si. (5.21) Ni Используя (5.20), можно записать затраты Qi за время qi Ci Si p Qi = = ( + Ci ) s T T или с учетом (5.21) Ci Ni Ci p s Qi = + Si, (5.22) Si что согласуется с (5.5).
Суммарные затраты Q для всех видов продукции определяются как сумма n n Ci Ni s p i Q = (Si ) = Si. (5.22а) Q + Ci Si 2Ni i=1 i= Задача оптимизации управления запасами состоит в том, чтобы минимизировать целевую функцию (5.22) при условии соблюдения неравенства n (5.23) i S I.
i= Легко показать, что задача оптимальна, если последнее неравенство превращается в равенство, т.е.
n (5.24) i S = I.
i= Безусловно, оптимальное значение Si, которое минимизирует (5.22), если бы условия (5.23) не бы ло, т.е. склад был бы бесконечен, определяется из необходимого условия экстремума функции многих переменных Qi / Si = 0 или конкретно Qi Ci Ni Ci p s = - + = 0, (5.25) Si Si откуда Ci Ni p Si* = 2. (5.26) Ci s Этот результат уже был получен при рассмотрении склада с одним продуктом.
Если бы теперь оказалось, что n * i S < I, i= то значения (5.26) были бы оптимальны, так как ограничения по величине склада I не играют роли (склад слишком большой и не препятствует завозу оптимальных объемов запасов).
Задача появится, если размеры склада этому препятствуют, т.е.
n * i S > I.
i= В этом случае Si*, найденные из (5.26), недопустимы и их нужно как-то уменьшить.
Задачу (5.22), (5.24) решают методом неопределенных множителей Лагранжа. Для этого составля ется новая вспомогательная функция n n i L(Si,) = (Si ) + ( - I), (5.27) i Q S i=1 i= где - неопределенный множитель Лагранжа.
Решение находится дифференцированием L(Si, ) по Si и приравниванием нулю производных L(Si,) / Si = 0.
Из (5.27) имеют Qi (Si ) + = 0 (5.28) (Si ) или Qi / (Si ) = -.
Отсюда видно, что производные Qi / Si в оптимальном режиме не равны нулю, как в (5.25), а рав ны некоторому числу (Ц). Причем они одинаковы для всех i = 1, 2, 3, Е, n, что свидетельствует о том, что оптимальные запасы Si* выбираются таким образом, чтобы увеличения затрат на единицу умень шения продукции Qi / Si были бы одинаковы для всех i = 1, 2, 3, Е, n:
Q1(S1) Q2 (S2 ) Qn (Sn ) = = L = = -.
(S1) (S2 ) (Sn ) Если считать, что i Qi (Si ) Q, то (Si ) (Si ) Q1 Q2 Qn = = L = = -, (S1) (S2 ) (Sn ) где (Si ) - уменьшение максимального пополнения запасов Si;
Qi - увеличение затрат из-за этого.
Соотношения (5.22), (5.24), (5.28) составляют систему уравнений для определения и оптимальных значений Si :
Ci Ni Ci p - + + = 0;
Si n = I.
Si i= Решение этой системы дает 2Ci Ni p Si* = ;
(5.29) Csi + n * (5.30) i S = I.
i= Для вычисления конкретных значений Si* по (5.29) необходимо задать, после проведения этих вычислений проверяется правильность задания по (5.30), в случае необходимости оно корректируется (если условие (5.30) не выполняется).
5.5 Вероятностная задача управления запасами Во многих случаях предсказать спрос нельзя, часто производство останавливается, если запас сырья мал, не всегда можно быстро восстановить производство, если уровень запасов был снижен. Поэтому используется алгоритм с прогнозом либо момента пополнения запаса, либо количества пополнения за паса, т.е. алгоритм прогноза уровня пополнения склада.
Другими словами, прогнозируется, когда нужно покупать (производить товар), либо сколько и какого товара нужно купить (произвести).
Эти два алгоритма прогноза основаны на двух детерминированных основополагающих алгоритмах.
СПИСОК ЛИТЕРАТУРЫ 1 Танаев В.С. Теория расписаний. М.: Знание. 1988. 32 с.
2 Танаев В.С. Теория расписаний. Одностадийные системы. М.: Наука, 1984.
3 Майник Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. 323 с.
4 Кофман А. Методы и модели исследования операций. М.: Мир, 1977. 432 с.
5 Шкурба В.В. Задача трех станков. М.: Наука, 1976. 95 с.
6 Рыжиков Ю.И. Управление запасами. М.: Наука, 1969. 343 с.
7 Вентцель Е.С. Исследование операций. М.: Наука, 1980. 230 с.
8 Кофман А., Крюон Р. Массовое обслуживание. Теория и приложение. М.: Мир, 1965. 302 с.
9 Кузин Л.Т. Основы кибернетики. Т. 1: Математические основы кибернетики. М.: Энергия, 1973.
504 с.
10 Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания. М.: Высш. шк., 1982. 256 с.
Pages: | 1 | 2 | Книги, научные публикации