Итак, задача вполне себе житейская.
Некий Мужик занимается перепродажей коров: он скупает их за фиксированную небольшую цену a рублей у местного населения и пытается продать с наценкой посетителям рынка. Предположим для простоты, что покупатели по своей платежеспособности делятся на n классов, и, что любому, подошедшему к Мужику покупателю из k -го класса, он продает любую из имеющихся у него коров с наценкой xk-тое рублей. Будем считать, что появление покупателя каждого класса описывается пуассоновским процессом с неким, характерным для этого класса нагрузочным параметром lk-тое. Если в момент появления покупателя у Мужика нет коров, то первый не становится в очередь, а удаляется восвояси и обратно уже не возвращается. Задачи бы попросту не было, если бы не два правдоподобных условия:
1) Каждая корова, купленная Мужиком у населения проедает за единицу времени корма на u рублей, поэтому держать большой запас коров не выгодно;
2) Мужик может всегда отправить с попутчиком в деревню просьбу привести еще коров, однако выполнение этой просьбы хотя и бесплатно, но требует T времени;
3) Ввиду сделанных оговорок, Мужик может и не продать корову, если их у него мало, а шанс встретить клиента побогаче достаточно велик, или наоборот — продать в убыток из излишков запаса лишь бы зря не кормить.
Какова оптимальная на длительном периоде стратегия Мужика при почти бесконечном начальном капитале?
Замечания:
1)запрос на пополнение коровами подобен телефонному звонку в службу доставки — можно звонить как угодно часто, лишь бы были деньги на предоплату, при этом все заявки выполнятся независимо друг от друга ровно через T времени после предоплаты;
2)есть соображения в пользу того, что величина капитала Мужика при разумных стратегиях будет подобна случайному блужданию на прямой, тогда под оптимальностью следует считать максимизацию отношения ожидания сдвига вправо за большой промежуток времени к величине этого промежутка, при этом шанс когда-либо разорится, скорее всего, уменьшается асимптотически по показательному закону от величины начального капитала.
Комментарии (212)
Sergey_Kovalenko
14.03.2017 18:12Спасибо за совет. В статье я предполагал, что задача в стиле книг бородатых 50-х годов и интересно прежде всего концептуальное, а не вычислительное решение, с исследованием асимптотик.
lair
14.03.2017 18:58+2ввиду сделанных оговорок, Мужик может и не продать корову, если их у него мало, а шанс встретить клиента побогаче достаточно велик
противоречит
любому, подошедшему к Мужику покупателю из k -го класса, он продает любую из имеющихся у него коров с наценкой xk-тое рублей
Ну и заодно:
появление покупателя каждого класса описывается пуассоновским процессом с неким, характерным для этого класса нагрузочным параметром lk-тое
Можете для тех, кто не в теме, рассказать о характеристиках этого процесса, а именно:
- по какой формуле рассчитывается вероятность появления покупателя того или иного класса в каждой момент времени t?
- может ли в момент t появиться одновременно два покупателя разных классов (и как тогда осуществляется продажа)?
mwambanatanga
14.03.2017 19:13+1Предположу, что автор имел в виду следующее:
- Время непрерывно, поэтому вопрос о вероятности появления клиента в определённый момент времени не имеет смысла. Вместо этого можно говорить о вероятности появления клиента за определённый промежуток времени. Поскольку дано распределение Пуассона, то среднее время между двумя последовательными покупателями равно 1/lk (или наоборот — за единицу времени в среднем придут lk покупателей).
- Процессы для разных классов покупателей независимы. Т.е. вероятность появления клиента одного класса не зависит от потока клиентов других классов.
Sergey_Kovalenko
14.03.2017 19:101) Да есть некоторая неточность языка. Считается, что Мужик всегда способен продать, если захочет.
2)Вы правы, забыл уточнить: независимые пуассоновские процессы с непрерывным временем(определение можно посмотреть почти в любой книге по теории вероятностей или математической энциклопедии)
3)Ввиду 2) появление когда либо сразу двух покупателей — событие нулевой вероятностиVjatcheslav3345
14.03.2017 19:27События все независимы, совместны но некоторые зависимы (и наверное даже — вероятностная зависимость есть и цепочках из n событий) а другие — нет.
Надо понять, какое событие случается в модели чаще всего и тогда можно определится как действовать/решать — так как это событие задаёт поведение всей системы.
lair
14.03.2017 22:59Ввиду 2) появление когда либо сразу двух покупателей — событие нулевой вероятности
Это почему?
trapwalker
15.03.2017 00:25+3Потому, что появление покупателя, решение о продаже и сама продажа (или отказ) мгновенны. Время непрерывно и вероятность любого события, из рассматриваемых в задаче, за время, стремящееся к нулю, тоже стремится к нулю. Это значит, что одновременно два покупателя не появятся исходя из самой природы вещей. Всегда кто-то из низ был раньше и всегда между ними ненулевое время.
Вернее как… вероятность того, что между приходами покупателей пройдёт нулевое время — тоже нулевая.
retran
15.03.2017 10:24У вас несколько независимых друг от друга по условию Пуассоновских потоков. Вероятность появления покупателей в один и тот же момент времени ненулевая по определению.
trapwalker
15.03.2017 10:49+1Какая разница? Вероятность случайно дважды попасть в одну вещественную математическую точку строго нулевая. Не важно к каким Пуассоновским или не пуассоновским процессам относятся эти величины. Если угодно, два вещественных случайных числа не равны с вероятностью строго 1.
retran
15.03.2017 10:53-2Это с какого перепугу?
mwambanatanga
15.03.2017 10:55Вы путаете (или, скорее, вольно используете) понятия «момент времени» и «интервал/промежуток времени». Из-за этого всё недопонимание между вами и коллегой trapwalker.
retran
15.03.2017 10:58-1Интервал — это сумма моментов времени.
mwambanatanga
15.03.2017 11:11Не втягивайте меня в ваш спор. Я лишь указал на причину вашего взаимо-непонимания. Вы считаете продолжительность «момента» бесконечно малой, но не нулевой. Ваш оппонент считает продолжительность «момента» пренебрежимо малой, а поэтому нулевой.
В любом случае, к решению данной задачи это не имеет отношения.trapwalker
15.03.2017 11:18+1Именно так. Я определяю момент как математическую точку на оси времени. Это никак не интервал. Если коллега считает моментом некий квант машинного времени, который по определению интервал, то нет смысла говорить об идеальном пуассоновском процессе и его нужно квантифицировать.
Короче, похоже, вы правильно указали на рассогласования, просто немного не очевидно выразились. Однако я неоднократно и достаточно явно говорил, что имею в виду под моментом, а retain не говорил, что считает момент интервалом. То, что интервал — это сумма моментов в интегральном смысле верно в любом случае.retran
15.03.2017 11:23Я считаю моментом бесконечно малый интервал. Другие определения (точка как нульмерные объект, например), кажется, вообще лишены смысла в рамках подобных задач.
trapwalker
15.03.2017 11:27+1Это отдельные понятия. Есть точка и есть интервал. Зачем вводить путаницу подразумевая под первым второе? Пуассоновский процесс оперирует и точками и интервалами в разных смыслах.
кажется, вообще лишены смысла в рамках подобных задач
То, что кажется, нужно оговаривать явно. И нет, не лишены.
trapwalker
15.03.2017 11:02+2Вот лично я ничего не путаю, а использую строго по назначению.
Любое событие происходит мгновенно в момент времени, а пуассоновский процесс определяет вероятность возникновения события на интервале времени. В интервале (любом вещественном диапазоне) бесконечное количество моментов (вещественных точек).
retran
15.03.2017 10:46Поясню, в пуассоновском потоке вероятность появления следующего события через время t рассчитывается как P(t) = lambda * pow(e, -lambda*t). Возьмем два потока, с интенсивностями lambda1 и lambda2, пусть t = const. Тогда вероятности появления события в обоих потоках через время t P1 = lambda1 * pow(e, -lambda1 * t) и P2= lambda2 * pow(e, -lambda2 * t). Общая вероятность того, что в обоих потоках придут события через одно и то же время P1 * P2 = lambda1 * pow(e, -lambda1 * t) * lambda2 * pow(e, -lambda2 * t) = lambda1 * lambda2 * pow(e, -(labmda1 + lambda2) * t). Эта вероятность ненулевая при любых положительных интенсивностях. Другой вопрос, что в рамках условия, это все не сильно важно, потому что время обслуживания клиента равно 0. А вот в реальной жизни придется учитывать возможность появления очередей.
trapwalker
15.03.2017 10:53+1в пуассоновском потоке вероятность появления следующего события через время t
Не «через», а «в течение». Разве нет? Вероятность появления события строго «через» время t по определению нулевая. Потому что dt->0.retran
15.03.2017 10:57-2Нет, почитайте матчасть, в том числе про пределы. Ваша ошибка в том, что вы считаете вероятность попадания в заданную математическую точку нулевой (а значит нулевой в любую точку, а значит вероятность попадания в отрезок, который является суммой математических точек — тоже нулевой… Бред.). Она конечно очень мала, но совсем не равна нулю.
http://sernam.ru/book_tp.php?id=114 — начиная со слов «Важной характеристикой потока является закон распределения длины промежутка между соседними событиями...»trapwalker
15.03.2017 11:09+2Не передергивайте. Я такого не говорил. А вот эти ваши рассуждения:
Ваша ошибка в том, что вы считаете вероятность попадания в заданную математическую точку нулевой (а значит нулевой в любую точку, а значит вероятность попадания в отрезок, который является суммой математических точек — тоже нулевой… Бред.)
ошибочны вот в этой части:
а значит нулевой в любую точку, а значит вероятность попадания в отрезок, который является суммой математических точек — тоже нулевой… Бред.
Нулевая вероятность попадания в конкретную точку. А в любую на заданном отрезке уже не нулевая.
Я, конечно, могу ошибаться, но пока что явные логические нестыковки именно в ваших рассуждениях. Готов спорить.
Если вас смущает разница между «нулевая» и «стремящаяся к нулю при dt->0». То готов согласиться.retran
15.03.2017 11:19Именно эта разница меня сильно и смущает. Между «нулевая» и «стремящаяся к нулю» есть огромная разница, которая проявляется, например, при попытке эти вероятности сложить. И, например, если пуассоновских потоков МНОГО, то вероятность о которой мы говорим становится вполне заметной.
trapwalker
15.03.2017 11:23+1Эта вероятность становится заметной только в случае, когда пуассоновских процессов БЕСКОНЕЧНО МНОГО. И то я бы еще подумал над этим. Бесконечности бывают разных порядков.
Подытожу. Математическая точка — это не интервал. Вероятность попадания в конкретную математическую точку строго нулевая, а вот вероятность попадания в отрезок стремящийся по длине к нулю уже не нулевая, а стремящаяся к нулю.retran
15.03.2017 11:25Хорошо, соглашусь. Только остается вопрос — почему вы считаете событие нульмерной математической точкой?
UPD. В рамках этой задачи. Чем отличается событие от процесса в физических моделях я знаю.trapwalker
15.03.2017 11:32+1По определению.
Если мы оперируем пуассоновскими определениями, то и события надо рассматривать в математическом смысле.
К тому же по условию задачи длительность обработки события не обсуждалась, посему имеет смысл считать его нулевым, как математическую абстракцию.retran
15.03.2017 12:29Ок. Действительно, существует абстрактное понятие элементарного события (https://en.wikipedia.org/wiki/Elementary_event), вероятность которого в непрерывном пространстве всегда равна нулю, из чего в определениях делается вывод, что в непрерывном пространстве имеют вероятность только НЕэлементарные события (а события в пуассоновском потоке, очевидно, вероятность имеют).
И, действительно, определение пуассоновского процесса в русской википедии содержит «Свойство ординарности: вероятностью наступления за элементарный промежуток времени более одного события можно пренебречь по сравнению с вероятностью наступления за этот промежуток не более одного события», с чем я спорить не буду.
Определение свойства из другого источника: Поток событий называется ординарным, если вероятность появления двух или более событий в течении элементарного интервала времени ?t есть величина бесконечно малая по сравнению с вероятностью появления одного события на этом интервале.
Про нулевую вероятность не нашел ничего.
Вот только нигде я не нашел определения того, что пуассоновский поток оперирует именно элементарными событиями. Наоборот, везде рассматривают ТОЛЬКО события попадания в некоторый интервал (тут, например, довольно подробно — https://en.wikipedia.org/wiki/Poisson_point_process).trapwalker
15.03.2017 12:48+1Я так понимаю сути дела наш терминологический спор не меняет. Зачем захламлять тред несущественным гиковским буквоедством? Давайте прекратим.
По существу, как я понял мы сошлись. Тем более в классическом паттерне технической реализации подобных систем с «одновременным» приходом покупателей проблем нет. Если таймштампы у них оказались равны, то обрабатываем их по мере поступления запросов. Надо сильно «постараться», чтобы это стало технической проблемой.retran
15.03.2017 18:24Каждая заявка влияет на стейт нашего продавца, а значит порядок обработки все-таки важен.
Более того, в реальных задачах на operations research есть процесс обработки заявки имеющий конкретную длину и стоимость, а сама заявка — тайм-аут, и стратегия разгребания очереди может очень сильно повлиять на финансовое состояние продавца.
Но да, давайте прекратим.
3dcryx
15.03.2017 14:07отрезок, который является суммой математических точек
Откуда вы это взяли? Что вообще значит эта фраза? Отрезок — это просто множество точек прямой лежащие между 2 точками этой прямой + сами эти 2 точки (концы отрезка). Вы имеете ввиду что длинна отрезка это сумма точек(в таком случае это вообще не понятно что)? Единственное опредление длинны отрезка которое мне изветсно дается через меру Жордана, и да мера Жордана конечного набора точек равно 0, а мера бесконечного набора может быть отличной от нуля (та самая длинна отрезка).
P.S Вероятность попадания в конкретную точку равна 0
TheShock
15.03.2017 15:13-1P.S Вероятность попадания в конкретную точку равна 0
Важно, что она равна не 0, а бесконечно мала. Первый раз мы ведь в эту точку попали, значит вероятность была ненулевая)mayorovp
15.03.2017 15:43-1Вероятность — это число. Действительное число не может быть бесконечно малым. Бесконечно малыми бывают только последовательности или функции.
TheShock
15.03.2017 15:47То есть вероятность нулевая, но, несмотря на нулевую вероятность, в точку мы все-таки попали?
trapwalker
15.03.2017 17:42Да. Было невероятно, что мы попадём именно в эту точку, но мы сделали это.
По-моему всё вполне интуитивно. А вас, похоже, смущает антропный принцип.
retran
15.03.2017 17:58-1В итоге — по определению непрерывного пуассоновского потока. Событие ненулевой вероятности, но по определению мы этой вероятностью пренебрегаем и считаем, что сумма пуассоновских потоков — это тоже пуассоновский поток.
ggrnd0
14.03.2017 19:23В самом начале покеупаем количество коров которое можно продать за 2Т времени + некоторый запас.
Случайные величины на то и случайные, что при вероятности события 1к10млн за час, оно может произойти трижды в течении минуты…
В дальнейшем, после продажи каждой коровы запрашиваем еще одну.
В итоге имеем фиксированные издежки содержания коров, при 100% реализации за время ~2Т.
Если данная стратегия убыточна, то следует установить планку минимальной цены продажи с исключением продаж классам, которые не могут купить за указанную цену.
Как следствие пропорционально уменьшится максимальный запас коров и издержки их содержания при увеличении средней выручки с коровы.
Конкуренции можно не бояться, конкурентам так же невыгодно продавать задешево.
mwambanatanga
14.03.2017 19:42Первая идея: отсеять те классы покупателей, прибыль от которых не покрывает затраты на содержание коров. Т.е. тех, торговая наценка (x) для которых меньше, чем содержание одной коровы (u), умноженное на среднее отклонение функции распределения (тоже l, ибо для Пуассона дисперсия равна матожиданию).
Vjatcheslav3345
14.03.2017 19:54Это уже есть в задаче — мужик продаёт коров с наценкой, а этот термин подразумевает ненулевую прибавку к ненулевой денежной сумме себестоимиости (т. е. это все равно что сказать, что у всех классов всегда есть минимальная или большая платежеспособность, равная сумме себестоимости и минимальной наценки).
Sergey_Kovalenko
14.03.2017 20:00Если коров скопилось очень много, то за их сбыт Мужик сам даст денег, потому что это выгоднее чем их понапрасну кормить.
mwambanatanga
14.03.2017 20:11Да, я уже понял, что идея решать задачу для каждого класса отдельно оказалась неверной.
В общем, пока так. Решение, продавать ли корову текущему покупателю, зависит от:
* Класса покупателя
* Количества коров на складе
* Потока коров из деревни (количества и времени поступления на склад)
Решение, заказывать ли ещё коров (или корову), зависит от:
* Количества коров на складе
* Потока коров из деревни
Поскольку процесс пуассоновский, предсказать появление следующего клиента на основе данных о предыдущих клиентах не получается и делать что-либо «в ожидании богатого клиента» нельзя.lgorSL
15.03.2017 17:30Поскольку процесс пуассоновский, предсказать появление следующего клиента на основе данных о предыдущих клиентах не получается и делать что-либо «в ожидании богатого клиента» нельзя.
Можно. (делать, а не предсказывать)
Пример: есть 1 корова, пополнение появится через большое время t.
По оценке, самый выгодный тип покупателей придёт раньше чем t c большой вероятностью (Например, 0.9). В таком случае нет смысла прям сейчас продавать корову дёшево.
mwambanatanga
16.03.2017 12:09Дополню самого себя:
Решение, заказывать ли ещё коров (или корову), зависит от:
* Количества коров на складе
* Потока коров из деревни
… а поток коров зависит от прежних заказов. Итого остаётся только зависимость до-заказа от текущего запаса. Дабы поток коров совпадал с ожидаемым (средним) потоком клиентов, за каждой продажей должен следовать заказ одной коровы. Желательно заказывать прямо в момент продажи. Чем меньше интервал между продажей (изменением состояния запаса) и прибытием заказанной коровы, тем легче управлять запасом — тем быстрее запас возвращается к оптимальному уровню.
Vjatcheslav3345
14.03.2017 21:47за их сбыт Мужик сам даст денег
Т. е. на рынке появляются ещё и клоны Мужика — клиенты, которым он дал корову и пообещал дать денег за её сбыт другому клиенту?
mwambanatanga
15.03.2017 13:39Нет. Это лишь означает, что Мужик продаст себе в убыток, лишь бы избавиться быстро и не увеличивать расходы.
Sergey_Kovalenko
14.03.2017 19:58Боюсь, оба решения вкладывают в вероятность совсем не тот смысл, который принят для этого понятия в математике. Вы никогда не знаете, сколько придет покупателей в ближайший час и каких: у вас есть лишь вероятности каждого их набора, которые оправдываются в среднем и то лишь по вероятности. Пусть, например, класс покупателей только один, их количество за час имеет распределение Пуассона с математическим ожиданием 1. Если вы собираетесь закупать раз в час корову, то учтите, что более чем в четверти случаев по истечению часа не сможете продать купленную в прошлый раз, и с довольно большой вероятностью, если на начало очередного часа у вас будет только одна корова, то по крайней мере один клиент будет потерян.
Vjatcheslav3345
14.03.2017 20:16Тогда нужно уравнять вероятности получения сопоставимых дохода от продажи коровы и потери от потери клиентов и расходов на содержание у мужика. Другое дело — избавится от потерь совсем и получить всю возможную прибыль — не получится в принципе.
ggrnd0
14.03.2017 21:19Если ответ был мне, то я как раз начал с покупки некоторого буфера, который мы будем восстанавливать после каждой покупки.
Буфер равен #(коров продаваемых за Т времени с рассчетом основанном на веротносях) + некоторый запас сверх рассчетов.
Запас следует корректировать исходя из реальных данных.
Указать размер этого запаса заранее крайне сложно зависит от конкретных значений распределения.
В случае 1/1 запас имеет смысл сделать равным 1, если это экономически целесообразно с учетом стоимости продажи и содержания коровы…
Я описал общую стратегию, а вот выводить точные формулы как то лень… =)Vjatcheslav3345
14.03.2017 21:39Достаточно словесных рассуждений.
Принимать эмпирический "+ некоторый запас сверх рассчетов." нет смысла так как для этого и предназначен вероятностный расчёт количества коров, и если расчёт вероятности не действует — то его надо править, убирая логический костыль.
Реальные барышники на реальных рынках скота (например — в дореволюционной России, на скотных рынках Аргентины — страна, которая в начале XX века считалась одной из самых процветающих в мире) статистику продаж мусоленным карандашом по обёрточной бумаге наверное вели, а вот обработать её, чтобы избавиться запаса сверх расчётов, не могли — и для этого они не должны были нанимать академика Крылова, достаточно было сообразить заплатить за эту работу бедному учителю математики или студенту тех времён.ggrnd0
14.03.2017 22:08Я тот студент.
А костыль следствие:
а) отсутствия конкретных данных, есть только всякие К-атые значения
б) Я описал общую стратегию, а вот выводить точные формулы как то лень
Описанная стратегия работает на максимизацию покрытия рынка.
Если надо максимизировать прибыль, то надо просто повысить нижнюю планку стоимости коровы и уменьшить запас.
Какова оптимальная на длительном периоде стратегия Мужика при почти бесконечном начальном капитале?
Вы заметили что тут даже целевой функции нет?
mwambanatanga
15.03.2017 05:33Целевая функция присутствует неявно. Это максимизация прибыли на интервале 0-бесконечность. Или, если угодно, средней прибыли за единицу времени.
ggrnd0
14.03.2017 22:15Буфер равен #(коров продаваемых за Т времени с рассчетом основанном на веротносях)
неправильно написал, основанном на матожиданиях.
а сверх-запас призван оперировать вероятностью, что коров не хватит.
По факту, конечно, должна быть формула, по которой можно посчитать точно необходимый запас по каждому классу с четом вероятностей и потом сложить.
Sergey_Kovalenko
14.03.2017 20:21Как мне представляется, задача достаточно сложная, ее решение с обоснованием, если оно где-то опубликовано,- небольшая глава в книге по алгоритмам. Не стоит торопится с ответом)
Vjatcheslav3345
14.03.2017 20:51Глава 7? (задача напомнила задачу про ковры скомбинированную с потоками в сетях)
Sergey_Kovalenko
15.03.2017 13:55Я еще раз обдумал Ваше предложение и должен признать, что приближенное решение можно свести к задаче сильно напоминающей поиск максимального по мощности циклического потока в графе, однако на этот поток, в случае чистой стратегии (детерминированной), накладываются ограничения неделимости в узлах, поэтому, как Вы понимаете, вся простота алгоритмов теряется. Если применять смешанные стратегии (зависящие от случая), решение приближенной задачи действительно можно найти указанным способом, однако есть две проблемы:
а) нужно доказать, что максимум достигается на чистой стратегии (почти очевидно)
б) вычислительная сложность растет по экспоненте от величины обратной к величине шага дискретизации.
Sergey_Kovalenko
17.03.2017 18:55+1б) можно отбросить: для поиска циклического потока максимальной стоимости есть алгоритм куда проще с вычислительной точки зрения, чем линейное программирования. Еще раз спасибо за идею.
koldyr
14.03.2017 21:07Всё это, конечно, контринтуитивно. Поэтому, на уровне гипотез.
Если мужик не продает коров совсем, то прибыль -0, но и убытков 0.
Таким образом, может возникнуть ситуация (например при низкой интенсивности потока покупателей), что стратегия минимизации убытков — не торговать.
Пусть мужик держит на продажу одну корову. Тогда можно построить что-то типа протокола разборчивой невесты.
Дальше пока не придумывается.
michael_vostrikov
14.03.2017 21:08+3при почти бесконечном начальном капитале
Зачем Мужику при почти бесконечном капитале продавать коров?)
michael_vostrikov
14.03.2017 21:17Если все условия можно задать в виде линейных неравенств, можно попробовать применить симплекс-метод.
ggrnd0
14.03.2017 21:27Не удастся выразить распределение пуассона в линейном виде.
Приближенная линейная функция будет давать серьезную погрешность, сводящую смысл применения симплексного метода к нулю.
Тут задача управления складским запасом, они решаются спец методами под это заточенными.
LonelyCruiser
14.03.2017 21:27В универе похожее решали на «Исследовании операций» (Мат. программирование)
trapwalker
15.03.2017 00:19+1Забавная задачка. Сходу напрашивается ряд «решений», а по зрелому размышлению проявляются интересные нюансы, упрощения и оптимизации.
Первое, что нам нужно для себя решить — это оптимальный размер буфера коров, который мы будем держать в резерве (S*). Очевидно, что оно будет зависеть от всех параметров этой задачи. Давайте отложим нахождение этой величины.
Итак, у нас для каждого случая (прихода покупателя; пронумеруем их по i) есть текущий запас коров S_i. Нам нужно:
1. решить, продавать корову этому покупателю или нет;
2. решить, сколько заказать коров из деревни (может быть 0, заказ-то бесплатный и, как я понял из задания, асинхронный? Поправьте меня, автор, если ошибаюсь).
По поводу второго пункта следует заметить, что акт заказа коров, строго говоря, не должен быть привязан к событиям прихода покупателей, то есть не обязательно должен происходить по факту прихода кого-то из них или по факту продажи. Похоже это тоже будет пуассоновский поток событий, параметр которого будет вычисляться из вероятностей потока покупателей. Если вероятности прихода покупателей рассчитаны (даны) верно, то процесс стационарный и, возможно, не придется даже динамически управлять параметром потока заказов. Вернее эффективнее будет не управлять.
Итак. Декомпозиция выявила три вопроса:
1. Каков оптимальный размер буфера (S*)?
2. Продавать ли корову i-му покупателю?
3. С каким интервалом дозаказывать коров?
Забавно, что в случае идеального пуассоновского процесса нам, скорее всего, можно вообще в самом начале определить какие классы обслуживать, а какие нет. И в начале же определить четко интервал времени дозаказа коровы. Очевидно, что при бесплатном асинхронном заказе нет смысла заказывать больше одной за раз.
Ок. С формулами я сейчас уже не осилю, да и тестовый стенд писать уже лень, но предположу, что мы просто откинем некоторые классы покупателей по рентабельности резервирования для них коровы с учетом среднего времени их появления. Остальным продаём корову из буфера, размер которого будет зависеть от вероятного количества обслуживаемых клиентов за время T.
Возможно следует еще оценить вероятностные характеристики убытка при потере клиента и как-то сравнить их с вероятностными характеристиками убытка от over-резервирования. Но это заметно усложнит формулу расчета глубины резерва.
Резюме. Задача похоже стационарна и не требует онлайн-управления процессом.lair
15.03.2017 00:49Мне вот тоже пришла в голову идея, что можно просто посчитать, сколько покупателей какого типа к нам (в среднем, но в долгосрочной перспективе только среднее и интересно) приходит за некий (произвольно взятый) интервал времени
Q. Столько коров нам и нужно (X). Дальше заказываем по одной корове вQ/X(а начальный резерв берем какT/(Q/X)).
Sergey_Kovalenko
15.03.2017 00:59Многие из ваших замечаний разумны, например, как вы правильно заметили, нужно учитывать, какие коровы уже заказаны и что они придут в будущем. Если же ваши ожидания насчет потока клиентов не оправдываются, действительно не стоит заказывать лишних коров, и поэтому правдоподобно, что заказ, если происходит, то только в момент продажи. Однако процесс требует постоянного управления и не сводится к определению размера буфера, поскольку оптимальность зависит не только от количества коров в вашем распоряжении сейчас но и от именно функции «уже заказанное пополнение»(«время»). С выбраковкой классов тоже не стоит спешить: если все шло как по часам, а затем случайно целый период T не было продаж, то возможно от лишних коров стоит избавится при первой возможности.
TheShock
15.03.2017 01:49если все шло как по часам, а затем случайно целый период T не было продаж, то возможно от лишних коров стоит избавится при первой возможности.
А если 10 раз подряд выпало красное, то нужно ставить на черное?
Согласен с предыдущими ораторами. В силу случайности и полной непредсказуемости все, что происходило до данного момента времени абсолютно неважно. У нас есть только сейчас и будущее. Весь вопрос только в размере буфера. Если буфер забольшой, что приходится продавать корову — значит неправильно посчитан буфер и корову продавать не нужно было.mwambanatanga
15.03.2017 08:55А если 10 раз подряд выпало красное, то нужно ставить на черное?
Не совсем так. Тут беда в том, что из-за отсутствия продаж на складе скопилось количество коров выше оптимального.
У нас есть только сейчас и будущее
Да. Поэтому оптимальное количество не зависит от прошлых продаж/непродаж. Если текущее количество выше/ниже, то его надо вернуть до оптимального.
Если буфер забольшой, что приходится продавать корову
Нет. При любом (!) буфере будут ситуации, когда коров слишком много, и ситуации, когда продавать нечего.trapwalker
15.03.2017 10:02+1из-за отсутствия продаж на складе скопилось количество коров выше оптимального.
оптимальное количество не зависит от прошлых продаж/непродаж. Если текущее количество выше/ниже, то его надо вернуть до оптимального.
При любом (!) буфере будут ситуации, когда коров слишком много, и ситуации, когда продавать нечего.
Чувствуете в чем подвох? Если размер буфера больше оптимального, издержки на его содержание растут быстрее, чем прибыль от не упущенных (за счет этого увеличения буфера) клиентов. Если размер буфера меньше оптимального, издержки по статье недополученной прибыли из-за упущенных (из-за этого уменьшения буфера) хороших клиентов будут раст быстрее чем выигрыш (экономия) на прокорме буфера.
Предполагается наличие седловой точки оптимума размера буфера.
Оптимальный размер буфера мы можем в среднем держать за счет установки скорости заказа коров, равной средней скорости сбыта их рентабельным клиентам. Если эта средняя скорость сбыта известна наверняка и точно, то мы всегда будем блуждать около этой точки туда-сюда. Экстренно динамически продавая лишних коров сверх оптимума нерентабельным клиентам вы делаете подстройку только с одной стороны.
Во-первых, почему вы тогда не предлагаете явно дозаказывать динамически коров в ускоренном режиме при перерасходе (то есть когда буфер меньшеоптимального)?
Во-вторых, зачем вообще эта дополнительная инертная обратная связь нужна, когда по условию задачи четко известна средняя скорость сбыта коров? Дёргая динамически буфер туда-сюда, то есть заказывая коров из деревни с непостоянной скоростью и сбывая их иногда нерентабельным клиентам вы лишь уменьшаете добротность системы внося еще один маятник со всеми вытекающими. У нас нет «тренья» в системе и, может быть ваш такой микроменеджмент и не приведёт в среднем ни к профиту ни к издержкам, но зачем усложнять алгоритм?
Полагаю это обосновано было бы только для безопасности на случай внезапного и незадокументированного изменения параметров потока покупателей. А об этом в задаче речи не шло. Потому я и сказал в треде. что на данном этапе хорошо бы уже спуститься в реальность, а не надувать сферического коня в безвоздушном пространстве.mwambanatanga
15.03.2017 13:56Предполагается наличие седловой точки оптимума размера буфера.
Ага. Только вот как его расчитать…
Оптимальный размер буфера мы можем в среднем держать за счет установки скорости заказа коров, равной средней скорости сбыта их рентабельным клиентам
Чуть сложнее: если в какой-то момент мы остались без коров и пропустили покупателя, нам придётся пропускать и заказ. И наоборот: если в какой-то момент мы накопили избыточный запас коров, для нас любой клиент внезапно становится рентабельным.
Во-первых, почему вы тогда не предлагаете явно дозаказывать динамически коров в ускоренном режиме при перерасходе (то есть когда буфер меньшеоптимального)?
Да, надо. Только вот по какому правилу? В каком количестве? В какой момент времени, учитывая время доставки? Как момент и объём заказа увязать с текущим остатком?
Как мне это видится, задача сводится к двум вопросам:
* Как определять, когда и сколько коров дозаказывать?
* Как определять, продавать текущему клиенту или нет?trapwalker
15.03.2017 14:23наоборот: если в какой-то момент мы накопили избыточный запас коров, для нас любой клиент внезапно становится рентабельным.
Тогда где остановиться? Характер закона распределения не позволяет нам рассчитывать на 100% от пропуска клиента при любом размере буфера. Да, в какой-то момент вероятность пропуска клиента становится столь малой, что можно пренебречь, но есть же и фиксированная цена заказа коровы a, а условие допускает отрицательную маржинальность. Это делает «любого клиента» ой как нерентабельным.
TheShock
15.03.2017 13:40А если 10 раз подряд выпало красное, то нужно ставить на черное?
Не совсем так.
Совсем не так!
Нет. При любом (!) буфере будут ситуации, когда коров слишком много, и ситуации, когда продавать нечего.
Нет. Если буфер равен 0 или 1 — коров не будет слишком много. Продавать коров нет смысла. Если вы дошли до ситуации, когда продаете корову по дешевке — значит не нужно было ее покупать.mwambanatanga
15.03.2017 14:02Если буфер равен 0 или 1 — коров не будет слишком много
0 коров это не буфер. На счёт 1 не уверен: 1 корова в момент непосредственно после сделки может быть «слишком много», если поток клиентов редкий, рентабельность низкая, а стоимость хранения высокая — в таких условиях можно было бы устроить её доставку ближе к середине среднего интервала между двумя клиентами, чтобы не кормить зря.TheShock
15.03.2017 15:08+1Просто в этом месте становится понятно, что вы не очень понимаете теорию вероятностей. Если вероятность, что клиент придет в ближайшую минуту — 0.001%, то от того, что клиент не приходил 1000 минут вероятность не изменится.
Вы мыслите на классическом обывательском уровне — «редкое событие произошло, значит в ближайшее время вероятность его возникновения понижена».
Понимаю, что для вас это контринтуитивно, но, увы, это не так.mwambanatanga
15.03.2017 16:51вы не очень понимаете теорию вероятностей
Я даже на «не очень» не претендую. Поэтому и написал в предыдущем комментарии, что «не уверен».
Кстати, после вашего наставления у меня прибавилось уверенности. Однозначно есть набор параметров, при котором одна корова в запасе будет «слишком много». Это будет в ситуации, когда для каждого класса покупателей k выполняется неравенство xklk < u :-)TheShock
15.03.2017 17:18Ну да, конечно, если покупателей, например, 0, то 1 корова уже слишком много)
Я говорил об этом:
в таких условиях можно было бы устроить её доставку ближе к середине среднего интервала между двумя клиентами
Я приведу пример. В рулетке вероятность выпадения числа 13 — 1/37. Если выпало 13 — необходимо ли пропустить пару следующих бросков, чтобы приблизиться к следующим 13?
Вот так и тут. От того, что клиент пришел абсолютно нету никакого резона отступать на какой-то промежуток времени — это не дает выгоды, а только затягивает игру.mwambanatanga
15.03.2017 18:09Я говорил об этом:
Да, я ошибся. Хотя у нас по-прежнему нет решения.
в таких условиях можно было бы устроить её доставку ближе к середине среднего интервала между двумя клиентами
Ну да, конечно, если покупателей, например, 0, то 1 корова уже слишком много)
Если покупателей 0, то нет задачи. А вот если торговля в принципе нерентабельна, всё равно нужна стратегия распродажи запасов с наименьшими потерями.
michael_vostrikov
15.03.2017 18:13Ну я так понимаю, вероятность 1/37 говорит о том, что после 37 бросков вероятность выпадения 13 хотя бы 1 раз близка к 1. Но ок, тут может и не так.
А вот распределение Пуассона, насколько я понял, зависит от времени, то есть за определенное время происходит определенное число событий. Получается, чем больше мы ждем, тем число событий ближе к этому определенному. А как только событие произошло, вероятность его повторения в следующий момент времени маленькая, иначе это число событий было бы больше.
Как с автобусом — чем дольше ждешь, тем больше вероятность, что придет нужный номер, и тем меньше причин ехать на другом. И после того, как он пришел, маловероятно, что через полминуты появится еще один такой же.
TheShock
15.03.2017 21:32+1Вот как раз сравнение с автобусом — ошибочно. Приход автобуса — процесс не случайный, ведь они ходят по графику. Если бы автобусы запускали подбрасыванием монетки — ага, решка, значит 15-й, а орел — 21-й, то ваш пример был бы аналогичен, но снова ошибочен.
Ну я так понимаю, вероятность 1/37 говорит о том, что после 37 бросков вероятность выпадения 13 хотя бы 1 раз близка к 1
Вероятность решки на монетке 1/2, следует ли из этого, что при двух бросках вероятность выбросить решку близка к 1?
А как только событие произошло, вероятность его повторения в следующий момент времени маленькая, иначе это число событий было бы больше.
Нет, нет и еще раз нет. Предыдущее событие НИКАК не влияет на следующее. Серьезно. Возьмите монетку. Киньте ее. А потом считайте, сколько раз выпало то же, что и в предыдущий, а сколько раз иной вариант. И вы увидите, что в 50% случаев выпадает тот же вариант, а в 50% случаев вариант меняется. Потому что неважно, что выпало перед этим. Если вы кинули 5 раз подряд орла — шестой раз ровно так же у орла 50% вероятности, как и у решки. Оно не уменьшается от того, что Пуассон вывел свое распределение.
Смотрите. Допустим мы монетку кидаем дважды. Значит у нас есть такие варианты:
(О-О), (О-Р), (Р-О), (Р-Р). Вероятность того, что выпадет два орла всего 25%, но если перед этим уже выпал орел вероятность того, что снова выпадет орел — 50%, понимаете?michael_vostrikov
16.03.2017 04:53Да, с монеткой вы правы. Ну я поэтому и сделал оговорку, что возможно это не так. Просто, как мне кажется, здесь 2 принципиально разные ситуации. В случае с рулеткой и монеткой вероятность зависит от количества вариантов, в случае пуассоновских процессов вероятность рассчитывается по отрезкам времени. Если мы знаем, что за час должно прийти 2 покупателя такого типа, то если за полчаса никто не пришел, то в следующие полчаса вероятность появления выше. А если и за час не пришел, то в следующий час можно ожидать 4. Иначе характеристика была бы не "2 покупателя в час", а "1 покупатель в час". А если стабильно никто не приходит, уже надо говорить о том, что характеристика изменилась.
С автобусами аналогично. Автобусы ходят по графику, но в пределах одной остановки появление следующего номера рассматривается как случайная величина. Вернее, обладающая свойствами случайных. Потому что есть светофоры, пробки, поломки, а также другие автобусы, у которых свое расписание и набор остановок. А вот расписание как раз и означает, что за час на эту остановку должно прийти 3 автобуса с этим номером.
TheShock
16.03.2017 05:20+1Нет, вам неправильно кажется.
Начнем с автобусов. На них не работает распределение Пуассона. Потому что оно работает только на независимых событиях. А приход автобусов очень даже зависим. Да, есть случайные факторы, которые смещают время прихода в одну или другую сторону, но это не связано с распределением Пуассона.
Дальше.
Если мы знаем, что за час должно прийти 2 покупателя такого типа, то если за полчаса никто не пришел, то в следующие полчаса вероятность появления выше
Нет, не выше. Вы думаете, что за углом стоит Пуассон и считает, сколько именно покупателей к нам заходит и если их меньше чем нужно, то срочно посылает своих агентов? А если пришли 8 вместо 2? То теперь шестеро умрут не выйдя из магазина?
Распределение Пуассона говорит приблизительно следующее. В среднем у нас десять покупателей в час. Следовательно:
11% вероятности, что у нас будет 10 покупателей
10% вероятности, что у нас будет 9 покупателей
9% вероятности, что у нас в ближайший час будет 11 покупателей
и даже 1% вероятности, что у нас будет 20 покупателей за ближайший час.
Все. Больше распределение Пуассона ни о чем не говорит. Только о том с какой вероятностью какой час выпадет. Так вот. Есть 5% вероятности, что придет 5 покупателей и 5% вероятности, что придет 15 покупателей. Если в первые полчаса пришло только двое — может мы попали в неудачные 5%. А если в первые 15 минут пришло 10, то может попали в тот удачный 1% и потом будет еще десять.
Самое главное, что предыдущие события НИКАК не влияют на следующие. То есть пусть у нас предыдущих два часа был полный завал или пустой магазин следующий час с сего момента (и с любого момента) имеет ровно тот же график распределения Пуассона.
Конечно, только в теории и потому с магазином контринтуитивно. Ведь вы ведь знаете — в обед в магазине обуви никого нет, а под вечер просто завал, вот же доказательство. Но нет, это влияние не распределения, а просто рабочего графика среднего класса
michael_vostrikov
16.03.2017 05:23А если и за час не пришел, то в следующий час можно ожидать 4.
Ок, почитал комменты ниже, понял, что не прав)
mayorovp
15.03.2017 21:50+3На самом деле, предел 1-(1-1/n)n стремится не к 1, а к 1-1/e, что составляет примерно 0,63
Именно такова будет вероятность получить хотя бы одно число 13 после 37 вращений рулетки.
trapwalker
15.03.2017 02:49С выбраковкой классов тоже не стоит спешить: если все шло как по часам, а затем случайно целый период T не было продаж, то возможно от лишних коров стоит избавится при первой возможности.
Во-первых, надо понимать, насколько адекватно у нас заданы условия. Это, я считаю, важно отметить в описнии задачи. Если характеристики случайных величин верны (например случайные величины специально генерируются с указанными параметрами), то онлайн регулирование не требуется, или требуется, но исключительно калибровочное. Мы можем немножко менять скорость выписывания коров или изредка просто сливать лишних как исключение. Для реального мира эти величины скорее всего взяты из статистики и нам постоянно грозят черные лебеди, неучтенные ошибки и изменения на рынке. В этом случае надо более агрессивно держать оптимальный запас.
В любом случае эти параметры тонкой настройки не гарантируют ничего. Это просто рандомная ставка на риски, те или иные — не важно.
Если же ваши ожидания насчет потока клиентов не оправдываются, действительно не стоит заказывать лишних коров
Мои ожидания по поводу потока клиентов основаны на данных из условий задачи. Это вектор l. Если эти ожидания не оправдываются на долгосрочной перспективе, то это значит лишь, что исходные данные (тот самый вектор) не описывает распределение событий. В этом случае мы должны корректировать вектор (например, уточнять его статистикой), или агрессивно подстраивать поток заказов. Но это уже не будет исходной задачей.
Да и на счет "лишних коров", почему вы однобоко подходите к возможным рискам? А если «неоправдавшиеся ожидания» привели к обратной ситуации и коров не хватило, отчего мы потеряли хороших клиентов и недополучили прибыль? Если скорость пополнения буффера и его размер выбраны верно, а «ожидания» соответствуют характеристикам случайной величины, то риски в ту и другую сторону одинаковы.
Ну а вы в данном случае поддались классическому когнитивному искажению отдавая в плане рисков незаслуженный приоритет тому, что имеете по отношению к тому, что могли бы иметь.
Подчеркну для ясности.
как вы правильно заметили, нужно учитывать, какие коровы уже заказаны и что они придут в будущем.
Я не говорил, что это нужно как-то учитывать онлайн-управлением. Это должно быть учтено автоматически в скорости заказа коров из деревни на основе вероятностных зарактеристик потока покупателей.
TheShock
15.03.2017 02:05не должен быть привязан к событиям прихода покупателей, то есть не обязательно должен происходить по факту прихода кого-то из них или по факту продажи
На самом деле, скорее всего, должен. Смотрите.
Допустим, у нас есть состояние (state). В этом состоянии:
1. Вероятность прихода покупателя
2. Текущее количество коров
3. И другая статика типа цены на корову
Решение о покупке (покупать или нет) мы делаем только на основе этого состояния, но не того, что было ДО него. У нас полностью случайный рынок, следовательно ситуация как в казино — приход 10 черных цифр все-еще оставляет равную вероятность прихода каждого цвета. Ждать какое-то время после прихода покупателя — все-равно, что ждать, чтобы выпало еще черное, чтобы ставить на красное.
То есть наш state изменяется исключительно в момент покупки коровы, а потом каждый отрезок времени ничего не меняется.
Значит весь вопрос задачи только в максимальном количестве коров, к которому мы всегда стремимся. Ну и, конечно, определение списка классов, которым мы продаем, но это статика, которая определяется до начала продаж.TheShock
15.03.2017 02:10И еще на примере. Допустим T=0 (то есть корову могут доставить сразу после заказа). Следовательно в таком случае мы делаем Макс=1 и заказываем корову сразу после того, как у нас забирают ту, что есть. Ждать время — это исключительно игра в рулетку:
— У меня корову только что купили, так что ближашие несколько минут покупателя точно не будет, значит надо немножко подождать, перед тем, как заказывать следующую и плевать на теорию вероятностей.TheShock
15.03.2017 03:22+1На примере. Допустим, цена продажи коровы Ц=100, цена содержание за время доставки — Р=70, а также приходит в среднем 10 человек за время доставки.
Если мы возьмем максимум коров М=10, то получим такое распределение:
Если количество коров М=15, то такое распределение:
Для того, чтобы посчитать среднюю прибыль для каждого количества коров необходимо умножить прибыль каждого варианта на вероятность этого варианта и просуммировать.
К примеру, для 15:
... + -550*вероятность(5) + ... + -50*вероятность(10) + ... + 450*вероятность(15)
Уверен, для этого есть формула. К сожалению, по образованию гуманитарий, так что вспомнить ее не могу.
Так вот, таким образом мы получим прибыль для каждого варианта. Увеличивая М на 1 будем получать все большую сумму. (при М=0 — С=0, при М=1 — С=~30). И в какой-то момент эта сумма начнет падать. Вот это число М, которое имеет наибольшую сумму — есть наш буфер для данных чисел.TheShock
15.03.2017 03:35Я забыл учесть, что коровы продаются, следовательно в расходе необходимо это учитывать. Например для М=15:
Расход в случае 5 покупателей: 70 * (15 - 5/2) Расход в случае 10 покупателей: 70 * (15 - 10/2) Расход в случае 15 покупателей: 70 * (15 - 15/2)
Может показаться странным, что я не беру в рассчет заказанные коровы, но это неважно. Мы рассчитываем буфер и заказываем новую корову при продаже старой. Следовательно за это время буфер обновится и в среднем для новых 15 коров будет та же выгода.
trapwalker
15.03.2017 03:23Никогда не стоит плевать на теорию вероятностей, иначе мы рискуем впасть в азарт и просадить все состояние из-за когнитивных искажений.
Не забывайте, что у нас речь идет о симметричном риске с двух сторон: 1) подержать лишних коров какое-то время на довольствии; 2) пропустить ценного клиента при опустевшем буфере.
Пуассоновский характер поступления покупателей даёт нам понимание, сколько в среднем на большом интервале времени их приходит за единицу времени. Этого (вкупе с прочими параметрами) достаточно, чтобы определить строгую регулярную частоту заказа коров, которая в среднем будет покрывать требования покупателей. Увеличение буфера уменьшает количество упущеных покупателей (недополученная прибыль), зато увеличивает расходы на корм. Уменьшение буфера снижает расходы на корм, зато недополученная прибыль на пропущенных клиентах начнет расти.TheShock
15.03.2017 03:30Про «плевать на теорию вероятностей» это был сарказм, конечно. Но если отвязаться от покупателя и просто покупать коров равнораспределенно, то тогда формулы вообще упрощаются.
trapwalker
15.03.2017 03:47Именно! И надежность решения растёт. Надо нарисовать графики рисков по упущению и по перерасходу кормёжки от размера буффера. Там, где они пересекутся и будет оптимальный размер.
Простите, не могу комментировать с вашей скоростью, поэтому отвечу здесь.
Я говорю о том, что по факту покупки необходимо покупать сразу корову, все. Продал корову — заказал новую. Если мы сидим с пустым буфером, то значит у нас в заказах уже висит максимальное количество коров. И такое может быть с абсолютно любой выгодной стратегией — пустой буфер, куча коров в ожидании и новый клиент. Вопрос исключительно в том, какой должен быть буфер.
Нельзя заказывать только по факту продажи из-за возможного очень большого лага T. Интуитивно представьте, что наблюдается времнное затишье и покупатели не идут. Если они потом не усилят частоту прихода, значит у нас неверные данные о потоке, а если верные, то потом покупатели пойдут чаще и мы тупо не сформируем лаг. Я настаиваю на том, что данные о потоке однозначно определяют скорость заказов. И это будет работать при любых соотношениях T и среднего времени появления поупателей. А из-за вашего лага придется неоправданно увеличивать буффер терпя издержки на хавчике.TheShock
15.03.2017 03:54На самом деле, что ваш, что мой вариант в долгосрочной перспективе приблизительно одинаковые. Смотрите, что у вас, что у меня будет буфер. И мы с вами в среднем заказываем абсолютно одинаковое количество коров за единицу времени. Вы ведь заказываете в среднем коров столько, сколько клиентов приходит и я заказываю коров столько, сколько клиентов приходит. Следовательно где-то уже через 1Т у нас с вами будут висеть в заказах одинаковое количество коров и равное среднему количеству покупателей.
Вопрос лишь в начальном буфере. С каким количество коров необходимо прийти, чтобы максимизировать прибыль?
TheShock
15.03.2017 03:37Увеличение буфера уменьшает количество упущеных покупателей (недополученная прибыль), зато увеличивает расходы на корм. Уменьшение буфера снижает расходы на корм, зато недополученная прибыль на пропущенных клиентах начнет расти
Главный вопрос — как правильно рассчитать буфер, чтобы максимизировать прибыль.trapwalker
15.03.2017 03:55Например, построить график прибыли (упущеной с вероятностью P=const) от размера буфера. И посроить график издержек (с той же зафиксированной вероятностью вероятностью P) от размера буфера. Точка пересечения — идеальный размер с вероятностью P.
Поигравшись с вероятностями и применив волшебные три сигма по гауссу мы получим хорошие показатели.TheShock
15.03.2017 03:58У нас есть М (количество коров), Ц (цена продажи), Р (расходы на корову за время, равное времени доставки коровы) и А (среднее количество человек). Какие формулы для этих графиков?
trapwalker
15.03.2017 04:12Формула на самом деле будет еще сложнее, чем кажется, из-за множества категорий клиентов с разной скоростью потоков. Тут можно статистически графики построить оттабулировав настройки. Благо модель не сложная.
Можно заморочиться интегралами и дифурами, конечно, но если задача чисто академиеская, то я лучше спать, а если практическая, то там наверняка не так всё гладко с параметрами потока и лучше сразу строить адативную модель, которая будет инкремнтально уточнять себя по мере накопления данных и даже с учетом их устаревания и инвалидации.
Это тот самый порог, где порой стоит остановиться и решать даьше практическую задачу, вместо сферической в вакууме.TheShock
15.03.2017 04:41Как-то мой товарищ сказал, что в задаче интереснее доказать, что сам факт, что она решаема, чем таки найти решение)
trapwalker
15.03.2017 03:35Решение о покупке (покупать или нет) мы делаем только на основе этого состояния, но не того, что было ДО него.
Нам не нужно принимать такие решения по факту покупки. Из-за T, которое может в том числе сильно превышать средний интервал появления клиентов, мы рискуем замешкаться и пропустить покупателей сидя у пустого буфера. При этом мы халатно не используем данные в условии задачи параметры потока клиентов. Вероятностные характеристики потока однозначно определяют скорость наших заказов коров. Попытка рулить онлайн чревата потерями.
По-прежнему настаиваю, что никаких решений онлайн принимать в задаче не надо, если речь идет о достоверно известных параметрах потока (то есть величины генерируются по этим параметрам). Если параметры распределения собраны статистически, то нужно делать предоханители сверху и снизу, а также агрессивную петлю отрицательной обратной связи для борьбы с неполнотой сведений о реальных параметрах случайных величин.
В реальном мире параметры этих случайных величин не могут быть известны достоверно в принципе. А статистика — это заведомо неполная неточная информация.TheShock
15.03.2017 03:40Нам не нужно принимать такие решения по факту покупки. Из-за T, которое может в том числе сильно превышать средний интервал появления клиентов, мы рискуем замешкаться и пропустить покупателей сидя у пустого буфера
Я говорю о том, что по факту покупки необходимо покупать сразу корову, все. Продал корову — заказал новую. Если мы сидим с пустым буфером, то значит у нас в заказах уже висит максимальное количество коров. И такое может быть с абсолютно любой выгодной стратегией — пустой буфер, куча коров в ожидании и новый клиент. Вопрос исключительно в том, какой должен быть буфер.
dimaleks
15.03.2017 01:20Хотел бы добавить несколько соображений.
- Запрашивать достаточно по одной корове. В любом случае запрос нескольких коров одновременно можно разбить на несколько запросов по одной корове с бесконечно малым промежутком по времени.
Deosis
15.03.2017 07:27Тогда можно ещё приравнять стоимость коровы к единице (если в исходных данных она ненулевая)
И время доставки тоже нормализовать, пересчитав параметры распределения. Минус два параметра.
Sergey_Kovalenko, Мужик платит за содержание коровы, пока её доставляют на склад или нет?
Это может сильно повлиять на стратегию: коровы ещё в пути, а он уже несет убытки.trapwalker
15.03.2017 08:29Похоже не платит за еду при доставке. Но, на самом деле, не важно. В случае, если платит,. задача не изменится. Время доставки фиксировано, а значит стоимость еды во время доставки можно заложить в цену коровы.
dimaleks
15.03.2017 14:13-1Простите, отправил недописанный комментарий! Должно было быть примерно так:
- Запрашивать достаточно по одной корове. В любом случае запрос нескольких коров одновременно можно разбить на несколько запросов по одной корове с бесконечно малым промежутком по времени.
- Похоже, что все классы покупателей можно рассматривать по-отдельности.
Пусть у нас есть только один класс k1, пусть для него оптимальной будет стратегия S1.
Стратегия,… в моём понимании, это некоторый функционал от всех имеющихся на данный момент данных (о клиентах, о коровах, о запросах и т.д.) и времени, который принимает значение 0 или 1. 0 означает, что в этот момент времени мы ждём, 1 — запрашиваем корову.Sergey_Kovalenko
15.03.2017 14:25+1Думаю, независимость стратегий стоит обосновать получше: когда на рынке два продавца, каждый на свою аудиторию, иногда им будет выгодно кредитовать друг друга коровами.
dimaleks
15.03.2017 15:50-1Продавец ведь всегда один, разве нет? Я про классы покупателей
Sergey_Kovalenko
15.03.2017 17:17+1Применение двух независимых стратегий эквивалентно двум не взаимодействующим продавцам, ориентирующимся каждый на свой класс покупателей.
Bronx
20.03.2017 08:30-1Если A кредитует B, то B получает выгоду в виде неупущенного клиента, но зато у A образуется дефицит и увеличивается вероятность отказать своему клиенту. С другой стороны, B придётся когда-то отдавать корову, и в момент отдачи у него тоже образуется дефицит и вероятность отказа, зато у A в этот момент увеличится буфер и уменьшатся риски. На круг, риски скомпенсируют бенефиты, и все останутся при своих, как если бы стратегии были полностью независимыми.
mayorovp
20.03.2017 09:02Не будет у B дефицита и вероятности отказа, потому что ту корову, которую он будет отдавать обратно, он закажет дополнительно.
Bronx
20.03.2017 12:56В любом решении этой задачи должен соблюдаться закон сохранения среднего потока, иначе коровы будут либо накапливаться, либо склад опустеет. Если A и B оба держат поток заказов в среднем равным потоку продаж, то количество коров на складе у них в среднем не растёт и не падает, а держится вблизи оптимума, задаваемого соотношением средней цены потери клиента и средней стоимости корма для коровы до её продажи.
Если кто-то начинает заказывать коров вне очереди, значит где-то должно быть накопление коров и отклонение от оптимума — либо у А, либо у B. Заказ дополнительной коровы для покрытия кредита эквивалентен экстренному заказу дополнительной коровы для покрытия внезапного опустошения буфера в сценарии объединённого буфера.mayorovp
20.03.2017 13:20Смотрите еще раз:
- А отдал Б корову
- Б продал корову и заказал новую
- Б получил корову и вернул ее А
Где тут нарушился баланс-то?
Bronx
21.03.2017 00:51-1Если бы кредитования не было, то вышло бы так:
1) А продал единственную корову первому миллионеру
2) А отказал второму миллионеру
3) А некоторое время не заказывает новую корову, потому что по его оптимальной стратегии делать это ещё рано: средний поток миллионеров мал, и если заказывать корову немедленно, то её придётся долго кормить. А должен поддерживать достаточно низкий поток коров. Делать это он может лишь меняя частоту заказов (он не может заказывать пол-коровы)
Но в случае с кредитованием Б приносит А корову через день, и теперь у А больше коров, чем его оптимум, и он тратит деньги на корм, хотя, возможно, следующего миллионера после двух первых придётся ждать очень долго. Эффективная частота заказов увеличилась из-за Б, и на бесконечно большом промежутке времени А проиграет примерно столько, сколько выиграл.Bronx
21.03.2017 01:14-1Но в случае с кредитованием Б приносит А корову через день,
Прошу прощения, в последнем абзаце напутал чутка. Б даёт корову А немедленно. После этого А заказывает и отдаёт корову Б, а также должен решить, заказывать ли корову для себя или нет. Если он закажет, то эффективная частота заказов будет выше оптимума, и он будет терять на корме. Оптимальной стратегией будет пропустить один запланированный заказ, чтобы скомпенсировать незапланированное увеличение потока заказов — но это увеличивает риск отказа. На бесконечном промежутке времени… и т.д.
mayorovp
20.03.2017 09:11Вот вам простейший пример. Допустим, есть два типа покупателей. Первый покупает задорого (например, за миллион), но настолько редко, что для него выгодно держать только 1 корову. Второй покупает чаще, но с наценкой всего в 1 рубль.
Допустим, первый покупатель пришел два раза подряд. В таком случае выгодно отдать ему корову, которую держали для второго покупателя — потому что одна его покупка выгодна так же, как миллион покупок второго покупателя.
Bronx
20.03.2017 12:33Это равносильно тому, что у мы смешиваем два буфера (для редких богачей, длиной 1 и для частых бедняков, длиной L) в один, и берём коров не глядя. В смешанном буфере будет L+1 корова, и если L настроено правильно, чтобы обслуживать большой поток бедняков, то у нас практически всегда найдётся корова для внезапного зашедшего богача (что увеличит риск отказа более часто заходящему бедняку). Пока не вижу отличий.
mayorovp
20.03.2017 13:17Вот именно в этом "берем коров не глядя" — и отличие, которое не дает свести задачу к двум независимым.
koldyr
20.03.2017 14:59-1Два потока с интенсивностью I и J и маржой x и y соответственно смешиваются в один с интнсивностью I+J и маржой (x*I+y*J)/(I+J).
Что позволяет из двух нерентабельных классов сделать один рентабельный.mayorovp
20.03.2017 15:04Докажите что так можно делать.
koldyr
20.03.2017 15:09В смысле? То что интенсивность двух потоков равна сумме интенсивностей? Это доказано в учебнике. А то что средняя маржа будет такая — так это потому что у вас биномиальное распределение, с вероятностью I/(I+J) один клиент, J(I+J) второй. Вот оно так и получается.
mayorovp
20.03.2017 15:19Но оптимальная стратегия-то для двух разных типов клиентов и для одного "среднего" типа может отличаться!
Bronx
21.03.2017 00:37-1А вообще, вы тут неявно пронесли дополнительное условие: якобы первый продавец не может спокойно ждать появления ещё одного покупателя, пока второй торгует вовсю. Т.е. вы задали граничное условие: конечность времени.
В случае с бесконечным временем нет проблем подождать своего покупателя хоть ещё миллиард лет — так как средний поток покупателей неизменен, то на длинном промежутке все отказы из-за дефицита коровы будут скомпенсированы удачными продажами сразу после прибытия новой коровы (без необходимости кормить её слишком долго).
Paka
15.03.2017 07:31Ваша задача происходит из экономики. И решается, как правило не математически, а организационным-экономическим путем, с помощью новых вводных.
В общем виде задача сводится к уменьшению количества связанного капитала. Или пропускной способности предприятия. Классическая книжка по теме: Голдрейт, Цель.
Кстати, если вам интересны экономические задачи. То я как раз занимаюсь проектом по решению более общей задачи: организацией разделения труда и вычислением требуемого количества капитала, для его существования. На основе модели Рикардо.
mwambanatanga
15.03.2017 08:40В общем виде задача сводится к уменьшению количества связанного капитала
А может и не сводится…
Задачи, о которых вы говорите, подразумевают положительную ставку процента — капитал ограничен платой за использование (иначе зачем уменьшать вложения?). Здесь капитал явно указан неограниченным, процентная ставка подразумевается нулевой (плата за него не указана и альтернативных вариантов использования не дано). Задача просто максимизировать прибыль (а не рентабельность вложения).Paka
15.03.2017 09:44Здесь капитал явно указан неограниченным
Задача просто максимизировать прибыль
Зачем максимизировать то, что даётся по условию в неограниченном количестве? Без ограничения по капиталу задача не имеет смысла в принципе. Экономика должна быть экономной, иначе это не экономика. Вы же не будете продавать людям снег зимой, и стараться просто максимизировать прибыль от этого занятия..?
процентная ставка подразумевается нулевой
в реальной жизни ставка уже давно отрицательная, лишь бы клиент нашелся, что бы было на кого риски спихнуть))mayorovp
15.03.2017 14:00Зачем максимизировать то, что даётся по условию в неограниченном количестве?
Затем, что это требуется по условию задачи :-)
koldyr
15.03.2017 12:48Есть классическая задача об обслуживании кораблей в порту. Возможно покупателей можно рассматривать как корабли, а коров — как причалы.
Sergey_Kovalenko
15.03.2017 13:57Буду благодарен за ссылку.
koldyr
15.03.2017 14:07К сожалению эта штука у меня только в виде конспекта. Как доберусь до него — посмотрю какие там отражены результаты.
mwambanatanga
15.03.2017 14:11Да, задача похожа на теорию массового обслуживания. Только здесь нет точек обслуживания (Мужик один, а корова после покупки выходит из игры), нет задержек на обслуживание (мгновенная продажа) и нет очередей (мгновенный отказ).
koldyr
15.03.2017 14:14Начну с конца. Системы массового обслуживания бывают без очередей. Корову можно считать устройством обслуживания, время обслуживания — Т (время доставки очредной коровы после продажи)
mayorovp
15.03.2017 15:48Очень похоже что так и есть, но хотелось бы доказательство того факта, что оптимальная стратегия всегда заказывает новую корову в момент продажи старой.
koldyr
15.03.2017 15:54Если вы закажете корову до продажи то число устройств обслуживания какое-то время будет больше чем нужно. А если после то меньше. Как то так.
Sergey_Kovalenko
15.03.2017 17:19"… что оптимальная стратегия всегда заказывает новую корову в момент продажи старой."-Это весьма правдоподобно, но не верно.
TheShock
15.03.2017 17:32не верно.
АргументируйтеSergey_Kovalenko
15.03.2017 17:53Всего один класс, разумные предположения о прибыли и расходах, T много больше среднего ожидания клиента, скажем минута и месяц, тогда стоит заказывать на месяц вперед одну корову в минуту почти независимо от текущего состояния дел.
trapwalker
15.03.2017 18:23+1Черт, классный пример. Как говорится, вместо тысячи слов. При заказе только по факту продажи мы будем продавать корову раз в месяц, а при ежеминутном раз в минуту начиная через месяц.
Но предвосхищу возражения и патчи алгоритма любителей интуитивных оптимизаций.
Они скажет, что заказывать надо только по факту прихода хорошего клиента независимо от того продали мы ему корову или нет.
На это возразить будет сложнее.
Сморите. Клиенты приходят в среднем раз в минуту, а это эквивалентно 60 раз в час.
Представьте, что так уж вышло, что пол часа было затишье, а потом они на какое-то время повалили быстрее. Вполне вероятная ситуация для пуассоновского процесса.
Фишка в том, что все эти пол часа мы не заказывали коров, но это никак не отразилось на размере буфера. Получасовое затишье в приходе коров произойдёт аж через месяц, а все эти пол часа приходили коровы, которые были заказаны месяц назад. То есть, мы зачем-то отодвинули затишье на месяц вперёд, когда оно может и не наступить, а может через месяц напротив на это получасовое затишье придет наплыв клиентов.
Понятно, что в среднем мы на этом потеряем не так много, но определённо потеряем. И бессмысленно усложним процесс закупки. Вместо заказов раз в минуту будем делать заказы именно в момент продажи.
Что это. как не суеверная интуитивная «оптимизация» (в кавычках, потому что нет, не оптимизация это).TheShock
15.03.2017 21:36+1Черт, классный пример. Как говорится, вместо тысячи слов. При заказе только по факту продажи мы будем продавать корову раз в месяц, а при ежеминутном раз в минуту начиная через месяц.
Плохой пример. Он проигнорировал необходимость буфера, который как раз на это и рассчитан. Мы берем столько коров, чтобы за этот месяц «ожидания» получить максимальную прибыль. Ровно так же, как и закупая их случайным образом. Необходим одинаковый буфер для обоих случае и число заказов для обоих случаев будет в среднем одинаковым.
Они скажет, что заказывать надо только по факту прихода хорошего клиента независимо от того продали мы ему корову или нет.
Глупость какая-то. Заказывать необходимо по факту продажи.trapwalker
15.03.2017 22:18Меня бомбит. Либо я дупак, либо лыжи не едут. Только не исчезайте, докажите мне что я не прав.
Под словом «пример» я подразумевал интервалы: минута и месяц. Это позволяет сделать проблему более интуитивно понятной.
Буфер делать в этом примере можно и нужно.
Давайте рассмотрим стационарную ситуацию.
Клиенты приходят примерно раз в минуту, коровы добираются по месяцу и буфер,, скажем, из 10 коров полон. Также в пути дофигища коров, они поступают тоже со скоростью примерно раз в минуту.
Рассмотрим ваш вариант. Пуассоновский процесс допускает вероятность, что случится «затишье» на пол часика, когда ни один клиент не придет, хотя мат-ожидание 1 минута.
Все эти пол часа ни одной коровы не вызвано из деревни. Ровно через месяц выдаются пол часа, когда коровы не приходят из деревни. За это время пусть пришло примерно 30 человек. Первые 10 выбрали пул, остальные 20 ушли. Это не прогноз, а просто один из вполне вероятных вариантов развития событий.
Теперь представьте, что при прочих равных коров мы заказываем строго раз в минуту, это значит, что пул вырастет за пол часа тишины на 30 коров (получится их 40 у нас), потом они постепенно будут рассасываться неопределенно долгое время. Но через месяц не будет полу часа без коров. Всё будет в штатном режиме.
Ваша схема фактически апрещает рост пула сверх некоторого числа, а моя никак не ограничивает его, но за счет фиксированного интервала заказа равного мат-ожиданию прихода покупателей скорость прихода коров получается в среднем равной скорости их сбыта.TheShock
15.03.2017 22:32У вас слишком маленький пул. Первую заказанную корову вы получите не раньше, чем через час по любой системе, следовательно необходимо прийти с количеством коров, достаточным для часа торговли (самым выгодным, если быть точным). Допустим, это 60.
Теперь возьмем ваш пример, но инвертированный. В первые полчаса пришли 60 клиентов, разобрали всех коров и следующие полчаса никогда не было. В следующий час снова в первые полчаса пришли 60 клиентов. Если мы заказывали коров сразу после покупки, то смогли обслужить всех 60 клиентов, а если равномерно, то вторая половина коров не получит, ибо пришли до их прихода.
Обратно работает и для равнораспределенного варианта — можно придумать кучу гипотетических ситуаций, когда он выгоден.
Допустим с монеткой. Можно ставить на орел, а можно ставить на решку. Например в случае если из трех раз орел выпадет три раза, или два раза, то выгоднее ставить на орла. А если же нет, то выгоднее ставить на решку.
Но в перспективе они одинаковые. Потому что как вы считаете среднее количество коров в час? Берете всех покупателей и делите на время. А я просто беру всех покупателей.
И если за час приходит в среднем 60 покупателей, то за 1000 придет приблизительно 60000 покупателей. И за 1000 часов и вы и я закажем и продадим приблизительно 60000 коров.trapwalker
15.03.2017 22:51Ок. похоже и я был предвзят в выборе примеров. Тогда получается нет разницы когда заказывать коров, лишь бы это происходило в среднем со скоростью потока? Надо обдумать. Но вы меня не убедили, что вариант с заказом во время покупки эффективнее.
TheShock
15.03.2017 23:27Но вы меня не убедили, что вариант с заказом во время покупки эффективнее.
Я не сказал, что мой вариант эффективнее. Я сказал, что оба варианта за 1000 часов продадут примерно 60000 коров, а значит они равнозначны.
TheShock
15.03.2017 22:37И еще один пример. Представьте инвертированную ситуацию. Допустим, клиент приходит в среднем раз в час, а корова до нас доходит за минуту. Если вы будете заказывать корову раз в час, то у вас будут моменты, когда будет и 3 и 4 коровы, а если вы продадите последнюю корову, а следующая покупка будет только через 40 минут, то все клиенты, которые придут в эти 40 минут останутся без коров. В то же время, если заказывать сразу после покупки — не будет излишка и мы можем потерять только 1/60 клиентов. Если сделать буфер в 2 коровы, а не в одну, то потеряем еще меньше клиентов — 1\3600. Понимаете?
trapwalker
15.03.2017 23:02Понимаю, что филигранно подобранным примером можно доказать все что угодно. Я даже сам в этом неслабо так преуспел доказывая себе=).
Не очень понятно откуда 1/60. А насчет ситуации, когда ща 40 минут придет много клиентов, которые обычно ходят с мат-ожиданием раз в час, то вероятность (вернее частота) таких ситуаций довольно мала. И ее надо сравнивать с настолько же неудобными и вероятными случаями для вашей стратегии.
Короче, надо либо формулы уже начинать писать, либо имитационную модель для статистической проверки стратегий.TheShock
15.03.2017 23:26Не очень понятно откуда 1/60
В среднем у нас не будет коров в течении 1 минуты каждый час. То есть смотрите. Следовательно в 1/60 случаев прихода клиентов у нас не будет коровы.
За 40 минут вполне может прийти 2-3 клиента, но в долгосрочной перспективе у нас также не будет коров, чтобы обслужить каждого 60-ого клиента)trapwalker
15.03.2017 23:31Да, не все буферы одинаково полезны. Вопрос с выбором его размерп по-прежнму открыт. Кто-то предлагал генетический алгоритм. Надо бы запилить.
trapwalker
15.03.2017 22:18Меня бомбит. Либо я дупак, либо лыжи не едут. Только не исчезайте, докажите мне что я не прав.
Под словом «пример» я подразумевал интервалы: минута и месяц. Это позволяет сделать проблему более интуитивно понятной.
Буфер делать в этом примере можно и нужно.
Давайте рассмотрим стационарную ситуацию.
Клиенты приходят примерно раз в минуту, коровы добираются по месяцу и буфер,, скажем, из 10 коров полон. Также в пути дофигища коров, они поступают тоже со скоростью примерно раз в минуту.
Рассмотрим ваш вариант. Пуассоновский процесс допускает вероятность, что случится «затишье» на пол часика, когда ни один клиент не придет, хотя мат-ожидание 1 минута.
Все эти пол часа ни одной коровы не вызвано из деревни. Ровно через месяц выдаются пол часа, когда коровы не приходят из деревни. За это время пусть пришло примерно 30 человек. Первые 10 выбрали пул, остальные 20 ушли. Это не прогноз, а просто один из вполне вероятных вариантов развития событий.
Теперь представьте, что при прочих равных коров мы заказываем строго раз в минуту, это значит, что пул вырастет за пол часа тишины на 30 коров (получится их 40 у нас), потом они постепенно будут рассасываться неопределенно долгое время. Но через месяц не будет полу часа без коров. Всё будет в штатном режиме.
Ваша схема фактически апрещает рост пула сверх некоторого числа, а моя никак не ограничивает его, но за счет фиксированного интервала заказа равного мат-ожиданию прихода покупателей скорость прихода коров получается в среднем равной скорости их сбыта.koldyr
15.03.2017 22:24+1То время, которое они будут рассасываться — они будут есть, принося убыток. Весь фокус в том, что вам придется согласиться с отказом в обслуживании. Иначе вам необходимо бесконечное число коров в пуле.
trapwalker
15.03.2017 23:07Отказ в обслуживании так или иначе неизбежен. Вопрос в том, какая стратегия окажется объективно выгоднее. Не понятно где больше потеряем при каждом размере буфера: при отказах или при кормёжке
TheShock
15.03.2017 21:39Вполне вероятная ситуация для пуассоновского процесса.
Фишка в том, что все эти пол часа мы не заказывали коров, но это никак не отразилось на размере буфера
И не должно. От того, что полчаса никто не приходил вероятность прихода клиента далее осталась такой же, как и была.
Поймите, распределение пуассона не говорит, что если первые полчаса никто не приходил, то все ожидаемые клиенты повалят во вторые полчаса. Оно говорит о том, что если мы в час ожидаем в среднем 10 клиентов, то можем за этот час получить и 1 и 25.trapwalker
15.03.2017 22:23-1Почему вы так старательно держите меня за идиота. КОнечно я не считаю, «что если первые полчаса никто не приходил, то все ожидаемые клиенты повалят во вторые пол часа».
Я просто сказал, что в бесконечном пуассоновском потоке с указанными характеристиками наверняка (100%) когда-то случаится такой час, когда в первой половине никого, а во творой 60. Вероятность, что следующий час будет именно таким не нулевая. Я просто привел это как пример. Если кто-то с вами не согласен, надо допускать всё же что это вы чего-то не поняли, а не собеседник тупит.
koldyr
15.03.2017 20:18Не надо рассматривать краевой эффект. Он в данном случае не имеет значения. Сравните:
У вас есть пул касс, клиенты приходят по пуассоновскому потоку. Время обслуживания на одной кассе Т.
У вас есть пул коров, вы заказываете новую сразу после продажи. Клиенты приходят по пуассоновскому потоку. Время доставки новой коровы Т.
Я думаю это одно и то же.trapwalker
15.03.2017 21:18Не очень понял почему вы ТАК ответили на комментарий выше и что хотели доказать, но вы только что привели еще один хороший довод ПРОТИВ идеи заказывать коров в момент покупки.
Вы привели аналогию, в которой пул касс фиксирован, их не становится больше, а должно становиться, чтобы не пропускать клиентов через T после «затишья».koldyr
15.03.2017 21:23+1Какое «затишье»? У вас интенсивность потока запросов на обслуживание задана и не меняется. Для системы массового обслуживания без очереди она определяет сколько нужно касс/коров, чтобы вероятность отказа в обслуживании не превышала заданную величину.
trapwalker
15.03.2017 21:29Вы забываете, что поток пуассоновский и описывается грубо говоря средним количеством на 1 времени. Это 1 в минуту = 60 в час и т.д., но интервалы между приходам это случайные величины и существует ненулевая вероятность сколь угодно долгого "затишья" независимо от мат ожидания. По затишье я имею в виду, что обычно люди идут 60 в час, но может статься, что и в течении получаса никто не появится. Почитайте мой коммент выше про это. Там про месячную доставку и ежеминутный поток.
koldyr
15.03.2017 21:36Я не понимаю, что вы хотите мне доказать. Если в течении получаса никто не появится коровы будут жрать сено и вы будете терпеть убытки. Но фишка в том, что вы не можете спрогнозировать затишье или аншлаг. Поэтому вам необходимо выбирать размер пула для обслуживания исходя из вероятности отказа в обслуживании.
Размышляя в этом направлении пришел к мысли о существовании нерентабельных клиентов, то есть таких, которые в среднем за промежуток времени приносят денег меньше чем корова съедает.trapwalker
15.03.2017 21:58А вы, похоже, неверно поняли условие задачи. А своей аналогие и вовсе себя запутали. Если задумаетесь как следует, поймёте, то оригинальная задача допускает ситуации, недопустимые в вашем примере, иначе число касс можно было бы варьировать. Пример с кассами нормально иллюстрирует только недостатки плохого решения с заказом коровы в момент покупки.
Если заказывать коров независимо от покупок равномерно со скоростью их потока, то получится эффективнее. Могу доказать, если еще сами не поняли.TheShock
15.03.2017 21:59Могу доказать, если еще сами не поняли.
не можете, потому что предположение ошибочно.trapwalker
15.03.2017 22:43-1В чем ошибка? Коровы поступают в среднем со скоростью сбыта. С постоянной скоростью. Размер буфера симметрично случайно колеблется относительно оптимума, а в вашем лучае буфер ограничен сверху, а значит больше склонен к опустошению.
koldyr
15.03.2017 22:03+1Я написал, что пример с фиксированным пулом касс эквивалентен примеру с фиксированным пулом коров и дозаказом в момент покупки.
И да, я хочу пример стратегии с нефиксированным пулом, с доказательством того что он не хуже. И пример случая, недопустимого в моем варианте.trapwalker
15.03.2017 22:37Уж несколько раз приводил такие примеры. Еще раз. Без краевого случая. У нас есть некое расчетное N — оптимальный размер пула для заданных a, T и вектора l. Оставим а скобками методику расчета этого N.
Мы постоянно заказываем коров со средней скоростью потока, то есть если средняя скорость потока 1/мин, то и коров мы заказываем по одной строго каждую минуту. Одно исключение. не заказываем очередную корову, если случилось, что пул опустел и клиент ушел без коровы, Очевидно, что если средняя скорость потока верна, то буфер в среднем будет держаться около N. Иногда он будет пустеть и мы будем пропускать клиентов, а иногда будет вырастать, возможно очень сильно больше N/koldyr
15.03.2017 22:43Отлично, пусть на некотором сколь угодно малом интервале, отличном от нуля у вас пул больше N, тогда вы на этом интервале несете убыток. Пусть у вас на некотором сколь угодно малом интервале, отличном от нуля пул меньше N, тогда вы несете убыток. Значит пул должен быть всегда N.
trapwalker
15.03.2017 23:18Пусть у вас на некотором сколь угодно малом интервале, отличном от нуля пул меньше N
Это почему?
Дв и не так важен сам факт наличия расходов, или прибыли, как их положительный баланс. Его нужно максимизировать. Пул можно зафиксировать только сверху. Снзу его невозбранно время от времени будут расхватывать клиенты. Если пул ограниен сверху,, то больше вероятность опустошения пула.
Вопрос что перевесит, недополученная прибыль при лишних опустошениях или расходы на кормёжку.
Вернее вопрос в том, как найти оптимальный средний размер пула, чтобы макимизировать баланс.koldyr
16.03.2017 07:17Потому что пулл отличен от оптимального (для определенности случай нескольких одинаковых оптимальных точек опустим). А раз он оптимальный по прибыли (не по доходам/расходам), а по прибыли, тогда он неоптимальный то плохо. В свою очередь процесс запросов на обслуживание непрерывен, значит можно рассматривать малые интервалы. И наконец если вы продали корову, но сразу не заказали новую у вас в пул меньше, если не продали но заказали — больше оптимального.
Что вы преподаете, если не секрет?
TheShock
15.03.2017 21:44Вы забываете, что поток пуассоновский и описывается грубо говоря средним количеством на 1 времени. Это 1 в минуту = 60 в час и т.д., но интервалы между приходам это случайные величины и существует ненулевая вероятность сколь угодно долгого «затишья» независимо от мат ожидания
Вы неправильно понимаете. Распределение Пуассона не говорит, что если мы ожидаем в среднем 1 клиента в минуту, то нам придет ровно 60 в час, но непонятно в какой момент. Для 1 человека в минуту в час может прийти и 1 (с очень маленькой вероятность) и 150 человек (с еще меньшей вероятностью). И оно говорит лишь нам о вероятности именно такого числа, а не распределении количества людей по времени.trapwalker
15.03.2017 21:54Отлчно я это всё понимаю. Просто проиллюстрировать хотел именно то что вы сказали. Но добился прямо противоположного эффекта. Я не утверждаю, что если первые пол часа тишина, то вторые пол часа обязательно придут 60 человек. Но такой расклад вполне возможен. Он не невозможен. Именно эту ситуацию, которую, конечно, никак не спрогнозировать, я и привел в качестве примера.
Я отлично понимаю распределение Пуассона.TheShock
15.03.2017 21:58Да, но точно так же в первый час может большинство клиентов прийти в начале часа и во второй час большинство клиентов в начале часа. Если закупать сразу после продажи, то ко второму наплыву буфер восстановится, если же закупать равномерно, то восстановиться не успеет. Оба варианта имеют плюсы и минусы, но оба равны в долгосрочной перспективе, потому что вариант с равномерной закупкой является средним от количества продаж.
trapwalker
15.03.2017 23:22Так а если они равны в долгосрочной перспективе, то почему не выбрать тот, что проще? Равномерный интервальный заказ проще же. Ну и насчет равнсти в перспективе… надо бы проверить аналитически или экспериментально.
TheShock
15.03.2017 23:29Чем проще? Они одинаково просты, как на меня.
trapwalker
15.03.2017 23:42Ну как же. В инженерном смысле навскидку:
- Изоляция. Мы можем один раз передать в деревню интервал и не слать больше сигналов туда, коровы сами пойдут.
- Равномерность и предсказуемость нагрузки на дереаню. Ъотя этот плюс компенсруется непредсказуемостью роста (пусть даже краткосрочно и маловероятно) буфера, что, явно, минус
В принуипе можно и в вашей стратегии найти плюсы. Типа, поток один и постоянно спит между прерываниями от клиентов.
Но ок. Что там, что там доводы не решающие. Ценность их зависит от конкретной задачи и реализации.
Sergey_Kovalenko
15.03.2017 21:41Для не краевого случая добавьте класс с тем же средним временем ожидания и нулевой надбавкой. Это позволяет избавиться от лишних коров куда быстрее, чем они смогут оказать какое-то влияние на распределение их запаса через месяц.
koldyr
15.03.2017 21:48Класс покупателей, приобретающих коров по закупочной цене, убыточен. Их вообще обслуживать нельзя.
trapwalker
15.03.2017 18:04Оптимальная скорость заказа коров равна средней скорости сбыта этих коров.
Размер буфера:
- чем он больше, тем меньше вероятность пропустить клиента, зато больше издержки на корм;
- чем он меньше, тем больше вероятность пропустить клиента, но меньше издержки на корм
Очевидно, что заказывать коров надо со средней скоростью сбыта (не больше и не меньше)
Ввиду Пуассоновского процесса наш реальный размер буфера будет топтаться около оптимума время от времени с ненулевой вероятностью то упираясь в ноль, то улетая в плюс. Беда в том, что упираясь в ноль мы теряем клиентов, а вылезая в плюс терпим перерасход на содержание скота.
Закупка следующей скотины только по факту продажи, а не когда пришло среднее время закупки толкает нас к нулю и потере клиентов в худшем случае на одну корову, в среднем на пол коровы (в коровах мы буфер измеряем).
Кстати, размер буфера вполне может быть нецелым. Эта мысль только что пришла. То есть седловая точка может попасть, скажем, на 10.5 коров в буфере. Процесс ламинарный по времени и если отвязать закупку коров от продажи эвентуально, то вполне можно держать дробное кол-во коров в буфере.TheShock
15.03.2017 21:48+1Закупка следующей скотины только по факту продажи, а не когда пришло среднее время закупки толкает нас к нулю и потере клиентов в худшем случае на одну корову, в среднем на пол коровы (в коровах мы буфер измеряем).
Не толкает. Смотрите. Если клиенты приходят равномерно — оба варианта равны. Если клиентов было сначала больше, потом меньше, то больше коров будет, если заказывать сразу после покупки. А если клиентов пришло сначала меньше, а потом больше, то больше коров будет в случае равномерной закупки. В среднем на долгосрочной перспективе оба варианта абсолютно идентичны.trapwalker
15.03.2017 23:26Похоже на то. Но заказ через интервал проще же и прозранее.
Надо тестовый стендик закодить для статистической проверки на днях.
Но я теперь знаю какую задачу задать студентам=).koldyr
17.03.2017 19:32Выяснилось, что равномерно со скорость потока клиентов заказывать коров нельзя.
TheShock
17.03.2017 22:43Почему?
koldyr
17.03.2017 22:52Сначала у вас будут отказы в обслуживании и поток сделок будет меньшей интенсивности чем поток заказов. Затем образуется буфер, который будет необходимо обслуживать.
Впрочем причины не важны. Просто есть контр пример.TheShock
17.03.2017 23:15Почему?
Где?
И как тогда заказывать?koldyr
17.03.2017 23:20Если очень хочется равномерно, то нужно снизить интенсивность потока заказов. Но глобального оптимума вы все равно не достигните.
TheShock
17.03.2017 23:22Если снизить интенсивность, то упремся в 0 и будем пропускать очень много клиентов. Аргументируйте свою позицию, пожалуйста
koldyr
17.03.2017 23:27Аргументирую. Пусть время доставки коровы 1. Интенсивность покупателей 3, прибыль от покупки 10. Корова съедает за 1 времени 2. При равномерном заказе надо заказывать коров не с интервалом 1/3 а с интервалом порядка 1.16/3.
Интервал заказов может чуть-чуть отличаться, я не помню точное значение, но он точно больше 1/3.
Впрочем, я мог ошибиться, нужен независимый контроль.TheShock
17.03.2017 23:33Это не аргумент. Вы просто вывалили какие-то цифры. Откуда взялось 1.16? Почему именно столько выгодно? А если корова съедает за 2 времени 1? И даже допустим на этих цифрах — как вы посчитали, что именно это выгодно?
koldyr
17.03.2017 23:39Посчитал я просто. Создал пуассоновский поток клиентов, создал поток коров. Скормил одно другому и посчитал среднюю прибыль. Да, сделал это при разных значениях начального параметра ГСЧ.
Получилось что получилось.
Надеюсь вы понимаете что контрпример нужен один.TheShock
17.03.2017 23:55А я говорю, что при таких параметрах получается 1.578/3.041. Потому что посчитал.
Если посчитали — как? Формулы, код программы.koldyr
18.03.2017 00:10Пока без программы. Вы правы, если снизить интенсивность то поджимает к 0 и начинаешь пропускать клиентов. Но при этом не кормишь коров. Если увеличивать интенсивность то клиентов становится больше, но и приходится кормить коров, которых в наличии становится больше. Почему вы решили что оптимум должен находиться там где скорость поступления коров совпадает со скоростью потока клиентов?
TheShock
18.03.2017 00:25Потому что я предположил, что в среднем выгоднее держать корову на каждого клиента, чем не держать и интенсивность дозаказа коров равна количеству их продажи — это максимальная цифра при которой буфер не будет безконтрольно и постоянно расти вверх.
Конечно, если выгоды от продаж коров нету, то в таких случаях закупки вообще быть не должно.
Таким образом, мы выбираем только клиентов, которых считаем выгодными, продаем только им и заказываем сразу после продажи.
Все, что между этими двумя значениями — исключительно гэмблинг — авось я угадаю, когда выгодно заказать корову.
А почему вы решили взять число 1.16?koldyr
18.03.2017 00:39Потому что я ошибся в одном месте (потом исправил) получил несоответсвие и стал подгонять модели. Так обнаружил что в указанном выше примере прибыль больше если заказывать реже.
Есть еще такое соображение, при равномерном заказе у вас будут промахи, когда коровы еще не пришли, а клиенты уже есть. Это дает в среднем вероятность отказа отличную от нуля. Но тогда интенсивность продаж меньше интенсивности прихода клиентов. А значит коров нужно заказывать реже. Заказываете реже, растет вероятность отказа, падает доход, но при этом падают расходы на коровник.TheShock
18.03.2017 00:49Потому что я ошибся в одном месте (потом исправил) получил несоответсвие и стал подгонять модели. Так обнаружил что в указанном выше примере прибыль больше если заказывать реже.
Похоже, что вы ошиблись не в одном месте, а т.к. код свой не показываете — понимаете, что это очень вероятно.
Есть еще такое соображение, при равномерном заказе у вас будут промахи, когда коровы еще не пришли, а клиенты уже есть
Конечно, всегда будут вероятности отказа, если только не с бесконечным буфером.
Но тогда интенсивность продаж меньше интенсивности прихода клиентов. А значит коров нужно заказывать реже
Что? Как у вас получилось вывести второе из первого? У нас недостаточно коров, а значит их нужно заказывать еще меньше?
В случае достаточной наценки нет никакого смысла заказывать коров меньше, чем среднестатистических приход клиента. Регулировать расход на коровник нужно исключительно размером буфера.koldyr
18.03.2017 01:03Наверное, может и ошибся. Путь к истине он такой извилистый. Сейчас уже точно не пойду перепроверять.
trapwalker
18.03.2017 14:37+1Может быть дело вот в чем… При равных скоростях потоков заказа и клиентов все равно остается вероятность отказов, и зависит она в том числе от среднего размера буфера. Фактически это значит, что поток коров превышает поток продаж. Именно поэтому нельзя заказывать со скоростью потока клиентов, а нужно со скоростью потока продаж. В принципе, это решающий и, по-моему, единственный важный аргумент в пользу заказа по факту продажи. Рассчитать равновесия поток через поток клиентов с учетом вероятности отказов сильно сложнее.
Но я по-моему по прежнему вижу проблему. Похоже, что возникнет положительная обратная связь: больше отказов — меньше заказов; меньше заказов — больше отказов. Хорошо бы сформировать отрицательную обратную связь. Это сильно сложнее, но можно рассчитать, например, оптимальный поток заказов с учетом вероятности отказов из-за конечного буфера. Именно с такой фиксированной скоростью и следует делать равномерный заказ. Это сформирует отрицательную обратную связь. При отказах формируется избыток коров и это влечет уменьшение отказов, что, в свою очередь уменьшает избыток, отчего растут отказы и так все саморегулируется.
Резюмирую гипотезу:
1) заказ по факту продажи формирует положительную обратную связь, ведущую к росту отказов;
2) заказ со скоростью потока клиентов формирует положительную обратную связь, приводящую к постоянному росту буфера;
3) наверно можно вычислить фиксированную скорость заказов, при которой буфер будет в среднем одной длины.
4) наверно можно сформулировать закон адаптивного изменения скорости регулярных заказов на основе текущей статистики процесса, чтобы эта скорость регулировалась отрицательной обратной связью.
Какие ваши соображения, коллеги?TheShock
18.03.2017 18:11больше отказов — меньше заказов; меньше заказов — больше отказов
Как-то непонятно. У нас есть буфер и (количество коров в буфере+количество заказанных коров) всегда константно. Больше продаж — больше заказов. Отказы, конечно, могут быть, но размером буфера мы балансируем так, чтобы получать максимальную прибыль.
Зачем вы раз за разом все усложняете без причины?trapwalker
19.03.2017 09:17Без причины или нет покажет эксперимент или строгое математическое доказательство. Пока что это все лишь гипотезы и предположения. В ваших рассуждениях выше о балансировке буфером в реальном времени речи не шло. Пояснительная как это мы балансирует буфером. Я очень стараюсь понимать ваш ход мысли. Надеюсь на взаимном там, ибо это может сэкономить время.
TheShock
19.03.2017 20:47балансировке буфером в реальном времени речи
Естественно, ведь по условиям задачи среднестатистическое появление покупателей не меняется, цены не меняются, следовательно и размер буфера не имеет причин меняться.
trapwalker
16.03.2017 15:51Так. Ок. Делаю скрипт для проверки наших гипотез. Нужно обсудить.
В питоновском пакете numpy нашел такую штуку:
import numpy print(numpy.random.poisson(100))
Вроде даёт интервалы с мат-ожиданием 100.
Вопроса сразу два:
- Почему оттуда целые числа сыпятся? Я думал там вещественные числа должны быть.
- Как правильно смешивать пуассоновские потоки?
По второму пункту я полагаю как-то так:
- взять из каждого потока по интервалу и отсортировать по неубыванию (сформировать кучу);
- извлечь и выдать минимальный интервал (из вершины кучи) и сгенерировать следующий интервал для потока, чей интервал только что извлекли;
- вычесть извлеченный из всех интервалов кучи;
- поместить новый интервал в кучу;
- повторять бесконечно от пункта 2...
mwambanatanga
16.03.2017 17:44+1Почему оттуда целые числа сыпятся? Я думал там вещественные числа должны быть.
Потому что этот генератор даёт не интервал ожидания следующего клиента, а количество клиентов за единицу времени. Интервал распределяется по экспоненциальному закону p(X<=t) = 1 — e^(-lambda*t). Случайный интервал генерируется как -log(1 — rand()) / lambda, где rand() между 0 и 1 (источник).
Как правильно смешивать пуассоновские потоки?
Просто сложением их лямбд. Сумма двух пуассоновских потоков есть пуассоновский поток с параметром, равным сумме двух исходных (т.е. за один интервал в среднем придёт lambda1 клиентов класса 1 И lambda2 клиентов класса 2).
koldyr
16.03.2017 19:46Породите несколько потоков потом вставте их друг в друга. Так у вас сохранится информация о классах покупателей.
mwambanatanga
17.03.2017 05:39Можно генерировать «общий» поток интенсивностью (l1 + l2 +...), а класс присваивать постфактум. Вероятность, что клиент принадлежит к классу i равна li/(l1 + l2 +… + li + ...), что легко моделируется при помощи интервалов для rand(). Псевдокод:
random = rand() * (l_1 + l_2 + ... + l_n);
if (random < l_1) class = 1;
elseif (random < l_1 + l_2) class = 2;
...
else class = n;
trapwalker
17.03.2017 08:00Ага. Тоже была такая мысль, но потом решил сделать на питоновских генераторах по отдельности и сливать потоки тоже генератором. Так можно будет при необходимости другие распределения использовать и даже роутить реальные события из какого-нибудь API
koldyr
17.03.2017 12:45Как и предполагалось, теория сошлась с практикой.
Система эквивалентна системе массового обслуживания с отказами.
Число коров в пуле равно числу коров находящихся на рынке плюс коровы в пути.
Заказывать коров надо по факту продажи, другие идеи не оптимальны.koldyr
17.03.2017 13:20Прошу прощения у аудитории. Чуть чуть поторопился. Реальность оказалась слегка сложнее. Кажется возможны не целые случаи и это надо разбирать дополнительно.
wladyspb
Мне кажется это тот случай, когда можно использовать генетическое программирование.
У вас есть некий набор параметров, которые должны вычисляться относительно друг друга с разными коэффициентами, + сама формула неизвестно как должна выглядеть.
Но есть точное условие выявления правильной формулы — она должна на длительном прогоне, вне зависимости от стартовых значений, выдавать положительный баланс, и чем выше прибыль тем лучше.
Таким образом, если написать программу, которая будет переставлять стартовые параметры и менять формулы, прогонять её на разных данных и считать итоговый коэффициент успешности формулы, то за несколько тысяч(сотен тысяч, в зависимости от теоретического количества комбинаций) итераций можно найти самый удачный вариант формулы.
ivlis
Да ну, у такой задачи наверняка должно быть аналитическое решение
kenoma
Обычного Монте-Карло хватит.