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

Задачи целочисленного программирования. Метод Гомори. 9 страница - student2.ru (85)

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

Задачи целочисленного программирования. Метод Гомори. 9 страница - student2.ru (86)

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

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

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

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

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

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

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

Рисунок 98

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

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

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

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

Рисунок 99.

где Задачи целочисленного программирования. Метод Гомори. 9 страница - student2.ru . Вероятность образования очереди определяется формулой:

Задачи целочисленного программирования. Метод Гомори. 9 страница - student2.ru (87)

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

Задачи целочисленного программирования. Метод Гомори. 9 страница - student2.ru (88)

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

Задачи целочисленного программирования. Метод Гомори. 9 страница - student2.ru (89)

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

Задачи целочисленного программирования. Метод Гомори. 9 страница - student2.ru (90)

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

Задачи целочисленного программирования. Метод Гомори. 9 страница - student2.ru (91)

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

Задачи целочисленного программирования. Метод Гомори. 9 страница - student2.ru (92)

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

Задачи целочисленного программирования. Метод Гомори. 9 страница - student2.ru (93)

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

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

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

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

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

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

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

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

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

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

Теперь рассмотрим математическое описание Марковского случайного процесса с дискретными состояниями системы So, Sl,S2 и с непрерывным временем. Полагаем, что все переходы системы массового обслуживания из состояния Si в состояние Sj происходят под воздействием самых простейших потоков событий с интенсивностями лij, а обратный переход под воздействием другого потока лij,. Введем обозначение pi как вероятность того, что в момент времени t система находится в состоянии Si. Для любого момента времени t справедливо записать нормировочное условие - сумма вероятностей всех состояний равна 1:

2 Уpi(t)=p0(t)+ p1(t)+ p2(t)=1 (94)

i=0

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

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

p1(t) [1 - (л10 + л12)* Д t]; (95)

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

Вероятность того, что система будет находиться в состоянии S1, в этом варианте равна po(t) л 01 Д t;

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

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

p2(t + Дt)= p1(t) [1 -(л10 + л12)* Д t] + po(t) л 01 Д t + p2(t) л21Д t , (96)

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

p2(t + Дt)- p1(t)/ Д t = po(t) л 01 + p2(t) л21- p1(t) (л10 + л12) . (97)

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

dp2/dt = p0 л 01 + p2 л21 -p110 + л12) , (98)

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

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

dp0 /dt = p1 л 10 , (99)

dp1 /dt = p0 л 01 +p2 л21 -p11012) , (100)

dp2 /dt= p1 л 12 +p2 л21 . (101)

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

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

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

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

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

Уpi(t) = 1 (102)

i=1

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

Для состояния So> p0 л 01 = p1 л 10 (103)

Для состояния S1> p11012) = p0 л 01 +p2 л21 (104)

Для состояния S2> p2 л21 = p1 л 12 (105)

p0 +p1 +p2 =1 (106)

dp 4(t) /dt= л34 p3(t) - л43 p4(t) , (107)

p1(t) + p2(t) + p3(t) + p4(t) = 1 . (108)

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

p1(0)=1, p2(0)= p3(0)= p4(0)=0 . (109)

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

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

pi(t), p2(t),…., pn(t) . (110)

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

lim pi(t) = pi (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; абсолютная пропускная способность - А; доля времени простоя в СМО - Р0; доля обслуженных заявок - Робс; доля потерянных заявок - Ротк, среднее число занятых каналов - nз; среднее число свободных каналов - nсв; коэффициент загрузки каналов - Кз; среднее время простоя каналов - tпр.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наши рекомендации