Разработка программы моделирования СМО
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
нове принципа - устройство, преобразующее входной сигнал каждый такт времени или дифференцирующий фильтр.
При использовании принципа состояния системы фиксируются только в особые моменты времени, шаг по времени в этом случае не постоянен, является величиной случайной и вычисляется в соответствии с информацией о предыдущем особом состоянии. К системам, имеющим особые состояния, относятся системы массового обслуживания (СМО). Особые состояния появляются в моменты поступления заявок, в моменты освобождения каналов и т.д. Для таких систем применение принципа нерационально, так как при этом возможны пропуски особых состояний и необходимы методы их обнаружения. Принцип дает возможность для ряда систем существенно уменьшить затраты машинного времени на реализацию моделирующих алгоритмов по сравнению с принципом . Для исследования процесса функционирования больших систем рационально использование комбинированного принципа построения моделирующих алгоритмов, сочетающего в себе преимущества каждого из рассмотренных принципов.
1.4 Аналитический метод моделирования систем
.4.1 Постановка задачи
К разомкнутым относятся системы, в которых поступающий поток требований теоретически неограничен [8], а количество ожидающих заявок в очереди наоборот, ограничено. Для примера можно взять работу автозаправки с несколькими бензоколонками. Автомобиль, заправившись, покидает систему. Если все заправочные места заняты, автомобили могут вставать в общую очередь. В случае, если величина очереди к бензоколонкам слишком большая, автомобиль покидает систему не обслуженным.
В подобных системах общее число циркулирующих требований ограничено (рисунок 1.1).
Рисунок 1.1 - Размеченный граф состояний разомкнутой СМО
В приведенном графе, состоянию S0 соответствует простой системы, то есть заявки на обслуживания не поступали или все поступившие были обслужены. Состояниям с S1 по SN сопоставимы события, когда в системе присутствуют N требований, при этом все они обслуживаются N каналами. И состояния с SN+1 по SN+m представляют собой ситуации, когда требования не могут быть обслужены, вследствие занятости каналов обслуживания, и помещены в очередь на обслуживание. m - величина, ограничивающая длину очереди (в другой терминологии - m - количество мест в накопителе очереди). Следующие параметры являются входными и задают структуру и особенности функционирования системы.
? - интенсивность потока обслуживания;
? - интенсивность входного потока;
N - число каналов (приборов) обслуживания;- величина, ограничивающая длину очереди.
Основные задачи теории моделирования разомкнутых СМО заключаются:
-в расчете выходных характеристик СМО, характеризующих эффективность функционирования системы (вероятность простоя системы, вероятность отказа в обслуживании, среднее число заявок в системе, среднее число занятых каналов, среднее время ожидания в очереди и т.д.);
-в оценке и анализе эффективности функционирования СМО на основе рассчитанных характеристик;
-в оптимизации характеристик функционирования СМО.
1.4.2 Процесс обслуживания как случайный процесс
Пусть имеется некоторая система S, которая в процессе функционирования может принимать различные состояния Si, i=1, 2,тАж, n. Если состояния системы меняются случайным образом, то последовательность состояний системы образует случайный процесс.
В каждый момент рассматриваемая система может находиться в одном из следующих состояний: в момент t в системе находятся k требовании (k=0, 1, 2,тАж). Если kN, то в системе находятся и обслуживаются k требований, а N-k - приборов свободны. Если k > N, то N требований обслуживаются, а k-N находятся в очереди и ожидают обслуживания. Обозначим через Sk состояние, когда в системе находятся k требований. Таким образом, система может находиться в состояниях S0, S1, S2, тАж Обозначим через Pb(t) - вероятность того, что система в момент t окажется в состоянии Sb.
Сформулируем, в чем заключается особенность изучаемых нами задач в сделанных предположениях. Пусть в некоторый момент t0 наша система находилась в состоянии Si. Докажем, что последующее течение процесса обслуживания не зависит в смысле теории вероятностей от того, что происходило до момента t0. Действительно, дальнейшее течение обслуживания полностью определяется тремя следующими факторами:
-моментами окончания обслуживаний, производящихся в момент t0;
-моментами появления новых требований;
-длительностью обслуживания требований, поступивших после t0.
Процесс, протекающий в системе S, называется Марковским процессом с дискретными состояниями и непрерывным временем (или непрерывной Марковской цепью), если выполняется условие: для любого фиксированного момента времени условные вероятности состояния системы в будущем зависят только от состояния системы в настоящем и не зависят от того, когда (на каком шаге) и откуда система перешла в это состояние [9].
Если в такой системе все потоки, переводящие систему из состояния в состояние Пуассоновские, то процесс называется Марковским случайным процессом гибели и размножения. Термин ведет начало от биологических задач, процесс описывает изменение численности популяции. Переход из состояния в состояние происходит в момент гибели или рождения особи.
1.4.3 Нахождение вероятностей состояний системы. Система уравнений Колмогорова
На практике значительная часть с