Принятие решений в СМО

Министерство общего и профессионального образования Российской Федерации Волгоградский государственный технический университет Кафедра САПР и ПК Семестровая работа по теории принятия решений Принятие решений в системах массового обслуживания.Выполнила Любимова Ольга Группа ИВТ-365 Проверила Заболеева-Зотова А.В. Волгоград 2004г. Содержание 1. Введение 2. Классификация СМО, их основные элементы, принятие решений 3. Обслуживание с ожиданием . 4. Определение стационарного решения . 5. Выводы 6. Список использованных материалов 31 Введение Во многих областях практической деятельности человека мы сталкиваемся с необходимостью пребывания в состоянии ожидания.

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

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

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

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

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

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

Исследование ситуации всегда производится с точки зрения интересов одного человека основного субъекта, которого называют лицом, принимающим решение ЛПР. Процесс подготовки и принятия решений ЛПР, организация их выполнения и контроля составляют сущность управления операцией. Управление - есть процесс формирования рационального разумно обоснованного поведения исследуемых систем в данных ситуациях. Основная цель управления состоит в том, чтобы обеспечить максимальную эффективность использования активных средств в операции при решении поставленной задачи. ЛПР управляет операцией в доступных ему пределах, выбирая стратегии из их допустимого множества.

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

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

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

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

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

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

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

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

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

Т. е. человек со сломанной рукой вряд ли пойдет к окулисту, значит вероятность попадания такого больного на прием окулиста 0,00001. Из выбора классических критериев критерии Минимакса, Байеса-Лапласа, Сэвиджа предпочтителен скорее всего критерий Байеса-Лапласа матрица решений eij дополнится одним столбцом, содержащим математическое ожидание значений каждой из альтернатив.

Выбирается же решения варианты, в строках которых стоят наибольшие значения этого столбца. Из производных критериев критерии Гурвица, Ходжа-Лемана, Гермейера в условиях наличия экспертной группы можно с достаточно малым риском применить критерий Гурвица где величину С-весовой множитель степени оптимизма, будет определять эксперт, либо Ходжа-Лемана где v-степень доверия решению, будет определять экспертная группа.

Для критерия Гурвица формула расчета будет выглядеть так ir ij 1- C ij , Для критерия Ходжа-Лемана рассчитывается решение по формуле ir n 1-n ir, 0 n 1. В системах с отказами поступившее требование, застав все устройства занятыми, покидает систему. Классическим примером системы с отказами может служить работа сотовой телефонной станции. В этом случае решением будет подключить оптимальное количество распределительных станций, чтобы сократить количество отклоненных заявок.

Здесь возможен однократный расчет, исключающий риск, как самый простой в реализации минимаксный критерий eir ir, В системах смешанного типа поступившее требование, застав все устройства занятыми, становятся в очередь и ожидают обслуживания в течение ограниченного времени. Не дождавшись обслуживания в установленное время, требование покидает систему. Пусть организуется работа общественного транспорта в новом городе с сетью предприятий, жилыми массивами и т.д. Необходимо в этой ситуации принять решения по каким маршрутам и какие транспортные средства направить В каких местах сделать остановки, как изменять частоту следования машин в зависимости от времени суток Определить приемлемую стоимость проезда и т. п. Опять, неправильный, вернее не совсем оптимизированный, вариант решения может повлиять на жизнь всего города.

Конечно, и в этом случае можно принять решение на основе интуиции эксперта ЛПР, но гораздо разумнее будут решения, если они будут подкреплены математическими расчетами.

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

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

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

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

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

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

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

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

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

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

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

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

При показательном законе распределения времени обслуживания вероятность события, что время обслуживания продлиться не более чем t, равна где v - интенсивность обслуживания одного требования одним обслуживающим устройством, которая определяется из соотношения , 1 где - среднее время обслуживания одного требования одним обслуживающим устройством. Следует заметить, что если закон распределения времени обслуживания показательный, то при наличии нескольких обслуживающих устройств одинаковой мощности закон распределения времени обслуживания несколькими устройствами будет также показательным где n - количество обслуживающих устройств. Важным параметром СМО является коэффициент загрузки, который определяется как отношение интенсивности поступления требований к интенсивности обслуживания v. 2 где a - коэффициент загрузки - интенсивность поступления требований в систему v - интенсивность обслуживания одного требования одним обслуживающим устройством.

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

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

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

Обслуживание с ожиданием

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

Определение стационарного решения

д. Из формул 18 и 19 следует, что поэтому при m 22 Само собой разумеется,... Формула 22 позволяет находить все интересующие числовые характеристики... Найдем среднюю потерю времени требованиями, пришедшими в систему обслу... Выводы В этой работе я постаралась раскрыть понятия, приводящие к сист...

Список использованных материалов

Список использованных материалов. А. Москва, 1982г. 3. www.iu5.bmstu.ru Модели теории массового обслуживания для описания пол...