Если система S находится в каком-то состоянии Si, из которого есть непосредственный переход в другое состояние Sj (стрелка, ведущая из Si, в Sj на графе состояний), то представим что на систему, пока она находится в состоянии Si, действует простейший поток событий, переводящий ее по стрелке Si->Sj. Как только появится первое событие этого потока, происходит «перескок» системы из Si в Sj.

Для наглядности на графе состояний у каждой стрелки проставим интенсивность того потока событий, который переводит систему по данной стрелке. Обозначим 0 интенсивность потока событий, переводящего систему из состояния Si в Sj. На рисунке 16.1 дан граф состояний с проставленными у стрелок интенсивностями (будем называть такой граф размеченным).

Рисунок 16.1

Построим размеченный граф состояний для технического устройства из двух узлов. Напомним состояния системы:

S0 -- оба узла исправны,

S1 -- первый узел ремонтируется, второй исправен,

S2 -- второй узел ремонтируется, первый исправен,

S3 -- оба узла ремонтируются.

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

Рисунок 16.2

Найдем все интенсивности потоков событий, переводящих систему из состояния в состояние. Пусть система находится в состоянии S0. Поток отказов первого узла переводит ее в состояние S1. Его интенсивность 1 равна единице, деленной на среднее время безотказной работы первого узла. Поток «окончаний ремонтов» первого узла переводит систему обратно из S1 в S0. Его интенсивность 1 равна единице, деленной на среднее время ремонта первого узла. Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем стрелкам графа рисунка 16.2.

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

Пусть рассматривается система S, имеющая n возможных состояний S1, S2, ..., Sn. Назовем вероятностью i-го состояния вероятность pi(t) того, что в момент t система будет находиться в состоянии Si. Очевидно, что для любого момента сумма всех вероятностей состояний равна единице:

n

У pi (t) = 1 (16.1)

i = 1

Имея в своем распоряжении размеченный граф состояний, можно найти все вероятности состояний pi(t) как функции времени. Для этого составляются и решаются так называемые уравнения Колмогорова -- особого вида дифференциальные уравнения, в которых неизвестными функциями являются вероятности состояний.

Пусть система S имеет четыре состояния: S1, S2, S3, S4, размеченный граф которых показан на рисунке 16.3.

Рассмотрим одну из вероятностей состояний, например p1(t). Это--вероятность того, что в момент t система будет в состоянии S1. Придадим t малое приращение t и найдем p1 (t + t) -- вероятность того, что в момент t + t система будет в состоянии S1.

Это может произойти двумя способами:

1) в момент t система уже была в состоянии S1, а за время t не вышла из него;

2) в момент t система была в состоянии S2, а за время t перешла из него в S1.

Найдем вероятность первого варианта. Вероятность того, что в момент t система была в состоянии S1, равна p1(t). Эту вероятность нужно умножить на вероятность того, что, находившись в момент t в состоянии S1, система за время t не перейдет из него ни в S2, ни в S3. Суммарный поток событий, выводящий систему из состояния S1, тоже будет простейшим, с интенсивностью 12+13. Значит, вероятность того, что за время t система выйдет из состояния S1, равна (12 + 13)t; вероятность того, что не выйдет:

1 -- (12 + 13)t. Отсюда вероятность первого варианта равна p1(t) [1 -- (12 + 13)t].

Найдем вероятность второго варианта. Она равна вероятности того, что в момент t система будет в состоянии S2, а за время t перейдет из него в состояние S1, т. е. она равна p2(t)21t.

Складывая вероятности обоих вариантов (по правилу сложения вероятностей), получим:

p1(t +t ) = p1(t) [1 -- (12 + 13)t] + p2(t)21t .

Раскроем квадратные скобки, перенесем p1(t) в левую часть и разделим обе части на t:

Устремим t к нулю; слева получим в пределе производную функции p1(t). Таким образом, запишем дифференциальное уравнение для p1(t):

или, короче, отбрасывая аргумент t у функций p1, p2 :

Рассуждая аналогично для всех остальных состоянии, напишем еще три дифференциальных уравнения. Присоединяя к ним уравнение (16.2), получим систему дифференциальных уравнений для вероятностей состояний:

Это -- система четырех линейных дифференциальных уравнений с четырьмя неизвестными функциями p1 p2, p3, p4. Одно из них (любое) можно отбросить, пользуясь тем, что p1 + p2 + p3 + p4 = 1, т.е. выразить любую из вероятностей pi через другие, это выражение подставить в (16.3), а соответствующее уравнение с производной dpi/dt отбросить.

Сформулируем общее правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятности какого-то (i-го) состояния. В правой части -- сумма произведений вероятностей всех состояний, из которых идут стрелки в данное состояние, на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i-ro) состояния.

Пользуясь этим правилом, запишем уравнения Колмогорова для системы S, размеченный граф состояний которой дан на рисунке 16.2:

dp0

---- = м1p1 + м2p2 - (л1 + л2) p0

dt

dp1

---- = л1p0 + м2p3 - (л2 + м1) p1

dt (16.4)

dp2

---- = л2p0 + м1p3 - (л1 + м2) p2

dt

dp3

---- = л2p1 + л1p2 - (м1 + м2) p3

dt

Чтобы решить уравнения Колмогорова и найти вероятности состояний, прежде всего надо задать начальные условия. Если мы точно знаем начальное состояние системы Si, то в начальный момент (при t = 0) р0(0) = 1, а все остальные начальные вероятности равны нулю. Так, например, уравнения (17.4) естественно решать при начальных условиях р0(0) = 1, p1(0) = р2(0) = р3(0) = 0 (в начальный момент оба узла исправны).

Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени.

§4. Финальные вероятности состояний

Если при t ? вероятности состояний p1(t), p2(t),... будут стремиться к каким-то пределам и если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний. В теории случайных процессов доказывается, что если число n состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то финальные вероятности существуют.

Предположим, что это условие выполнено и финальные вероятности существуют:

lim pi (t) = pi (i = 1, 2, . . . , n) (17.1)

t -> ?

Финальные вероятности будем обозначать теми же буквами p1, р2, ..., что и сами вероятности состояний, но понимая под ними уже не переменные величины (функции времени), а постоянные числа. Очевидно, они тоже образуют в сумме единицу:

n

У pi (t) = 1 (17.2)

i = 1

При t ? в системе S устанавливается предельный стационарный режим, в ходе которого система случайным образом меняет свои состояния, но их вероятности уже не зависят от времени. Финальную вероятность состояния Si можно рассматривать как среднее относительное время пребывания системы в этом состоянии. Например, если система S имеет три состояния S1, S2, S3 и их финальные вероятности равны 0,2, 0,3 и 0,5, это значит, что в предельном, стационарном режиме система в среднем две десятых времени проводит в состоянии S1, три десятых--в состоянии S2 и половину времени -- в состоянии S3.

Если вероятности p1, p2, ... постоянны, то их производные равны нулю. Значит, чтобы найти финальные вероятности, нужно все левые части в уравнениях Колмогорова положить равными нулю и решить полученную систему уже не дифференциальных, а линейных алгебраических уравнений. Если перенести отрицательный член каждого уравнения из правой части в левую, то получим сразу систему уравнений, где слева стоит финальная вероятность данного состояния рi, умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа -- сумма произведений интенсивностей всех потоков, входящих в i-е состояние, на вероятности тех состояний, из которых эти потоки исходят.

Пользуясь этим правилом, напишем линейные алгебраические уравнения для финальных вероятностей состояний системы, граф состояний которой дан на рисунке 16.2:

(л1 + л2) p0 = м1p1 + м2p2

(л2 + м1) p1 = л1p0 + м2p3

(л1 + м2) p2 = л2p0 + м1p3 (17.3)

(м1 + м2) p3 = л2p1 + л1p2

При решении этой системы четырех уравнений с четырьмя неизвестными р0, р1, р2, р3, воспользуемся так называемым нормировочным условием:

p0 + p1 + p2 + p3 = 1 (17.4)

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

Зададимся численными значениями интенсивностей 1 = 1, 2=2, 1 = 2, 2 = 3 и решим систему (17.3). Вместо четвертого уравнения добавим нормировочное условие (17.4). Уравнения примут вид:

3p0 = 2p1 + 3p2

4p1 = p0 + 3p3

4p2 = 2p0 + 3p3 (17.5)

p0 + p1 + p2 + p3 = 1

Решая их, получим:

p0 = 6/15=0,40; p1 =3/15 =0,20; p2 = 4/15 = 0,27; P3=2/15 =0,13,

т. е. в предельном, стационарном режиме система S в среднем 40% времени будет проводить в состоянии S0 (оба узла исправны), 20% -- в состоянии S1 (первый узел ремонтируется, второй работает), 27% --в состоянии S2 (второй узел ремонтируется, первый работает) и 13% -- в состоянии S3 полной негодности (оба узла ремонтируются). Знание этих финальных вероятностей может помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов. Предположим, что система S в состоянии S0 (полностью исправная) приносит в единицу времени доход 8 (условных единиц), в состоянии S1--доход 3, в состоянии S2--доход 5, в состоянии S3 -- вообще не приносит дохода. Тогда в предельном, стационарном режиме средний доход в единицу времени будет

W = 0,40 * 8 + 0,20 * 3 + 0,27 * 5 = 5,15.

Теперь оценим загрузку рабочих, занятых ремонтом узлов 1 и 2. Узел 1 ремонтируется долю времени, равную p1 + р3 = 0,20 + 0,13 = 0,33. Узел 2 ремонтируется долю времени p2 + р3 = 0,40.

Раздел 5. Теория массового обслуживания

§1. Понятие системы массового обслуживания. Классификация систем массового обслуживания

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

Системы массового обслуживания по наличию того или иного признака можно классифицировать таким образом:

1. По характеру поступления требований - на системы с регулярным и случайным потоками поступления требований в систему. Случайный поток подразделяется на стационарный и нестационарный:

- если количество поступающих требований в систему в единицу времени (интенсивность потока) постоянно или является заданной функцией времени, то это система с регулярным потоком поступления требований, в противном случае - со случайным;

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

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

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

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

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

- если поступившее требование застает все каналы обслуживания занятыми и становится в очередь, но находится в ней ограниченное время, после чего, не дождавшись обслуживания, покидает систему, то имеем систему с ограниченным ожиданием. Примером такого «нетерпеливого требования» может быть автосамосвал с раствором: если время ожидания велико, то во избежание затвердения раствора он может быть разгружен в другом месте;

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

5. По способу выбора требований на обслуживание - с приоритетом, по мере поступления, случайно, последний обслуживается первым. Иногда в таком случае говорят о дисциплине обслуживания:

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

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

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

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

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

7. По числу каналов обслуживания - на одноканальные и многоканальные системы. Так, при монтаже дома для обслуживания прибывающих на стройку изделий может быть использован один подъемный кран (один канал обслуживания) или несколько (много каналов).

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

9. По однородности требований, поступающих на обслуживание, - на системы с однородными и неоднородными потоками требований. Так, если под погрузку прибывают фургоны одной грузоподъемности, то такие требования называются однородными, если разной - неоднородными.

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

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

§2. Схема гибели и размножения

Имея размеченный граф состояний, можно написать уравнения Колмогорова для вероятностей состояний, а также написать и решить алгебраические уравнения для финальных вероятностей. Для некоторых случаев удается последние уравнения решить заранее, в буквенном виде. В частности, это удается сделать, если граф состояний системы представляет собой так называемую «схему гибели и размножения».

Граф состояний для схемы гибели и размножения имеет вид, показанный на рисунке 19.1.

Размещено на http://www.allbest.ru/

л01 л12 л23 лk-1,k лk,k-1 лn-1,n

л10 л21 л32 лk,k-1 лk+1,k лn,n-1

Рисунок 19.1

Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S1, S2, ..., Sn-1) связано прямой и обратной стрелкой с каждым из соседних состояний -- правым и левым, а крайние состояния (S0, Sn) -- только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

Предположим, что все потоки событий, переводящие систему по стрелкам графа,-- простейшие.

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

Для первого состояния S0 имеем:

01p0=10p1. ( 19.1 )

Для второго состояния S1:

(12 + 10)p1 = 01p0 + 21P2.

В силу ( 19.1 ) последнее равенство приводится к виду

12p1 = 21Р2;

далее, совершенно аналогично

23Р2 = 32p3

и вообще

k-1,kpk-1=k,k-1pk,

где k принимает все значения от 0 до n. Итак, финальные вероятности р0, p1,..., pn удовлетворяют уравнениям

01p0=10p1

12p1 = 21Р2

…………………. ( 19.2 )

k-1,kpk-1=k,k-1pk

………………….

n-1,npn-1=n,n-1pn

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

p0 +p1+p2+ ... +рn =1. ( 19.3 )

Решим эту систему уравнений. Из первого уравнения (19.2 ) выразим р1 через р0:

p1 = (01/10)p0. (19.4 )

Из второго, с учетом ( 19.4 ), получим:

p2=(12/21)p1=(1201)/(2110)p0; ( 19.5 )

из третьего, с учетом ( 19.5 ),

p3=(231201)/(322110)p0 (19.6 )

и вообще, для любого k (от 1 до n):

pk=(k-1,k... 1201)/(k,k-1... 2110)p0 ( 19.7 )

Обратим внимание на формулу ( 19.7 ). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния Sk,), а в знаменателе -- произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до Sk).

Таким образом, все вероятности состояний р0, р1, ..., рn выражены через одну из них (р0). Подставим эти выражения в нормировочное условие ( 19.3 ). Получим, вынося за скобку p0:

отсюда получим выражение для р0:

Все остальные вероятности выражены через р0 (см. формулы (19.4) - (19.7)). Коэффициенты при р0 в каждой из них представляют собой последовательные члены ряда, стоящего после единицы в формуле ( 19.8 ). Значит, вычисляя р0, мы уже нашли все эти коэффициенты.

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

§3. Простейшие системы массового обслуживания и их параметры

Рассмотрим одноканальную замкнутую систему массового обслуживания (СМО) с неограниченным временем ожидания требований для него и с простейшим потоком. Этот поток характеризуется следующими особенностями: первая - поступление требований в систему на обслуживание происходит по одному, то есть вероятность прибытия двух и более требований в один момент времени очень мала, и поэтому ею можно пренебречь (поток требований ординарный). Вторая - вероятность поступления последующих требований в любой момент времени не зависит от возможности их прибытия в предыдущие моменты - поток требований без последействия. Третья особенность - поток требований стационарный.

Функционирование любой системы массового обслуживания можно представить через все возможные состояния ее и интенсивность перехода из одного состояния в другое. Основными параметрами функционирования СМО являются вероятности ее состояния, то есть возможности наличия n требований (покупателей, рабочих, заданий, машин, неполадок) в системе - Pn. Так, вероятность Р0 характеризует состояние, когда в системе нет требований и канал обслуживания простаивает.

Важным параметром функционирования СМО является среднее число требований, находящихся в системе Nsyst , то есть в очереди на обслуживание, а также средняя длина очереди Noch. Исходными параметрами, характеризующими систему массового обслуживания, являются: число каналов обслуживания - N (касс, компьютеров, кранов, ремонтных бригад,...); число требований (покупателей, заданий, машин, неполадок,...) - m; интенсивность поступления одного требования на обслуживание - л, то есть число поступлений требований в единицу времени; интенсивность обслуживания требований - м.

Интенсивность поступления требования на обслуживание определяется как величина, обратная времени возвращения требования, - tвоз:

л = 1/ tвоз.

Интенсивность обслуживания требований определяется как величина, обратная времени обслуживания одного требования, - tобс:

м = 1/ tобс.

Постановка задачи

Пусть задан комплект машин «экскаватор - автосамосвалы». Экскаватор погружает за один рабочий цикл gэ = 1 т массы грунта. Грузоподъемность автосамосвала gа = 7 т. Число машин, обслуживающих экскаватор, m = 5. Время рабочего цикла экскаватора составляет tр.ц. = 18 с, а время обращения автосамосвала tобр. = 10 мин. Определить фактическую производительность комплекта машин; среднее число машин, находящихся в системе; среднее число машин, находящихся в очереди; вероятность наличия n машин в системе.

Построение математической модели.

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

- в системе нет ни одного требования - вероятность состояния Р0;

- в системе находится одно требование - вероятность состояния P1;

- в системе находится n требований - вероятность состояния Рn.

Представим все возможные состояния СМО в виде размеченного графа состояний (рисунок 20.1). Каждый прямоугольник графа, количественно оцениваемый вероятностью состояний Рn, определяет одно из всех возможных состояний. Стрелки указывают, в какое состояние система может перейти и с какой интенсивностью.

Первый прямоугольник с вероятностью Р0 определяет состояние СМО, при котором канал обслуживания простаивает из-за отсутствия требований в ней. Из этого положения система может перейти только в состояние Р1. Тогда в ней появится одно требование, так как входной поток их ординарный. С интенсивностью м система может перейти также из состояния Р1 в состояние Р0; когда в системе находилось одно требование, оно было обслужено раньше, чем появилось новое и т.д.

Рассмотрим установившийся режим работы системы массового обслуживания, когда основные вероятностные характеристики СМО постоянны во времени, например, в течение часа. Тогда интенсивности входных и выходных потоков для каждого состояния будут сбалансированы. Эти балансы выглядят так:

P0m л = P1 м

P1(м + (m - 1) л) = P0m л + P2 м

P2(м + (m - 2) л) = P1 (m - 1) л + P3 м

. . . . . . . . . . . . . . . . . .

Pn(м + (m - n) л) = Pn-1 (m - (n - 1)) л + Pn+1 м (20.1)

. . . . . . . . . . . . . . . . . .

Pm м = Pm -1 л

Обозначим величину л/ м через ш и назовем ее коэффициентом загрузки.

Из первого уравнения можно найти значение Р1:

P1 = P0m л / м = P0m ш.

Из второго уравнения найдем значение Р2:

P2 = P1 + P1(m - 1) л / м - P0m л / м

Но первый член - P1 = P0m л / м , следовательно, первый и третий сокращаются:

P2 = P1(m - 1) л / м = P0m(m - 1) ш2.

Из третьего уравнения найдем значение Р3:

P3 = P2 + P2(m - 2) л / м - P1(m - 1) л / м

Но первый член - P2 = P1(m - 1) л / м , следовательно, первый и третий сокращаются:

P3 = P2(m - 2) л / м = P0m(m - 1)(m - 2)ш3

……………………………………………………

m

Pn = Pn-1(m - (n - 1)) л / м = P0m(m - 1)…(m - (n - 1))шn = P0 ? (m - (n - 1))! • шn

n=0

m

Используя очевидное равенство ? Pn = 1 , получим:

n=0

m

1 = P0 ? (m - (n - 1))! • шn (20.2)

n=0

Зная вероятность простоя канала обслуживания Р0, можно определить его фактическую производительность:

Pf = (1 - P0) •µ • G (20.3)

где G, например, количество груза, помещенного за одно обслуживание в машину.

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

(m - Nsyst) • л = (1 - P0) • µ (20.4)

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

Nsyst = m - (1 - P0) / ш (20.5)

Среднее же число требований (машин), находящихся в очереди, будет вычислено так:

Noch = Nsyst - (1 - P0) = m - (1 - P0) (1/ ш + 1) (20.6)

Решение задачи при установившемся режиме работы.

Время обслуживания одного грузовика составит:

gа

tпогр = ------- tр.ц. (20.7)

gэ

18 х 7

tпогр = -------- = 2,1 мин.

60 х 1

Интенсивность погрузки автосамосвала экскаватором составит:

1

µ = ------ (20.8)

tпогр

60

µ = ------ = 29 погрузок в час.

2,1

Интенсивность же поступления автосамосвала на погрузку составит:

1

л = ------ (20.9)

tобр

60

л = ------- = 6 обращений в час.

10

Коэффициент ш = л/ м будет равен ш = 0,207.

Вероятность простоя экскаватора в этом случае составит:

1

P0 = --------------------------------- (20.10)

m

1 + ? (m - (n - 1))! • шn

n=1

1

P0 = --------------------------------- = 0,271

5

1 + ? (5 - (n - 1))! • шn

n=1

Таким образом, фактическая производительность данного комплекта машин будет на 27,1% ниже технической.

Вероятности наличия n машин в системе:

P1 = P0 m ш = 0,281

P2 = P1 (m - 1) ш = 0,233

P3 = P2 (m - 2) ш = 0,144

P4 = P3 (m - 3) ш = 0,06

P5 = P4 (m - 4) ш = 0,012

Фактическая производительность комплекта машин определяется по формуле 20.3 :

Pf = (1 - 0,271) • 29 • 7 = 147,947 т/час.

Среднее число машин, находящихся в системе определяется по формуле 20.6 :

Nsyst = 5 - (1 - 0,271) / 0,207 = 1,477

Среднее число машин, находящихся в очереди определяется по формуле 20.7 :

Noch = 5 - (1 - 0,271) (1/0,207 + 1) = 0,749

Раздел 6. Имитационное моделирование

§1. Метод имитационного моделирования. Типы имитационных моделей

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

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

1. Задачи в различных областях естественных наук (математика, физика, химия):

- вычисление площадей фигур, ограниченных кривыми, или, в более общем случае, вычисление кратных интегралов;

- вычисление констант (например р, равной 3,14159..,);

- обращение матриц;

- изучение диффузионных процессов.

2. Практические задачи:

- производственно-технологические задачи, возникающие в процессе создания систем массового обслуживания, систем связи, в сфере управления запасами, а также при анализе химических процессов;

- экономические и коммерческие задачи, включая оценки поведения потребителя, определение цен, экономическое прогнозирование деятельности фирм;

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

- задачи биомедицинских систем, например проблема баланса жидкости в организме человека, размножения клеток крови, деятельности мозга;

- задачи анализа той или иной военной стратегии и тактики.

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

Использование современных имитационных моделей основано, в основном, на идее метода Монте-Kapло (выборка случайных чисел для получения искомых оценок). Отличие состоит в том, что имитационная модель обычно связана с изучением реально существующей системы, поведение которой является функцией времени. Существует два типа имитационных моделей.

Непрерывные модели используются для систем, поведение которых изменяется непрерывно во времени. Типичным примером непрерывной имитационной модели является изучение динамики народонаселения мира. Непрерывные имитационные модели обычно представляются в виде разностно-дифференциальных уравнений, которые описывают взаимодействие между различными элементами системы.

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

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

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

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

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

§2. Языки имитационного моделирования

Реализация имитационных моделей влечет за собой два различных типа вычислений:

1) манипуляции регистрацией, которые имеют дело с хронологическим накоплением и обработкой событий модели;

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

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

Доступные языки дискретного имитационного моделирования делятся на две большие категории:

1) Языки, ориентированные на планирование событий.

2) Языки, ориентированные на обработку процессов (процедур).

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

Процедурно-ориентированные языки используют блоки (или узлы), которые можно соединять для формирования сети, которая описывает движение транзакций или объектов (т.е. клиентов) в системе.

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

Наиболее известными языками программирования, ориентированными на планирование событий, являются SIMSCR1PT, SLAM и SIMAN. Все эти языки позволяют пользователю создавать модели (или их отдельные части) на языках высокого уровня, таких как FORTRAN и С. Это необходимо для того, чтобы дать возможность пользователю программировать сложные логические операции, которые невозможно или трудно осуществить обычными средствами этих языков.

Первым процедурно-ориентированным языком был GPSS. Этот язык, первая версия которого появилась в начале 60-х годов, совершенствовался на протяжении нескольких лет, чтобы удовлетворить новым требованиям, связанным с моделированием сложных систем. Чтобы эффективно использовать этот язык, пользователю необходимо настроить примерно восемьдесят различных блоков. До сих пор язык GPSS все еще имеет некоторые трудно объяснимые особенности моделирования.

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

Раздел 7. Прогнозирование

§1. Основная идея прогнозирования. Методы прогнозирования

Принимая решения, мы определяем планы на будущее. Следовательно, используемые при этом данные должны соответствовать будущим событиям. Например, в теории управления запасами мы обосновываем наши решения посредством спроса на определенные виды продукции в течение определенного планового периода. Аналогично в финансовом планировании необходимо предсказать структуру денежного потока в будущем на основе структуры текущих денежных потоков.

Рассмотрим две методики прогнозирования изменений интересующих нас переменных как функций времени.

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

yt = b + еt

где yt - действительное (или наблюденное) значение случайной величины у в момент времени t;

b-- неизвестный постоянный параметр, который оценивается на основе представленной информации;

еt - случайный компонент (или шум) в момент времени t.

Предполагается, что случайная ошибка еt имеет нулевое математическое ожидание и постоянную дисперсию.

Метод с использованием скользящего среднего предполагает, что последние п наблюдений являются равнозначно важными для оценки параметра b. Другими словами, если в текущий момент времени t последними n наблюдениями есть yt-n+1, yt-n+2, …, yt, тогда оцениваемое значение для момента t + 1 вычисляется по формуле

yt-n+1 + yt-n+2 + … + yt

yt+1* = --------------------------------

n

где yt* - расчетное значение (оценка) случайной величины у в момент времени t.

Не существует четкого правила для выбора числа n - базы метода, использующего скользящее среднее. Если есть весомые основания полагать, что наблюдения в течение достаточно длительного времени удовлетворяют модели yt = b + еt, то рекомендуется выбирать большие значения n. Если же наблюдаемые значения удовлетворяют приведенной модели в течение коротких периодов времени, может быть приемлемым и малое значение n. На практике величина я обычно принимается в пределах от 2 до 10.

Прогнозирование путем экспоненциального сглаживания. Прогнозирование путем экспоненциального сглаживания (метод экспоненциального сглаживания) предполагает, что вероятностный процесс определяется моделью yt = b + еt.

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

Определим величину б (0 < б < 1) как константу сглаживания, и пусть известны значения временного ряда для прошедших t моментов времени у1, у2, …, уt. Тогда оценка yt+1* для момента времени t + 1 вычисляется по формуле

yt+1* = бyt + б(1 - б)yt-1 + б(1 - б)2yt-2 + …

Коэффициенты при yt, yt-1, yt-2, … постепенно уменьшаются, тем самым эта процедура приписывает больший вес последним (по времени) данным.

Формулу для вычисления yt+1* можно привести к следующему (более простому) виду:

yt+1* = бyt + (1 - б){бyt-1 + б(1 - б)yt-2 + б(1 - б)2yt-3 …} = = бyt + (1 - б)y*t

Таким образом, значение yt+1* можно вычислить на основании значения y*t . Вычисления в соответствии с этим уравнением начинаются с того, что пропускается оценка y*1 для t = 1 и в качестве оценки для t = 2 принимается величина для t = 1, т.е. y*2 = y1.

Выбор константы сглаживания б является решающим моментом при вычислении значения прогнозируемой величины. Большее значение б приписывает больший вес последним наблюдениям. На практике значение б берут в пределах от 0.01 до 0.30.

Раздел 8. Теория принятия решений

§1. Элементы теории принятия решений

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

1. Принятие решений в условиях определенности, когда данные известны точно.

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

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

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

Принятие решений в условиях определенности

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

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

Метод анализа иерархий

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

Мартин Ганс -- выпускник-отличник средней школы, который получил полную стипендию от трех университетов: А, В и С. В целях выбора университета Мартин сформулировал два основных критерия: местонахождение университета и его академическая репутация. Будучи отличным учеником, он оценивает академическую репутацию университета в пять раз выше, чем его местонахождение. Это приводит к тому, что репутации университета приписывается вес примерно 83%, а его местонахождению -- 17%. Далее Мартин использует системный анализ (сущность его излагается ниже) .для оценки трех университетов с точки зрения их местонахождения и репутации. Проведенный анализ дает следующие оценки.

	Университет
	A	B	C
Местонахождение	12,9%	27,7%	59,4%
Репутация	54,5%	27,3%	18,2%

Структура задачи принятия решений приведена на рисунке 24.1. Задача имеет единственный иерархический уровень с двумя критериями (местонахождение и репутация) и три альтернативных решения (университеты А, В и С).

Оценка трех университетов основана на вычислении комбинированного весового коэффициента для каждого из них.

Университет А: 0.17 х 0.129 + 0.83 х 0.545 = 0.4743.

Университет В: 0.17 х 0.277 + 0.83 х 0.273 = 0.2737.

Университет С: 0.17 х 0.594 + 0.83 X 0.182 = 0.2520.

На основе этих вычислений университет А получает наивысший комбинированный вес и, следовательно, является наиболее оптимальным выбором Мартина.

Общая структура метода анализа иерархий может включать несколько иерархических уровней со своими критериями.

Рисунок 24.1 - Структура задачи принятия решений

Принятие решений в условиях риска

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

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

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

Предположим, что вы хотите вложить на фондовой бирже 10 000 долларов в акции одной из двух компаний: А или В. Акции компании А являются рискованными, но могут принести 50% прибыли от суммы инвестиции на протяжении следующего года. Если условия фондовой биржи будут неблагоприятны, сумма инвестиции может обесцениться на 20%. Компания В обеспечивает безопасность инвестиций с 15% прибыли в условиях повышения котировок на бирже и только 5% -- в условиях понижения котировок. Все аналитические публикации, с которыми можно познакомиться (а они всегда есть в изобилии в конце года), с вероятностью 60% прогнозируют повышение котировок и с вероятностью 40% -- понижение котировок. В какую компанию следует вложить деньги?

Информация, связанная с принятием решения, суммирована в следующей таблице 24.1.

Таблица 24.1

Альтернативное решение	Прибыль от инвестиций за один год
	При повышении котировок ($)	При понижении котировок ($)
Акции компании А	5000	-2000
Акции компании В	1500	500
Вероятность события	0,6	0,4

Эта задача может быть также представлена в виде дерева решения, показанного на рисунке 24.2. На этом рисунке используется два типа вершин: квадратик представляет "решающую" вершину, а кружок-- "случайную". Таким образом, из вершины 1 ("решающая") выходят две ветви, представляющие альтернативы, связанные с покупкой акций компании А или В. Далее две ветви, выходящие из "случайных" вершин 2 и 3, соответствуют случаям повышения и понижения котировок на бирже с вероятностями их появления и соответствующими платежами.

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

Для акций компании А: $5000 х 0.6 + (-2000) х 0.4 = $2 200.

Для акций компании В: $1500 х 0.6 + $500 х 0.4 = $1 100.

Вашим решением, основанным на этих вычислениях, является покупка акций компании А.

Рисунок 24.2 - Дерево решения

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

Раздел 9. Теория игр

§1. Основные понятия теории игр. Простейшие методы решения задач теории игр

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

В игровом конфликте участвуют два противника, именуемые игроками, каждый из которых имеет некоторое множество (конечное или бесконечное) возможных выборов, которые называются стратегиями. С каждой парой стратегий связан платеж, который один из игроков выплачивает другому. Такие игры известны как игры двух лиц с нулевой суммой, так как выигрыш одного игрока равен проигрышу другого. В такой игре достаточно задать результаты в виде платежей для одного из игроков. При обозначении игроков через А и В с числом стратегий m и n соответственно, игру обычно представляют в виде матрицы платежей игроку А:

A1 A2 … Am	B1 B2 ….. Вn
	a11 a12 ………. a1n a21 a22 ………. a2n …………………………. am1 am2 ………. amn

Такое представление матричной игры означает, что если игрок А использует стратегию i, а игрок В -- стратегию j, то платеж игроку А составляет аij и, следовательно, игроку В -- -аij.

Оптимальное решение игры двух лиц с нулевой суммой

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

Например, две компании А и В продают два вида лекарств против гриппа. Компания А рекламирует продукцию на радио (А1), телевидении (А2) и в газетах (А3). Компания В, в дополнение к использованию радио (В1), телевидения (В2) и газет (В3), рассылает также по почте брошюры (В4). В зависимости от умения и интенсивности проведения рекламной кампании, каждая из компаний может привлечь на свою сторону часть клиентов конкурирующей компании. Приведенная ниже матрица характеризует процент клиентов, привлеченных или потерянных компанией А

Минимумы строк

A1 A2 A3	B1 B2 В3 В4
	8 -2 9 -3 6 5 6 8 -2 4 -9 5

Максимумы столбцов 8 5 9 8

Минимакс

Решение игры основано на обеспечении наилучшего результата из наихудших для каждого игрока. Если компания А выбирает стратегию А1 то, независимо от того, что предпринимает компания В, наихудшим результатом является потеря компанией А 3% рынка в пользу компании В. Это определяется минимумом элементов первой строки матрицы платежей. Аналогично при выборе стратегии А2 наихудшим исходом для компании А является увеличение рынка на 5% за счет компании В. Наконец, наихудшим исходом при выборе стратегии Аз является потеря компанией А 9% рынка в пользу компании В. Эти результаты содержатся в столбце "Минимумы строк". Чтобы достичь наилучшего результата из наихудших, компания А выбирает стратегию А2, так как она соответствует наибольшему элементу столбца "Минимумы строк".

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

Оптимальным решением игры является выбор стратегий А2 и В2, т.е. обеим компаниям следует проводить рекламу на телевидении. При этом выигрыш будет в пользу компании А, так как ее рынок увеличится на 5%. В этом случае говорят, что цена игры равна 5% и что компании А и В используют стратегии, соответствующие седловой точке.