А. Кофман и Р. Фор. Займемся исследованием операций (стр. 9 )

,

где Pr(Q ³ q) означает «вероятность того, что интервал Q больше или равен данному значению q», - основание натуральных лагарифмов, а m — уровень обслуживания, т. е. среднее число обслуживаний за единицу времени. Здесь m = 1/1,1 » 0,9 и q измеряется в минутах.

Почему нужно сравнивать[26] измеренный закон с теоретическим экспоненциальным? Потому что если интервалы времени, разделяющие события, поместить на одной прямой вплотную, то получается ряд событий, удовлетворяющих закону Пуассона, хотя статистика доказывает, что продолжительность обслуживания распределена экспоненциально. Три гипотезы, сформулированные выше по поводу закона Пуассона, должны остаться верными для времени обслуживания, но на этот раз интервалы времени расположены не вплотную, так как бывает, что кладовщики не заняты.

Теперь нужно ввести очень важную величину — нормы деятельности или интенсивность деятельности кладовщика. Если m — уровень обслуживания для одного кладовщика, то для S кладовщиков, у которых предполагаются одинаковые способности, этот уровень будет равен m×S.

Так как рассматриваются средние величины, важно, чтобы норма прибытий не превосходила общего уровня обслуживания, т. е.

l < mS

или же

.

Величина l/mS, которую мы обозначим через y, называется интенсивностью деятельности.

Читатель интуитивно допустит, что средняя длина очереди и средняя продолжительность ожидания одного рабочего являются функциями от y; и то и другое доказывается одинаково. В рассмотренной задаче имеем

y = 1,6/0,9×S = 1,77/S.

Для того чтобы рассмотреть экономическую сторону задачи, нужно располагать некоторыми формулами, от объяснения которых мы здесь воздержимся, но тем не менее будем их использовать; напомним, что они являются уже классическими и были выведены датским инженером Эрлангом около сорока лет тому назад, когда он посвятил себя знаменитой работе по аналитическому изучению очередей на примере телефонов.

Сначала нам нужно вычислить вероятность того, что время ожидания равно нулю. Обозначим ее p0:

Найдем также среднее время ожидания в очереди

.

Какими сложными кажутся эти формулы! Специалисты по исследованию операций встречаются и не с такими сложностями, но надо ли жалеть того, кого увлечение завело столь далеко? К счастью, эти специалисты построили также таблицы, которые дают в случаях, подобных рассматриваемому нами, значения как функции отy, m и S; на рис. 4.2 представлена таблица такого типа.

Для удобства читателя мы не будем вычислять р0 и воспользуемся таблицей. Возьмем различные значения S: S = 2, 3, 4, ... и вычислим значения, соответствующие y = 1,77/S. Каждой рассматриваемой абсциссе S сопоставим точку пересечения прямой, параллельной оси ординат и проходящей через эту абсциссу, с кривой, соответствующей подходящему значению y, а затем в случае надобности произведем интерполяцию.

Например, для S = 2, y = 1,77/2 » 0,88 нет кривой, помеченной 0,88, но, интерполируя между кривыми, соответствующими 0,85 и 0,90, получим искомое значение ординаты, равное 3,6. Эта ордината дает; в нашем случае m = 0,9. Затем получают  = 4 (минуты) для S = 2. Вот результаты, которые читатель сможет проверить, для некоторых значений S:

S = 2;	y = 0,88;	= 3,6;	откуда =3,6/0,9= 4;
S = 3;	y = 0,59;	= 0,28;	откуда =0,28/0,9= 0,31
S = 4;	y = 0,44;	= 0,054;	откуда =0,054/0,9= 0,06

Мы не вычислили значения для S = 1, так как в этом случае y > 1 и среднее время ожидания было бы бесконечным. Это означает, что очередь все время увеличивалась бы от начала работы к концу. Вооруженные знанием среднего времени ожидания рабочего в очереди, мы сможем перейти к экономическому изучению задачи.

В течение одного восьмичасового рабочего дня с нормой 1,6 рабочего в минуту мы имеем

l×60×8 = 1,6×60×8 = 768.

Иначе говоря, на склад придут семьсот шестьдесят восемь рабочих.

Этому числу прибытий для среднего времени обслуживания 1/m соответствует общее ежедневное время обслуживания

768×=768/0,9= 853 минуты = 14 часов 13 минут = 14,21 часа.

Следовательно, ежедневная продолжительность простоя обслуживающей системы вычислится просто:

для двух кладовщиков (S = 2):

2×8 - 14,21 = 16 - 14,21 = 1,79 часа;

для трех кладовщиков (S = 3):

3×8 - 14,21 = 24 - 14,21 = 9,79 часа;

для четырех кладовщиков (S = 4);

4×8 - 14,21 = 32 - 14,21 = 17,79 часа

Рис. 4.2.

Для каждого из этих случаев вычислим время, потерянное рабочими из-за очереди:

S = 2: 768×4 = 3072 минут = 51,2 часа,

S = 3: 768×0,31 = 238 минут = 3,96 часа,

S = 4: 768×0,06 = 40 минут = 0,76 часа.

При себестоимости часа работы служащих и рабочих соответственно в 3 и 6 франков можно вычислить общую ежедневную стоимость часов, потерянных теми и другими для различных случаев:

S = 2: С2 = 1,79×3 + 51,2×6 = 312,57 франков,

S = 3: С3 = 9,79×3 + 3,96×6 = 53,13 франков,

S = 4: С4 = 17,79×3 + 0,76×6 = 57,93 франков.

Если бы мы вычислили С5 для S = 5, нашли бы 75,37 франков. Видно, что функция стоимости достигает минимума для S = 3.

Чтобы убедиться в том, что наилучшее решение состоит, по-видимому, в использовании трех кладовщиков, специалист по исследованию операций должен тщательно доложить управляющему кадрами, что предпочтительным было бы иметь в среднем по крайней мере одного из трех кладовщиков незанятым... С первого взгляда управляющий мог бы подвергнуть это серьезному сомнению. Но после того как его убедили, он решил отыграться и нанять четырех кладовщиков. Когда его спросили о причине этой перемены, он небрежно бросил: «Я вычисляю, что наем четырех кладовщиков будет мне стоить в день только на 4,80 франка больше; затем я заметил, что служащие в среднем отлучаются со своего места 8% времени; если я нанял бы только трех кладовщиков, то, когда кто-либо из них отсутствует, добавочные затраты составили бы

312,57 - 53,13 = 259,44 франков,

т. е. ежедневно в среднем

259,44 × 0,08 = 20,75 франков.

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

Основные понятия теории очередей и ее приложения.

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

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

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

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

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

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

Пусть l и m — соответственно средняя норма прибытий и среднее число обслуживаний в единицу времени. Интенсивность деятельности или коэффициент использования равен y = l/m; система с очередью не будет закупорена, если l/m < 1. Предположим, что в момент t в системе имеется n единиц (клиентов), включая тех, которые находятся в состоянии обслуживания; это событие происходит с вероятностью pn(t). Найдем вероятность pn(t + Dt) того, что в момент t + Dt в очереди будут также n клиентов, где Dt — малый промежуток времени.

В дальнейшем мы допустим, что первая гипотеза, указанная на стр.64 и связанная с законом Пуассона, всегда будет справедлива.

По определению (третья гипотеза закона Пуассона), вероятность того, что за время Dt произошло одно прибытие, равна lDt; аналогично вероятность того, что за это же время кончило работу одно обслуживающее устройство, равна mDt.

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

1 - lDt и 1 - mDt.

С самого начала могут представиться две возможности:

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

pn(t)(1 - lDt)×(1 - mDt) = pn(t)[1 - (l + m)Dt + lmDt2];

б)  за время Dt произошли новое прибытие и окончание одного обслуживания; вероятность совмещения этих событий равна

pn (t) l Dtm Dt = pn(t)lm Dt2.

Однако это не единственные возможности реализации pn(t + Dt).

Действительно, мы имеем также n единиц в момент t + Dt, если в момент t имелось n + 1 единиц, за время Dt одна единица вышла из очереди, а другая еще не прибыла. Вероятность в этом случае равна

pn+1 (t) (1 - l Dt) m Dt = pn+1 (t) [m Dt - lm Dt2].

Наконец, в момент t имеется еще n единиц, если имелось n - 1 в момент t, а за время Dt одна единица прибыла и ни для одной не кончилось обслуживание. Этот последний случай имеет вероятность

pn-1 (t) l Dt (1 - m Dt) = pn-1 (t) [l Dt - lm Dt2].

Заметим еще, что произведением lmDt2 можно пренебречь по сравнению с lDt или с mDt (например, если Dt = 1/100, то lDt и mDt имеют порядок 1/100, а lmDt2 имеет порядок 1/10000). Следовательно, сумма вероятностей, соответствующих различным возможным случаям реализации pn(t + Dt), сводится к

pn (t + Dt) = pn (t) [1 - (l + m) Dt] + pn+1 (t) m Dt + pn-1 (t) l Dt

или же к

[pn (t + Dt) - pn (t)]/Dt = l pn-1 (t) - pn (t) (l + m) + pn+1 (t) m.

Левая часть этого уравнения становится равной производной от pn(t), когда Dt стремится к нулю; поэтому можно написать

pn' (t) = l pn-1 (t) - (l + m) pn (t) + m pn+1 (t).

В этой задаче мы интересуемся установившимся режимом, так что производная pn'(t), очевидно, равна нулю, ибо вероятности пребывания n единиц в системе устойчивы, каково бы ни было n. Заметим, что эта самая простая из гипотез, относящихся к процессу Пуассона, приводит к рекуррентной формуле для pn (t):

l pn-1 (t) - (l + m) pn (t) + m pn+1 (t) = 0.

Эта формула справедлива для n > 1. Легко видеть, что она не имеет места для n = 1; для этого частного случая мы имеем

-l p0 (t) + m p1 (t) = 0.

Вычисляем последовательно; для уравнения, соответствующего частному случаю, мы имеем

p1 = y p0,

а затем, используя общую формулу для n > 1, получаем

m p2 = (l + m) p1 - l p0,

т. е.

p2 = (1 + y) p1 - y p0 

или же

p2 = (1 + y) y p0 - y p0 = y2 p0

и т. д.

Выпишем последовательные соотношения между рn:

p0 = p0,

p1 = y p0,

p2 = y2 p0,

¼;

pn = yn p0 

и затем просуммируем почленно

.

Устремляя n к бесконечности, по определению, имеем

.

Но сумма геометрической прогрессии с первым членом 1 и знаменателем y равна

,

откуда

и

.

Отсюда также следует, что

pn = yn (1 - y).

Вычислим среднее количество (или математическое ожидание) единиц находящихся в системе

.

Последняя скобка является производной от

,

т. е. она равна

.

Окончательно имеем

.

Обозначим через среднее число единиц, находящихся в очереди (не считая той, которая находится в состоянии обслуживания). В каждый момент v = n - 1, если n > 0.

Частное от деления среднего числа единиц в системе на среднее число обслуживаний в единицу времени m, очевидно, дает нам время обслуживания среднего числа единиц /m. Частное от деления среднего числа единиц в очереди на норму прибытий l дает нам время ожидания /l среднего числа единиц. Так как режим стационарный, эти две величины равны

.

Из этого равенства мы можем вычислить :

.

так же как и среднее время ожидания в очереди:

.

Пример. Представим себе окошко передвижной сберегательной кассы, которая обычно прибывает в некоторые маленькие города в базарные дни. Единственный служащий выполняет там все операции, требуемые клиентурой; окошко открыто с 7 до 13 часов без перерыва. Было замечено, что среднее число клиентов в день равно 54, а время обслуживания — 5 минут на каждого человека.

Из этого непосредственно вычисляем

человек в час и обслуживаний в час.

Далее мы имеем:

;

;

;

.

Эти вычисления показывают, что среднее число клиентов в системе (включая тех, которые находятся в состоянии обслуживания) равно 3, среднее число клиентов в очереди (не считая тех, которые проходят обслуживание) равно[27] 9/4 = 2,25; наконец, средняя продолжительность ожидания в очереди равна 1/4 часа.

Более полное изучение явления позволило бы определить вероятность нахождения в системе более N лиц и вероятность того, что время обслуживания не меньше T и т. д., где N и T— числа, фиксированные заранее.

Рассмотрим теперь систему, в которой норма прибытий и среднее число обслуживаний в единицу времени всегда равны соответственно l и m, а число обслуживающих устройств равно S. Когда число единиц в системе n меньше, чем S, то все они одновременно обслуживаются, и не все устройства заняты, что приводит к общей норме обслуживания, равной nm. Наоборот, если число n единиц больше или равно S, то все S устройств одновременно заняты, и общая норма обслуживания равна Sm.

При этих условиях в случае стационарного режима рекуррентные формулы, найденные выше, принимают вид:

n = 0:	-lp0 + mp1 = 0
1 £ n < S:	-(l + nm) pn + l pn-1+ (n+1)m pn+1= 0
n ³ S:	- (l + Sm) pn + l pn-1 + Sm pn+1 = 0

Метод, аналогичный использованному ранее, позволяет получить

если 1 £ n < S,

и

если n ³ S,

откуда

;

; ; ;

Среднее число незанятых устройств равно

Для S = 2 и y = 1,777¼ (данных, связанных с задачей о заводе «По-судоаппарат») имеем сразу:

;

минут;

Отсюда следует

С2 = 0,222×480×(3/60)×768×4×(6/60) = 312,5 франков,

в случае, если в течение дня кладовые открыты 480 минут и туда приходит 768 клиентов. Это дает хорошее соответствие с результатом, приведенным ранее на стр. 68.

ГЛАВА 5. Вот это кофе! Франко-мексиканская история (Транспортная сеть. Алгоритм Форда-Фалкерсона).

Общество Конора Эрманос и К° располагает в портах Веракрус, Тампико, Туспан и Кампече запасами кофе, на который оно получило заказы импортеров из Дюнкерка, Бордо, Сен-Назера и Гавра[28].

В самом деле, известно, что мексиканский кофе имеет тонкий вкус и что эта страна экспортирует половину своей продукции. Имеются в распоряжении следующие запасы:

Веракрус — 120 т; Тампико — 100 т; Туспан — 100 т; Кампече —100 т. Налагаются следующие требования по доставке:

Дюнкерк — 100 т; Бордо — 80 т; Сен-Назер — 90 т; Гавр — 150 т.

Различные суда покидают один из портов атлантического побережья Мексики, направляясь во французские порты назначения; их грузоподъемность приведены ниже в табл. 5.1.

Таблица 5.1

Порт отправления	Порт назначения	Дюнкерк	Бордо	Сен-Назер	Гавр
		Е	F	G	Н
Веракрус…	А	70	30	20	0
Тампико…	В	50	40	10	0
Туспан…	С	0	20	40	80
Кампече…	D	0	20	40	80

Судно, идущее из Веракруса в Дюнерк, может перевезти 70 т; однако судов, идущих из Веракруса в Гавр, не имеется (или если такое судно существует, то оно не обладает соответствующей грузоподъемностью). В таких случаях говорят, что пропускная способность от A к H равна нулю.

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

Поставим следующую задачу. Абстрагируясь от стоимости перевозок (можно считать, что стоимость перевозки из Веракруса или любого другого мексиканского порта в Гавр, Сен-Назер, Дюнкерк или Бордо практически одна и та же), попытаемся максимально удовлетворить требованиям по доставке.

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

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

1)  Каждый порт отправления связан ориентированной стрелкой или дугой с портами назначения; дуге приписано число, представляющее пропускную способность, т. е. объем груза, который может быть перевезен по этому пути. Само собой разумеется, что нельзя начертить никакой дуги между портом отправления и портом назначения, если нет судна, осуществляющего связь, или же если существует судно с грузоподъемностью, равной нулю.

2)  Вспомогательная точка O связана с каждым портом отправления дугой, имеющей в качестве пропускной способности величину наличного запаса в этом порту.

3)  Каждый порт назначения связан с вспомогательной точкой Z дугой, пропускная способность которой равна требованию по доставке в этом порту.

Получают, таким образом, транспортную сеть, изображенную на рис. 5.1 (числа, обведенные рамкой, первостепенны). Задача состоит теперь в том, чтобы найти максимальную величину — максимальный поток, который можно перевезти из O в Z.

Найдем сначала полный поток, т. е. такой поток, что каждый путь из O в Z содержит по крайней мере одну насыщенную дугу.

Это сделать крайне просто: исходя из какого-нибудь потока, проверяют, существует ли путь, не содержащий ни одной насыщенной дуги. Если это так, увеличивают на единицу поток по этому пути; далее поступают таким же образом до тех пор, пока каждый из путей такого типа не будет содержать по крайней мере одну насыщенною дугу.

Удовлетворим теперь первостепенным требованиям. Чтобы удовлетворить требованию в H, насытим дугу HZ; припишем пути ODHZ поток 80