Задачи целочисленного программирования. Метод Гомори. 9 страница

(85)

Среднее число обслуживаемых заявок определяется формулой:

(86)

Отличие такой СМО от СМО, рассмотренной выше, состоит в том, что время ожидания обслуживания, когда заявка находится в очереди, считается случайной величиной, распределённой по показательному закону с параметром , где – среднее время ожидания заявки в очереди, а – имеет смысл интенсивности потока ухода заявок из очереди. Граф такой СМО изображён на рисунке 9.

Рисунок 97. – граф многоканальной СМО с ограниченной очередью и ограниченным временем ожидания в очереди

Остальные обозначения имеют здесь тот же смысл, что и в подразделе.

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

Рисунок 98

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

,

Рисунок 99.

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

(87)

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

(88)

Относительная пропускная способность:

(89)

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

(90)

Среднее число заявок, находящихся в очереди, находится по формуле и равно:

(91)

Среднее число заявок, обслуживаемых в СМО, находится по формуле и равно:

(92)

Среднее время пребывания заявки в СМО складывается из среднего времени ожидания в очереди и среднего времени обслуживания заявки:

(93)

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

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

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

Такие случайные процессы называются процессами без последствия, или Марковскими, в которых при фиксированном настоящем будущее состояние СМО не зависит от прошлого. Случайный процесс, протекающий в системе, называется Марковским случайным процессом, или «процессом без последствия», если он обладает следующим свойством: для каждого момента времени t₀ вероятность любого состояния t > t₀ системы S_i, - в будущем (t >t_Q) зависит только от ее состояния в настоящем (при t = t₀) и не зависит от того, когда и каким образом система пришла в это состояние, то есть оттого, как развивался процесс в прошлом.

Такие Марковские случайные процессы делятся на два класса: процессы с дискретными и непрерывными состояниями. Процесс с дискретными состояниями возникает в системах, обладающих только некоторыми фиксированными состояниями, между которыми возможны скачкообразные переходы в некоторые, заранее не известные моменты времени. Теперь рассмотрим пример процесса с дискретными состояниями. В офисе фирмы имеются два стационарных телефона. Возможны только следующие состояния у этой системы обслуживания: S_o-телефоны свободны; S_l - один из телефонов занят; S₂- оба телефона заняты.

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

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

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

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

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

Теперь рассмотрим математическое описание Марковского случайного процесса с дискретными состояниями системы S_o, S_l,S₂ и с непрерывным временем. Полагаем, что все переходы системы массового обслуживания из состояния S_i в состояние Sj происходят под воздействием самых простейших потоков событий с интенсивностями л_ij, а обратный переход под воздействием другого потока л_ij,. Введем обозначение p_i как вероятность того, что в момент времени t система находится в состоянии S_i. Для любого момента времени t справедливо записать нормировочное условие - сумма вероятностей всех состояний равна 1:

₂ Уp_i(t)=p₀(t)+ p₁(t)+ p₂(t)=1 (94)

ⁱ⁼⁰

Теперь проведем анализ системы в момент времени t, задав малое приращение времени Дt, и найдем вероятность р₁ (t + Дt) того, что система в момент времени (t + Дt) будет находиться в состоянии S₁ которое достигается разными вариантами:

а) система в момент t с вероятностью p₁(t) находилась в состоянии S₁ и за малое приращение времени Дt так и не перешла в другое соседнее состояние ни в S₀, ни b S₂. Вывести систему из состояния S₁ можно суммарным простейшим потоком c интенсивностью (л₁₀ + л₁₂), поскольку суперпозиция простейших потоков и также является простейшим потоком. Тогда на этом основании вероятность выхода из состояния S₁ за малый промежуток времени Д t приближенно равна (л₁₀ + л₁₂)* Д t. И тогда вероятность невыхода из этого состояния равна [1 -(л₁₀ +л₁₂)* Д t]. B соответствии с этим вероятность того, что система останется в состоянии Si на основании теоремы умножения вероятностей, равна:

p₁(t) [1 - (л₁₀ + л₁₂)* Д t]; (95)

б) система находилась в соседнем состоянии S_o и за малое время Д t перешла в состояние S_o. Переход системы происходит под воздействием потока л₀₁ с вероятностью, приближенно равной л₀₁Д t

Вероятность того, что система будет находиться в состоянии S₁, в этом варианте равна p_o(t) л ₀₁ Д t;

в) система находилась в состоянии S₂ и за время Д t перешла в состояние S₁ под воздействием потока интенсивностью л ₂₁ с вероятностью, приближенно равной л₂₁Д t. Вероятность того, что система будет находиться в состоянии S₁, равна p₂(t) л₂₁Д t.

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

p₂(t + Дt)= p₁(t) [1 -(л₁₀ + л₁₂)* Д t] + p_o(t) л ₀₁ Д t + p₂(t) л₂₁Д t , (96)

которое можно записать иначе:

p₂(t + Дt)- p₁(t)/ Д t = p_o(t) л ₀₁ + p₂(t) л₂₁- p₁(t) (л₁₀ + л₁₂) . (97)

Переходя к пределу при Дt -> 0, приближенные равенства перейдут в точные, и тогда получим производную первого порядка

dp₂/dt = p₀ л ₀₁ + p₂ л₂₁ -p₁ (л₁₀ + л₁₂) , (98)

что является дифференциальным уравнением.

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

dp₀ /dt = p₁ л ₁₀ , (99)

dp₁ /dt = p₀ л ₀₁ +p₂ л₂₁ -p₁ (л₁₀ +л₁₂) , (100)

dp₂ /dt= p₁ л ₁₂ +p₂ л_{21 . (101)}

Однако для составления уравнений Колмогорова существуют общие правила.

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

Если предельная вероятность состояния S₀ - равна p₀ ⁼ 0,2, то, следовательно, в среднем 20% времени, или 1/5 рабочего времени, система находится в состоянии S_o. Например, при отсутствии заявок на обслуживание к = 0, р₀ = 0,2,; следовательно, в среднем 2 ч в день система находится в состоянии S_o и простаивает, если продолжительность рабочего дня составляет 10 ч.

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

Такую систему уравнений составляют по размеченному графу состояний СМО по следующим правилам: слева от знака равенства в уравнении стоит предельная вероятность р_i рассматриваемого состояния Si умноженная на суммарную интенсивность всех потоков, выводящих (выходящие стрелки) изданного состояния S_i систему, а справа от знака равенства сумма произведений интенсивности всех потоков, входящих (входящие стрелки) в состояние Si систему, на вероятность тех состояний, из которых эти потоки исходят. Для решения подобной системы необходимо добавить еще одно уравнение, определяющее нормировочное условие, поскольку сумма вероятностей всех состояний СМО равна 1: _n

Уp_i(t) = 1 (102)

ⁱ⁼¹

Например, для СМО, имеющей размеченный граф из трех состояний S_o, S₁, S₂, система уравнений Колмогорова, составленная на основе изложенного правила, имеет следующий вид:

Для состояния S_o> p₀ л ₀₁ = p₁ л _{10 (103)}

Для состояния S₁> p₁ (л₁₀ +л₁₂) = p₀ л ₀₁ +p₂ л_{21 (104)}

Для состояния S₂> p₂ л₂₁ = p₁ л _{12 (105)}

p₀ +p₁ +p₂ =1 (106)

dp ₄(t) /dt= л₃₄ p₃(t) - л₄₃ p₄(t) , (107)

p₁(t) + p₂(t) + p₃(t) + p₄(t) = 1 . (108)

К этим уравнениям надо добавить еще и начальные условия. Так например, если при t = 0 система S находится в состоянии S_1, то начальные условия можно записать так:

p₁(0)=1, p₂(0)= p₃(0)= p₄(0)=0 . (109)

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

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

p_i(t), p₂(t),…., p_n(t) . (110)

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

lim p_i(t) = p_i (i=1,2,…,n) ; t>? (111)

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

Вычислить предельные вероятности состояния р_i можно, если в системе положить все производные равными 0, поскольку в уравнениях Колмогорова при t-> ? зависимость от времени пропадает. Тогда система дифференциальных уравнений превращается в систему обычных линейных алгебраических уравнений, которая совместно с нормировочным условием и позволяет вычислить все предельные вероятности состояний.

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

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

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

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

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

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

Например, особенностями показателей СМО с отказами являются: время ожидания заявок в очереди Т_оч=0, поскольку по своей природе в таких системах существование очереди невозможно, то L_оч=0 и, следовательно, вероятность ее образования Р_оч=0. По числу заявок k определятся режим работы системы, ее состояние: при k=0 - простой каналов, при 1<k<n - обслуживание заявок, при k>n - обслуживание и отказ. Показателями таких СМО являются вероятность отказа в обслуживании Р_отк, вероятность обслуживания Р_обс, среднее время простоя канала t_пр, среднее число занятых n_з и свободных каналов n_св, среднее обслуживания t_обс, абсолютная пропускная способность А.

Для СМО с неограниченным ожиданием характерно, что вероятность обслуживания заявки Р_обс=1, поскольку длина очереди и время ожидания начала обслуживания не ограничены, т.е. формально L_оч>? и Т_оч>?. В системах возможны следующие режимы работы: при k=0 наблюдается простой каналов обслуживания, при 1<k?n - обслуживание и при k>n - обслуживание и очередь. Показателями таких эффективности таких СМО являются среднее число заявок в очереди L_оч, среднее число заявок в системе k, среднее время пребывания заявки в системе Т_смо, абсолютная пропускная способность А.

В СМО с ожиданием с ограничением на длину очереди, если число заявок в системе k=0, то наблюдается простой каналов, при 1<k?n- обслуживание, при n<k<n+m - обслуживание и очередь и при k>n+m- обслуживание, очередь и отказ в ожидании обслуживания. Показателями эффективности таких СМО являются вероятность отказа в обслуживании Р_отк - вероятность обслуживания Р_обс, среднее число заявок в очереди L_оч, среднее число заявок в системе L_смо среднее время пребывания заявки в системе Т_смо, абсолютная пропускная способность А.

Таким образом, перечень характеристик систем массового обслуживания можно представить следующим образом: среднее время обслуживания - t_обс; среднее время ожидания в очереди - Т_оч; среднее пребывания в СМО - Т_смо; средняя длина очереди - L_оч; среднее число заявок в СМО- L_смо; количество каналов обслуживания - n; интенсивность входного потока заявок - л; интенсивность обслуживания - м; интенсивность нагрузки - с; коэффициент нагрузки - б; относительная пропускная способность - Q; абсолютная пропускная способность - А; доля времени простоя в СМО - Р₀; доля обслуженных заявок - Р_обс; доля потерянных заявок - Р_отк, среднее число занятых каналов - n_з; среднее число свободных каналов - n_св; коэффициент загрузки каналов - К_з; среднее время простоя каналов - t_пр.

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

Это часто связано с решением вопросов согласованной работы всей цепочки или совокупностей СМО.

Например, в коммерческой деятельности обязательно необходимо учитывать еще и экономические показатели СМО: общие затраты - С; издержки обращения - С_ио, издержки потребления - С_ип, затраты на обслуживание одной заявки - С₁, убытки, связанные с уходом заявки, - С_у1, затраты на эксплуатацию канала - С_к, затраты простоя канала - С_пр, капитальные вложения - С_кап, приведенные годовые затраты - С_пр, текущие затраты - С_тек, доход СМО в единицу времени - Д₁

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

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

С= (С_ио+С_ип) >min (112)

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

С={(С_прn_св+С_экзn_з) + С_очР_обсл (Т_оч + t_обс) + С_изР_откл}>min. (113)

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

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

С={С_экзn_з+C_пр(n-n _з)+C_отк*Р_отк*л+С_сист* n_з}>min (114)

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

К_об=[(З_пу*К_у)+(З_пв*К_в)+(З_пд*К_д)+(З_пз*К_з)+(З_по*К₀)+(З_кт*К_кт)]*К_мп, (115)

где З_пу - значимость показателя устойчивости ассортимента товаров;

К_у - коэффициент устойчивости ассортимента товаров;

З_пв - значимость показателя внедрения прогрессивных методов продажи товаров;

К_в - коэффициент внедрения прогрессивных методов продажи товаров;

З_пд - значимость показателя дополнительного обслуживания;

К_д - коэффициент дополнительного обслуживания;

З_пз - значимость показателя завершенности покупки;

К_з - коэффициент завершенности покупки;

З_по - значимость показателя затрат времени на ожидание в обслуживании;

К_о - показатель затрат времени на ожидание обслуживания;

З_кт - значимость показателя качества труда коллектива;

К_кт - коэффициент качества труда коллектива;

К_мп - показатель культуры обслуживания по мнению покупателей;

Для анализа СМО, конечно, можно выбирать и другие критерии оценки эффективности работы СМО. Например, в качестве такого критерия для систем с отказами можно выбирать вероятность отказа Р_отк, значение которого не превышало бы какой то заранее заданной величины. Например, требование Р_отк<0,1 означает, что не менее чем в 90% случаев система будет справляться с обслуживанием потока заявок при заданной интенсивности л. Можно также ограничить среднее время пребывания заявки в очереди или в системе. В качестве показателей, которые должны подлежать определению, могут выступать: либо число каналов n при заданной интенсивности обслуживания м, либо интенсивность м при заданном числе каналов.

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