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

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

КУРСОВАЯ РАБОТА

на тему: «Статическое моделирование системы массового обслуживания»

Содержание

Введение

Глава 1. Параметры и характеристики систем массового обслуживания

1.1 Параметры систем массового обслуживания

1.2 Характеристики функционирования СМО

Глава 2. Авторизация поиска максимальных потоков в сетях

2.1 Описание интерфейса программы

2.2 Инструкция пользователя

2.3 Описание программного кода

2.4 Тестовый пример

Заключение

Список литературы

Приложение

Введение

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

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

В данной курсовой работе, мы рассмотрим и реализуем на языке программирования Object Pascal в интегрированной среде Delphi7 статическую модель системы массового обслуживания.

Целью настоящего курсового проекта является написание программного продукта реализующего статическую модель СМО.

Задачи:

- изучить специальную литературу;

- создать блок-схему;

- создать необходимые процедуры;

- создать программный продукт;

- протестировать программный продукт;

- сделать отладку программы.

Глава 1. Параметры и характеристики систем массового обслуживания

1.1 Параметры систем массового обслуживания

интерфейс программа модель массовое обслуживание

Общие положения.

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

Процесс функционирования СМО включает в общем случае следующие этапы:

1) приход (поступление) требования;

2) ожидание (при необходимости) в очереди;

3) обслуживание в приборе;

4) уход требования из системы.

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

Для формализации любой СМО необходимо описать:

1) процесс поступления заявок в систему;

2) процесс обслуживания заявок в системе;

3) дисциплину обслуживания.

Процесс поступления заявок.

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

Пусть t₁, t₂, t₃, ... , t_k, ... -- моменты поступления в систему 1-го, 2-го, 3-го, ..., k-го, ... требований:

Обозначим через _k = t_k - t_k-1 промежуток времени между моментами прихода (k-1)-го и k-го требований, который называется интервалом прихода k-го требования (k = 1, 2, 3, ...).

Если интервалы прихода всех заявок являются постоянными, т.е. , то такой поток называется детерминированным или регулярным. Однако, как правило, интервалы прихода _k являются случайными величинами, и соответствующий поток заявок называется стохастическим или случайным. Очевидно, что регулярный поток является частным случаем случайного потока.

Для описания стохастического потока (стохастического процесса поступления) заявок необходимо задать функцию распределения случайного в общем случае интервала прихода для каждой заявки:

.

Поток заявок, для которого функции распределения интервалов прихода всех заявок одинаковы, т.е.

называется рекуррентным. Другими словами, для рекуррентного потока интервалы прихода ( ) всех заявок распределены по одному и тому же закону.

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

Величина а, обратная интенсивности (а=1/), определяет среднее значение интервалов прихода или средний интервал поступления заявок.

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

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

При анализе СМО важное место занимает так называемый простейший поток. Простейшим называется поток, в котором интервалы поступления заявок распределены по экспоненциальному закону:

.

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

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

Простейший поток обладает следующими свойствами.

1) Сумма (слияние) двух или более простейших потоков образует простейший поток, интенсивность которого равна сумме интенсивностей составляющих его простейших потоков.

2) Если из простейшего потока интенсивности исключить каждую заявку с вероятностью р (а с вероятностью 1-р оставить), то как поток исключенных, так и поток оставшихся заявок, окажутся простейшими с интенсивностями р и (1-р) соответственно:

3) Число заявок N(t) простейшего потока, поступающих в СМО за время t, будучи случайной целочисленной дискретной величиной, распределено по закону Пуассона:

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

Таким образом, для описания рекуррентного, стационарного и ординарного процесса поступления заявок необходимо в общем случае задать функцию распределения интервалов их поступления. Однако не всегда бывает известной функция распределения. В таких случаях вместо неизвестной функции распределения для описания входного потока задаются интенсивность (или средний интервал а=1/) и коэффициент вариации (КВ) _а интервалов поступления, что оказывается достаточным для многих теоретических и практических приложений. Более того, в большинстве аналитических исследований в качестве входного потока заявок рассматривается простейший поток, ибо только в этом случае удается получать сколько-нибудь содержательные результаты анализа СМО. А для описания простейшего потока достаточно задать интенсивность , т.к. при этом КВ _а1 в силу экспоненциального характера распределения интервалов поступления заявок.

Выделение используемых при анализе СМО потоков схематически представлено на рисунке:

Процесс обслуживания.

По аналогии с процессами поступления заявок в систему для описания процессов обслуживания необходимо задать функцию распределения B_k(t) длительности обслуживания для каждой k-й заявки (k = 1, 2, 3, ...), которая в общем случае является случайной величиной. При этом под длительностью обслуживания _в понимается промежуток времени, в течение которого заявка находится в обслуживающем приборе. Далее будем считать, что все заявки создают статистически однородную нагрузку, т.е. длительности обслуживания всех заявок распределены по одному и тому же закону:

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

Величина b, обратная интенсивности (b=1/), определяет среднее время обслуживания одной заявки.

Как и в случае интервалов поступления, если функция распределения B(t) неизвестно, то для многих приложений (теоретических и практических) оказывается достаточным определить интенсивность обслуживания (или среднее время обслуживания b) и КВ _в длительности обслуживания. Если длительность обслуживания распределено по экспоненциальному закону, то достаточно задать интенсивность обслуживания (или среднее время обслуживания b). Следует отметить, что, в отличие от интервалов поступления заявок, отказ от экспоненциального характера распределения длительности их обслуживания не столь усложняет задачу аналитического исследования СМО, и многие содержательные результаты получены при произвольном характере распределения времени обслуживания.

Дисциплина обслуживания.

Дисциплиной обслуживания (ДО) называется правило, по которому выбираются на обслуживание заявки из очереди. Различают следующие ДО:

1) обслуживание в порядке поступления или дисциплина FIFO (First Input, First Output -- первым пришел, первым ушел);

2) обслуживание в обратном порядке или дисциплина LIFO (Last Input, First Output -- последним пришел, первым ушел);

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

В дальнейшем в качестве ДО будем рассматривать ДО FIFO.

Таким образом, для описания СМО необходимо задать:

1) функцию распределения A(t) интервалов поступления (общий случай) или интенсивность поступления (или средний интервал а=1/) и КВ _а интервалов поступления;

2) функцию распределения В(t) длительности обслуживания (общий случай) или интенсивность обслуживания (или среднее время обслуживания b=1/) и КВ _в времени обслуживания;

3) дисциплина обслуживания (ДО FIFO).

Следует отметить, что на практике СМО описывается, как правило, путем определения совокупности параметров {, _a} и {, }, считая, что ДО по умолчанию является дисциплина FIFO. Более того, если интервалы поступления или длительности обслуживания распределены по экспоненциальному закону, то нет необходимости задать и соответствующий КВ, т.к. в таком случае он равен 1 (_a 1 или = 1). Графическое представление СМО, для которой определены параметры, имеет вид:

СМО с неоднородной нагрузкой.

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

Для формализации СМО с неоднородной нагрузкой необходимо описать:

1) процесс поступления заявок каждого класса, т.е. необходимо задать либо функции распределений А1(t), А2(t), ..., АH(t) интервалов поступления (общий случай), либо интенсивности поступления ?1, ?2, ..., ?H (или средние интервалы поступления a1, a2, ..., аH) с КВ ?а1, ?а2, ..., ?аH интервалов поступления, где Н - количество классов заявок, поступающих в систему;

2) процесс обслуживания заявок каждого класса, т.е. необходимо задать либо функции распределения В1(t), B2(t), ..., BH(t) длительностей обслуживания (общий случай), либо интенсивности обслуживания ?1, ?2, ..., ?H (или средние времена обслуживания b1, b2, ..., bH) с КВ ?1, ?2,..., ?H длительностей обслуживания;

3) дисциплину обслуживания, в качестве которой может быть задана:

а) ДО бес приоритетная, когда между заявками разных классов нет приоритетов (приоритет ? это преимущественное право на обслуживание);

б) ДО с относительными приоритетами, когда приоритеты заявок учитываются только в моменты выбора их из очереди на обслуживание;

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

г) ДО со смешанными приоритетами, когда заявки данного класса имеют к заявкам одних классов относительный приоритет, к заявкам других - абсолютный, а к заявкам третьих - нет приоритета.

Вопросы математической формализации перечисленных ДО выходят за рамки курса "Моделирование дискретных систем".

Графическое представление СМО с неоднородной нагрузкой имеет вид

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

1)-- интенсивность объединенного потока (простейшего);

2)-- усредненное время обслуживания заявок объединенного потока, где -- доля заявок класса k в суммарном потоке ();

3) -- из этого выражения определяется КВ длительности обслуживания заявок объединенного потока.

После преобразований исходная модель примет вид:

Многоканальные СМО.

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

Для описания МК СМО задается та же совокупность параметров, что и для ОК СМО (см. раздел 1.4). Дополнительно задается только количество N обслуживающих приборов. Графическое представление МК СМО имеет вид:

Мнемоническое обозначение СМО.

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

А - описывает распределение (или задает характер закона распределения) интервалов поступления заявок;

В - описывает распределение длительностей обслуживания заявок;

N - задает количество обслуживающих приборов в СМО.

Иногда, когда СМО является системой с ограниченной емкостью накопителя (или с ограниченной очередью), приведенное обозначение расширяется до четырех букв А/В/N/К, где последняя буква (на самом деле число, как и N) К задает емкость накопителя (количество мест ожидания).

Приведенные трех или четырех буквенные обозначения называют обозначениями Кендалла. В этих обозначениях А и В могут принимать значения из следующего набора символов {M, D, E_k, H_k, G, U}. При этом:

а) А или В=M, если распределение интервалов поступления или длительностей обслуживания заявок является экспоненциальным (М - от слова Markovian - Марковский);

б) А или В=D, если интервалы поступления или длительности обслуживания являются детерминированными (D - Determinate);

в) А или В=E_k, если соответствующие распределения являются Эрланговскими порядка k (E - Erlang);

г) А или В=H_k, в случае гиперэкспоненциальных распределений порядка k (H - Hyperexponential);

д) А или В= G, в случае распределений общего (произвольного) вида (G - General - общий, общего вида);

е) А или В= U - при равномерных распределениях соответствующих случайных величин (U - Uniform distribution - равномерное распределение).

Так, например, обозначение вида:

М/М/1 означает СМО с простейшим потоком на входе и экспоненциально распределенной длительностью обслуживания заявок в приборе (один)

D/Е₂/3/5 - СМО с регулярным потоком на входе, длительностью обслуживания, распределенной по закону Эрланга 2-го порядка, тремя обслуживающими приборами и пятью местами ожидания;

М/G/2 - СМО с простейшим потоком на входе, длительностью обслуживания, распределенная по закону произвольного вида, и двумя обслуживающими приборами.

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

1.2 Характеристики функционирования СМО

Характеристики одноканальной СМО с однородной нагрузкой.

Предположим, что задана ОК СМО общего вида (типа G/G/1), для которой определены параметры нагрузки, а, именно, интенсивность и КВ _а интервалов поступления, интенсивность обслуживания и КВ длительности обслуживания:

Основными характеристиками, определяющими качество функционирования такой СМО, являются:

1) вероятности состояний системы;

2) загрузка или коэффициент использования системы;

3) время ожидания заявок в системе;

4) время пребывания в системе;

5) число заявок в очереди системы или длина очереди;

6) число заявок в системе.

Следует отметить, что все перечисленные характеристики имеют смысл только в том случае, когда система функционирует в установившемся режиме (без перегрузок), что и предполагается далее. Кроме того, последние четыре характеристики являются случайными величинами ("3" и "4" - непрерывные, "5" и "6" - дискретные) и полный анализ этих характеристик предполагает определение соответствующих функций распределения. Однако в большинстве практических приложений достаточно анализировать данные характеристики на уровне их средних значений, что и делается далее.

Остановимся на перечисленных характеристиках более подробно.

1) Вероятности состояний системы -- это наиболее полная характеристика системы в том смысле, что, зная вероятности состояний, можно определить все остальные характеристики. При этом под состоянием СМО понимается число заявок, находящихся в системе. Вероятность состояния системы, когда в ней находится k заявок, обозначим далее через Р_k, k=0, 1, 2, ...

2) Загрузка системы -- это отношение интенсивности поступления к интенсивности обслуживания и обозначается через :

=/=b=b/а,

где а=1/ и b=1/ - средние значения интервалов поступления и длительности обслуживания соответственно.

Значение загрузки определяет условие существования в системе стационарного режима. Необходимым и достаточным условием существования в стохастической СМО стационарного режима является условие, когда <1 или <. Выполнение этого условия означает, что система в среднем справляется с поступающей нагрузкой. Если 1, то система работает в режиме перегрузок.

Загрузка СМО характеризует:

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

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

в) вероятность того, что прибор занят обслуживанием заявок;

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

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

Справедливость утверждения "а" следует из определения загрузки =b: если - среднее число заявок, поступающих в единицу времени, то за время b в систему поступят в среднем b заявок.

Справедливость утверждения "б" можно показать следующими простыми рассуждениями. Рассмотрим достаточно длинный интервал t времени функционирования системы. Для простоты предположим, что в начале и в конце этого интервала система была свободна. Очевидно, что за время t в систему в среднем поступят t заявок. Каждая из этих заявок в среднем обслуживается за время b. Тогда суммарное время обслуживания всех заявок равно tb. Отсюда доля времени, в течение которого прибор занят обслуживанием заявок, равна tb/t=b=, что и следовало показать.

Утверждение "в" напрямую следует из утверждения "б", ибо рассмотренная ранее доля времени и есть вероятность занятости прибора. Тогда вероятность простоя системы равна 1-.

Справедливость утверждения "г", в свою очередь, следует из утверждения "в": в приборе может находиться 1 заявка с вероятностью и 0 заявок с вероятностью 1-. Тогда среднее число заявок в приборе равно

1· + 0·(1-)=.

3) Время ожидания -- это, как правило, случайное время, которое заявка проводит в очереди в состоянии ожидания. Среднее значение этого времени, которое представляет наибольший интерес, обозначается через .

4) Время пребывания -- это случайный промежуток времени от момента поступления заявки в систему до момента окончания ее обслуживания. Для среднего значения u времени пребывания справедливо равенство:

u=+b.

5) Среднее число заявок в очереди или средняя длина очереди

l=.

6) Среднее число заявок m, находящихся в системе, складывается из средних значений числа заявок, находящихся в очереди (l) и в приборе ():

m=l+= +b=(+b)=u

Формулы =b, l= и m=u называются формулами Литтла соответственно для прибора, очереди и системы в целом. Справедливость этих формул показывается далее в разделе 2.4.

Ранее отмечалось, что если известны вероятности состояний, то можно определить и все остальные характеристики системы. Предположим, что вероятности состояний Р_к=Pr{в системе находится k заявок}, k = 0, 1, 2, ..., известны или заданы. Тогда загрузка системы, которая характеризует вероятность того, что, прибор занят обслуживанием, определяется равенством:

,

где P₀ - вероятность простоя системы.

В системе могут находиться 1, 2, 3, ... заявок соответственно с вероятностями P₁, P₂, P₃, .... Тогда, исходя из определения математического ожидания дискретной случайной величины, среднее число заявок в системе

.

Если в системе находится k заявок, то в очереди ожидают k-1 заявка (k= 1, 2, 3, ...). Тогда средняя длина очереди

m-.

Зная среднее число заявок в системе (m) и в очереди (l), соответствующие временные характеристики можно определить по формуле Литтла:

u=m/ и =l/=u-b.

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

Характеристики одноканальной СМО с неоднородной нагрузкой.

Рассмотрим характеристики функционирования ОК СМО с неоднородной нагрузкой. Пусть в СМО поступают заявки Н классов с параметрами:

- ₁, ₂, ... , _н -- интенсивность поступления;

- _а1, _а2, ... , _ан -- КВ интервалов поступления;

- b₁, b₂, ... , b_н -- среднее время обслуживания;

- ₁, ₂, ... , _н -- КВ длительности обслуживания.

Приведенные параметры полностью описывают систему, которая является СМО типа :

Характеристики СМО в случае неоднородной нагрузки определяются как для заявок отдельных классов, так и для заявок объединенного потока, и те и другие характеристики во многом аналогичны соответствующим характеристикам системы с однородной нагрузкой.

Характеристики заявок отдельных классов.

1) Pr{n₁, n₂, ..., n_H} -- вероятности состояний СМО, где под состоянием системы здесь понимается вектор , показывающий, сколько заявок каждого класса находятся в системе.

2) _к=_кb_к -- загрузка СМО заявками класса k (k-заявок). При этом, загрузка _к имеет тот же физический смысл, что и в случае однородной нагрузки, но только применительно к классу k .

3) _k -- среднее время ожидания k-заявок.

4) u_k=_k+b_k -- среднее время пребывания в системе k-заявок.

5) l_k=_kk -- средняя длина очереди заявок класса k.

6) m_k=_ku_k =l_k+_k -- среднее число k-заявок в системе .

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

Характеристики заявок объединенного потока.

1)-- суммарная загрузка системы и СМО функционирует в стационарном режиме, если R<1. При этом =1-R -- коэффициент простоя.

2)-- среднее время ожидания заявок объединенного потока, где -- интенсивность результирующего потока.

3) -- среднее время пребывания, где -- усредненное время обслуживания.

4)-- средняя (суммарная) длина очереди.

5) -- среднее число заявок в системе.

Характеристики многоканальной СМО (однородная нагрузка).

Рассмотрим МК СМО из N обслуживающих приборов, в которую поступает поток заявок интенсивности и КВ _а интервалов поступления. Все приборы совершенно идентичны и среднее время обслуживания в одном приборе равно b, а КВ длительности обслуживания - . Определим для описанной МК СМО (типа G/G/N) характеристики функционирования.

1) Вероятности состояний. Под состоянием МК СМО как и в случае ОК СМО понимается число заявок k, находящихся в системе, и вероятность такого состояния также обозначается через P_k, k = 0, 1, 2, ...

2) Загрузка. По аналогии с ОК СМО произведение b можно было бы трактовать как загрузку МК СМО. Однако это не так и в качестве загрузки МК СМО принимается загрузка ее одного прибора, определяемая как =b/N. Это делается с тем, чтобы использовать одинаковые обозначения для загрузки, придать одинаковый смысл загрузке, "приравнять" отдельные приборы МК СМО и прибор в ОК СМО. После такого определения загрузки МК СМО для нее справедливы все утверждения, приведенные ранее относительно загрузки ОК СМО. Отношение /N= в выражении для загрузки характеризует интенсивность заявок, приходящих на один прибор МК СМО. Условием существования стационарного режима: =b<1.

3) Среднее число заявок m в МК СМО определяется так же, как и в ОК:

m=.

4) Средняя длина очереди

l=,

где k-N -- число заявок в очереди, когда в системе находится k заявок.

5) Среднее время ожидания определяется по формуле Литтла:

=l/.

6) Среднее время пребывания

u=m/=+b.

7) Вероятность ожидания или вероятность того, что все N приборов заняты обслуживанием заявок

.

8) Для МК СМО представляет интерес такая характеристика как среднее число занятых приборов, определяемая следующим равенством:

.

С другой стороны, -- это среднее число заявок, находящиеся в обслуживающих приборах, т.к., очевидно, что число занятых приборов всегда равно числу заявок в приборах. Вспомним, что загрузка =b/N -- это среднее число заявок в приборе (одном). Тогда среднее число заявок в N приборах равно N. Таким образом

=b.

Очевидно, что m=l+ (сравните с m=l+ для ОК СМО). Действительно

Вывод формулы Литтла.

Универсальная формула Литтла (справедлива для любой системы без отказов) устанавливает связь между средними значениями числа заявок, времени пребывания и интенсивности поступления. Так для СМО в целом эта связь имеет вид: m=u, вывод которой приводится ниже.

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

Очевидно, что n(t)=(t)-(t) -- число заявок в системе в момент времени t. С другой стороны, площадь между кривыми (t) и (t) (заштрихованная площадь) на интервале (0, t) есть общее (суммарное) время, проведенное всеми заявками в системе на момент времени t. Обозначим это общее время через (t).



Пусть _t -- интенсивность поступления заявок в систему на интервале (0, t). Очевидно, что _t=.

Пусть u_t -- среднее время пребывания заявок в системе на интервале (0, t). Тогда u_t =.

Пусть m_t -- среднее число заявок в системе на интервале (0, t). Тогда m_t=. Из полученных равенств имеем: .

Пусть существуют пределы =_t, u=u_t и m=m_t, что имеет место, если система имеет стационарный режим функционирования. Тогда m=l, что и требовалось показать.

Теперь если под "системой", о которой шла речь выше, понимать "очередь" или "прибор", то получим соответствующие выражения для средней длины очереди (l=) и среднего числа заявок в обслуживающем приборе (=b).

Глава 2. Авторизация поиска максимальных потоков в сетях

2.1 Описание интерфейса программы

Главное окно программы содержит:

- таблицу для вывода статистики СМО;

- поле для ввода интенсивности;

- поля для ввода g (целого числа, много больше единицы);

- кнопку “В Excel” для переноса данных в Excel;

- кнопки “Вкл”, “Выкл” для расчета данных и выхода из программы (рис.2.1).

Рис.2.1. Главное окно программы

2.2 Инструкция пользователя

Для запуска проекта программы нужно запустить файл Project1.dpr или только для выполнения расчетов запускаем файл программы Project1.exe.

Для вывода статической модели в таблицу необходимо выполнить следующие действия:

1. Выбрать интенсивность в поле “Выберите интенсивность”.

2. Ввести число g в поле “Другое” (по умолчанию 567).

3. Заполнить матрицу пропускных способностей и указать номера вершин, которые будут началом и концом сети.

4. Для выполнения расчета используется кнопка “Вкл”.

5. Для вывода результата в Excel используется кнопка “В Excel”.

6. Для выхода из программы используется кнопка “Выкл”.

2.3 Описание программного кода

Прикладная программа написана языком Object Pascal в интегрированной среде Delphi7.

Окно программы (Form1: TForm) содержит такие компоненты:

- текстовое поле (Edit1:TEdit);

- Таблицу( StringGrid1: TStringGrid);

- надписи (Label1, Label2, Label3: TLabel);

- кнопки (Button1,Button2,Button3: TButton );

- панели группы радиокнопок(RadioGroup1: TRadioGroup; GroupBox1: TGroupBox);

- радиокнопоки(RadioButton1, RadioButton2: TRadioButton);

В программе отслеживается 5 действий (табл. 1).

- procedure FormCreate(Sender: TObject);

- procedure Button1Click(Sender: TObject);

- procedure Button2Click(Sender: TObject);

- procedure Button3Click(Sender: TObject);

- procedure Edit1Change(Sender: TObject).

Алгоритм работы метода нахождения максимального потока изображен на рисунке 2.2. в виде блок-схемы.

Таблица 1. Отслеживаемые действия

Название действия	Назначение
TForm1.FormCreate	Заполняет названия колонок в таблице
TForm1.Button1Click	Выполняет расчет
TForm1.Button2Click	Позволяет выйти из программы
TForm1.Button3Click	Отсылает данные в Excel
TForm1. Edit1Change	Позволяет изменить число g

Предназначение текстовых полей приведено в таблице 2.

Таблица 2. Назначения текстовых полей

Название поля	Предназначение
Ti	момент поступления i-го требования
Vi	время ожидания
Ti`	вес ребра.
Xi	псевдослучайные числа в диапазоне (0,1), отвечающие закону равномерной плотности вероятности, с начальным значением x0
TAU	время обслуживания
Ti``	момент окончания обслуживания

2.4 Тестовый пример

Пример 1.

При интенсивности 6.

Решение. Результат работы программы приведен на рис.2.3.

Рис.2.3. Результат решения примера 1

Пример 2.

При интенсивности 12.

Рис.2.4. Результат решения примера 2

Заключение

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

Отметим преимущества и недостатки данной программы.

Преимущества:

- программа почти оптимальна в своём решении.

- программа проста в использовании.

- программа актуальна и интересна.

- программа имеет простую структуру

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

Список литературы

1. Архангельский А.Я. Приемы программирования в Delphi. Версии 5 - 7. М.: ЗАО «Издательство БИНОМ», 2003.

2. Климова Л.М. Delphi 7. Основы программирования. Решение типовых задач. Самоучитель - М.: КУДИЦ-ОБРАЗ, 2004. - 480 с.

3. Липский В. Комбинаторика для программистов: Пер. с польск. - М.: Мир, 1988. - 213 с.: ил.

4. Лифшиц А.Л. Статистическое моделирование СМО, М., 1978.

5. Советов Б.А., Яковлев С.А. Моделирование систем, М: Высшая школа, 1985.

6. Гмурман В.Е. Теория вероятностей и математическая статистика, М: Высшая школа, 2001.

7. Пригодин Н.В. Системный подход в моделировании. М., 1986.

Приложение

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, ExtCtrls, ComCtrls,comobj;

const

m1 = 6; { Интенсивность обслуживания (№ по журналу группы) }

m2 = 12; { Интенсивность (m2 = m1 * 2) }

x0 = 0.34; { Начальное значение псевдослучайных чисел }

type

TForm1 = class(TForm)

StringGrid1: TStringGrid;

Panel1: TPanel;

Label1: TLabel;

Button1: TButton;

Button2: TButton;

Button3: TButton;

Label2: TLabel;

RadioGroup1: TRadioGroup;

RadioButton1: TRadioButton;

RadioButton2: TRadioButton;

GroupBox1: TGroupBox;

Label3: TLabel;

Edit1: TEdit;

procedure Button1Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure Edit1Change(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

private

procedure PoceedTask(k : integer; s : real);

{ Private declarations }

public

{ Public declarations }

end;

var

Form1 : TForm1;

x : real; { Псевдослучайное число }

v : real; { Время ожидания }

g : longint; { Целое число, много больше единицы; }

t_post : real; { Момент поступления i-требования }

t_all : real; { Накопительная переменная }

t_st_m : real; { Момент начала обслуживания }

tau : real; { Время обслуживания }

t_end : real; { Момент окончания обслуживания }

m : integer;

implementation

{$R *.dfm}

procedure TForm1.Button2Click(Sender: TObject);

begin

Application.Terminate;

end;

procedure TForm1.Button3Click(Sender: TObject);

var Row, Col: integer;

estRange: OleVariant;

Excel: Variant;

i,j:integer;

begin

Excel := CreateOleObject('Excel.Application');

Excel.Visible := True;

Excel.WorkBooks.Add; { Создать новую таблицу }

Excel.Range['A1', 'G1'].Font.Size := 14;

Excel.Range['A1', 'G1'].Font.FontStyle := 'Bold';

Excel.Range['A1', 'G1'].Font.Name := 'Arial';

Excel.Range['A1', 'G1'].Interior.Color := RGB(195, 196, 197);

Excel.ActiveSheet.Range['A1', 'A1'].Value := '№';

Excel.ActiveSheet.Range['B1', 'B1'].Value := 'Ti';

Excel.ActiveSheet.Range['C1', 'C1'].Value := 'Vi';

Excel.ActiveSheet.Range['D1', 'D1'].Value := 'Ti`';

Excel.ActiveSheet.Range['E1', 'E1'].Value := 'Xi';

Excel.ActiveSheet.Range['F1', 'F1'].Value := 'TAU';

Excel.ActiveSheet.Range['G1', 'G1'].Value := 'Ti``';

for j:=0 to StringGrid1.ColCount do

for i:=1 to StringGrid1.RowCount do

Excel.ActiveSheet.Cells[i+1,j+1].Value := StringGrid1.Cells[j,i];

end;

procedure TForm1.Edit1Change(Sender: TObject);

begin g:=strtoint(Edit1.Text); end;

procedure TForm1.FormCreate(Sender: TObject);

begin

StringGrid1.Cells[0,0]:='№';

StringGrid1.Cells[1,0]:='Ti';

StringGrid1.Cells[2,0]:='V';

StringGrid1.Cells[3,0]:='Ti`';

StringGrid1.Cells[4,0]:='Xi';

StringGrid1.Cells[5,0]:='tau';

StringGrid1.Cells[6,0]:='Ti``';

Edit1.Text:='567';

g:=strtoint(Edit1.Text);

end;

procedure TForm1.PoceedTask(k : integer; s : real);

begin

if t_end < s then

begin

t_st_m := s; { Момент начала обслуживания }

v := 0; { Задержка }

end else begin

t_st_m := t_end; { Момент начала обслуживания }

v := t_st_m - s; { Задержка }

end;

x := g*x - int(g*x); { Получение значения псевдочисла }

tau := ((-1)/m)*ln(1-x); {Вычисление времени обслуживания }

StringGrid1.RowCount:=StringGrid1.RowCount+1;

StringGrid1.Cells[0,k]:=inttostr(k);

StringGrid1.Cells[1,k]:=FormatFloat('0.00',t_post);

StringGrid1.Cells[2,k]:=FormatFloat('0.00',v);

StringGrid1.Cells[3,k]:=FormatFloat('0.00',t_st_m);

StringGrid1.Cells[4,k]:=FormatFloat('0.00',x);

StringGrid1.Cells[5,k]:=FormatFloat('0.00',tau);

StringGrid1.Cells[6,k]:=FormatFloat('0.00',t_end);

t_end := t_st_m + tau; {Вычисление момента окончания }

end;

{ Обслуживание потока требований }

procedure TForm1.Button1Click(Sender: TObject);

var k:integer;

begin

if RadioButton1.Checked=true then

m:=m1;

if RadioButton2.Checked=true then

m:=m2;

//randomize;

x := g*x0 - int(g*x0); { Получение значения псевдочисла }

v := 0; { Задаём начальное время ожидания }

t_post := 0; { Задаём начальное время поступления требования }

t_st_m := t_post; { Задаём момент начала обслуживания }

tau := ((-1)/m)*ln(1-x); {Вычисление времени обслуживания }

t_end := t_st_m + tau; {Вычисление момента окончания }

StringGrid1.Cells[0,1]:='1';

StringGrid1.Cells[1,1]:='0';

StringGrid1.Cells[2,1]:='0';

StringGrid1.Cells[3,1]:='0';

StringGrid1.Cells[4,1]:=FormatFloat('0.00',x);

StringGrid1.Cells[5,1]:=FormatFloat('0.00',tau);

StringGrid1.Cells[6,1]:=FormatFloat('0.00',t_end);

t_post := t_post + 0.07;

{ Вызов функции обслуживания требования}

for k:=2 to 10 do

begin

PoceedTask(k,t_post);

t_post := t_post + 0.07;

end;

end;

end.

Размещено на Allbest.ru

...