В двух словах проблема звучит так:
в магазин (работает всего 1 продавец) каждые 2 минуты приходит покупатель, и обслуживается ровно 2 минуты. Загрузка продавца = 100%... Но это ведь не значит, что покупатель никогда не обслужится ? Вы согласны ?
А судя по формулам, которые приведены ниже, ему придется стоять в очереди целую бесконечность...

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

Дано к примеру такое:

Код

№ заявки:      1  2  3  4  5  6  7  8  9  10 ---------------------------------------------- t прихода:      1  3  5  6  8  11 12 14 17 18 ---------------------------------------------- t обслуживания: 4  4  2  5  3  4  3  2  2  4

(навсякий случай поясню, это нужно понимать так: к примеру, вторая заявка приходит в момент времени=3, и время необходимое для её обслуживания=4)...
Диаграмму работы СМО для наглядности можно посмотреть в прикрепленном рисунке, синеватый фон - промежуток времени наблюдения за СМО.

Рассматриваемая СМО работала в течении ModelTime=33 единиц времени.
Как видно из задания, в систему пришло Count=10 заявок.
Теперь элементарнейшие расчеты:

1) Считаем среднее время обслуживания:
Mean = (4+4+2+5+3+4+3+2+2+4)/10 = 33/10 = 3.3

2) Считаем интенсивность входного потока:
Lambda = Count/ModelTime = 10/33 = 0.3030303...

3) Считаем коэффициент загрузки устройства:
Ro = Lambda*Mean = 1
(что в принципе видно по диаграмме - устройство на протяжении всего времени наблюдения было занято, 100% загрузка)

4) Теперь самое интересное! Есть несколько формул расчета разных характеристик, и везде в знаметеле стоит (1-Ro) - т.е. получается деление на 0!
Например: Среднее время ожидания:

Код

Mean*Ro*(1 + C*C) w = -----------------          2*(1-Ro)

(где C=Sigma/Mean=0.34 - коэффициент вариации, Sigma=1.122 - среднеквадратичное отклонение)

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

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

Присоединённый файл ( Кол-во скачиваний: 15 )
 diag.png 7,04 Kb

Добрый день.

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

Это сообщение отредактировал(а) esperant0 - 11.6.2005, 22:42

А если я увеличу время наблюдения, ро уменьшится, будет меньше 1, тогда что ? Всё равно цифры большие получаются...
И есть ли формулы тогда для этого случая (ро=1) ?

Формулы верны, при ро=1, Среднее время ожидания равняется бесконечности

Добавлено @ 22:50
Может быть это контринтуитивно, но ни синь пороха не поделаешь.

esperant0, ну а как тогда быть с тем примером про магазин, который я привел вначале ?... Как-то нелогично, не то что уж неинтуитивно:

Цитата(p0s0l @ 11.6.2005, 22:21)

в магазин (работает всего 1 продавец) каждые 2 минуты приходит покупатель, и обслуживается ровно 2 минуты. Загрузка продавца = 100%... Но это ведь не значит, что покупатель никогда не обслужится ?  Вы согласны ? А судя по формулам, которые приведены ниже, ему придется стоять в очереди целую бесконечность...

Если бы в магазин приходил ТОЧНО один человек в минуту и он обслуживался РОВНО одну минуту - то Вы были бы правы. У нас же и время прихода и время обслуживания это пуасонновские процессы.

Интуиция связана со следующим примером.
Рассмотрим случайное блуждание на прямой.

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

Если частица находится в ноле то она делает шаг вправо на одну клетку.

На каждом шаге частица с вероятностью 0.5 делает шаг вправо на один и с такой же вероятностью влево на один.

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

Хм...
Может тогда мне что-нибудь посоветуете ?
Дело в том, что я делаю диплом по моделированию (лабораторный практикум), и там упор делается на моделирование одно- и многоканальных СМО.
Студенту даётся задание вроде такого:

Код

№ заявки:      1  2  3  4  5  6  7  8  9  10 ---------------------------------------------- t прихода:      1  3  5  6  8  11 12 14 17 18 ---------------------------------------------- t обслуживания: 4  4  2  5  3  4  3  2  2  4

Он строит диграмму (как в рисунке в первом моем сообщении):
Дальше по диаграмме он рассчитывает характеристики СМО - это просто.
Потом должен бы по идее рассчитать эти же характеристики аналитическим способом, т.е. только по исходным данным, не глядя на диаграмму... Но тут и появились эти проблемы...
Как быть ? Если я сделаю времена обслуживания заявок в среднем меньше, чем промежутки между прибытиями заявок (Ro будет меньше 1) - это дело спасёт ?

И так, поправте меня если я не прав.

Исходные данные:

Имеется однокональная система с одним продавцом и бесконечной очередью. М\М\1

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

Количество покупателей приходящих за одну минуту распределено по Пуасону с параметром 0.5, т.е в среднем в две минуты приходит один покупатель.

Имеется также набор наблюдений над системой - Ваша таблица и диаграмма.

Требуется:
Дать оценки параметров системы с помощью эксперементальных данных - таблицы.

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

Правильно ли я Вас понял

Цитата(esperant0 @ 11.6.2005, 23:36)

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

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

Т.е. дана только таблица наблюдений, больше нет никаких известных данных...

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

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

Иначе аналитичиские подсчеты не уместны.

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

Данные отличались по двум причинам

Во=первых малая выборка.
Во-вторых, чем ближе ро к единице тем больше нестабильность оценки и как следствие необходимость в больших выборках

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

Это сообщение отредактировал(а) esperant0 - 12.6.2005, 00:20

Все перепроверил, сделал выборку из 1000 человек (время наблюдения - около 3900), не из головы, а генерацией случайных чисел... Разница всё равно огромная...
Параметры:
Ro = 0.642
Среднее время обслуживания = 2.526
Среднеквадратичное отклонение = 1.203
Интенсивность входного потока = 0.254

В результате имеем:
без скобок - данные моделирования, (в скобках - аналитические данные):
Среднее время ожидания: w = 0.77 ( 2.781 )
Средняя длина очереди: 0.196 ( 0.707 )
Среднее время пребывания в магазине: 3.296 ( 5.307 )
Среднее количество покупателей в магазине: 0.838 ( 1.349 )

Ну уж слишком они различаются... Не должно быть такого...

Добавлено @ 01:24
Вот пример полного расчета на 10 покупателей - загруженность продавца примерно 70%, почти все покупатели поступают прямо на обслуживание:

Код

№ заявки:      1  2  3  4  5  6  7  8  9  10 ---------------------------------------------- t прихода:      1  3  5  8  12 14 17 19 22 26 ---------------------------------------------- t обслуживания: 2  1  3  1  3  1  2  3  1  2

(Диаграмма прикреплена к посту)

1) Среднее время обслуживания:
Mean = (2+1+3+1+...+2)/10 = 1.9

2) Среднеквадратичное отклонение времени обслуживания:
Sigma = (Sqr(2-1.9) + Sqr(1-1.9) + ... )/9 = 0.7666...

3) Коэффициент вариации:
C = Sigma / Mean = 0.404

4) Интенсивность входного потока:
Lambda = 10 / 27 = 0.37 (10 покупателей в течение 27 минут)

5) Коэффициент загрузки продавца:
Ro = Lambda * Mean = 0.704 (это соответствует диаграмме)

6) Среднее время ожидания:

Код

Mean*Ro*(1 + C*C) w = ----------------- = 2.624          2*(1-Ro)

Хотя по диаграмме далеко не 2.624... Всего 1 покупатель ждал всего 1 минуту... Т.е. w = 0.1

7) Средняя длина очереди:
Nq = Lambda * w = 0.972
По диаграмме: Nq = 0.37

8) Среднее время пребывания в магазине:

Код

Ro*(1+C*C) а) T = Mean * (1 + ----------) = 4.524                    2*(1-Ro) б) T = w + Mean = 4.524

По диаграмме: T = 2.0

9) Среднее количество покупателей в магазине:

Код

Ro*Ro*(1+C*C) а) N = Ro + ------------- = 1.675               2*(1-Ro) б) N = Lambda*T = 1.675

По диаграмме: N = 0.741

Я конечно ожидал расхождения между результатами, но не до такой же степени! T больше чем в 2 раза отличается, w - в 26 раз(!), N - в 2 раза, Nq - в 3 раза...

Присоединённый файл ( Кол-во скачиваний: 6 )
 diag.png 5,48 Kb

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


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

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

Вы уверены, что правильно генерируете величины пуасоноввского потока?

Рекомендую спросить тут:
http://www.nsu.ru/phorum/list.php?f=6
Добавлено @ 01:46
В любом случае нет смысла считать по формуле, лучше считать напрямую

Цитата

Вы уверены, что правильно генерируете величины пуасоноввского потока?

Я генерировал числа по экспоненциальному распределению.

Цитата(esperant0 @ 12.6.2005, 01:45)

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

Тут странность такая, что при увеличении числа опытов лучше не становится...

Цитата

Рекомендую спросить тут: http://www.nsu.ru/phorum/list.php?f=6

Еще подумаю, и если никто не поможет, спрошу...
Добавлено @ 01:59

Цитата(esperant0 @ 12.6.2005, 01:45)

В любом случае нет смысла считать по формуле, лучше считать напрямую

Идея состояла в том, чтобы сравнить результаты моделирования с аналитическими результатами...