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

Это выражение получается, если каждый элемент вектора состояния р(п) умножить на соответствующую вероятность перехода, которая приводит в момент n + 1 в состояние Ej, и затем просуммировать результаты; таким образом, мы получаем вероятность состояния Ej в момент n + 1.

Выпишем теперь все элементы вектора p(n + 1):

Но это есть матричное произведение:

=p(n)M.

Заметим, что сумма элементов каждой строки матрицы M равна единице; действительно, такая строка представляет собой набор вероятностей перехода из данного состояния во все другие возможные состояния (включая само себя). В этих условиях матрица перехода принадлежит к классу стохастических матриц[24].

Если pij не зависят от времени, то марковский процесс называется стационарным и легко проверить, что

p(n) = p(0)×M n.

Пример. Рассмотрим мастерскую по ремонту двух типов моторов. Ремонт мотора M1 требует двух дней; ремонт мотора М2 - одного дня. Каждое утро вероятность того, что в ремонт поступит мотор M1, равна 1/3, вероятность поступления мотора М2 равна 1/2. Работы, не выполняемые мастерской, отправляются в другие места.

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

Какая политика лучше?

Сначала мы запишем матрицы перехода между различными возможными состояниями при двух сделанных выше предположениях.

В этих двух случаях возможными состояниями являются: отсутствие работы (состояние 0), первый день работы над M1 (состояние 1), второй день работы над M1 (состояние 2), работа над M2 (состояние 3).

Вероятность того, что заказа на ремонт M1 не будет, равна 1 - 1/3; вероятность отсутствия заказа на M2 равна 1 - 1/2.

Рассмотрим одну из двух гипотез:

а)  Вероятность того, что в течение всего дня не представилось никакой работы, равна всегда (1 - 1/3) (1 - 1/2), каковы бы ни были состояния предшествующего дня, за исключением случая, когда в предыдущий день начали ремонтировать мотор M1. Это случай, когда вероятность просто становится равной нулю.

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

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

При первой гипотезе:

в)  Предпочитают ремонтировать мотор M1, когда предлагается не один он; тогда вероятность того, что начинают ремонтировать мотор M1 (состояние 1), всегда равна 1/3, за исключением случая, когда в состоянии 1 мы находились в предшествующий день. Только в этом случае следует отказаться от новой работы (вероятность 0).

г)  Так как мотор М2 не пользуется предпочтением, вероятность его ремонта (состояние 3) всегда равна произведению вероятности его появления на вероятность отсутствия мотора M1 т. е. (1/2) (1 - 1/3), за исключением, разумеется, случая, когда уже один день работали над ремонтом M1 и ремонт следует закончить. Из этого следует, что в этом случае вероятность состояния 3 равна 0.

При второй гипотезе:

На этот раз предпочитается ремонт M2, и аналогичные рассуждения позволяют найти столбец, соответствующий состоянию 1. Все его элементы равны (1 - 1/2) (1/3), кроме второго, равного нулю; таким же образом элементы столбца, соответствующего состоянию 3, все равны 1/2, кроме второго, который равен 0.

Матрица перехода. Первая гипотеза:

Матрица перехода. Вторая гипотеза:

Для каждой из гипотез матрицы перехода можно представить в виде графов (рис. 3.6).

Первая гипотеза Вторая гипотеза

Рис. 3.6.

В условиях первой гипотезы мы имеем

p(n) = р(0) M n ,

где

Заметим, что, если возвести матрицу M1 в степень n, она примет вид

Отсюда, неограниченно увеличивая n, получаем

При этих условиях, каково бы ни было p(0), имеем

Предположим, что аналогичное свойство справедливо и для второй гипотезы. Если обозначить через π0, π1, π2 и π3 вероятности нахождения в состояниях 0, 1, 2 и 3, когда , то

откуда

M2M2

и

(π0, π1, π2, π3) M2 = (π0, π1, π2, π3),

где

π0 + π1 + π2 + π3 = 1.

Вычисляя, получаем

откуда выводим систему уравнений:

где π0 + π1 + π2 + π3 = 1.

Легко видеть, что

и затем мы получаем

откуда

Таким образом,

Нетрудно заметить, что первая гипотеза более благоприятна для работы мастерской, чем вторая; действительно, время работы, соответствующее первой гипотезе, составит 3/4 всего времени, тогда как при второй гипотезе оно равно только 5/7 всего времени. Но 3/4 > 5/7.

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

Это не всегда так; на самом деле стохастические матрицы бывают разных категорий. Если они редуцируемые, т. е. имеют вид

где A и D - квадратные подматрицы, то, начав с состояния, содержащегося в A, никогда нельзя оказаться в состоянии из D, и наоборот. Рассмотрим, например, матрицу M и соответствующий граф (рис. 3.7):

Рис. 3.7.

Заметим, что граф состоит из двух отдельных подграфов, и мы имеем

Если матрицы перехода периодичны, т. е. имеют вид

где нулевые матрицы являются квадратными, то система колеблется между состояниями из B и С.

Пример:

Рис. 3.8.

Система переходит из состояния 0 в состояние 1 или 2, чтобы затем снова возвратиться в состояние 0 и так далее.

Легко увидеть, например, что

,

и мы имеем

M 2n = M 2, M 2n + 1 = M

Это означает, что если выйти из состояния 0, то после четного числа переходов мы там окажемся снова, а после нечетного числа переходов с вероятностями 1/2 мы будем находиться в состояниях 1 или 2. Обратно, после четного числа переходов, выйдя из состояний 1 или 2, мы окажемся с вероятностями в состояниях 1 или 2; после нечетного числа переходов, выйдя из состояния 1, окажемся в 0, и выйдя из состояния 2, снова окажемся в 0.

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

или

где A и D – квадратные матрицы

Рис. 3.9.

Пусть, например, дана матрица

Ей соответствует граф, изображенный на рис. 3.9. Легко видеть, что когда система из состояний 0 или 1 переходит в состояния 2 или 3, она не сможет возвратиться обратно. Состояния 0 и 1 в этом случае называются переходными состояниями системы.

ГЛАВА 4. ТЕРПЕНИЕ И ХОД ВРЕМЕНИ. (РАСПРЕДЕЛЕНИЕ ОБОРУДОВАНИЯ НА ПРЕДПРИЯТИИ. ТЕОРИЯ ОЧЕРЕДЕЙ).

Завод «Посудоаппарат» производит машины для мытья посуды; он расположен в одном из парижских пригородов. Его продукция довольно безразлична французским мужчинам, но это не должно долго продолжаться, так как губительный пример их американских (из США) собратьев, имеющих солидный опыт в области мытья посуды, рискует вызвать головокружительный подъем курса подобных предприятий на бирже.

В настоящий момент на «Посудоаппарате» имеется тысяча рабочих и производится шесть различных типов машин для мытья посуды; действительно, французу несвойственно иметь такую же машину, как и у соседа, или пользоваться тарелками нормального размера. К тому же «Посудоаппарат» выпускает только серии среднего объема и должен обладать весьма разнообразным оборудованием. Нельзя предоставить рабочим одновременно все инструменты, которые им необходимы; разнообразные инструменты, которые нужны для выполнения определенной работы, имеются на складе, находящемся в сборочном цехе. Поэтому, к несчастью, наблюдается образование очередей рабочих перед дверьми склада. Очевидно, следует уменьшить время ожидания рабочих, так как оно потеряно для производства.

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

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

Себестоимость часа рабочего времени была оценена в 6 франков, а времени работы служащего — в 3 франка[25].

Посмотрим теперь, как оценить общую стоимость времени ожидания в предположении, что в кладовой работают 1, 2, 3, ... или n служащих.

Рис. 4.1. Очередь рабочих

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

Первым делом следует проанализировать закон прибытия рабочих к дверям склада: нужно навести статистику на эти прибытия. Из этих статистических сведений исключим по полчаса в начале работы, во время перерыва на обед и в конце работы. Допустим, что вне этих особых периодов статистический закон прибытия остается одним и тем же (математики скажут, что речь идет о стационарном режиме).

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

Таблица 4.1

Число прибытий за 10минут	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
Наблюдаемая частота (%)	1	0	1	2	1	3	5	6	9	10	11	12	8	9	7	5	4	3	1	1	1
Теоретическая частота (закон Пуассона)	0,1	0,2	0,6	1,2	2,1	3,4	4,9	6,6	8,1	9,3	9,9	9,9	9,3	8,3	6,9	5,5	4,2	3,1	2,1	1,4	0,9

Затем найдем среднее значение числа прибытий за 10 минут. Пусть оно равно

= 5×0,01 + 6×0 + 7×0,01 + … + 14×0,10+ … + 25×0,01 = 15,61 » 16.

Отсюда мы заключаем, что в среднем за 10 минут приходит 16 рабочих, или же (если простить это дробление человека, достойное каннибала) 1,6 рабочего в минуту. Мы займемся приближением наших измерений теоретическим законом распределения вероятностей, часто используемым и весьма удобным.

Для этого предположим, что справедливы следующие гипотезы:

1)  прибытие одного рабочего не зависит от прибытия другого (независимость прибытий);

2)  никогда не приходят сразу два или более рабочих;

3)  среднее количество прибытий не изменяется со временем.

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

, (1)

где е – основание натуральных логарифмов, а n! означает

1∙2∙3…(n - 1)∙n,

т. е. последовательное произведение n натуральных чисел от 1 до n. Эта формула дает вероятность того, что за время t произойдет n прибытий. Величина l представляет собой среднее количество прибытий за выбранную единицу времени; в нашем примере l равно 1,6 прибытий в минуту. В третьей строке таблицы 4.1 помещены значения pn(t) для lt = 16. Но почему пытаются ввести этот закон Пуассона? Просто потому, что для случая, когда прибытие в явлениях, связанных с очередями, соответствует этому закону, получены удобные формулы. Таким образом, когда последовательные события разделены случайными интервалами и когда три перечисленные выше гипотезы справедливы, хотя бы приближенным способом находят пуассоновский закон.

Как проверить, что измеренный закон (строка 2) достаточно близок к теоретическому закону (строка 3)? Для этого вычислим относительные квадратичные уклонения наблюденных частот от теоретических и затем сложим их следующим образом:

.

Результат этого подсчета называется c2 (хи квадрат). Существуют таблицы значений c2 , сверяясь с которыми, можно оценить, когда не следует отвергать гипотезу о том, что теоретически определенный закон хорошо описывает измеряемое явление. Находя здесь, что с вероятностью 0,88 гипотеза может быть принята, мы можем расценить эту вероятность как достаточную и считать, что наблюденный закон — это закон Пуассона со средним lt = 16, т. е. с величиной l = 1,6. Заметим, что для любого произвольно выбранного интервала формула Пуассона (1) дает нам значения вероятностей n прибытий, если нам известно l.

Таким образом, вероятность того, что в течение данного интервала 10 минут произойдут n прибытий, равна

где n принимает значения 0, 1, 2, 3, 4… .

Мы должны теперь заняться способом, которым производится обслуживание. Когда рабочий приходит, один из свободных кладовщиков, если таковой имеется, ищет требуемые инструменты и выдает их в обмен на жетон. Продолжительность этого обслуживания случайна, например 15 секунд или 30, или 90... . Когда все кладовщики заняты, рабочие ждут и образуют очередь. Допускается, что рабочие не оказывают предпочтения некоторым кладовщикам, когда многие из них свободны; вероятность того, что прибывающий обслуживается тем или другим, одна и та же.

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

Для этого был использован электронный регистратор. Как только обслуживание начинается, кладовщик нажимает на красную кнопку «начало обслуживания», а в конце обслуживания рабочий нажимает на зеленую кнопку «конец обслуживания». Регистрирование производится для каждого обслуживания. Таким образом было зарегистрировано 1000 продолжительностей обслуживания (при необходимости можно было бы зарегистрировать и больше).

Вычислили частоты, соответствующие длительности 0—15, 15—30, 30—45. Они собраны в табл. 4.2, где в строках 1 и 2 представлены классы 0, 15, 30 и т. д.

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

Таблица 4.2

Интервалы времени (s)	0	15	30	45	60	75	90	105	120	135	150	165	180	195	210	225	240	255	270	285	300
Наблюденная накопленная частота (%)	1000	813	652	512	408	330	261	210	163	125	95	79	62	51	44	35	26	21	17	13	10
Теоретичес- кая частота (экспоненци- альный закон)	1000	798	637	508	406	324	259	207	165	131	105	84	67	53	42	34	27	21	17	14	11

поместили значения, соответствующие закону интервалов, называемому экспоненциальным законом: