Исследование систем массового обслуживания с групповым поступлением требований и управлением входящим потоком

Содержание Введение

1. Управляемые марковские процессы с дисконтированием

1.1 Уравнение оптимальности

1.2 Метод итераций по критерию

1.3 Метод итераций по стратегиям

2. Описание системы массового обслуживания с групповым поступлением требований

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

2.2 Управляемый марковский процесс, описывающий функционирование системы

2.3 Структура и свойства оптимальной стратегии управления входящим потоком

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

3.1 Блок-схема алгоритма

3.2 Описание блоков алгоритма

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

4.1 Список идентификаторов

4.2 Описание и назначение функций

4.3 Числовой пример

5. Результаты исследования систем массового обслуживания с групповым поступлением требований и управлением входящим потоком Заключение Список использованных источников Приложение

Введение

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

Выпускная квалификационная работа состоит из пяти разделов.

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

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

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

В четвёртом разделе описывается программа на ЭВМ, реализующая алгоритм метода анализа рассматриваемых систем обслуживания, выполненная на языке C++ в среде разработки Microsoft VisualStudio 2010. Приводится подробное описание интерфейса программы, ее функций и принципов функционирования. Рассматривается числовой пример.

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

1. Управляемые марковские процессы с дисконтированием

1.1 Уравнение оптимальности Целью анализа управляемых марковских процессов с дисконтированием является нахождение

(1.1)

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

Теорема 1.1. Функция v является решением уравнения

(1.2)

т.е. v является неподвижной точкой оператора T.

Теорема 1.2. Уравнение (1.2) имеет единственное решение .

Доказательство. Пусть будут векторами управления, соответствующими решениям уравнения (1.2). Тогда Так как, то, применив (1.3) s раз, получим

(1.4)

Правая часть (1.4) стремится к 0 при, так как. Следовательно,

(1.5)

Аналогично можно получить обратное к (1.5) неравенство.

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

Доказательство. Пусть ф будет любой стратегией из множества Р. Тогда. Также имеем

(1.6)

Первое равенство получили из (1.20). Таким образом,

(1.7)

Применив (1.7) s раз, получим

(1.8)

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

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

Теорема 1.4. Если положить, то где е — единичная функция, т. е.. Функция v является оптимальным полным ожидаемым доходом с дисконтированием, и стратегия р является оптимальной для управляемого марковского процесса с бесконечным временем, а функция является оптимальным полным ожидаемым доходом с дисконтированием за n шагов.

Доказательство. Имеем Тогда

(1.9)

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

(1.10)

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

Рассмотрим некоторые свойства оператора Т. Пусть для функций

Аналогичные определения введём для операций. Норму определим следующим образом:

Теорема 1.5. Если, то Теорема 1.6. Если, то Теорема 1.7.

Теорема 1.8. Пусть Тогда Далее рассмотрим два метода решения уравнения (1.2), а именно, метод итераций по критерию и метод итераций по стратегиям. В методе итераций по стратегиям число итераций ограничено числом стратегий, т. е., где обозначает мощность множества .

1.2 Метод итераций по критерию Рассмотрим уравнения для управляемого марковского процесса с конечным временем при (произвольная функция)

(1.11)

Обозначим через v единственное решение уравнения (1.2). Пусть

(1.12)

(1.13)

Теорема 1.9.

(1.14)

Доказательство.

(1.15)

Здесь — вектор управления, полученный при решении уравнения (1.15). Если соответствует n оставшимся шагам, то .

Тогда

(1.16)

Правая часть неравенства (1.14) верна для, так как Предполагаем, что правая часть неравенства (1.14) верна для всех. Тогда, используя (1.16) и теорему 1.5 при u, заменённой на, и, заменённой на, получаем Для левой части неравенства (1.14) имеем и доказательство проводим по аналогии с доказательством правой части.

Из неравенства (1.14) вытекает следующая теорема о сходимости.

Теорема 1.10. Последовательность при сходится по норме к v.

Доказательство. Рассмотрим неравенство (1.14). Если, то теорема доказана. Предположим, что. Положим Если, то утверждение теоремы очевидно.

Пусть, и Тогда, если, то Так как значение — произвольное, то стремится к 0 при .

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

Теорема 1.11. Пусть и функция удовлетворяет неравенству. Тогда последовательность является неубывающей.

Доказательство.

Тогда

(1.17)

Также Предполагаем, что

(1.18)

Тогда из (1.17), используя (1.18) и теорему 1.5, получаем

(1.19)

В случае если неравенство выполняется.

Неравенство (1.14) задаёт априорные ограничения для решения v, т. е. известные до выполнения вычислений. Но нужно иметь возможность оценить решение на любой стадии вычислений, т. е. получить апостериорные ограничения.

Пусть

(1.20)

Теорема 1.12.

(1.21)

Доказательство.

Тогда Таким образом, где — единичная матрица. Это даёт правую часть неравенства (1.21). Левая часть неравенства доказывается аналогично.

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

Теорема 1.13.

(1.22)

Доказательство. Правая часть неравенства (1.22) очевидна, так как v является оптимальным решением. Имеем Следовательно, Таким образом, Теорема 1.14.

Доказательство следует из теорем 1.12 и 1.13.

Теоремы 1.12, 1.13 и 1.14 представляют апостериорные ограничения для решения v в том смысле, что оценка решения выполняется на текущей итерации на основе найденных и .

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

Теорема 1.15. Пусть вектор удовлетворяет равенству Тогда существует число такое, что для стратегия является оптимальной для управляемого марковского процесса с бесконечным временем, т. е. .

1.3 Метод итераций по стратегиям Метод итераций по стратегиям состоит в следующем [1]:

Шаг 1. Выбираем начальную стратегию .

Шаг 2. Решаем уравнение

(1.23)

Шаг 3. Находим новую стратегию ,

(1.24)

Шаг 4. Заменяем и повторяем шаги алгоритма.

Данный алгоритм порождает последовательности. Алгоритм завершается, когда на шаге 3

(1.25)

или, иначе, когда

(1.26)

Условия завершения алгоритма (1.25) и (1.26) являются эквивалентными.

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

Доказательство.

Следовательно, где. (1.27)

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

(1.28)

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

Если для завершения алгоритма используем условие (1.26), то. Тогда, и условие (1.25) также может использоваться для завершения алгоритма.

Если для завершения алгоритма используем условие (1.25), то опять, и условие (1.26) также может использоваться для завершения алгоритма. Таким образом, условия завершения алгоритма (1.25) и (1.26) являются эквивалентными, т .е.

Следовательно, завершим алгоритм при некотором n, когда т. е.

(1.29)

Из теоремы 1.2 и равенства (1.29) получаем, что. Очевидно, что является оптимальной стратегией.

2. Описание системы массового обслуживания с групповым поступлением требований

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

(2.1)

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

В систему поступает группа с вероятностью .

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

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

2.2 Управляемый марковский процесс, описывающий функционирование системы Построим управляемый марковский процесс с дискретным временем, описывающий функционирование (работу) системы, в которой используется стратегия частичного приёма требований с целью максимизации полного ожидаемого дохода с дисконтированием при конечном времени (- коэффициент дисконтирования). Пусть состояние системы — число требований в системе. Дисконтирование интерпретируется следующим образом: система прекращает работу через экспоненциально распределённое с параметром время. Поступления требований наблюдаются в соответствии с пуассоновским потоком с интенсивностью. Тогда максимальная возможная интенсивность выхода из любого состояния равна

. (2.2)

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

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

(2.3)

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

(2.4)

(2.5)

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

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

(2.6)

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

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

Лемма 2.1. Для всех и для всех

(2.7)

при условии, что неравенства справедливы для .

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

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

(2.8)

по определению стратегии, которой следует система В, по гипотезе индукции и вследствие униформизации.

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

Следствие 1: класс 1 является предпочтительным.

С групповыми поступлениями можно допускать приём в систему нескольких требований в один и тот же момент времени. Тогда значение ожидаемых расходов «дополнительного» требования не известно, так как соответствующее связанное состояние не фиксировано. Однако, расходы всех классов требований в определённом состоянии являются одинаковыми из-за одинаковых интенсивностей обслуживания, что позволяет выбрать последовательное поступление требований: всякий раз, когда оба требования класса и класса являются допустимыми при, т. е., требования класса поступают перед требованиями класса. Следовательно, существует индекс в каждом состоянии, определяемый как

(2.9)

такой, что для всех, для всех и

. Будем использовать это замечание в последующих результатах.

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

Лемма 2.2. Для всех имеем

(2.10)

при условии, что неравенство справедливо для .

Доказательство. Утверждение справедливо для при для всех Предположим, что оно также справедливо для некоторого. Перепишем неравенство (2.4) и используем лемму 3.1:

(2.11)

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

(2.12)

Последнее неравенство может быть переписано в виде:

(2.13)

Теперь можно повторно применить это неравенство, чтобы получить неравенство

(2.14)

которое справедливо для всех и для всех .

Теперь покажем, что функции также удовлетворяют неравенству (2.10). Пусть системы соответствуют системам в состояниях соответственно и на шаге. Пусть и являются оптимальными состояниями, в которые переходят системы A и D соответственно, так что и, где и .

Заметим, что и являются наибольшими индексами классов требований, которые имеют требования, принимаемые в системы, А и D соответственно. Также полагаем

(2.15)

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

Случай 1:. В этом случае система D отказывает двум требованиям, которые система, А принимает, таким образом,. Пусть и будут классами этих двух требований, так что при. Теперь полагаем, системы В и С допускают все требования, которые допускает система А, кроме требований класса и соответственно, так что обе системы переходят в состояние :

(2.16)

где неравенство следует из оптимальности .

Случай 2:. Теперь полагаем, что система В повторяет решения системы А, так что она принимает те же самые требования, что и система А, переходя в состояние, тогда как система С принимает те же самые требования, что и система D, переходя в состояние. Заметим, что оба состояния и допустимые, так как. Следовательно,

(2.17)

где первое неравенство следует из описания стратегий, которым следуют системы A-D.

Теперь можем рассмотреть. Устанавливаем соответствие (связываем) каждого из дополнительных требований в системах В и С с одним из дополнительных требований в системе D, т. е. если дополнительное требование в системе В или С уходит, что происходит с вероятностью, то также уходит одно из дополнительных требований в системе D. Следовательно,

(2.18)

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

Леммы 2.1 и 2.2 вместе описывают оптимальную пороговую стратегию с монотонными пороговыми значениями.

Теорема 2.1. Оптимальная стратегия для рассматриваемой системы может быть описана следующим образом: для всех

1. и

2. Для всех существуют числа такие, что

(2.19)

где для любого вещественного числа. Кроме того, .

Доказательство. Первое утверждение следует непосредственно из следствия 1 леммы 2.1. Заметим, что и для того, чтобы были допустимыми.

Докажем второе утверждение теоремы. Сначала определим числа следующим образом:

(2.20)

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

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

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

В обоих случаях

как утверждается в теореме.

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

по определению, вследствие упорядоченности классов и леммы 2.2, откуда следует, что .

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

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

.

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

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

— максимальный полный ожидаемый дисконтируемый мгновенный доход системы на шаге ;

— максимальный полный ожидаемый дисконтируемый доход системы на шаге ;

— количество элементов множества управлений;

— количество рассматриваемых шагов;

— количество элементов множества мгновенных состояний.

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

. (3.1)

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

Далее под оптимальным доходом будем понимать доход, получаемый при оптимальном управлении.

Рисунок 1 — Блок-схема алгоритма

3.2 Описание блоков алгоритма Блок 1. Задание исходных параметров.

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

— количество приборов;

— количество классов требований;

— максимальное число поступающих требований каждого класса;

— количество рассматриваемых шагов алгоритма (время функционирования системы);

— доходы от требований каждого класса;

— интенсивность поступления групп требований;

— интенсивность обслуживания каждого прибора;

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

(3.2)

Если вектор не задан, полагается, что все вероятности

(3.3)

(3.4)

Блок 2. Формирование множества управлений.

Множество управлений имеет вид:

(3.5)

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

Блок 3. Формирование множества мгновенных состояний.

Множество мгновенных состояний имеет вид:

(3.6)

где характеризует количество требований в системе.

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

Блок 4. Нахождение оптимального дохода и оптимального управления.

Номер состояния .

— индекс для обозначения номера текущего мгновенного состояния.

Номер шага .

— индекс для обозначения номера текущего шага. Полагаем, что .

Номер управления .

— индекс для обозначения номера выбранного на данный момент управления.

Вычисление .

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

.

Если полученное на этом шаге значение больше, переходим к действию 4.6. Иначе переходим к действию 4.7.

Сохранение оптимального дохода и оптимального управления.

Сохраняем значение и соответствующее ему оптимальное управление .

Вычисление .

Перед началом выполнения алгоритма полагаем, что .

Вычисляем по формуле:

(3.8)

где вектор. Полагаем,

.

.

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

.

Увеличиваем значение индекса на единицу и переходим к действию 4.4.

.

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

.

Увеличиваем значение индекса на единицу и переходим к действию 4.3.

.

Если, то переходим к действию 4.13. Иначе переходим к блоку 5.

s.

Увеличиваем значение индекса на единицу и переходим к действию 4.2.

Блок 5. Вывод результатов.

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

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

Программная реализация алгоритмов выполнена на языке программирования C++ в среде разработки Microsoft Visual Studio 2010. Разработанная программа предназначена для моделирования и анализа систем массового обслуживания с групповым поступлением требований и управлением входящим потоком. Программа выполняет следующие функции:

· Генерация пространства векторов управлений;

· Генерация пространства состояний СМО с групповым поступлением требований;

· Вычисление максимального полного ожидаемого дохода для каждого состояния;

· Нахождение оптимального управления для каждого состояния;

· Сохранение результатов в файл.

Программа имеет консольный вид. Интерфейс программы представлен на рисунке 2.

Рисунок 2 — Интерфейс программы Параметры системы вводятся в текстовый файл «input.txt», который должен находиться в той же папке, что и файл программы «optimum_drive.exe». Формат вводимых данных должен соответствовать пояснению, появляющемуся на экране в начале работы программы (см. рисунок 2).

Пользователь должен ввести число 1, 2 или 3 для выбора варианта вывода данных. Программа не продолжит работу, пока не будет введён корректный ответ на запрос. В противном случае экран обновится, некорректный ответ на запрос будет удалён, и снова будет предложен выбор варианта вывода данных. Результаты работы программы записываются в текстовый файл «output.txt», который так же находится в той же папке, что и файл программы.

4.1 Список идентификаторов В таблице 1 приводится список идентификаторов, используемых в программе.

Таблица 1 — Список идентификаторов

4.2 Описание и назначение функций В программе «optimum_drive» используются следующие функции:

Функция int getPM (vector tJX).

Назначение: преобразование вектора однозначных чисел в одно многозначное число.

Входные данные: .

Выходные данные: .

Функция void managment_generation ().

Назначение: генерация пространства всевозможных управлений.

Функция void condition_generation ().

Назначение: генерация пространства всевозможных мгновенных состояний.

Функция vector mult (vector a_temp, vector b_temp).

Назначение: покомпонентное умножение вектора на вектор .

Входные данные: — векторы одинаковой размерности.

Выходные данные: вектор .

Функция void write (char I, int n).

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

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

Функция void main ().

Назначение: исполнительная функция. Состоит из нескольких основных блоков:

· Считывание данных из файла;

· Вызов функции management_generation ();

· Вызов функции condition_generation ();

· Итерации по состояниям и по управлениям, вычисление мгновенных доходов;

· Нахождение максимального полного ожидаемого дохода и оптимального управления;

· Вывод результатов на экран и/или в файл.

Перед началом работы программы в файле «input.txt» должны быть корректно указаны входные данные по указанному выше шаблону. В начале работы программы осуществляется вывод вспомогательной информации на экран с предложением выбора варианта вывода результатов. После этого выбора при помощи стандартной функции осуществляется считыванием данных из файла.

Далее происходит генерация всевозможных управлений и состояний, представленных в виде двух двумерных массивов. Это осуществляется при помощи функций managment_generation () и condition_generation () соответственно.

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

Если i-ый элемент текущего управления превосходит количество требований i-го класса, то данное управление пропускается.

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

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

По окончанию вычислений функцией write () осуществляется вывод данных на экран и/или в файл, в зависимости от выбора.

4.3 Числовой пример Рассмотрим функционирование программы на конкретном числовом примере. Пусть

(4.1)

В начале матрицы мгновенных доходов, оптимальных управлений и полных ожидаемых доходов — нулевые. Обозначим Начинаем итерацию по шагам работы системы. Описание приведено в таблице 2.

Таблица 2 — Пошаговое описание работы программы для числового примера

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

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

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

— количество приборов;

— количество классов требований;

— максимальное число поступающих требований каждого класса;

— количество рассматриваемых шагов алгоритма (время функционирования системы);

— доходы от требований каждого класса;

— интенсивность поступления групп требований;

— интенсивность обслуживания каждого прибора;

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

Пример 1.

Параметры системы:

, ,, , ,

.

На 30-м шаге значения оптимальных доходов совпадают со значениями на 29-м шаге с точностью до и на 21-м и 20-м с точностью до (см. приложение B).

Пример 2.

Параметры системы:

, ,, , ,

.

На 14-м шаге значения оптимальных доходов совпадают со значениями на 13-м шаге с точностью до и на 11-м и 10-м с точностью до (см. приложение C).

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

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

Пример 3.

Параметры системы:

, ,, , ,

.

На втором шаге итерации получаем:

На третьем:

Из полученных результатов можно сделать вывод о том, что выполняется неравенство 2.7 из леммы 2.1.

Проанализировав оптимальные управления, убедимся, что они удовлетворяют описанию оптимальной стратегии управления в теореме 2.1 (см. приложение C):

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

Таблица 3 — Оптимальные управления при различных

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

Заключение

В выпускной квалификационной работе рассмотрен метод анализа систем массового обслуживания с групповым поступлением требований и управлением входящим потоком. Данный метод позволяет найти максимальный полный ожидаемый дисконтируемый доход системы для каждого мгновенного состояния и соответствующие оптимальные стратегии управления. Разработан алгоритм этого метода анализа, для чего построена блок-схема, представляющая структуру алгоритма, и выполнены подробные описания блоков алгоритма. Алгоритм реализован в виде программы на ЭВМ на языке C++ в среде разработки Microsoft VisualStudio 2010.

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

Список использованных источников

1 Вагнер Г. Основы исследования операций / Г. Вагнер; пер. М.: Мир, 1973. 594 с.

2 Коршунов Ю. М. Математические основы кибернетики / Ю. М. Коршунов; М.: Наука, 1972. 376 с.

3 Майн, Х. Марковские процессы принятия решений / Х. Майн, С. Осаки; пер. М.: Наука, 1977. 176 с.

4 Рогачко Е. С. Управляемые марковские процессы и их приложения в системном анализе: Учебное пособие / Е. С. Рогачко; под ред. Ю. И. Митрофанова. Саратов: Научная книга, 2008. 108 с.

5 Ховард Р. А. Динамическое программирование и марковские процессы / Р. А. Ховард; пер. М.: Сов. радио, 1964. 189 с.

6 Цrmeci E.L. Admission control with batch arrivals / E.L. Цrmeci, A. Burnetas // Operation Research. 2004. Vol. 32. P. 448−454.

Приложение A

Текст программы

#include

#include

#include

#include

#include

#include

using namespace std;

int c, //количество приборов

x, //состояние системы

K, //количество классов требований

M; //максимальное число требований i-го класса

vector r; //доходы от каждого класса требований

double lambda, mu; //интесивности поступления и обслуживания

vector> a; //все возможные управления

int a_size; //количество всевозможных управлений

vector> condition; //всевозможные состояния

int con_size; //количество всевозможных состояний

vector p; //вероятности поступления групп требований

ofstream of («output.txt»);

#define va V[getPM (condition[x])]. a

#define vv V[getPM (condition[x])]. v

#define xx condition[x][0]

class Profit_and_Managment { //доход и управление;

public:

double v; //мгновенный доход

vector a; //оптимальное управление

};

vector V; //таблица макс. полных ожидаемых доходов.

vector U; //полные доходы

int getPM (vector tJX) {

int index = 0;

for (int i = tJX. size ()-1; i>=1; i—) {

index += tJX[i]*pow (10, double (tJX.size ()-1-i));

}

index += tJX[0]*pow (10, double (tJX.size ()-1));

return index;

}

void managment_generation () {

//vector ci = vector (K); //вспомогательный вектор

int a_temp = 0;

int ai = 0;

int aj = K-1;

while (true) {

if (aj == K-1) {

a[ai][aj] = a_temp;

a_temp++;

if (a_temp > M)

a_temp = 0;

ai++;

if (ai>=a_size) {

ai = 0;

aj—;

if (aj < 0)

break;

a_temp = 0;

}

continue;

}

a[ai][aj] = a_temp;

ai++;

if (ai>=a_size) {

ai = 0;

aj—;

if (aj < 0)

break;

a_temp = 0;

continue;

}

bool check = true;

for (int j = aj; j

if (a[ai][j] ≠ 0)

check = false;

if (check) {

if (a_temp > M)

a_temp = 0;

}

}

}

void condition_generation () {

K++;

int c_temp = 0;

int ci = 0;

int cj = K-1;

while (true) {

if (cj == K-1) {

condition[ci][cj] = c_temp;

c_temp++;

if (c_temp > M)

c_temp = 0;

ci++;

if (ci>=con_size) {

ci = 0;

cj—;

if (cj < 0)

break;

c_temp = 0;

}

continue;

}

condition[ci][cj] = c_temp;

ci++;

if (ci>=con_size) {

ci = 0;

cj—;

if (cj < 1)

break;

c_temp = 0;

continue;

}

bool check = true;

for (int j = cj; j

if (condition[ci][j] ≠ 0)

check = false;

if (check) {

c_temp++;

if (c_temp > M)

c_temp = 0;

}

}

K—;

ci = 0;

while (true) {

for (int j=0; j<(int)pow ((double)M+1, K); j++) {

condition[(ci* (int)pow ((double)M+1, K))+j][0] = ci;

}

ci ++;

if (ci>=c)

break;

}

}

int summ (vector vec) //суммирование вектора

{

int s = 0;

for (int i=0; i

s += vec[i];

return s;

}

double summ (vector vec) //суммирование вектора

{

double s = 0;

for (int i=0; i

s += vec[i];

return s;

}

vector mult (vector a_temp, vector b_temp) {//умножение

vector m = vector (a_temp.size ());

for (int i=0; i

m[i] = (double)a_temp[i]*b_temp[i];

return m;

}

void write (char I, int n) {

if (I=='1') {

cout<<" nШаг «<<

cout<<" Состояние|Доход |Управление" <

cout<<" ==============================="<

for (int x=0; x

cout<

for (int i=0; i

cout<

}

cout<<" | «<<<» | «;

for (int i=0; i

cout<<<" «;

}

cout<

}

}

if (I=='2') {

of<<" nШаг «<<

of<<" Состояние|Доход |Управление" <

of<<" ==============================="<

for (int x=0; x

of<

for (int i=0; i

of<

}

of<<" | «<<<» | «;

for (int i=0; i

of<<<" «;

}

of<

}

}

if (I=='3') {

write ('1', n);

write ('2', n);

}

}

void main () {

setlocale (LC_ALL, «Russian»);

int N; //количество шагов в алгоритме

ifstream input_data («input.txt»);

/*Формат:

cKMlambda mu N;

r; (vector)

p; (vector)

*/

char change_out = 0;

while (true) {

system («cls»);

change_out = 0;

cout<<" Файл входных данных «input.txt» должен иметь следующий формат:" <

cout<<" nсKMlambdamuNn" ;

cout<<" rn" ;

cout<<" pn" ;

cout<<" nГдеn" ;

cout<<" c — количество приборов в системеn" ;

cout<<" K — количество классов требованийn" ;

cout<<" M — максимальное число требований каждого классаn" ;

cout<<" lambda — интенсивность входящего потока требованийn" ;

cout<<" mu — интенсивность обслуживания требованийn" ;

cout<<" N — количество шагов работы системыn" ;

cout<<" r — вектор доходов каждого классаn" ;

cout<<" p — вектор вероятностей поступления групп требованийnn" ;

cout<<" Выберите вариант вывода данных: n" ;

cout<<" 1 — на экранn" ;

cout<<" 2 — в текстовый файлn" ;

cout<<" 3 — на экран и в файлn" ;

cin>>change_out;

if (change_out=='1'||change_out=='2'||change_out=='3') {

break;

}

}

input_data>>c>>K>>M>>lambda>>mu>>N;

for (int i=0; i

double ri;

input_data>>ri;

r.push_back (ri);

}

for (int i=0; i<(int)pow ((double)M+1, K); i++) {

double pj;

input_data>>pj;

p.push_back (pj);

}

int Vsize = 0;

for (int i = K; i>=0; i—) {

Vsize += M*pow (10, double (K-i));

}

Vsize += c*pow (10, double (K+1));

V = vector (Vsize+1);

U = vector (c+1);

//Генерация всевозможных управлений

a_size = (int)pow ((double)M+1, K);

a = vector> (a_size);

for (int i=0; i

a[i] = vector (K);

managment_generation ();

//Генерация всевозможных состояний

con_size = c*pow (double (M+1), double (K));

condition = vector> (con_size);

for (int i=0; i

condition[i] = vector (K+1);

condition_generation ();