14 марта 2017 года Sergey_Kovalenko опубликовал задачу черезвычайно взволновавшую умы хабражителей. За пару вечеров было сломано много копий и наверняка было бы разбито много голов, если бы встреча была очной.
Ниже вас ожидает условие задачи и расммотрение одного подхода к решению.
Условие
Некий Мужик занимается перепродажей коров: Он скупает их за фиксированную небольшую цену a рублей у местного населения и пытается продать с наценкой посетителям рынка. Предположим для простоты, что покупатели по своей платежеспособности делятся на n классов, и, что любому, подошедшему к Мужику покупателю из k -го класса, он продает любую из имеющихся у него коров с наценкой xk-тое рублей. Будем считать, что появление покупателя каждого класса описывается пуассоновским процессом с неким, характерным для этого класса нагрузочным параметром lk-тое. Если в момент появления покупателя у Мужика нет коров, то первый не становится в очередь, а удаляется восвояси и обратно уже не возвращается.
- Каждая корова, купленная Мужиком у населения проедает за единицу времени корма на u рублей, поэтому держать большой запас коров не выгодно;
- Мужик может всегда отправить с попутчиком в деревню просьбу привести еще коров, однако выполнение этой просьбы хотя и бесплатно, но требует T времени;
- Ввиду сделанных оговорок, Мужик может и не продать корову, если их у него мало, а шанс встретить клиента побогаче достаточно велик, или наоборот — продать в убыток из излишков запаса лишь бы зря не кормить.
Какова оптимальная на длительном периоде стратегия Мужика при почти бесконечном начальном капитале?
Решение
Для расстрела этой проблемы мы достанем одну из самых замечательных пушек, которыя издавна используется математиками и программистами — «метод чайника».
Пусть имеется пуассоновский поток клиентов c параметром I, каждый клиент платит за корову наценку x, мужик продает корову всегда, когда она есть.
Для дальнейшей работы нам понадобится несколько дополнительных соображений, которые позволят успешно «вылить воду из чайника».
Хлев на рынке может быть очень большого, но всетаки конечного размера m. Клиенты так и остаются клиентами. Коровы же превращаются в устройства обслуживания следующим образом: когда корова стоит в хлеву на рынке то устройство обслуживания не занято, когда мужик продаёт корову устройство обслуживания становится занятым до того момента, пока из деревни на это место не придет новая корова.
Пусть теперь в момент времени t в хлеву находится i коров и происходит продажа коровы. Мужику необходимо решить, заказать корову немедленно или отложить требование. Важным моментом является то, что какое бы решение он не принял корову раньше чем через T он не получит. Таким образом время доставки коровы на освободившееся место является случайной величиной t, принимающей значения из промежутка и математическим ожиданием . Распределение этой величины зависит от стратегии заказа коров.
Как справедливо заметили в коментариях, к сожалению придется потребовать независимости времен обслуживания.
Таким образом, мы получаем что исходная задача, при указанных ограничениях, эквивалента системе массого обслуживания без очереди с m устройств обслуживания.
Тогда можно вычислить вероятность того что покупатель уйдет с коровой.
Где вычисляется по формуле Эрланга. Заметим, что вероятность отказа не зависит от распределения t, важно только среднее время обслуживания.
Пусть теперь коровник потребляет u рублей в единицу времения не на корову, а на стойло. Но, когда клиент покупает корову он сверху «платит» рублей.
Тогда средняя прибыль в единицу времени может быть выражена как
А сама задача сводится к нахождению .
Анализ полученных результатов
Если максимум r достигается при то единственно возможная стратегия — заказ коров по факту продажи.
Нельзя пытаться менять значение m, так как в силу свойств пуассоновского потока можно вырезать временные интервалы где m не оптимально и склеить их. И в результате получится результат хуже оптимального.
Комментарии (102)
mayorovp
20.03.2017 07:59Решение неполное, поскольку не рассмотрены стратегии заказа коров, зависящие от остатка коров.
С такой стратегией ваши времена обслуживания будут нетривиально зависеть друг от друга — и использованная вами формула будет уже неприменима.
koldyr
20.03.2017 08:40Формула применима к любой стратегии, для которой существует математическое ожидание времени обслуживания.
mayorovp
20.03.2017 08:56Вообще-то, формула Эрланга требует чтобы поток был пуассоновым.
koldyr
20.03.2017 09:04+1Б. В. Гнеденко, И. Н. Коваленко. Введение в теорию массового обслуживания. Издательство Наука 1966 год. Стр. 48: «Формула Эрланга сохраняет свой вид для задачи с потерями при любом распределении длительности обслуживания, лишь бы его среднее значение было...».
Когда я нашел это, я был счастлив как червь в яблоке.mayorovp
20.03.2017 09:22Но какие-то коэффициенты при неизменном виде изменяться могут? А ведь в таком случае общей формулы будет уже недостаточно для нахождения оптимума.
koldyr
20.03.2017 11:26Какие коэффициенты? В формуле эрланга ничего не изменяется.
mayorovp
20.03.2017 11:55Единица делить на ка факториал, к примеру...
Совсем ничего не меняться ничего не может. Вот вам контрпример.
Рассмотрим поток, аналогичный пуассоновому — но с тем условием, что клиенты ходят в два раза реже, зато парами. Матожидание у него такое же.
Если принять ваше утверждение о применимости формулы — получим равенство p{m}(I,T) = p{m/2}(I,2T) — что неверно.
koldyr
20.03.2017 12:04В утверждении сказано что формула не зависит от распределения времени обслуживания. Клиенты должны ходить по пуассону. Если вы предполагаете что клиенты ходят парами склейте по две коровы и по два клиента.
получите что интенсивность упала до I/2 обслуживание стойла теперь стоит 2u, время обслуживания не изменилось и осталось Т.mayorovp
20.03.2017 12:25Да, согласен, я перепутал параметры, надо мне минус за тот пример влепить...
Вот вам другой пример. Допустим, у нас есть две кассы, обслуживание на которых длится время T. И они магически связаны — если приходит клиент пока другая касса занята — новый клиент обслуживается мгновенно, а обслуживание старого затягивается еще на T. Пока T < I матожидание времени обслуживания от введения подобного правила не меняется, а вот вероятность отказа в обслуживании падает до 0, что противоречит формуле Эрланга.
Так что ваше решение рассматривает лишь стратегии, в которых случайная величина t не зависит от потока клиентов, в противном случае "время обслуживания" нельзя считать для разных коров независимым. А тот факт, что можно ограничиться лишь такими стратегиями — опять не доказан...
koldyr
20.03.2017 12:37Как было показано время обслуживания каждой коровы не может быть меньше чем T. Я не могу развить ваш контр пример на этот случай.
Чему противоречит ваша идея в классическом случае с ходу не пойму, но, похоже дело в том что есть отличная от нуля вероятность обслужиться за время 0.mayorovp
20.03.2017 12:58+1Этот контрпример противоречит утверждению, что используемая формула остается справедливой для зависимых распределений времени ожидания.
Ошибка в любом из аргументов ведет к разваливанию доказательства.
koldyr
20.03.2017 12:54Вот видимо оно: ваша смо не просто имеет ненулевую вероятность обслужиться за 0. Вероятность обслужиться за 0 при условии что она находится в состоянии две кассы заняты равна 1. А при анализе диаграммы состояний нужна интенсивность обслуживания, это 1/(время обслуживания).
mayorovp
20.03.2017 13:02Ну хорошо, не будет сокращать время обслуживания не до 0 — а до достаточно малого ?.
В таком случае, пока 1 касса занята, вторая будет давать вероятность отказа p1(I, ?), что ограничивает сверху общую вероятность отказа в обслуживании. Эта величина все еще не может быть равна p2(I, T).
koldyr
20.03.2017 13:08Вот тут нужно подумать, что там с независимостью времени обслуживания на разных устройствах. И что может измениться, если они зависимы, но время обслуживания нельзя сделать ниже T.
koldyr
20.03.2017 13:41-1Придётся потребовать независимость времени обслуживания. В конце концов остается достаточно много стратегий удовлетворяющих этому условию. Данная статья предлагает хорошего кандидата. А если кто-то сможет обыграть пуассона на зависимостях обслуживания при данных словиях, с удовольствием посмотрю.
TheShock
20.03.2017 12:31стратегии заказа коров, зависящие от остатка коров
Оно и зависит: уменьшился остаток — заказали еще коровуmayorovp
20.03.2017 13:05Нет, я говорил о другой зависимости.
Навроде "последнюю корову заказываем сразу же, вторую — через секунду, третью — через две секунды". На независимые "коровы обслуживания" подобная стратегия ну никак не раскладывается, а чтобы доказать оптимальность решения — ее надо тоже рассмотреть.
TheShock
20.03.2017 14:15-1Так мы и не заказываем сразу три, а первую после первой покупки, вторую после второй и так далее.
Есть огромное количество стратегий, которые не имеют под собой никакого обоснования, например заказывать зависимо от фазы луны или силы ветра, и это не означает, что для доказательства необходимо расмотреть их все.
Коровы идут определенное время и откладывать их заказ — это игра в рулетку или гадание на звездах, смотря что вам больше нравится. Потому что мы понятия не имеем, сколько коров будет через время Т, любой bounce будет вырождаться либо в «заказываем как приходят клиенты только черех 3 секунды», либо «заказываем как приходят клиенты, только с все увеличивающейся задержкой», первый не нужен — лишь бессмысленное усложнение, а второй — еще и вредное, ибо со временем скушает буфер и мы будем в серьезном минусе.mayorovp
20.03.2017 14:19-1Тем не менее, есть еще один фактор, неплохо поддающийся предсказанию — ожидаемое прибытие коров.
Пока что мне не удается найти способ строго доказать, что оптимальная стратегия не должна учитывать этот фактор при принятии решений на заказ коров.
Нестрого-то я ваши аргументы раз пять сам себе повторил… не помогает :)
koldyr
20.03.2017 14:24Любая стратегия, кроме немедленного заказа после продажи, увеличивает среднее время обслуживания. Это пока единственно что точно верно. Есть гипотеза как выглядит функция r, но доказать я её не могу. Из гипотезы следует что заказывать надо сразу по факту продажи.
TheShock
20.03.2017 14:26Тем не менее, есть еще один фактор, неплохо поддающийся предсказанию — ожидаемое прибытие коров.
Пока что мне не удается найти способ строго доказать, что оптимальная стратегия не должна учитывать этот фактор при принятии решений на заказ коров.
Очень просто — мы не можем никак повлиять на прибытие. Даже если закажем сотню прям сейчас — они не придут раньше тех, кто уже идет.mayorovp
20.03.2017 14:35Да, но ожидаемое прибытие коров влияет на ожидаемое число коров через время T, что в свою очередь влияет на необходимость заказывать сейчас.
TheShock
20.03.2017 14:44(Количество коров в пуле + количество коров в пути) у нас всегда константно и в терминологии топика равно m. Чтобы узнать количество коров через время T необходимо от m отнять количество купленных коров за время Т, а данная цифра нам неизвестна даже приблизительно до окончания отрезка времени. То есть у нас есть константа и неизвестное. Как из одного известного числа m можно определить, что именно в данный раз необходимо дозаказать коров?
Попробую еще раз акцентировать. Если заказывать сразу после продажи, то (Количество коров в пуле + количество коров в пути) = m и константен. Также константен средний поток покупателей. Так почему в разные моменты времени при абсолютно одинаковых входящих данных вы хотите принять разные решение о покупке или непокупке коров?mayorovp
20.03.2017 14:56Вы ходите кругами.
Во-первых, входные данные — неодинаковые, я уже говорил почему.
Во-вторых, фиксированность размера пула тоже было бы неплохо строго доказать.koldyr
20.03.2017 15:02Для независимых времен обслуживания это доказано. Для зависимых все это, как вы правильно заметили, не работает. Но зато есть первое решение-кандидат. Можно поробовать его обыграть и видно на каком поле. Но вот лично я сильно сомневаюсь в успехе.
mayorovp
20.03.2017 15:07+1Для независимых времен обслуживания это не столько доказано, сколько постулировано :)
Сама возможность рассматривать коров независимо друг от друга, ставя однозначное соответствие между моментов продажи и моментов заказа означает что у нас есть фиксированный пул коров.
koldyr
20.03.2017 15:11Вы не поняли. Вы не обязаны заказывать коров в момент продажи, но если времена ожидания будут независимыми то вся теория работает и существуют Т и м, для которых прибыль максимальна.
mayorovp
20.03.2017 15:20Само понятие "время ожидания" включает в себя возможность поставить в соответствие события продажи коровы и ее покупки. Для неограниченных пулов это невозможно.
koldyr
20.03.2017 15:23Прекрасно, если вы отвлечетесь и перечитаете предположения в которых сделано решение, там явно указано что m конечно. Иначе это анекдот про счетное колличество математиков в ковбойской интерпритации.
mayorovp
20.03.2017 15:24Так я об этом и написал. Само использование понятия «независимые времена обслуживания» постулирует конечность пула.
koldyr
20.03.2017 15:30Нет, не постулирует. Не вижу причин, по которым время обслуживания должно быть зависимым в случае счетного размера коровника. В конце концов на эту роль прекрасно подойдет константа
TheShock
20.03.2017 15:12Вы ходите кругами.
Потому что вы раз за разом повторяете ту же ошибку.
Во-первых, входные данные — неодинаковые, я уже говорил почему.
Какие именно неодинаковые и как они меняются и от каких условий? Среднестатистических приход покупателя — единственные входящие данные и они не меняютсяmayorovp
20.03.2017 15:23+1Я не повторяю ошибку, я жду доказательства. Математически корректного.
PS
Пишут как-то Ландау и Лифшиц «Электродинамику сплошных сред», ну и в одной главе получали какую-то сумасшедшую формулу с использованием максвелловского тензора напряжений в анизотропной среде. А на следующий день Лифшиц и говорит:
— Слушай, я вчера три листа выкладок в трамвае потерял.
Что делать?
— *Да ладно, — говорит Ландау, — напишем, как обычно: «откуда очевидно»...TheShock
20.03.2017 15:56Давайте еще раз рассмотрим, что у нас есть.
У нас есть среднее количество людей, которые приходят за Х времени, назовем это число 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) вероятность прихода покупателя в ближайшее время.
Понимаете о чем я?mayorovp
20.03.2017 16:09Вы разобрали самый простой случай. Теперь рассмотрим случай, который возникает когда мы корову таки заказали — а потом пришел другой покупатель.
У нас (K-2) коров, 1 в пути (осталось времени t1) и вероятность прихода покупателя в ближайшее время — p(t).
Вы понимаете, что эта ситуация меняется каждую секунду?
TheShock
20.03.2017 16:31+1Да, с этим согласен. Смотрите.
У нас было К-1 коров и мы приняли решение заказывать еще одну.
Сейчас у нас (К-2)+(1 в пути), т.е. максимум К-1 коров, то есть сейчас у нас, грубо, меньше или равно коров, чем тогда, когда мы решили заказывать.
Ситуация, когда у нас все коровы на месте и ни одной в пути — найболее стабильная, то есть нет такой ситуации при которой мы решим заказать корову при (К-1) коров, но не заказать корову при (К-2)+(1 в пути), потому что если мы заказываем корову при (К-1), значит предполагаем, что за время доставки коровы у нас выкупят (К-1), а следовательно выкупят и (К-2+1), понимаете?mayorovp
20.03.2017 16:54О, отлично! Вот это уже похоже на правду.
Еще бы доказать, что в ситуации ((K-2)+1) нам нет смысла заказывать сразу двух коров, и лемма о фиксированном пуле и времени ожидания будет доказана.
TheShock
20.03.2017 17:05Ситуация К-2+1 в общем случае равна К-1 (кроме исключений). Конечно, будут ситуации, когда выгодно заказать две и ситуации, когда не выгодно заказать ни одной, но заранее мы не узнаем.
Если время прихода коров Т, а в среднем за Т время мы продаем Н коров, то необходимо стремиться, чтобы в каждый Т отрезок времени у нас было ровно Н коров.
AndreyXors
20.03.2017 13:04-2Во-первых, че вы всё усложняете вечно? Разбивайте задачку на 4 части и решайте на уровне логики пятиклассника.
Во-вторых, че вы прицепились к этому пуассоновскому процессу? Вынесите его в отдельную подзадачу. Нам нужна только вероятность появления нищеброда и вероятность появления мажора.
1) Если в текущий момент времени (dSm — dSn) > (A/B) * (сколько прошло времени после последней продажи в секундах) * стоимость содержания коровы в секунду, ТО продаем только мажорам, нищебродов шлем лесом. Иначе продаем всем.
dSm — наценка для мажора
dSn — наценка для нищеброда
А — вероятность появления нищеброда.
В — вероятность появления мажора.
2) A, B уже определяете этим вашим пуассоновским процессом. Мы его выносим в отдельный «черный ящик». Тут расписывайте свои четырехэтажные формулы, сколько душе угодно.
3) Оптимальное количество коров в наличии в единицу времени = фактическое текущее (в зависимости от условия 1) количество продаж в единицу времени. Это ежу понятно. Именно этот пункт описал автор решения в данном посте. Но для поддержания оптимального количества, заказывать нужно заранее (условие 4)
4) При этом, если T (время доставки) > временного промежутка между фактическими продажами (в зависимости от условия 1), то заказывать корову нужно заранее за (T — время между продажами) до прогнозируемой продажи (опять же в зависимости от условия 1).
Всю эту систему из четырех «черных ящиков» выполняем в цикле. Вот и вся стратегия.mayorovp
20.03.2017 13:08Вот в пункте 4 у вас и ошибка, а без него вся очевидная стратегия разваливается. Ежу тут, конечно же, все понятно, вот только… ежик иногда ошибается.
AndreyXors
20.03.2017 13:17Можете поподробнее, в чем ошибка то? Давайте на уровне простейшей логики, без абстракций. Мы же можем сделать простейший прогноз на основе статистики, не вмешивая сюда пуассоновский процесс.
koldyr
20.03.2017 13:19+1Не можете, потому что процесс есть, он от вас и вашей статистики не зависит. Это все равно что прогнозировать игру на рулетке на основе выпавших чисел и сделанных ставок.
mayorovp
20.03.2017 13:12Объясняю на пальцах, последний раз. Допустим, у вас T = 1 минуте, а прогнозируемое время до следующего покупателя — 2 минуты. Вы предлагаете ждать 1 минуту перед заказом новой коровы. ОК, ждем минуту!
Подождали минуту. T у нас все еще равно 1 минуте, прогнозируемое время до следующего покупателя — все еще 2 минуты. Покупать корову или опять ждать?
AndreyXors
20.03.2017 13:22Почему прогнозируемое время остается 2 минуты? если мы уже подождали минуту, то и прогнозируемое время уменьшится 2 — 1 = 1 минута. Я подразумеваю, что оно динамически изменяется. Система работает в цикле. То есть через 1 минуту у нас прибудет корова от поставщика и через 1 минуту придет за ней заказчик. Всё оптимально.
mayorovp
20.03.2017 13:26Учите теорию вероятностей. Прогнозируемое время до прихода покупателя со временем не уменьшается. Потому что пуассонов поток такой вот нехороший для прогнозирования.
AndreyXors
20.03.2017 13:33Если мне девушка сказала, что придёт через 20 минут. Спустя 10 минут, она всё-равно придет через 20? Вот почему их постоянно приходится ждать…
mayorovp
20.03.2017 13:34Приход девушки описывается не пуассоновым потоком, а нормальным распределением.
AndreyXors
20.03.2017 13:39А насколько вообще оправдано приход клиента описывать пуассоновым процессом?
mayorovp
20.03.2017 13:54+1Пуассонов процесс — это самая простая модель потока покупателей, когда нам о них ничего не известно (кроме матожидания числа покупателей в единицу времени).
Так, в примере с девушкой, если бы она вам не обещала выйти через 20 минут, а все ваши знания о ней исчерпывались тем фактом, что она приходит к вам раз в сутки — адекватной моделью было бы уже не нормальное, а равномерное распределение. А если заменить этот самый раз в сутки сначала на 7 раз в неделю, потом на 30 раз в месяц, 365 раз в год и т.п. — то в пределе и получим пуассонов поток, когда девушка в среднем приходит раз в сутки, но никому ничего не обещала и предсказанию не поддается.
TheShock
20.03.2017 14:06Почему прогнозируемое время остается 2 минуты? если мы уже подождали минуту, то и прогнозируемое время уменьшится 2 — 1 = 1 минута. Я подразумеваю, что оно динамически изменяется.
А если подождали 3 минуты, а клиента все нету, то прогнозируемое время ожидания -1 минута?AndreyXors
20.03.2017 14:12Ну, мы вроде уже разобрались, что моё решение не подходит. Но всё-равно отвечу, как я предполагал в пределах моего решения. Если подождали 2 минуты, а клиента нет, то ожидание обнуляется, но при этом количество ожидаемых(планируемых) клиентов остается неизменно, а времени на их ожидание становится меньше. Соответственно, время до прогнозирования следующего прихода клиента уменьшается. То есть уже не 2 минуты, а допустим 1,9 минут. В этом есть издержки, что придется в каких-то моментах держать товар на складе дольше и платить за это. Именно из-за этих издержек моё решение не самое оптимальное.
indocoder
23.03.2017 07:11Если подождали 2 минуты, а клиента нет, то ожидание обнуляется, но при этом количество ожидаемых(планируемых) клиентов остается неизменно, а времени на их ожидание становится меньше.
Но ведь нет же. Чем меньше промежуток времени — тем меньше мат. ожидаемое кол-во клиентов. Если у вас на промежутке 60 мин. мат ожидание пришедших клиентов — 60, то подождав 2 минуты, мат ожидание вдруг не становится 60 клиентов на 58 мин.
Средние издержки поэтому будут тоже одинаковы по мат ожиданию.TheShock
23.03.2017 16:14Если у вас на промежутке 60 мин. мат ожидание пришедших клиентов — 60, то подождав 2 минуты, мат ожидание вдруг не становится 60 клиентов на 58 мин.
То мат ожидание на ближайшие 60 минут — 60 клиентов)
koldyr
20.03.2017 13:24+1Потому, что есть предметы в порядке изучения: анализ, теория меры, теория вероятностей, мат статистика, теория случайных процессов.
AndreyXors
20.03.2017 13:28То есть простейшая логика вещей уже не работает?
mayorovp
20.03.2017 13:31Работает — если ее применять правильно. Например, когда в задаче сказано "приход покупателя непредсказуем", нельзя строить решение исходя из предсказания его прихода.
AndreyXors
20.03.2017 13:44Ну, значит моё заблуждение в том, что я не стал вдаваться в специфику процесса пуассона. Просто представил, что есть на выходе некие вероятности появления того или иного клиента.
Ugrum
20.03.2017 16:14-1Так, щас я отгребу очередных минусов.
Но, с моей точки зрения (а я именно тот мужик на базаре, только не с КРС, а скажем, так с немного другими группами товара), самая оптимальная стратегия- держать в наличии количество коров, продающееся (всем клиентам, и мажорам и нищебродам) за время доставки следующей партии (+5-10% про запас, опять же не учитывая сезонные факторы и форс-мажоры), но для этого нужна какая-никакая, но статистика.
и где наш Milfgard?mayorovp
20.03.2017 16:26Задача-то математическая, а не практическая. Тут интересует именно самая оптимальная стратегия. Точная формула того самого запаса. А также всякие краевые случаи.
И еще доказательство что выбранная стратегия — самая оптимальная.
koldyr
20.03.2017 17:43-1Предлагаю новое соображение.
Для любой стратегии s (по модулю независимости), для которой существует среднее время доставки. Существует описанная система массового обслуживания, с тем же самым средним даставки и некоторым м, с маленкой добавкой: Надо взять ближайшую смо где вероятность отказа меньше и чуток подкрутить. Чтобы клиенту отказывали с некоторой вероятностью, даже если корова есть.
И подумать: может ли такая стратегия уменьшить расходы на коровник.
vanxant
21.03.2017 00:25-2Простите, но задачу вы не решили, а только переформулировали.
По сути, вы сказали, что идеальная стратегия в том, что нужно найти некое оптимальное m и поддерживать количество коров максимально близко к m снизу.
Но, простите, это ни о чем вообще. Вы даже близко не показали существование решения, его единственность, а также сходимость (устойчивость) алгоритма оптимизации (какого, кстати)?
popolznev
21.03.2017 14:18-1Простите, вот этого места я не понял:
… время доставки коровы на освободившееся место является случайной величиной t, принимающей значения из промежутка [T,+?) и математическим ожиданием T?. Распределение этой величины зависит от стратегии заказа коров.
Зачем упоминать о случайной величине, если дальше используется только её матожидание?
mayorovp
21.03.2017 14:20Затем, что матожидание бывает только у случайных величин.
popolznev
21.03.2017 15:07Если от случайной величины нужно только матожидание, то можно ограничиться случайными величинами, которые принимают некоторое значение с вероятностью 1.
koldyr
21.03.2017 15:11Все правильно, только наоборот. Формула применима к некоторому классу величин. В формуле используется только математическое ожидание, поэтому разумно взять из этого класса то что попроще, в данном случае — константу.
popolznev
21.03.2017 15:28С этой формулой Эрланга вообще, по-моему, какой-то цирк с конями. Нам надо найти оптимальную стратегию, но поскольку легко посчитать выигрыш мы можем только с помощью одной формулы, то оптимизировать будем лишь в классе тех стратегий, для которых эта формула применима. Таков подход?
koldyr
21.03.2017 15:31К сожалению да. Делаю что могу, кто может пусть сделает лучше.
popolznev
21.03.2017 15:38Разумеется, нельзя упрекать человека за то, что он делает лишь то, что может, и не больше. Это низость — ругать за такое. Но надо же чётко прописывать, чтО именно сделано и какие дополнительные ограничения наложены. А у вас в тексте:
Таким образом мы получаем что исходная задача эквивалентна системе массового обслуживания
А она не эквивалентна — ровно перед этим вы сузили задачу.
koldyr
21.03.2017 15:40Хорошо, чтобы исключить двусмыслие при прочтении, добавлю «при заданных ограничениях». И спрошу: при заданных ограничениях Верно?
popolznev
21.03.2017 16:18Верно ли утверждение об эквивалентности исходной задачи "при заданных ограничениях" системе массового обслуживания? Может быть, я дую на воду, но я бы выразился иначе. Просто я привык, что когда говорят об ограничениях в задаче, то имеются в виду ограничения в условиях (ну, например, в данном случае: классов покупателей всего два и они встречаются равновероятно, то есть мощности соответствующих потоков равны). А здесь можно сказать что-то вроде: "Задачу оптимизации в таком-то классе можно решить с помощью теории массового обслуживания".
koldyr
21.03.2017 14:20Потому, что это важно. Так как в классичесом случае формула Эрланга была расчитана только для экспоненциально распределенных, независимых времен обслуживания. От торебования вида распределения математикам удалось избавится. Независмость же, как видно из комментария mayorovp важна.
ggrnd0
это элементарный вывод и от типа распределения случайной величины не зависит.
А сколько коров надо купить в самом начале? Не имея коров, нельзя их продать и дозаказать по факту продажи...
koldyr
Так же начиная с n<m и заказывая по факту продажи их всегда будет не больше чем n, что неоптимально. Поэтому начинаем с m коров.
TheShock
А как посчитать m?
koldyr
Это то m при кором достигается максимум r.
TheShock
Очевидно. А формула?
ggrnd0
в кратце, ответ не верный.
Конечно мы не сможем закупить больше чем m, однако может выйти, что необходимо будет купить меньше чем m.
TheShock
Ну значит наш воображаемый хлев будет равен m.
koldyr
Я не понимаю что вы имеете в виду под необходимо меньше. У вас есть функция. Она достигает максимума на каких то m и среднем T. Если вы уклонитесь от этих значений результат будет хуже.
koldyr
Что вы понимаете под словом формула?
TheShock
У нас есть (средний приток клиентов), (цена содержания коровы), (цена трат на корову за единицу времени) и (время ожидания коровы). Как из этих параметров посчитать m, при котором прибыль будет максимальна?
koldyr
Перебором.
TheShock
Такая красивая теоретическая база и такое некрасивое решение? Неее)
Ugrum
И хорошо бы не забыть учесть ещё сезонность всех этих четырёх величин.
koldyr
А хорошо бы еще прочитать условие задачи.
Ugrum
Читал. Но почему бы не дополнить, для вящей реалистичности.
koldyr
Дополните, с удовольствием ознакомлюсь с обобщением.
Sergey_Kovalenko
Приятно видеть такой интерес к моей публикации, однако считаю должным со своей стороны заметить, что решение, может быть и верное, не относится к задаче, которая была приведена мною. Время доставки не является случайной величиной, поскольку оно определяется однозначно условиями задачи и стратегией Мужика, дилемма продажи и ожидания более состоятельного покупателя, бывшая центральной, в упомянутой мною задаче, в указанном решении совсем не отражена. Тем не менее, я должен отдать должное образованности и амбициозности автора этой публикации и попросить читателей не рассматривать поспешное решение как смертный грех, поскольку процесс познания лишенный права на ошибку правдоподобного вывода попросту теряет шанс открыть что-либо новое.
koldyr
К счастью при анализе выражения r дилема исчезнет.
Так пропуская покупателей вы снижаете вероятность продажи коровы, искусственно занижая пропускную способность системы.
И для того чтобы понять что время доставки можно рассматривать как случайную величину, представте, что кто-то предъявляет вам результаты работы гсч, при этом начальное заполнение и алгоритм вы не знаете. То что вы видите — случайно или нет?
AndreyXors
Элементарный вывод для меня — заказ коров за T времени до продажи. То есть нужна статистика по продажам, чтобы прогнозировать.
AndreyXors
Точнее так: ваше решение справедливо в случае, если T < времени, за которое раскупают всех коров. Иначе количество коров будет в стойле будет постепенно убывать и стремиться к нулю. Поэтому если T > времени, за которое раскупают всех коров, нужно прогнозировать и делать заказ коров за T времени до продажи.
mayorovp
Время, за которое раскупают всех коров — зависит от величины m ("размера коровника"). А эту величину выбираем мы.
mayorovp
Пуассонов поток нельзя "прогнозировать"!
AndreyXors
Че вы все прицепились к этому пуассону? Это только одна подзадача, в задаче другое спрашивается! Засуньте этот пуассонов процесс в «черный ящик», нас интересует на выходе вероятность появления клиента того или иного класса. Вы так никогда не найдете решение, если всё будете смешивать.