Задача оптимизациии для систем массового обслуживания

      Казахский национальный университет им.Аль-Фараби

                                              Механико-математический факультет

                                                     “Информационные системы ”

 

 

 

 

 

 

 

 

 

 

  Реферат

    На тему: «Задача оптимизации для       

        систем массового  обслуживания»

 

 

 

 

 

                                                                      

                                                                            

                                                                                 Подготовил: Шамшинуров А.Б

                                                                                  Проверил: Белогуров А.П

                                                                                                                  E-MAIL:  aibels@ok.kz

 

 

 

 

                                                        

                                                               Алматы 2012             

                                    Содержание

Введение…………………….……………………………………………...…..3

Многоканальная СМО  с отказами……….…..…………….…..…...…………5

Основы теории массового  обслуживания.……………………………..…....10

Понятие случайного процесса……………..…....…………………………....10

Марковский случайный  процесс..…………..…..…………………………....11

Потоки событий…..……………..……………………….…………………....12

Уравнения Колмогорова для вероятностей состояний. …………………....13

Задачи теории массового  обслуживания …………………………………....16

Одноканальная СМО с  отказами…………………………..………………....18

Возможные постановки задач оптимизации n – канальных СМО с отказами

….………………………………………………………………………….…....23

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

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

Задача теории массового обслуживания – установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что заявка будет обслужена; математического ожидания числа обслуженных заявок и т.д.), от входных показателей (количества каналов в системе, параметров входящего потока заявок и т.д.). Результирующими показателями или интересующими нас характеристиками СМО являются – показатели эффективности СМО, которые описывают, способна ли данная система справляться с потоком заявок.

Системы массового обслуживания могут быть одноканальными или многоканальными.

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

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

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

Задача оптимизации  – задача выбора из множества возможных  вариантов наилучшего, оптимального. Оптимизация – от латинского слова  «оптимус» - наилучший – поиск  наилучшего, поиск наилучшего проектного изделия.

Каждая задача оптимизации  обязательно должна иметь три компоненты:

неизвестные (что ищем, то есть, план);

ограничение на неизвестные (область поиска);

целевая функция (цель, для которой ищем экстремум).

Математическая модель, та которая определена с помощью  математических формализмов. Математическая модель не является точной, а является идеализацией.

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

Выявление основных особенностей, взаимосвязей и количественных закономерностей

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

Важным параметром функционирования СМО является также среднее число  требований, находящихся в системе N_syst, то есть в очереди на обслуживание, а также средняя длина очереди N_och. Исходными параметрами, характеризующими систему массового обслуживания, являются: число каналов обслуживания - n; число требований - m; интенсивность поступления одного требования на обслуживание - λ, то есть число поступлений требований в единицу времени; интенсивность обслуживания требований - μ.

Многоканальная  СМО с отказами

Рассмотрим n-канальную  СМО с отказами. Будем нумеровать состояния системы по числу занятых  каналов (или, что в данном случае то же, по числу заявок, связанных  с системой). Состояния будут: 
S₀ - все каналы свободны, S₁ - занят ровно один канал, остальные свободны,

S_k - заняты ровно k каналов, остальные свободны, S_n - заняты все n каналов.

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

 

Рис.1

 

Если система находиться в состоянии S_k (занято k каналов) и пришла новая заявка, система переходит (перескакивает) в состояние S_k+1

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

Пусть система находиться в состоянии S₁ (занят один канал). Тогда, как только закончиться обслуживание заявки, занимающей этот канал, система перейдет в S₀; значит, поток событий, переводящий систему по стрелке S₁ ® S₀, Имеет интенсивность m. Очевидно, если обслуживанием занято два канала, а не один, поток обслуживаний, переводящий систему по стрелке S₂ ® S₁, будет вдвое интенсивнее (2m); если занято k каналов - в k раз интенсивнее (km). Проставим соответствующие интенсивности у стрелок, ведущих справа налево.

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

Пользуясь общими правилами, можно  составить уравнения Колмогорова  для вероятностей состояний:

(1)

Уравнения (1) называются уравнениями Эрланга. Естественными начальными условиями для их решения являются:

p₀(0)=1; p₁(0)=p₂(0)=...=p_n(0)=0 (в начальный момент система свободна).

Интегрирование системы уравнений (1) в аналитическом виде довольно сложно; на практике такие системы дифференциальных уравнений обычно решаются численно, на ЭВМ. Такое решение дает нам все вероятности состояний p₀(t), p₁(t),..., p_n(t) как функции времени.

Естественно, нас больше всего будут  интересовать предельные вероятности  состояний p₀ , p₁ ,..., p_k ,..., p_n, характеризующие установившийся режим работы СМО (при t ® ¥). Для нахождения предельных вероятностей воспользуемся уже готовым решением задачи, полученным для схемы гибели и размножения. Согласно этому решению,

(2)

В этих формулах интенсивность  потока заявок l и интенсивность  потока обслуживаний (для одного канала) m не фигурируют по отдельности, а входят только своим отношением l /m. Обозначим это отношение l /m=r и будем называть величину r "приведенной интенсивностью" потока заявок. Физический смысл ее таков: величина r представляет собой среднее число заявок, приходящих в СМО за среднее время обслуживания одной заявки.

С учетом этого обозначения, формулы (2) примут вид:

(3)

Формулы (3) называются формулами  Эрланга. Они выражают предельные вероятности  всех состояний системы в зависимости  от параметров l, m и n (l - интенсивность потока заявок, m - интенсивность обслуживания, n - число каналов СМО).

Зная все вероятности состояний p₀ , p₁ ,..., p_k ,..., p_n, можно найти характеристики эффективности СМО: относительную пропускную способность q, абсолютную пропускную способность А и вероятность отказа P_отк.

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

(4)

Вероятность того, что  заявка будет принята к обслуживанию (она же относительная пропускная способность q) дополняет P_отк до единицы:

(5)

Абсолютная пропускная способность:

(6)

Одной из важных характеристик  СМО с отказами является среднее  число занятых каналов (в данном случае оно совпадает со средним  числом заявок, находящихся в системе). Обозначим это среднее число k^-.

Величину k^- можно вычислить непосредственно через вероятности p₀ , p₁,..., p_n по формуле:

(7)

как математическое ожидание дискретной случайной величины, принимающей значения 0,1,...,n с вероятностями p₀ , p₁,..., p_n. однако значительно проще выразить среднее число занятых каналов через абсолютную пропускную способность А, которую мы уже знаем. Действительно, А есть не что иное, как среднее число заявок, обслуживаемых в единицу времени; один занятый канал обслуживает в среднем за единицу времени m заявок; среднее число занятых каналов получится делением А на m:

или, переходя к обозначению l/m = r,

(8)

[5], [6].

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

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

 Рассмотрим подробнее математическую  модель работы поста ГИБДД  как системы массового обслуживания. Для решения задачи было принято  допущение, что очередь клиентов  ограничена, и, следовательно, данная  модель является СМО с ограниченной очередью, где n – количество каналов обслуживания. Также принимаем допущение, что все потоки событий (случайные события) в системе являются Марковскими. Напомним, что случайный процесс, протекающий в системе, называется Марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние.