Сегодня любой опытный менеджер знает, что браться за новый проект нужно только в том случае, если его можно закончить в строго определенный и достаточно короткий срок. Сотни гениальных программ канули в Лету только потому, что устарели уже на стадии реализации. Особенно остро эта проблема стоит сейчас, когда одна фирма дышит в затылок другой, причем производят они очень похожие продукты. Одних текстовых редакторов десятки, не говоря уже об утилитах общего назначения, переводчиках и т. д. Одна из сред, в которой быстрее всего можно реализовать проект, это среда Visual Basic.
Глава 2
Математическое описание модели.
Данный раздел описания базируется на работах Е. С. Вентцель.
2.1 Марковские случайные процессы.
Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние
Пусть в момент t0 система находится в определенном состоянии S0. Мы наблюдаем процесс со стороны и в момент t0 знаем состояние системы S0 и всю предысторию процесса, все, что было при t < t0. Нас интересует будущее (t > t0). В точности невозможно его предугадать, так как процесс — случайный, а значит — непредсказуемый. Но вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время t система S окажется в состоянии S1 или сохранит состояние S0, и т. п.
Для марковского случайного процесса такое «вероятностное предсказание» оказывается гораздо проще, чем для немарковского. Если процесс — марковский, то предсказывать можно, только учитывая настоящее состояние системы S0 и забыв о его «предыстории» (поведении системы при t < t0). Само состояние S0, разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. В марковском процессе «будущее зависит от прошлого только через настоящее».
На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. Пример: система S — группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» — x и «синих» — y, сохранившихся (не сбитых) к определенному моменту. В момент t0 нам известны численности сторон — x0 и y0. Нас интересует вероятность того, что в момент времени t0 + t численный перевес будет на стороне «красных». В первую очередь эта вероятность будет зависеть от того, в каком состоянии находится система в момент t0, а не от того, когда и в какой последовательности погибали сбитые до момента t0 самолеты.
В сущности, любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит «будущее», включить в «настоящее». Например, пусть речь идет о работе некоторого технического устройства; в момент t0 оно еще исправно, и нас интересует вероятность того, что оно проработает еще время t. Если за настоящее состояние системы считать просто «система исправна», то процесс безусловно немарковский, потому что вероятность того, что она не откажет за время t, зависит, в общем случае, от того, сколько времени она уже проработала и когда был последний ремонт. Если оба эти параметра (общее время работы и время после последнего ремонта) включить в настоящее состояние системы, то процесс можно будет считать марковским. Однако такое «обогащение настоящего за счет предыстории» далеко не всегда бывает полезно, поэтому в дальнейшем, говоря о марковском процессе, будем подразумевать его простым, с небольшим числом параметров, определяющих «настоящее».
На практике марковские процессы в чистом виде обычно не встречаются, но нередко приходится иметь дело с процессами, для которых влиянием «предыстории» можно пренебречь. При изучении таких процессов можно с успехом применять марковские модели.
В исследовании операций большое значение имеют так называемые марковские случайные процессы с дискретными состояниями и непрерывным временем. Процесс называется процессом с дискретными состояниями, если его возможные состояния S1, S2, S3, ... можно заранее перечислить (перенумеровать), и переход системы из состояния в состояние происходит «скачком», практически мгновенно. Процесс называется процессом с непрерывным временем, если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны, т. е. если переход может осуществиться в любой момент времени. При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой — так называемым графом состояний. Состояния системы изображаются прямоугольниками (или кругами, или точками), а возможные переходы из состояния в состояние — стрелками, соединяющими состояния. Мы будем изображать состояния прямоугольниками, в которых записаны обозначения состояний: S1, S2, ..., Sn.
Потоком событий называется последовательность однородных событий, следующих одно за другим в случайные моменты времени. Например: поток вызовов на телефонной станции; поток отказов (сбоев) ЭВМ; поток железнодорожных составов, поступающих на сортировочную станцию, и т. д.
Важной характеристикой потока событий является его интенсивность l — среднее число событий, приходящееся на единицу времени. Интенсивность потока может быть как постоянной (l= const), так и переменной, зависящей от времени t. Например, поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, в часы пик — интенсивнее, чем в другие часы.
Поток событий называется регулярным, если события следуют одно за другим через определенные, равные промежутки времени. На практике чаще встречаются потоки нерегулярные, со случайными интервалами.
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. Поток событий называется потоком без последействия, если для любых двух непересекающихся интервалов времени t1 и t2 число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. По сути это означает, что события, образующие поток, появляются в те или иные моменты времени независимо друг от друга, причем каждое вызвано своими собственными причинами.
Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами по несколько сразу. Например, поток клиентов, направляющихся в парикмахерскую или к зубному врачу, обычно ординарен, чего нельзя сказать о потоке клиентов, направляющихся в загс для регистрации брака. Поток поездов, подходящих к станции, ординарен, а поток вагонов — неординарен. Если поток событий ординарен, то вероятностью попадания на малый интервал времени t двух или более событий можно пренебречь.
Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия. Название «простейший» связано с тем, что процессы, связанные с простейшими потоками, имеют наиболее простое математическое описание. Самый простой, на первый взгляд, регулярный поток не является «простейшим», так как обладает последействием: моменты появления событий в таком потоке связаны жесткой функциональной зависимостью.
Простейший поток играет среди других потоков особую роль. А именно, при наложении (суперпозиции) достаточно большого числа независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивности) получается поток, близкий к простейшему.
Для простейшего потока с интенсивностью l интервал между соседними событиями имеет так называемое экспоненциальное распределение с плотностью
(t > 0) (1)
Величина l в формуле (1) называется параметром показательного закона. Для случайной величины Т, имеющей экспоненциальное распределение, математическое ожидание mT есть величина, обратная параметру, а среднее квадратическое отклонение sT равно математическому ожиданию:
(2)
В теории вероятностей в качестве «меры случайности» неотрицательной случайной величины нередко рассматривают так называемый коэффициент вариации:
(3)
Из формул (2), (3) следует, что для показательного распределения nt = 1, т. е. для простейшего потока событий коэффициент вариации интервалов между событиями равен единице.
Очевидно, что для регулярного потока событий, у которого интервал между событиями вообще не случаен (nt = 0), коэффициент вариации равен нулю. Элементом вероятности называется вероятность попадания на этот интервал хотя бы одного события потока. Легко доказать, что элемент вероятности (с точностью до малых величин более высокого порядка по сравнению с Dt) равен:
(4)
т. е. для простейшего потока элемент вероятности равен интенсивности потока, умноженной на длину элементарного интервала. Элемент вероятности, в силу отсутствия последействия, совершенно не зависит от того, сколько событий и когда появлялись ранее.
Нормальное распределение занимает центральное место среди непрерывных распределений. Его плотность определяется формулой:
F(t) = (5)
где s > 0, m — параметры распределения. При s = 1 и m = 0 имеет место стандартное нормальное распределение с плотностью:
F(t) = (6)
Пусть рассматривается система S, имеющая n возможных состояний S1, S2, ..., Sn. Назовем вероятностью i-го состояния вероятность pi(t) того, что в момент t система будет находиться в состоянии Si. Очевидно, что для любого момента сумма всех вероятностей состояний равна единице.
Имея в своем распоряжении размеченный граф состояний, можно найти все вероятности состояний pi(t) как функции времени. Для этого составляются и решаются так называемые уравнения Колмогорова — дифференциальные уравнения особого вида, в которых неизвестными функциями являются вероятности состояний.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25
