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

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

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Московский институт электроники и математики им. А.Н. Тихонова

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

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

Загонова Елизавета Алексеевна

Москва 2020



Аннотация

В данной работе рассматривается Марковская система массового обслуживания M | M | n | ? с нетерпеливыми клиентами, где время до ухода требования из очереди распределено экспоненциально с заданным параметром. Цель исследования - изучить описанную систему массового обслуживания и решить задачу двухкритериальной оптимизации для системы с заданными параметрами несколькими способами. В ходе исследования функционирования системы будет рассчитано среднее время до момента ухода первого нетерпеливого клиента из очереди и доход, полученный за это время, для разного числа каналов с использованием имитационной модели. Корректность полученных значений будет проверена с помощью аналитических методов решения. На основе полученных значений критериев для системы с заданными параметрами, будет решена задача двухкритериальной оптимизации несколькими способами при помощи программы, написанной на языке Python. Результаты, полученные в данной работе, могут использоваться для анализа эффективности и оптимизации работы экстренных служб и других систем, для которых выбранные критерии являются ключевыми.

This study investigates the Markov queuing system M | M | n | ? with impatient customers, where the average time until the leaving of the first impatient customer is distributed exponentially with the specified parameter. The goal of the study is to investigate the described queuing system and solve the problem of two-criteria optimization. During the study of the system functioning, the average time until the first impatient client leaves the queue and the income received during this time will be calculated for a different numbers of channels via simulation model. The correctness of the obtained values ??will be checked using analytical solution methods. Based on the obtained values ??of criteria, the problem of two-criteria optimization will be solved in several ways using a program written in Python. The results obtained in this paper can be used for analysis of the effectiveness and optimization of emergency services and other systems with the same key criteria.

имитационный моделирование доход



Содержание

Введение

1. Обзор проблематики и постановка задачи

1.1 Теоретическая часть

1.2 Метод свёртки критериев

2. Практическая часть

2.1 Вычисление критериев аналитическими методами

2.2 Вычисление критериев при помощи имитационного моделирования

2.3 Решение задачи оптимизации

Заключение

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

Приложение



Введение

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

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

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

Для достижения поставленной цели были поставлены следующие задачи:

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

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

Вычислить средний удельный доход в стационарном режиме

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

Сравнить полученные результаты

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

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

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

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



1. Обзор проблематики и постановка задачи

Обзор литературы

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

Для оптимизации структуры системы используются самые разнообразные методы. Интересной показалась статья группы пакистанских учёных, которые занимались оптимизированием работы госпиталя в условиях чрезвычайных ситуаций [2]. В 2018 году в Пакистане последовал ряд террористических актов, в условиях которых не хватало докторов для оказания помощи. В связи с этим, в работе анализировалась система массового обслуживания в условиях чрезвычайных ситуаций. Требовалось найти оптимальное расписание работы докторов, минимизируя при этом функционал затраченных ресурсов и максимизируя такие показатели системы как среднее время ожидания в очереди, вероятность потери требования, среднюю длину очереди. Данные показатели уже имеют аналитические формулы, поэтому их расчёт не требовал дополнительных исследований. Однако возникает многокритериальная задача оптимизации. Учёные свели решение возникшей многокритериальной задачи к задаче нахождения максимума одного критерия - функционала дохода при ограничениях на другие критерии. Ограничения на показатели системы были вычислены аналитически на основе данных, полученных опытным путём.

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

Постановка задачи

В работе изучается Марковская система массового обслуживания М | M | n | ?, которая функционирует следующим образом (рис. 1). Поступление требований в систему является Пуассоновским потоком с параметром л. Из поступивших требований формируется очередь неограниченной длины, обслуживание которой производится по принципу FIFO (first in, first out). Если заявка не поступает на обслуживание в течение времени, распределённого экспоненциально с параметром г, она покидает систему. Требование, поступившее на обслуживание, пребывает там время, распределённое экспоненциально с параметром м, затем покидает систему.

Рисунок 1. Функционирование СМО с нетерпеливыми клиентами

Для данной СМО введём случайный процесс о(t) с непрерывным временем и дискретным множеством состояний. Состоянием процесса будет являться количество запросов в системе. Тогда множество состояний является бесконечным и представляется следующим образом: Е={0,1,2,…}.

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

Введём функционал W(t), равный доходу системы в момент времени t. Значение данного функционала рассчитывается на основе следующих параметров системы:

- доход за обслуживание клиента

- плата за простой канала в ед. времени

- плата за ожидание в очереди в ед. времени

- плата за потерю клиента

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

Итак, поставлена задача двухкритериальной оптимизации:

(1)

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

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

Далее обозначим E(D) средний удельный доход системы в стационарном режиме и поставим ту же задачу, но с другим показателем дохода:

(2)

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

Выводы

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

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

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

1.1 Теоретическая часть

Поскольку основным объектом изучения в данной работе является Марковская система массового обслуживания, выпишем её основные свойства [3], которые потребуются для решения поставленной задачи.

Свойство 1. Ординарность.

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

Из данного свойства следует, что вероятность того, что в интервале h произойдёт более одного события, равна o(h).

Свойство 2. Распределение минимума из экспоненциальных распределений.

Пусть даны случайные величины жi, имеющие экспоненциальное распределение с параметром лi, тогда min(ж1,…, жn) имеет экспоненциальное распределение с суммарным параметром и .

Также в работе используется формула математического ожидания функции от непрерывной случайной величины [4]. Пусть о - случайная величина с функцией распределения F(x), тогда математическое ожидание f(о) рассчитывается по формуле:

(3)

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

Порядок обслуживания заявок - FIFO

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

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

Входящий поток заявок - Пуассоновский

Заявка покидает очередь, не дождавшись выезда, через время, распределённое экспоненциально

При данных предположениях система является Марковской и задаётся следующими параметрами:

л - среднее число поступлений заявок в единицу времени

м - среднее число заявок, обслуженных в единицу времени

г - среднее число потерянных заявок в единицу времени

Для вычисления дохода потребуются следующие показатели:

С1 - средний расход на один выезд

С2 - средний расход на содержание машины в единицу времени

С3 - насколько в среднем увеличится расход на выезд, если заявка ожидала выезда единицу времени

С4 - затраты на устранение последствий потерянной заявки

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

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

Метод «идеальной точки».

В основу метода положен расчёт расстояния между точками, соответствующими рассматриваемым вариантам альтернатив и идеальной альтернативой в многомерном пространстве критериев [5]. Идеальной считается альтернатива, которая имеет наилучшие значения по всем критериям. В реальности идеальная точка, как правило, недостижима. Однако наилучшей считается точка , расстояние от которой до идеальной наименьшее.

,

N - количество критериев

- идеальное значение по j-му критерию для идеального варианта

- значение по j-му критерию для i-ой альтернативы

- расстояние от i-ой альтернативы до идеальной точки

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

1.2 Метод свёртки критериев

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

,…, - критерии

б1,…, бn: - веса

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

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

E(D) - средний удельный доход системы в стационарном режиме

{рj }j=1,…,? - стационарное распределение вложенной Марковской цепи

d(j) - средний доход в единицу времени в состоянии j

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

,

, где

Средний доход в состоянии i для рассматриваемого типа СМО рассчитывается по формуле:

(5)

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

(6)

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



2. Практическая часть

2.1 Вычисление критериев аналитическими методами

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

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

(7)

Система представляет собой набор рекуррентных соотношений для последовательности математических ожиданий mi, i = 1,…,. Перепишем её таким образом, чтобы каждый следующий элемент был выражен через предыдущие элементы.

(8)

Первые два соотношения образуют линейную систему из n+1 уравнений с n+1 неизвестной при известном mn+1. Такая система имеет ровно одно решение и может быть разрешена методом Гаусса или Крамера. Сложность решения системы (8) заключается в последнем соотношении, которое порождает бесконечное число уравнений.

Заметим, что при k = 0 в третьей строчке получается такое же уравнение, что и во второй строчке при i = n. Поскольку для решения конечной системы полученной из первых двух соотношений требуется найти условное математическое ожидание , включим его в последнее соотношение, сделав нумерацию для k начиная с нуля.

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

Пусть производящая функция имеет вид:

(9)

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

(10)

После домножения k-того уравнения на и их суммирования получим следующее:

,

На основании принятых обозначений (9) и (10) получаем дифференциальное уравнение:



,

Подстановка z = 0 в выражение (9) даёт начальное условие .

Полученное уравнение является линейным неоднородным дифференциальным уравнением первого порядка. Решение однородного уравнения для производящей функции будет выглядеть следующим образом:

,

Применив метод вариации постоянной, получаем выражение для константы:

,

,

.

Полученное дифференциальное уравнение не имеет первообразной в пространстве элементарных функций, поэтому получить явное решение системы (8) в данной работе не удалось. Но поскольку главной целью является не решение дифференциального уравнения, а получение mn+1, производящая функция может быть использована в дальнейших исследованиях для разложения в ряд. Если такое разложение удастся получить, коэффициент при первой степени z будет являться искомым условным математическим ожиданием mn+1, значение которого позволит решить конечную систему для m0, …, mn.

Как уже было описано ранее, функционирование описанной системы массового обслуживания представляется в виде процесса о(t), в котором состоянием будет являться количество запросов в системе. Тогда множество состояний является бесконечным, дискретным и представляется следующим образом: Е={0,1,2,…}. Для определения среднего дохода до ухода первого нетерпеливого клиента, введем следующую случайную величину:

D(з) - момент ухода первого нетерпеливого клиента.

Тогда - условное математическое ожидание этой случайной величины.

Пусть процесс в момент времени t = 0 находится в состоянии i = 0, которое означает, что в системе на данный момент нет требований. В силу свойства 1 экспоненциального распределения, вероятность того, что произойдёт одновременно больше одного события, равна 0, поэтому далее процесс может перейти только в состояние о(x) = 1 в случае прихода клиента (рис. 2). Доход, полученный за время x равен расходу за простой n приборов в течение этого времени и составит условных единиц.

Рисунок 2. Схема процесса при о(0)=0

Здесь момент смены состояния x является случайной величиной и имеет распределение времени ожидания очередного требования:

,

Для подсчёта среднего дохода за время нахождения в состоянии 0, воспользуемся формулой математического ожидания непрерывной случайной величины (2) и получим следующее выражение: .

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

,

Теперь рассмотрим систему, находящуюся в начальный момент времени в состоянии i = 1. Далее процесс может оказаться либо в состоянии о(х) = 2, в случае прихода очередного клиента (рис.3, а), либо в состоянии о(х) = 0, если канал завершит обслуживание за время x (рис.3, б).

Рисунок 3. Схема процесса при о(0) = 1

Интервал x - это минимум из длительностей интервалов обслуживания и ожидания, следовательно, по свойству 2, он распределен экспоненциально с суммарным параметром:

,

Доход полученный в случае а) равен как сумма расхода за простой приборов за время x и дохода при начальном состоянии 2. В случае б) доход рассчитывается как сумма платы за простой n-1 канала за время x, дохода за обслуженную заявку и дохода, полученного при старте из состояния 0: .

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

Тогда выражение для математического ожидания в этом случае имеет следующий вид:

Аналогично будет выглядеть выражение для всех последующих , где с отличием в числе работающих каналов в момент времени t = 0, которое повлияет на суммарный параметр и количество простаивающих приборов в состоянии i.

Далее рассмотрим систему, находящуюся в состоянии i = n + k в начальный момент времени. В этой ситуации все обслуживающие приборы заняты и в очереди имеется k требований, а значит, возможны три варианта развития системы: из очереди ушёл нетерпеливый клиент, в систему пришла очередная заявка или завершил работу канал обслуживания. В первой ситуации доход будет складываться из затрат на ожидание k заявок в очереди и среднего дохода после перехода в состояние n+k+1. Во втором варианте доход равен затратам на нахождение запросов в очереди в течение времени x, дохода за обслуживание и среднего дохода, получаемого при старте из состояния n+k-1. В случае потери заявки, к затратам за ожидание в очереди прибавляется штраф за потерю клиента. Тогда выражение для записывается следующим образом:

где ; k=1, …, ?

Получена бесконечная система уравнений, которую задают формулы 11, 12 и 13 относительно условных математических ожиданий :

,

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



,

,

,

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

2.2 Вычисление критериев при помощи имитационного моделирования

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

Построение имитационной модели для рассматриваемой системы уже производилось в курсовой работе [8]. Модель была реализована при помощи программного кода на языке Python и позволяла вычислять среднее время до ухода первого нетерпеливого клиента для заданных параметров системы (Приложение 1). Для того чтобы вычислять средний доход, модель была скорректирована как показано на блок схеме (рис. 4).

На вход подаются следующие параметры системы:

T0 - момент прихода очередного требования

T[k] - моменты освобождения k-ого канала обслуживания

Q[s] - очередь Очередь представляет собой объект переменной длины, с возможностью добавления и удаления элементов., в ячейках которой хранятся моменты ухода s-того требования

Q1[s] - очередь, в ячейках которой хранятся моменты прихода s-того требования

L - текущая длина очереди

w - текущий доход

Этими параметрами задается начальное состояние системы, затем начинается основной цикл. Количество повторений цикла ограничено временем, которое назначается исходя из того, сколько необходимо проработать системе, чтобы значение нужного параметра было близко к результату, полученному в стационарном режиме. В рассматриваемом случае время равно 2000 условных единиц. В теле цикла вычисляются параметры системы в моменты прихода требований. Цикл заканчивается либо по истечении времени, либо после потери первого требования. На выходе модель выдаёт искомое значение дохода.

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



Рисунок 4. Блок схема имитационной модели

2.3 Решение задачи оптимизации

Решение задачи оптимизации (1), (2) производится на примере отделения службы помощи в чрезвычайных ситуациях города И. В ходе исследования была изучена работа службы путём опроса работников. На основе собранной информации, можно утверждать, что функционирование рассматриваемого отделения не противоречит сделанным ранее предположениям относительно математической модели системы, изучаемой в данной работе. Также были взяты данные, на основе которых получены параметры системы. Таким образом, рассматривается система массового обслуживания с нетерпеливыми клиентами и бесконечной очередью со следующими параметрами: л = 0.345 1/ч, µ = 0.342 1/ч и 1/ч. Параметры дохода: С1 = -5 тыс. руб., С2 = -0.066 тыс. руб./час, С3 = -0.417 тыс.руб./час, С4 = -15 тыс.руб.

Для решения задачи (1) необходимо при помощи результатов, полученных в 3.1 и 3.2, рассчитать значения критериев для разного количества каналов. Результаты работы программ (Приложение 1,2) для удобства представлены в таблице 1.

Таблица 1.

n	1	2	3	4	5	6	7	8	9
	14.8	42.6	156.1	678.8	1605.3	1970.8	2040.8	2040.8	2040.8
	-29.4	-83	-258	-1168.8	-3103.4	-3980.1	-4049.7	-4075.3	-4066.6

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

Рисунок 5. Зависимость критериев от количества каналов

Далее была построена зависимость двух критериев (рис. 6). Как видно из графиков, между критериями существует обратная зависимость: при увеличении значений времени, доход начинает падать и наоборот. Это говорит о том, что вся область является не улучшаемой или Парето-оптимальной.

Рисунок 6. Зависимость критериев

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

Рисунок 7. Отшкалированный график зависимости



Как видно на графике, наилучшей альтернативой в данном случае является точка (1,1), поскольку она соответствует максимуму критериев. Далее при помощи программного кода было вычислено расстояние от каждой из точек до «идеальной» (Приложение 3). По результатам вычислений, наименьшее расстояние до идеальной альтернативы имеет точка, соответствующая 4 каналам обслуживания. Таким образом, при помощи метода «идеальной точки» было установлено, что 4 канала обслуживания является оптимальным для системы с заданными параметрами.

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

,

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

Рисунок 8. Целевая функция для весов (0.5, 0.5)

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

Однако задача решается для службы, в которой критерий среднего времени до ухода первого нетерпеливого клиента является более значимым. В таком случае целесообразно решить задачу тем же методом, но при большем весе критерия времени. Ниже представлены график (рис. 9) целевой функции для весовых коэффициентов (0.6, 0.4), где первая компонента - вес времени, а вторая - вес дохода.

Рисунок 9. Целевая функция для весов (0.6, 0.4)

Как можно заметить, при увеличении влияния критерия времени, максимум функции достигается на 7 каналах. Такой же результат будет и при увеличении весового коэффициента времени до 0.7. Это говорит о том, что при рассмотрении критерия времени в качестве основного, 7 каналов является оптимальным.

Далее решим задачу оптимизации с использованием критерия среднего удельного дохода (2). При помощи программы (Приложение 4), которая подсчитывает доход по формулам (4), (5) и (6), были получены значения математического ожидания дохода в стационарном режиме (табл.2).

Таблица 2.

n	1	2	3	4	5	6	7	8	9
	-1.3	-1.48	-1.74	-1.89	-1.98	-2.05	-2.12	-2.19	-2.25

График зависимости критериев представлен на рисунке 10.

Рисунок 10. Зависимость критериев

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

Воспользуемся методом «идеальной» точки для нахождения оптимального количества каналов. В данном случае «идеальной» будет также точка (1, 1). Согласно результатам работы программы для расчёта расстояния (Приложение 3), было получено, что наименьшее расстояние до «идеальной» имеет точка, соответствующая 5 каналам обслуживания.



Рисунок 11. Отшкалированный график зависимости

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

Рисунок 12. Целевая функция для весов (0.5, 0.5) и (0.6, 0.4)

Анализ результатов

Для начала оценим корректность работы имитационной модели путём сравнения эмпирических и теоретических результатов. Для этого рассчитаем значения времени и дохода для различных начальных состояний state, с параметрами системы, которые использовались для решения задачи оптимизации. Затем подставим в системы (7) и (14) рассчитанные значения и проверим, являются ли они решением. Запишем системы для параметров из пункта 3.3. и количества каналов n=2:

,

,

Значения критериев были получены при помощи программы (Приложение 1, 2) при изменении состояния State. Результаты подсчёта значений представлены в таблице 3.

Таблица 3.

	0	1	2	3	4	5
	41.28	38.4	31.7	16.81	7.84	2
	-73.2	-72.8	-67.76	-45.346	-32.1	-22.8

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

Согласно результатам применения метода «идеальной» точки к полученным значениям при решении задачи (1), оптимальным является 4 канала. Такой же результат показал и метод свёртки критериев при весовых коэффициентах б=(0.5, 0.5). Вспомним, что данная задача решалась для реальной системы массового обслуживания - службы помощи в чрезвычайных ситуациях, которая на момент исследования располагала тремя машинами. Результат двух методов оптимизации показал, что для данной системы будет лучше увеличить количество каналов до 4. В этом случае среднее время до ухода первого нетерпеливого клиента равно 678.8 часов при расходах 1168.8 тысяч рублей. Также если принять во внимание результат метода свёртки критериев при коэффициентах (0.6, 0.4), структура данной системы будет наилучшей при количестве каналов равном 7. В этом случае среднее время до ухода первого нетерпеливого клиента достаточно большое при минимальных затратах.

Интересными показались результаты оптимизации с использованием критерия среднего удельного дохода. Значения, полученные при помощи разных методов, не совпали: первый метод показал, что 5 является оптимальным числом каналов, второй метод показал, что оптимальное число каналов - 6. Причём результат второго метода не меняется при увеличении коэффициента при критерии времени. Различие в полученных значениях допустимо, поскольку методы основаны на разных подходах. В рассматриваемой ситуации целесообразно выбрать 6 каналов, поскольку время является более важным критерием для служб экстренной помощи.

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

В рамках этой главы были получены следующие результаты:

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

Посчитаны значения критериев для разного числа каналов при помощи имитационного моделирования;

Решена задача оптимизации для системы с конкретными параметрами несколькими способами;



Заключение

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

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

Разработана имитационная модель для вычисления критериев;

Проверена корректность полученной модели путём сравнения теоретических и эмпирических результатов;

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

Решена задача оптимизации для данной системы несколькими методами и предложены варианты оптимизации её структуры;

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

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

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



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

1. Wallace Agyei, Christian Asare-Darko, Frank Odilon. Modeling and Analysis of Queuing Systems in Banks: (A case study of Ghana Commercial Bank Ltd. Kumasi Main Branch) // International Journal of Scientific & Technology Research. 2015. №4. стр. 160-163.

2. Yousaf Ali, Muhammad Bilal, Muhammad Asees Awan, Jehangir Khan. Optimization of Emergency Procedure in Hospitals: Peshawar City a Case in Point // Professional Trends in Industrial and Systems Engineering. 2018. Стр. 300-319.

3. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания. М.: Высшая школа, 1982.

4. Вентцель Е.С. Теория вероятностей. М.: Высшая школа, 1999.-- 576 c.

5. Трахтенгерц Э.А. Компьютерная поддержка принятия решений. М.: СИНТЕГ, 1998. С. 396.

6. Ногин В.Д. Линейная свертка критериев в многокритериальной оптимизации // Искусственный интеллект и принятие решений. 2014. № 4. С. 73-82.

7. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и её инженерные приложения: учебное пособие для студентов вузов. М.: Высшая школа, 2000.

8. Загонова Е.А. Вычисление среднего времени до ухода заданного числа нетерпеливых клиентов из очереди в марковской системе массового обслуживания. М.: Высшая школа экономики, 2019.



Приложение

Реализация имитационной модели для подсчёта критерия времени

Реализация имитационной модели для подсчёта критерия дохода



Вычисление расстояний до «идеальной» точки

Вычисление среднего удельного дохода в стационарном режиме

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