Comments 102
Так пропуская покупателей вы снижаете вероятность продажи коровы, искусственно занижая пропускную способность системы.
И для того чтобы понять что время доставки можно рассматривать как случайную величину, представте, что кто-то предъявляет вам результаты работы гсч, при этом начальное заполнение и алгоритм вы не знаете. То что вы видите — случайно или нет?
Пуассонов поток нельзя "прогнозировать"!
Решение неполное, поскольку не рассмотрены стратегии заказа коров, зависящие от остатка коров.
С такой стратегией ваши времена обслуживания будут нетривиально зависеть друг от друга — и использованная вами формула будет уже неприменима.
Вообще-то, формула Эрланга требует чтобы поток был пуассоновым.
Когда я нашел это, я был счастлив как червь в яблоке.
Но какие-то коэффициенты при неизменном виде изменяться могут? А ведь в таком случае общей формулы будет уже недостаточно для нахождения оптимума.
Единица делить на ка факториал, к примеру...
Совсем ничего не меняться ничего не может. Вот вам контрпример.
Рассмотрим поток, аналогичный пуассоновому — но с тем условием, что клиенты ходят в два раза реже, зато парами. Матожидание у него такое же.
Если принять ваше утверждение о применимости формулы — получим равенство p{m}(I,T) = p{m/2}(I,2T) — что неверно.
получите что интенсивность упала до I/2 обслуживание стойла теперь стоит 2u, время обслуживания не изменилось и осталось Т.
Да, согласен, я перепутал параметры, надо мне минус за тот пример влепить...
Вот вам другой пример. Допустим, у нас есть две кассы, обслуживание на которых длится время T. И они магически связаны — если приходит клиент пока другая касса занята — новый клиент обслуживается мгновенно, а обслуживание старого затягивается еще на T. Пока T < I матожидание времени обслуживания от введения подобного правила не меняется, а вот вероятность отказа в обслуживании падает до 0, что противоречит формуле Эрланга.
Так что ваше решение рассматривает лишь стратегии, в которых случайная величина t не зависит от потока клиентов, в противном случае "время обслуживания" нельзя считать для разных коров независимым. А тот факт, что можно ограничиться лишь такими стратегиями — опять не доказан...
Чему противоречит ваша идея в классическом случае с ходу не пойму, но, похоже дело в том что есть отличная от нуля вероятность обслужиться за время 0.
Ну хорошо, не будет сокращать время обслуживания не до 0 — а до достаточно малого ε.
В таком случае, пока 1 касса занята, вторая будет давать вероятность отказа p1(I, ε), что ограничивает сверху общую вероятность отказа в обслуживании. Эта величина все еще не может быть равна p2(I, T).
стратегии заказа коров, зависящие от остатка коров
Оно и зависит: уменьшился остаток — заказали еще корову
Нет, я говорил о другой зависимости.
Навроде "последнюю корову заказываем сразу же, вторую — через секунду, третью — через две секунды". На независимые "коровы обслуживания" подобная стратегия ну никак не раскладывается, а чтобы доказать оптимальность решения — ее надо тоже рассмотреть.
Есть огромное количество стратегий, которые не имеют под собой никакого обоснования, например заказывать зависимо от фазы луны или силы ветра, и это не означает, что для доказательства необходимо расмотреть их все.
Коровы идут определенное время и откладывать их заказ — это игра в рулетку или гадание на звездах, смотря что вам больше нравится. Потому что мы понятия не имеем, сколько коров будет через время Т, любой bounce будет вырождаться либо в «заказываем как приходят клиенты только черех 3 секунды», либо «заказываем как приходят клиенты, только с все увеличивающейся задержкой», первый не нужен — лишь бессмысленное усложнение, а второй — еще и вредное, ибо со временем скушает буфер и мы будем в серьезном минусе.
Тем не менее, есть еще один фактор, неплохо поддающийся предсказанию — ожидаемое прибытие коров.
Пока что мне не удается найти способ строго доказать, что оптимальная стратегия не должна учитывать этот фактор при принятии решений на заказ коров.
Нестрого-то я ваши аргументы раз пять сам себе повторил… не помогает :)
Любая стратегия, кроме немедленного заказа после продажи, увеличивает среднее время обслуживания. Это пока единственно что точно верно. Есть гипотеза как выглядит функция r, но доказать я её не могу. Из гипотезы следует что заказывать надо сразу по факту продажи.
Тем не менее, есть еще один фактор, неплохо поддающийся предсказанию — ожидаемое прибытие коров.
Пока что мне не удается найти способ строго доказать, что оптимальная стратегия не должна учитывать этот фактор при принятии решений на заказ коров.
Очень просто — мы не можем никак повлиять на прибытие. Даже если закажем сотню прям сейчас — они не придут раньше тех, кто уже идет.
Да, но ожидаемое прибытие коров влияет на ожидаемое число коров через время T, что в свою очередь влияет на необходимость заказывать сейчас.
Попробую еще раз акцентировать. Если заказывать сразу после продажи, то (Количество коров в пуле + количество коров в пути) = m и константен. Также константен средний поток покупателей. Так почему в разные моменты времени при абсолютно одинаковых входящих данных вы хотите принять разные решение о покупке или непокупке коров?
Вы ходите кругами.
Во-первых, входные данные — неодинаковые, я уже говорил почему.
Во-вторых, фиксированность размера пула тоже было бы неплохо строго доказать.
Для независимых времен обслуживания это не столько доказано, сколько постулировано :)
Сама возможность рассматривать коров независимо друг от друга, ставя однозначное соответствие между моментов продажи и моментов заказа означает что у нас есть фиксированный пул коров.
Само понятие "время ожидания" включает в себя возможность поставить в соответствие события продажи коровы и ее покупки. Для неограниченных пулов это невозможно.
Вы ходите кругами.
Потому что вы раз за разом повторяете ту же ошибку.
Во-первых, входные данные — неодинаковые, я уже говорил почему.
Какие именно неодинаковые и как они меняются и от каких условий? Среднестатистических приход покупателя — единственные входящие данные и они не меняются
PS
Пишут как-то Ландау и Лифшиц «Электродинамику сплошных сред», ну и в одной главе получали какую-то сумасшедшую формулу с использованием максвелловского тензора напряжений в анизотропной среде. А на следующий день Лифшиц и говорит:
— Слушай, я вчера три листа выкладок в трамвае потерял.
Что делать?
— *Да ладно, — говорит Ландау, — напишем, как обычно: «откуда очевидно»...
У нас есть среднее количество людей, которые приходят за Х времени, назовем это число C(x) (customer от X). Из этого числа мы можем посчитать вероятность того, что в ближайшее время придет покупатель назовем это p(t) — какая вероятность того, что за время t придет покупатель. Важно понимать, что p(t) в пределах одних входных данных всегда одинаково. То есть даже если буквально только что от нас вышло 100500 покупателей p(t) не уменьшилось — так работает теория вероятностей. От того, что выпало 20 решек подряд — вероятность выпадения орла не увеличивается.
То есть замечу важную вещь — p(t) константно в пределах одной задачи.
Дальше. Допустим, у нас есть К коров и 0 (ноль) в пути (ситуация, с которой мы начинаем). Теперь к нам приходит покупатель, забирает одну корову и мы оказываемся в следующей ситуации:
— (К-1) коров
— 0 в пути
— p(t) вероятность прихода покупателя в ближайшее время.
На базе этих данных мы можем или принять решение о покупке, или, допустим, решение подождать некоторое время. Так вот — сколько бы мы времени не ждали, если не придет новый покупатель все входные данные для решения будут одинаковыми:
— (К-1) коров
— 0 в пути
— p(t) вероятность прихода покупателя в ближайшее время.
То есть в данном случае если ждать, то только до прихода следующего покупателя- чтоб изменились данные на основе которых принимаем решение. И тогда у нас будет ситуация:
— (К-2) коров
— 0 в пути
— p(t) вероятность прихода покупателя в ближайшее время.
Понимаете о чем я?
Вы разобрали самый простой случай. Теперь рассмотрим случай, который возникает когда мы корову таки заказали — а потом пришел другой покупатель.
У нас (K-2) коров, 1 в пути (осталось времени t1) и вероятность прихода покупателя в ближайшее время — p(t).
Вы понимаете, что эта ситуация меняется каждую секунду?
У нас было К-1 коров и мы приняли решение заказывать еще одну.
Сейчас у нас (К-2)+(1 в пути), т.е. максимум К-1 коров, то есть сейчас у нас, грубо, меньше или равно коров, чем тогда, когда мы решили заказывать.
Ситуация, когда у нас все коровы на месте и ни одной в пути — найболее стабильная, то есть нет такой ситуации при которой мы решим заказать корову при (К-1) коров, но не заказать корову при (К-2)+(1 в пути), потому что если мы заказываем корову при (К-1), значит предполагаем, что за время доставки коровы у нас выкупят (К-1), а следовательно выкупят и (К-2+1), понимаете?
О, отлично! Вот это уже похоже на правду.
Еще бы доказать, что в ситуации ((K-2)+1) нам нет смысла заказывать сразу двух коров, и лемма о фиксированном пуле и времени ожидания будет доказана.
Если время прихода коров Т, а в среднем за Т время мы продаем Н коров, то необходимо стремиться, чтобы в каждый Т отрезок времени у нас было ровно Н коров.
Во-вторых, че вы прицепились к этому пуассоновскому процессу? Вынесите его в отдельную подзадачу. Нам нужна только вероятность появления нищеброда и вероятность появления мажора.
1) Если в текущий момент времени (dSm — dSn) > (A/B) * (сколько прошло времени после последней продажи в секундах) * стоимость содержания коровы в секунду, ТО продаем только мажорам, нищебродов шлем лесом. Иначе продаем всем.
dSm — наценка для мажора
dSn — наценка для нищеброда
А — вероятность появления нищеброда.
В — вероятность появления мажора.
2) A, B уже определяете этим вашим пуассоновским процессом. Мы его выносим в отдельный «черный ящик». Тут расписывайте свои четырехэтажные формулы, сколько душе угодно.
3) Оптимальное количество коров в наличии в единицу времени = фактическое текущее (в зависимости от условия 1) количество продаж в единицу времени. Это ежу понятно. Именно этот пункт описал автор решения в данном посте. Но для поддержания оптимального количества, заказывать нужно заранее (условие 4)
4) При этом, если T (время доставки) > временного промежутка между фактическими продажами (в зависимости от условия 1), то заказывать корову нужно заранее за (T — время между продажами) до прогнозируемой продажи (опять же в зависимости от условия 1).
Всю эту систему из четырех «черных ящиков» выполняем в цикле. Вот и вся стратегия.
Вот в пункте 4 у вас и ошибка, а без него вся очевидная стратегия разваливается. Ежу тут, конечно же, все понятно, вот только… ежик иногда ошибается.
Объясняю на пальцах, последний раз. Допустим, у вас T = 1 минуте, а прогнозируемое время до следующего покупателя — 2 минуты. Вы предлагаете ждать 1 минуту перед заказом новой коровы. ОК, ждем минуту!
Подождали минуту. T у нас все еще равно 1 минуте, прогнозируемое время до следующего покупателя — все еще 2 минуты. Покупать корову или опять ждать?
Учите теорию вероятностей. Прогнозируемое время до прихода покупателя со временем не уменьшается. Потому что пуассонов поток такой вот нехороший для прогнозирования.
Приход девушки описывается не пуассоновым потоком, а нормальным распределением.
Пуассонов процесс — это самая простая модель потока покупателей, когда нам о них ничего не известно (кроме матожидания числа покупателей в единицу времени).
Так, в примере с девушкой, если бы она вам не обещала выйти через 20 минут, а все ваши знания о ней исчерпывались тем фактом, что она приходит к вам раз в сутки — адекватной моделью было бы уже не нормальное, а равномерное распределение. А если заменить этот самый раз в сутки сначала на 7 раз в неделю, потом на 30 раз в месяц, 365 раз в год и т.п. — то в пределе и получим пуассонов поток, когда девушка в среднем приходит раз в сутки, но никому ничего не обещала и предсказанию не поддается.
Почему прогнозируемое время остается 2 минуты? если мы уже подождали минуту, то и прогнозируемое время уменьшится 2 — 1 = 1 минута. Я подразумеваю, что оно динамически изменяется.
А если подождали 3 минуты, а клиента все нету, то прогнозируемое время ожидания -1 минута?
Если подождали 2 минуты, а клиента нет, то ожидание обнуляется, но при этом количество ожидаемых(планируемых) клиентов остается неизменно, а времени на их ожидание становится меньше.
Но ведь нет же. Чем меньше промежуток времени — тем меньше мат. ожидаемое кол-во клиентов. Если у вас на промежутке 60 мин. мат ожидание пришедших клиентов — 60, то подождав 2 минуты, мат ожидание вдруг не становится 60 клиентов на 58 мин.
Средние издержки поэтому будут тоже одинаковы по мат ожиданию.
Потому, что есть предметы в порядке изучения: анализ, теория меры, теория вероятностей, мат статистика, теория случайных процессов.
Кстати, что за непорядок? Второй пост длится математический мордобой — а главный математик куда-то делся… Sirion, приди!
Но, с моей точки зрения (а я именно тот мужик на базаре, только не с КРС, а скажем, так с немного другими группами товара), самая оптимальная стратегия- держать в наличии количество коров, продающееся (всем клиентам, и мажорам и нищебродам) за время доставки следующей партии (+5-10% про запас, опять же не учитывая сезонные факторы и форс-мажоры), но для этого нужна какая-никакая, но статистика.
и где наш Milfgard?
Для любой стратегии s (по модулю независимости), для которой существует среднее время доставки. Существует описанная система массового обслуживания, с тем же самым средним даставки и некоторым м, с маленкой добавкой: Надо взять ближайшую смо где вероятность отказа меньше и чуток подкрутить. Чтобы клиенту отказывали с некоторой вероятностью, даже если корова есть.
И подумать: может ли такая стратегия уменьшить расходы на коровник.
По сути, вы сказали, что идеальная стратегия в том, что нужно найти некое оптимальное m и поддерживать количество коров максимально близко к m снизу.
Но, простите, это ни о чем вообще. Вы даже близко не показали существование решения, его единственность, а также сходимость (устойчивость) алгоритма оптимизации (какого, кстати)?
Простите, вот этого места я не понял:
… время доставки коровы на освободившееся место является случайной величиной t, принимающей значения из промежутка [T,+∞) и математическим ожиданием T¯. Распределение этой величины зависит от стратегии заказа коров.
Зачем упоминать о случайной величине, если дальше используется только её матожидание?
Затем, что матожидание бывает только у случайных величин.
Если от случайной величины нужно только матожидание, то можно ограничиться случайными величинами, которые принимают некоторое значение с вероятностью 1.
С этой формулой Эрланга вообще, по-моему, какой-то цирк с конями. Нам надо найти оптимальную стратегию, но поскольку легко посчитать выигрыш мы можем только с помощью одной формулы, то оптимизировать будем лишь в классе тех стратегий, для которых эта формула применима. Таков подход?
Разумеется, нельзя упрекать человека за то, что он делает лишь то, что может, и не больше. Это низость — ругать за такое. Но надо же чётко прописывать, чтО именно сделано и какие дополнительные ограничения наложены. А у вас в тексте:
Таким образом мы получаем что исходная задача эквивалентна системе массового обслуживания
А она не эквивалентна — ровно перед этим вы сузили задачу.
Верно ли утверждение об эквивалентности исходной задачи "при заданных ограничениях" системе массового обслуживания? Может быть, я дую на воду, но я бы выразился иначе. Просто я привык, что когда говорят об ограничениях в задаче, то имеются в виду ограничения в условиях (ну, например, в данном случае: классов покупателей всего два и они встречаются равновероятно, то есть мощности соответствующих потоков равны). А здесь можно сказать что-то вроде: "Задачу оптимизации в таком-то классе можно решить с помощью теории массового обслуживания".
На рынке корову мужик продавал (оптимально)