Элементы математического моделирования использовались с самого начала появления точных наук, и не случайно, что некоторые методы вычислений носят имена таких корифеев науки, как Ньютон и Эйлер, а слово «алгоритм» происходит от имени средневекового арабского ученого Аль-Хорезми. Второе «рождение» этой методологии пришлось на конец 40-х—начало 50-х годов XX века и было обусловлено по крайней мере двумя причинами. Первая из них — появление ЭВМ (компьютеров), хотя и скромных по нынешним меркам, но тем не менее избавивших ученых от огромной по объему рутинной вычислительной работы. Вторая — беспрецедентный социальный заказ — выполнение национальных программ СССР и США по созданию ракетно-ядерного щита, которые не могли быть реализованы традиционными методами. Математическое моделирование справилось с этой задачей: ядерные взрывы и полеты ракет и спутников были предварительно «осуществлены» в недрах ЭВМ с помощью математических моделей и лишь затем претворены на практике. Этот успех во многом определил дальнейшие достижения методологии, без применения которой в развитых странах ни один крупномасштабный технологический, экологический или экономический проект теперь всерьез не рассматривается, причем сказанное справедливо и по отношению к некоторым социально-политическим проектам.
Говоря о России, можно вспомнить, что наука математического моделирования развивается с конца 1950;х — начала 1960;х гг[77].
Невозможно представить себе современную науку без широкого применения математического моделирования. Сущность этой методологии состоит в замене исходного объекта его «образом» — математической моделью — и дальнейшем изучении модели с помощью реализуемых на компьютерах вычислительно-логических алгоритмов. Этот «третий метод» познания, конструирования, проектирования сочетает в себе многие достоинства как теории, так и эксперимента. Работа не с самим объектом (явлением, процессом), а с его моделью дает возможность безболезненно, относительно быстро и без существенных затрат исследовать его свойства и поведение в любых мыслимых ситуациях (преимущества теории). В то же время вычислительные (компьютерные, симуляционные, имитационные) эксперименты с моделями объектов позволяют, опираясь на мощь современных вычислительных методов и технических инструментов информатики, подробно и глубоко изучать объекты в достаточной полноте, недоступной чисто теоретическим подходам (преимущества эксперимента).
Неудивительно, что методология математического моделирования бурно развивается, охватывая все новые сферы — от разработки технических систем и управления ими [19, 39, 55, 80, 82] до анализа сложнейших экономических и социальных процессов [4, 5, 9, 22, 31, 36, 49, 50, 60, 69, 95, 96].
Развитие науки и техники, усложнение экономики и общественного строя — все это непрерывные и необратимые процессы, приводящие к необходимости иметь дело с все более сложными и масштабными системами, в которых в свою очередь возникают многочисленные задачи, отражающие специфику этих систем и цели их исследования. Но, не смотря на многообразие индивидуальных особенностей, можно выделить задачи, общие для широкого круга систем, и притом, вне зависимости от их предметной направленности.
В частности, во многих аспектах человеческой деятельности, в большинстве создаваемых человеком систем, имеет место спрос на выполнение тех или иных операций. При этом запросы, в общем случае, возникают в случайные моменты времени, и продолжительность выполнения требуемой операции также достоверно не известна заранее. Следовательно, необходимо создание моделей систем, учитывающих случайный характер поступления требований и их обслуживания. Задачи построения и анализа таких моделей решает наука, известная в русскоязычной литературе как теория массового обслуживания, а в иностранной как теория очередей.
Теория массового обслуживания зародилась сравнительно недавно, в начале XX века. Работа А. К. Эрланга в копенгагенской телефонной компании натолкнула его на мысль рассчитать необходимое количество телефонных линий, чтобы клиентам не приходилось проводить много времени в ожидании свободного канала. Так в 1909 году была опубликована первая статья по теории массового обслуживания «Теория вероятностей и телефонные разговоры» [103]. Им были рассмотрены системы с пуассоновским входящим потоком, очередью и одним, двумя, тремя или неограниченным числом каналов в случае экспоненциального времени обслуживания, а также системы с потерями. С тех пор поле возможных приложений теории массового обслуживания существенно расширилось [7, 57, 71]. Стремительное развитие науки, техники, экономики, средств связи и транспорта привело к необходимости создания все более сложных математических моделей, а также развития методов их исследования [88, 110]. В связи с этим особый интерес вызывают системы массового обслуживания с большим числом каналов обслуживания (многолинейные), а также сети [8]. Например, при организации промышленного производства значительный экономический резонанс имеет нехватка станков и нахождение их достаточного для бесперебойной работы количества [103, 109, 112]. На крупных промышленных предприятиях, где установлен поточный характер производства, для вычисления времени простоя линии [83], длины очереди перед той или иной фазой производства [107], успешно применяются многофазные системы массового обслуживания [106].
В сфере торговли и общественного питания также возникают задачи, требующие исследования многофазных систем [108], например, с входящим потоком заявок, интенсивность которого зависит от состояния системы[105]. Свое применение многофазные и многолинейные СМО нашли и при анализе работы крупного морского порта [115], и при моделировании распределенных вычислительных систем [16, 38, 64, 72, 85, 99], и при расчетах показателей нагрузки линии связи [23, 33, 70, 114].
В последние годы появляется все больше работ, посвященных исследованию многолинейных систем массового обслуживания. Это работы Бочарова [13, 14], Башарина [8], Печинкина [37, 73, 74, 75, 76], Чаплыгина [37, 73, 74, 75, 76], Клименок [15, 43, 45, 46, 47], Дудина [15, 33], Ивницкого [40], Назарова[1, 24, 66, 67]. Очевидно, что исследуемые СМО все более усложняются, на вход поступают неординарные или групповые потоки заявок, потоки отрицательных заявок, уничтожающие одну или несколько положительных заявок входящего потока. В работах [45, 46] рассматриваются системы, у которых, наряду с большим количеством линий, на одной из фаз реализуется процедура повторного обращения к прибору.
К сожалению, для анализа столь сложных систем редко удается применить аналитические методы. Основные методы исследования классических СМО приведены во многих монографиях по теории массового обслуживания [12, 17, 27, 28, 41, 42, 44, 59, 66, 81, 89, 100, 101]. Некоторые из них применимы и для анализа многолинейных систем, например, метод дополнительной переменной, метод вложенных цепей Маркова, методы характеристической и производящей функций, преобразования Фурье и Лапласа-Стилтьеса, метод дополнительных событий. С помощью этих и других методов удается найти стационарное распределение состояний исследуемой системы и основные характеристики ее производительности. При увеличении количества фаз и линий обслуживания, при усложнении структуры системы, на помощь аналитическим методам приходят метод асимптотического анализа [2, 11, 10, 65] и численные методы (метод Монте-Карло, матричные и суперматричные алгоритмы). Для анализа показателей очень сложных и не поддающихся аналитическому исследованию систем применяют аппарат имитационного моделирования [18, 19,21,32, 39, 48, 55,58, 86, 97, 102, 111].
Особый интерес вызывает возникающая в некоторых прикладных задачах необходимость повторного обслуживания заявок. Попытки реализовать такую возможность в многолинейных и многофазных системах до сих пор сводились или к добавлению источника повторных вызовов на одной из фаз [45, 46], или к исследованию систем с повторным обслуживанием на приборах, но лишь в случае экспоненциального времени обслуживания [62, 63].
На основании вышесказанного можно сделать вывод о необходимости и актуальности проведения дальнейших исследований многолинейных и многофазных систем все более сложной структуры, а также развития новых методов их исследования.
В настоящее время внимание к теории массового обслуживания в значительной степени стимулировалось необходимостью применения результатов этой теории к важным практическим задачам, возникающим в связи с бурным развитием систем коммуникаций, возникновением информационно-вычислительных систем, появлением и усложнением разнообразных технологических систем, созданием автоматизированных систем управления.
Поэтому возникает необходимость в разработке новых математических моделей систем массового обслуживания, а именно, систем с вариантами обслуживания заявок неординарных входящих потоков, в том числе систем с двумя и более блоками обслуживания.
Исследованию однолинейных систем массового обслуживания с неординарными входящим потоком (пуассоновским и рекуррентным) посвящены работы Бочарова П. П., Печинкина A.B., Чаплыгина В. В. и других российских ученых [34, 35, 84, 91, 113]. В работах Ч. Д’Апиче, Р. Манзо [3, 13] рассматриваются системы массового обслуживания с марковским неординарным входящим потоком, несколькими типами заявок, обобщенной дисциплиной преимущественного разделения прибора, марковским обслуживанием и накопителем бесконечной емкости. Но, как правило, все заявки в группе являлись однотипными, и время их обслуживания было одинаково распределенным, что не всегда применимо для описания реальных вычислительных процессов. Исследование подобных систем с двумерным пуассоновским потоком приводится в статье украинских ученых [94], но предлагаемый авторами метод довольно сложен и неприменим для исследования аналогичных систем с произвольным временем обслуживания или не пуассоновским входящим потоком.
В связи с возникающей во многих практических задачах возможностью частичной циркуляции заявок в системе, в настоящее время необходимо построение математических моделей, учитывающих возможность повторного обслуживания на приборах. Рассмотренные в работах [45, 46, 62, 63] системы с повторными обращениями заявок имеют один блок обслуживания и не применимы в случае поступления потоков кратных заявок.
Все вышесказанное подтверждает, что построение и анализ новых математических моделей с параллельно функционирующими блоками обслуживания, общими входящими потоками кратных заявок и повторным обслуживанием в блоках имеет большое практическое значение.
Целью данной работы является построение математических моделей случайных потоков, возникающих в различных предметных областях, объекты которых рассматриваются в виде систем массового обслуживания с неограниченным числом линий обслуживания и их исследование с помощью метода предельной декомпозиции.
В рамках указанной цели были поставлены следующие задачи:
1. Построить математическую модель потоков клиентов коммерческой организации в виде потоков в однои двухфазной системах массового обслуживания с неограниченным числом линий и повторными обращениями к фазам, количественными характеристиками которых являются доход компании и число клиентов компании различной категории (новые, постоянные, VIP — клиенты).
2. Исследовать вероятностные характеристики указанных СМО, когда входящий поток клиентов является простейшим, а время обслуживания произвольное.
3. Построить и исследовать экономико-математическую модель влияния параметров проводимых маркетинговых акций (размер предоставляемых скидок, бонусов постоянным покупателям) на доход компании.
4. Построить математическую модель финансовых потоков процедуры пожизненной ренты в виде потоков в системе с неограниченным числом фаз и линий и исследовать вероятностные характеристики этой модели.
5. Построить математическую модель распределенной вычислительной системы в виде системы параллельного обслуживания парных заявок с повторными обращениями.
6. Исследовать характеристики указанной системы при входящем потоке парных заявок и экспоненциальном с параметрами и л2 времени обслуживания в блоках.
7. Построить имитационную модель системы массового обслуживания с неограниченным числом приборов и повторным обслуживанием, позволяющую получать характеристики системы, в случае, когда входящий поток заявок не является пуассоновским и метод предельной декомпозиции неприменим.
Методика исследования. В качестве математических моделей процессов изменения числа клиентов коммерческой организации предлагается рассмотреть СМО с неограниченным числом линий, одной, двумя или неограниченным числом фаз обслуживания и повторным обращением к ним. Процесс изменения дохода компании определяется дифференциальным соотношением, включающим число клиентов компании и размер предоставляемой скидки или бонуса.
В качестве математической модели распределенной вычислительной системы предлагается система параллельного обслуживания парных заявок с повторными обращениями к блокам.
Финансовые потоки процедуры пожизненной ренты предлагается моделировать потоками системы с неограниченным числом фаз и линий.
В качестве метода исследования систем массового обслуживания с неограниченным числом фаз и линий с повторным обслуживанием, пуассоновским входящим потоком и произвольным временем обслуживания предлагается метод предельной декомпозиции.
Исследование всех указанных математических моделей проводится также методами анализа марковизируемых систем, методами теории вероятностей, теории случайных процессов, теории массового обслуживания, теории интегральных и дифференциальных уравнений в частных производных.
Все численные расчеты проводились с использованием стандартных, опробованных и протестированных методов и процедур [54].
В случае, когда входящий поток в исследуемых системах отличен от пу-ассоновского, метод предельной декомпозиции становится не применим. Для анализа характеристик таких систем в работе предложен алгоритм имитационного моделирования системы массового обслуживания с неограниченным числом линий, повторным обслуживанием и непуассоновским входящим потоком и реализован с использованием пакета МаЛсаё, версия 13.0.
Межпредметность проведенных исследований.
На современном этапе развития теории массового обслуживания одним из востребованных направлений является исследование систем массового обслуживания с групповым поступлением заявок и параллельным обслуживанием. Область применения таких СМО довольно обширна, например, при моделировании современных информационно-вычислительных систем необходимо учитывать пакетный характер трафика, а также один из основных принципов при проектировании современных компьютерных сетей — параллельность процессов обработки информации [30, 80, 85, 99, 90].
Производственно-торговая и торговая деятельность, направленная на удовлетворение массового спроса потребителей, также представляет собой широкое поле применения моделей, основанных на методах теории массового обслуживания [56]. Практически каждый вид коммерческой деятельности содержит в качестве своего элемента совокупность распределенных во времени деловых сделок. Это заставляет уделять должное внимание математическому описанию потоков коммерческих сделок, характер и свойства которых определяются содержанием коммерческих операций [68, 87]. В моделях массового обслуживания последовательность сделок рассматривается как случайный поток событий, что позволяет применить к ее описанию методы теории случайных процессов [79].
Инструмент пожизненной ренты играет в настоящее время очень серьезную роль, так как многие престарелые люди, заключая договоры ренты, пытаются обеспечить свою жизнь. Но часто договоры ренты становятся орудием мошенников и злоумышленников.
В соответствии со ст. 597 Гражданского кодекса РФ пожизненная рента выплачивается в виде определенных в договоре периодически выплачиваемых денежных сумм. Размер денежной суммы, которая подлежит выплате по договору ренты, определяется сторонами самостоятельно на свое усмотрение. Таким образом, построение и исследование математической модели процедуры пожизненной ренты и нахождение оптимального размера рентного платежа позволяют уменьшить риски сторон, заключающих такой договор. Владельцы недвижимости, желающие заключить договоры пожизненной ренты, принимают такое решение в различные моменты времени и независимо друг от друга. Моменты заключения таких договоров образуют некоторый случайный поток однородных событий, адекватной математической моделью которого является пуассоновский поток, поступающий на вход системы массового обслуживания с неограниченны числом фаз и линий.
Требования практики выдвигают перед теорией массового обслуживания большое число новых постановок задач. Рассмотрение их необходимо для приложений, для постепенного приближения условий, в которых они решаются, к истинной картине изучаемых явленийс другой стороны, это поучительно для выработки методов исследования и для создания стройной теории, которая даст возможность решать все эти частные задачи почти автоматически [28].
Научная новизна результатов проведенных исследований:
1. Предложены математические модели изменения числа клиентов коммерческой организации в виде систем массового обслуживания с неограниченным числом линий, одной, двумя или неограниченным числом фаз обслуживания и повторным обслуживанием на фазах, а также новый метод их исследования. Это метод предельной декомпозиции, который позволяет провести исследование СМО с неограниченным числом фаз и линий, повторным обслуживанием и произвольной функцией распределения времени обслуживания на приборе, то есть найти характеристики потоков клиентов компании при произвольном времени между моментами совершения покупок. Применяемые ранее для решения подобных задач методы производящих и характеристических функций допускали исследование подобных систем лишь для экспоненциального времени обслуживания на приборе, что существенно сокращает область применения полученных результатов. В то время как разные компании могут иметь различные распределения времени обдумывания клиента ввиду различий в специфике товара или организации торговли в целом, а также для одних и тех же компаний распределение может смениться в связи с, например, изменением экономической ситуации на рынке.
2. Построена математическая модель процедуры пожизненной ренты в виде системы массового обслуживания с неограниченным числом фаз и линий и проведено исследование потоков в этой системе и процесса изменения прибыли плательщика ренты.
3. Построена математическая модель распределенной вычислительной системы в виде системы параллельного обслуживания парных заявок с повторными обращениями к блокам. В случае экспоненциального времени обслуживания исследование указанной системы проведено методом производящих функций и методом предельной декомпозиции. Проведенное сравнение показывает, что предлагаемый метод предельной декомпозиции не только позволяет аналитически исследовать СМО с неограниченным числом фаз и линий и произвольным временем обслуживания, но и в случае экспоненциального обслуживания позволяет существенно упростить процедуру решения.
4. Построена имитационная модель СМО с неограниченным числом линий и повторным обслуживанием с непуассоновским входящим потоком.
Практическая значимость диссертации и использование полученных результатов заключается в создании новых математических моделей, применимых для анализа систем из различных предметных областей и развитии аналитических методов исследования систем массового обслуживания с неограниченным числом линий различной структуры и произвольным временем обслуживания.
Результаты работы используются в учебном процессе при проведении практических занятий по курсу «Теория массового обслуживания», в научно-исследовательской работе студентов при написании курсовых и дипломных работ по специальности «Прикладная математика и информатика», включены в монографию [24] и использовались при выполнении проекта «Разработка методов исследования немарковских систем массового обслуживания и их применение к сложным экономическим системам и компьютерным сетям связи», при поддержке Аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы (2009;2011 гг.)» и Федерального агентства по образованию РФ.
Публикации основных положений диссертационного исследования.
Результаты диссертационной работы опубликованы в 19 печатных работах, из них 3 статьи в журналах списка ВАК: *.
1. Ананина И. А. Математическая модель процесса изменения дохода торговой компании, расширяющей свое присутствие на рынке / И. А. Ананина // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. — 2011. — № 2 (15). — С. 5−14.
2. Ананина* И. А. Математическая модель процедуры пожизненной ренты / A.A. Назаров, И.А. Ананина* // Известия Томского политехнического университета. — 2011. — Т. 318, № 5. — С. 160−165.
3. Захорольная И. А. Математическая модель параллельного обслуживания кратных заявок с повторными обращениями / С. П. Моисеева, И. А. Захорольная // Автометрия. — 2011. — Т. 47, № 6. — С. 51−58.
4. ZakhoroPnaya I.A. Mathematical model of retrial queueing of multiple requests / S.P. Moiseeva, I.A. ZakhoroPnaya // Optoelectronics, instrumentation and data processing. — 2011. — Vol. 47, № 6. — P. 51−58.
5. Ананина* И. А. Исследование потоков в системе M|GI|oo с повторным обращением методом предельной декомпозиции / И.А. Ананина*, А. А. Назаров, С. П. Моисеева // Вестник Томского государственного университета. Управление, вычислительные технологии и информатика. — 2009. — № 3 (8). -С. 56−67.
6. Ананина* И. А. Исследование суммарного потока обращений в системе M|GI|oo с повторными обращениями с учетом номера попытки / И.А. Ананина* // Массовое обслуживание: потоки, системы, сети: материалы междунар. научн. конф. «Современные вероятностные методы анализа и оптимизации информационно-телекоммуникационных сетей». — Минск: РИВШ, 2011. -Вып. 21.-С. 8−13.
7. Захорольная И. А. Математическая модель процесса изменения дохода от продажи взаимодополняющих товаров / И. А. Захорольная, С. П. Моисеева // Труды X международной конференции по финансово-актуарной математике и эвентоконвергенции технологий / КГТЭИ СФУ. — Красноярск, 2011. — С. 157−160.
8. Захорольная И. А. Исследование модели параллельного обслуживания кратных заявок с повторными обращениями к блокам / И. А. Захорольная, С. П. Моисеева // Научное творчество молодежи: материалы XV Всероссийской научно-практической конференции. — Томск: Изд-во Том. ун-та, 2011. -Ч.1.-С. 25−28.
9. Захорольная И. А. Исследование многомерных потоков обращений в системе M|GI|oo с повторными обращениями с учетом номера попытки / И. А. Захорольная // Студент и научно-технический прогресс: материалы XLIX Международной научной студенческой конференции / Новосиб. гос. ун-т. -Новосибирск, 2011. — С. 195−197.
10. Ананина* И. А. Исследование СМО с повторным обращением и неограниченным числом обслуживающих приборов методом предельной декомпозиции / И.А. Ананина*, A.A. Назаров, С. П. Моисеева // Информационные технологии и математическое моделирование (ИТММ-2008): материалы VII Всероссийской научно-практической конференции с международным участием (14−15 ноября 2008 г.). — Томск: Изд-во Том. ун-та, 2008 — С. 3−5.
11. Ананина* И. А. Исследование потоков в системе обслуживания с неограниченным числом фаз и линий методом предельной декомпозиции / И.А. Ананина*, A.A. Назаров, О. Н. Галажинская // Массовое обслуживание: потоки, системы, сети: материалы международной научной конференции «Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей». — Минск: РИВШ, 2009. — С. 170−174.
12. Ананина* И. А. Математическая модель изменения дохода торговой компании / И. А. Ананина, A.A. Назаров, С. П. Моисеева // Труды VIII международной ФАМ'2009 конференции / Сиб. федерал, ун-т. — Красноярск, 2009.-С. 114−116.
13. Ананина И. А. Основные вероятностные характеристики дохода торговой компании с учетом влияния скидки на товар / И.А. Ананина*, С. П. Моисеева // Научное творчество молодежи: материалы XIII Всерос. научно-практич. конф. 14−15 мая 2009 г. / Том. гос. ун-т. — Томск, 2009. -С. 8−10.
14. Ананина* И. А. Исследование потоков в системе M|GI|oo с повторным обращением с учетом номера попытки / И.А. Ананина*, A.A. Назаров // Теория вероятностей, математическая статистика и их приложения: материалы Международной конференции в Минске 22−25 февраля 2010 г. — Минск: РИВШ, 2010.-С. 11−14.
15. Ананина И. А. Математическая модель изменения дохода торговой компании при предоставлении скидок по категориям покупателей / И.А. Ананина* // Труды IX Международной ФАМЭТ конференции / Сиб. федер. ун-т. — Красноярск, 2010. — С. 34−37.
16. Ананина* И. А. Исследование потоков в системе M|GI|oo с повторным обращением с учетом номера попытки / И.А. Ананина* // Информационные технологии и математическое моделирование (ИТММ-2009): материалы VIII Всероссийской научно-практической конференции с международным участием (13−14 ноября 2009 г.). — Томск: Изд-во Том. ун-та, 2009. — Ч. 1. — С. 36.
17.Ананина* И. А. Исследование суммарного потока обращений в двухфазной бесконечнолинейной СМО с повторными обращениями / И. А. Ананина // Научное творчество молодежи: материалы XIV Всероссийской научно-практической конференции. — Томск: Изд-во Том. ун-та, 2010. — Ч. 1. -С. 3−5.
18. Захорольная И. А. Исследование выходящих потоков в системе массового обслуживания с параллельным обслуживанием парных заявок / И. А. Захорольная, С. П. Моисеева // Информационные технологии и математическое моделирование: материалы X Всероссийской научно-практической конференции с международным участием. — Томск: Изд-во Том. ун-та, 2011. -Ч. 1.-С. 121−124.
19. Ананина* И. А. Исследование математической модели потоков клиентов таксопарка / И.А. Ананина* // Информационные технологии и математическое моделирование: материалы IX Всероссийской научно-практической конференции с международным участием. — Томск: Изд-во Том. ун-та, 2010. -Ч. 1.-С. 3−7.
Апробация результатов исследования.
Основные результаты диссертационного исследования докладывались и обсуждались на следующих конференциях:
1. VII Всероссийская научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск. АСФКемГУ. Ноябрь 2008 г.
В 2011 году произошла смена фамилии. В работах, вышедших ранее, диссертант Захорольная И. А. имела фамилию Ананина.
2. VIII Международная конференция «Финансовая математика и смежные вопросы». Красноярск, КГТЭИ. 24−26 апреля 2009 г.
3. XIII Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск. АСФКемГУ. 14−15 мая 2009 г.
4. VIII Всероссийская научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск. АСФКемГУ. Ноябрь 2009 г.
5. IX Международная конференция по финансово-актуарной математике и эвентоконвергенции технологий. Красноярск, КГТЭИ. Апрель 2010 г.
6. XIV Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск. АСФКемГУ. Апрель 2010 г.
7. VIII Российская конференция с международным участием «Новые информационные технологии в исследовании сложных структур». Томск, ТГУ. 5−8 октября 2010 г.
8. IX Всероссийская научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск. АСФКемГУ. 19−20 ноября 2010 г.
9. XLIX Международная научная студенческая конференция «Студент и научно-технический прогресс». Новосибирск. НГУ. 16−20 апреля 2011 г.
10. X Международная конференция по финансово-актуарной математике и эвентоконвергенции технологий. Красноярск, КГТЭИ. 23−24 апреля 2011 г.
11. XV Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск. АСФКемГУ. 28−29 апреля 2011 г.
12. X Всероссийская научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск. АСФКемГУ. 25−26 ноября 2011 г.
13. Российская научная конференция с участием зарубежных исследователей «Моделирование систем информатики». Новосибирск, СГУТиИ. 8−11 ноября 2011 г.
Краткое содержание работы:
Работа состоит из четырех глав, введения, заключения, списка литературы из 116 наименований.
Первая глава посвящена исследованию потоков заявок в системах массового обслуживания с неограниченным числом линий, одной и двумя фазами обслуживания и повторным обслуживанием на фазах.
Для исследования потоков в системах массового обслуживания с неограниченным числом обслуживающих линий и входящим пуассоновским потоком заявок предлагается метод предельной декомпозиции. Суть этого метода заключается в следующем.
Пуассоновский с интенсивностью X входящий поток разделим по полиномиальной схеме с равными вероятностями на N независимых пуассонов-ских потоков с интенсивностями X/N.
Для заявок каждого из потоков определим единственную соответствующую линию обслуживания и будем рассматривать однолинейную СМО с отказами в обслуживании для тех заявок, которые поступили на периодах занятости линии.
Линия считается занятой, если занята одна из ее фаз обслуживания.
Следовательно, формируется N независимо функционирующих однолинейных систем обслуживания, исследование которых гораздо проще, чем исследование исходной системы с неограниченным числом линий.
В связи с возможностью отказов в обслуживании, суммарные характеристики полученной совокупности N независимых однолинейных систем не эквивалентны соответствующим характеристикам исходной системы с неограниченным числом линий. Показано, что этот недостаток устраняется предельным переходом в суммарных характеристиках при N -> оо .
Рассмотрена система массового обслуживания (СМО) с неограниченным числом обслуживающих приборов, на вход которой поступает простейший с параметром X поток заявок. Время обслуживания на каждом приборе имеет произвольную функцию распределения В (х) одинаковую для всех приборов. Заявка, завершившая обслуживание, с вероятностью 1 -г покидает систему, а с вероятностью г обращается к системе для повторного обслуживания, формируя тем самым поток повторных обращений. Доказана Теорема 1.1. о том, что производящая функция суммарного числа обращений т ({) в системе М|01|оо с повторными обращениями имеет вид: t х, г1) = ехр{р (х, /)} = ехр< (х -1).
А/ + г | / (х, я)*/,?, о где функция/(х, О определяется преобразованием Фурье-Стилтьеса вида.
Х и Л В*(а) е- = 0.
Ф (а, х) = ] е*" а,/(х, *)=-А- (х — ,.
1 -гrxB (а] а В*(а)= - преобразование Фурье-Стилтьеса от функции распрео деления В (х).
Найдены математическое ожидание и дисперсия числа суммарных обращений к системе.
Рассмотрены отдельно потоки первичных и повторных обращений в СМО М|С1|оо с повторным обслуживанием заявок.
Доказана Теорема 1.2. о том, что производящая функция 0{х, у,() двумерного процесса п (первичных и повторных обращений в исследуемой системе имеет вид:
0(х, у, = ехр|(х — + г (у -1)| /(х, у, я^Зя где функция/{х, у, определяется преобразованием Фурье-Стилтьеса вида ф (а, х) = ?еуаЦ/(х, у,0 = -^~(х-1 + г (у-х)) В о 1 -гryB (а).
00 а В*{о)~ - преобразование Фурье-Стилтьеса от функции распрео деления В (х).
Найдены числовые характеристики числа повторных обращений к системе.
Поострена математическая модель потоков клиентов коммерческой организации в виде потоков системы массового обслуживания М|01|оо с повторным обслуживанием заявок.
При объявлении компанией акции «подарок за покупку» вероятность возвращения клиента в данную компанию возрастает. Рассмотрена характеристическая функция величины суммарного дохода компании, полученного за время ^ проведения акции «подарок за покупку», доказано, что она имеет вид где ф (а) = Ме м) — характеристическая функция величины ^ - М, то есть разности цены покупки и величины Мбонуса выдаваемого покупателю при совершении им покупки величиной.
Найден средний доход компании, получено выражение для определения оптимального размера бонуса, приведен численный пример расчета ожидаемого дохода компании.
Далее в главе рассматривается двухфазная система массового обслуживания с неограниченным числом линий, на вход которой поступает простейший с параметром X поток заявок. Поступившая заявка занимает одну из свободных линий, начиняя обслуживание с первой фазы. Линия считается занятой, если занята любая из её фаз. Завершив обслуживание на первой фазе, с вероятностью 1 -гх заявка покидает систему, а с вероятностью гх обслуживается повторно: с вероятностью 1 — д на той же первой фазе, а с вероятностью q на второй. Завершив обслуживание на второй фазе, заявка с вероятностью 1 — г2 покидает систему, а с противоположной вероятностью г2 обслуживается на этой фазе вновь. Продолжительности фаз обслуживания стохастически независимы и определяются функциями распределения ^(х) и В2{х) для первой и второй фазы соответственно. Процессы обслуживания для различных линий одинаковы и стохастически независимы. Таким образом, формируются потоки повторных заявок, описываемые случайными процессами, п2 (V), где пк (/) — число повторных обращений к к-ой фазе, реализованных за время наблюдения t.
Доказана Теорема 1.3. о том, что производящая функция суммарного числа обращений п ({) в двухфазной системе с неограниченным числом линий и повторными обращениями к фазам имеет вид:
С (х, = ехр^ (х -1}.
АЛ+ гх /х (х, +г21 /2 где функции /к (х, {) определяются преобразованиями Фурье-Стилтьеса вида.
X (В* (а) ф1(а, х) = | (х, () = —£-г (х -1) 1.
0 1-ГД1−4) ии р2 (а, х) = | е/аЧ/2 (х, /) =.
Х, г^(х -1).
1(1-^X1-^(1-^)) а).
52*(а).
1-хг2В2*(а) где 5А*(а)= - преобразование Фурье-Стилтьеса от функции расо пределения ?=1,2. Найдены основные числовые характеристики исследуемого случайного процесса.
Доказана Теорема 1.4. о том, что производящая функция С (х, у1, у2^) трехмерного случайного процесса (02 (0} в двухфазной системе массового обслуживания с неограниченным числом линий и повторными обращениями к фазам имеет вид:
У, У2^)= ехР 1 ~0'+ Л (УС1 ~Я)'+ У24 ~О/Л (*>УъУг^ г2 {у2 — Ц/2 У1>У2> и? и г > о ] где функции /1(х, у1, у2^) и /2(х, у], у2,?) определяются преобразованиями Фурье-Стилтьеса вида.
Ф! (а, х, у1) = | е^й^ {х, уг, у2, *) о л-1 + Г! (1-^1-*)).
В, а) а)'.
00 ф2 (а, Х, у2) = ^ е70Ч/2 (*> У1>У2> О о.
В2а).
00 где Вк*(а)= - преобразование Фурье-Стилтьеса от функции распределения Вк{{), к=, 2. Найдены основные числовые характеристики исследуемого случайного процесса.
Предложена модель изменения числа клиентов некоторой торговой компании можно в виде двухфазной системы массового обслуживания с неограниченным числом линий, произвольным временем обслуживания на фазах, с повторными обращениями.
Решена задача нахождения основных вероятностных характеристик дохода, полученного торговой компанией за время t действия скидок постоянным покупателям. Полученные характеристики позволяют найти оптимальный размер предоставляемой скидки, обеспечивающий максимальный доход компании.
Вторая глава диссертационной работы посвящена исследованию потоков в системах массового обслуживания с неограниченным числом фаз и линий.
Рассмотрена система массового обслуживания с неограниченным количеством обслуживающих приборов, на вход которой поступает простейший с параметром X поток. В системе реализуется многократное обслуживание заявок. Заявка, выполняющая к-ое по счету обслуживание, называется к — заявкой. Первичные заявки, то есть заявки входящего простейшего потоо ка, являются 1-заявкой. Завершив обслуживание, кзаявкас вероятностью 1 — гк покидает систему, а с вероятностью гк возвращается на прибор для повторного обслуживания, становясь (к +1) — заявкой. Время обслуживания А:-заявки имеет произвольную функцию распределения Вк (х). Доказана Теорема 2.1. о том, что производящая функция (7(х,/) суммарного числа т ({) обращений в системе с неограниченным числом линий и повторными обращениями с учетом номера попытки имеет вид: в{х, = ехр< (х -1) к=1 о где функции /к (х, ?) определяются выражениями к-1 (к>2.
1=1 7=1 У, а — (Ы+1)-кратная свертка распределений В^), ., Вк^). Найдены основные числовые характеристики исследуемого случайного процесса.
Доказана Теорема 2.2. о том, что производящая функция С (х1?х2,.,/) случайного вектора {?%(/), п2 (0? •••} с неограниченным числом компонент системе массового обслуживания с неограниченным числом приборов и повторным обслуживанием с учетом номера попытки имеет вид:
С (х!, х2,., = ехр< А,^(х1 -1).
—VI /+ -1)|/^(х^хз,.
I Л=2 О где функции /к (х1,х2,.^) определяются выражениями х (х1, х2,., г) = Х (1 + (х1 -1)5! (*)), к-1 о =.
У=1.
V /=1 7=г+1 к> 2, а ~ (&—*+1)-кратная свертка распределений 5 г (?), ., Вк^). Найдены основные числовые характеристики исследуемого случайного вектора.
Построена математическая модель потоков клиентов обычного таксопарка, в условии проведения акции «/-ая поездка бесплатно». Получена функция прибыли во время действия такой акции. Исследовано изменение величины месячной прибыли компании в зависимости от параметра / проводимой акции.
Построена математическая модель финансовых потоков процедуры пожизненной ренты в виде потоков системы массового обслуживания с неограниченным числом линий и бесконечным числом фаз обслуживания в каждой линии. Найдена характеристическая функция величины прибыли плательщика ренты и проведен численный анализ влияния на величину прибыли размера рентного платежа.
В третьей главе диссертационной работы проводится исследование математической модели распределенной вычислительной системы в виде системы параллельного обслуживания парных заявок с повторным обслуживанием в блоках.
Рассматривается некоторый вычислительный комплекс для решения задач, требующих параллельной реализации двух итерационных алгоритмов, каждый из которых решает свою подзадачу. Исходные задачи, состоящие из двух подзадач, поступают независимо друг от друга и их количество достаточно велико. В итоге одного выполнения итерационного алгоритма решение может быть не найдено, в таком случае алгоритм запускается заново и эта процедура выполняется, пока подзадача не будет решена. Аналогично реализуется решение другой подзадачи вторым алгоритмом.
В качестве математической модели функционирования такого комплекса рассматривается система массового обслуживания с двумя обслуживающими блоками, каждый из которых содержит неограниченное число приборов. На вход системы поступает простейший с параметром X поток сдвоенных заявок, то есть в момент наступления события в рассматриваемом потоке в систему одновременно поступают две заявки.
Дисциплина обслуживания определяется тем, что одна из этих заявок поступает в первый, а другая во второй блоки обслуживания и занимает любой из свободных приборов, на котором выполняется ее обслуживание в течение случайного времени, распределенного по экспоненциальному закону с параметрами jii и соответственно. Закончив обслуживание, заявка &—го блока с вероятностью 1—гкпокидает систему, а с вероятностьювозвращается обратно на прибор для повторного обслуживания. Доказана Теорема 3.1. о том, что совместная производящая функция четырехмерного случайного процесса {z'i (/)? h (t), щ (0> n2(t)} - числа занятых приборов в блоках и повторных обращений к ним имеет вид i-nXi-r2).
F (xl, x2, yl, y2j)=exp<
O-^iX1-^).
Xt +.
1-n.
1-ПУ1.
— x,.
— Hi (l-w)'.
V,.
1 -r, y2-i).
1~Г2Уг [}~Г2У2 У У l-rj+^l-rj Л.
1-r,.
ФгО i-Wi U-i^i.
Xi Л у X у s (y2-i).
1-r,.
Xo.
Л Л.
— Ц2(1-/" 2у2> У У m (l-l).
— X Х.
1−1.
1−1.
1-г,.
1-W.
•X,.
1-г2.
1-^2.
JX*—).
— H2(l-i-2>>2> l i-^iX1-^) J.
1(1-^x1-^2).
Получены математическое ожидание и дисперсия числа занятых приборов в блоках.
Далее, с помощью метода предельной декомпозиции, доказана Теорема 3.2. о том, что совместная производящая функция числа повторных обращений к блокам обслуживания в системе М2|М2|оо с повторным обслуживанием в блоках имеет вид:
— 1) r2(x2 -1) 1 -(l — xxrx)(l ~x2r2) |a, (l — xxrx) ¦+ (i2 (lX2r2).
Xrx (xx — l)(lr2) 1 -Xr2(.x2 -lXln) 1 -| l-x^Xl-зд) Hii1″ ^) (l-^i^iX1″ ^^) Цг^-зд) J.
Показано, что полученное выражение совпадает с выражением для маргинальной совместной производящей функции числа повторных обращений к блокам, получаемым с помощью Теоремы 3.1. Однако использование метода предельной декомпозиции существенно упрощает аналитические выкладки. Получены математическое ожидание, дисперсия и функция корреляции числа занятых приборов в блоках.
В четвертой главе диссертационной работы приведен комплекс проблемно-ориентированных алгоритмов и программ имитационного моделирования системы массового обслуживания с неограниченным числом линий и повторным обслуживанием с непуассовновским входящим потоком. Построены имитационные модели MAPи SM-потоков, используемые в качестве моделей потока заявок, поступающего на вход указанной системы массового обслуживания.
Таким образом, с помощью предложенного метода предельной декомпозиции удалось провести исследование и найти характеристики потоков заявок в различных системах массового обслуживания с неограниченным числом фаз, линий и реализацией повторного обслуживания на приборах, являющихся математическими моделями многих реальных процессов из различных областей человеческой деятельности.
ЗАКЛЮЧЕНИЕ
.
В работе построены математические модели потоков клиентов коммерческой организации в виде потоков в однои двухфазной системах массового обслуживания с неограниченным числом линий и повторными обращениями к фазам. Проведено исследование таких количественных характеристик, как доход и число клиентов компании различной категории (новые, постоянные, VIP — клиенты), что позволило построить и исследовать экономико-математическую модель влияния параметров проводимых маркетинговых акций (размер предоставляемых скидок, бонусов постоянным покупателям) на доход компании.
Построена математическая модель финансовых потоков процедуры пожизненной ренты в виде потоков в системе с неограниченным числом фаз и линий и проведено исследование вероятностных характеристик этой модели.
Построена математическая модель распределенной вычислительной системы в виде системы параллельного обслуживания парных заявок с повторными обращениями и проведено исследование ее вероятностных характеристик при входящем потоке парных заявок и экспоненциальном с параметрами |j, i и j~i2 времени обслуживания в блоках.
В работе предложен метод предельной декомпозиции как аналитический метод исследования потоков в системах массового обслуживания с неограниченным числом линий, простейшим входящим потоком и произвольным временем обслуживания. С помощью этого метода проведено исследование и найдены характеристики потоков заявок в следующих системах массового обслуживания:
• M|G|oo с повторным обслуживанием;
• M|G |оо —>|G|oo с повторным обслуживанием на фазах;
• M|G |оо с повторным обслуживанием с учетом номера попытки;
• M|G |оо —>|G|oo—>. —>|G|co—". ;
2 2 со с повторным обслуживанием в блоках.
В ходе проведенного исследования показано, что предложенный метод предельной декомпозиции действительно позволяет аналитически исследовать потоки в достаточно сложных системах массового обслуживания с неограниченным числом фаз и линий, с процедурами повторного обслуживания в линиях в условиях произвольного времени обслуживания с функцией распределения общего вида В (х).
Кроме того, будучи применен к исследованию потоков в подобных системах с экспоненциальным временем обслуживания, этот метод позволяет существенно упростить аналитические выкладки по сравнению, например, с методами непосредственного решения уравнений для производящих и характеристических функций для потоков в системах с неограниченным числом линий.
Недостатком метода является его неприменимость, в случае если входящий поток заявок отличен от пуассоновского. Однако СМО с повторным обслуживанием и неограниченным числом линий является хорошей математической моделью реальных процессов из различных предметных областей, в том числе и из таких, где входящий поток не может быть аппроксимирован пуассоновским.
В связи с этим, в настоящей работе предложен комплекс проблемно-ориентированных алгоритмов и программ, моделирующих такие СМО для непуассоновского входящего потока. В частности предложены модели МАРи БМ-потоков.
Результат сравнения полученных в ходе исследования теоретической и эмпирической функций распределений вероятностей числа повторных обращений в системе с неограниченным числом линий и повторным обслуживанием говорит о достаточно хорошей аппроксимации, что позволяет применять построенную имитационную модель для нахождения характеристик системы когда ее аналитическое исследование провести не удается, то есть при непуассоновском входящем потоке.