14 марта 2017 года Sergey_Kovalenko опубликовал задачу черезвычайно взволновавшую умы хабражителей. За пару вечеров было сломано много копий и наверняка было бы разбито много голов, если бы встреча была очной.
Ниже вас ожидает условие задачи и расммотрение одного подхода к решению.
Условие
Некий Мужик занимается перепродажей коров: Он скупает их за фиксированную небольшую цену a рублей у местного населения и пытается продать с наценкой посетителям рынка. Предположим для простоты, что покупатели по своей платежеспособности делятся на n классов, и, что любому, подошедшему к Мужику покупателю из k -го класса, он продает любую из имеющихся у него коров с наценкой xk-тое рублей. Будем считать, что появление покупателя каждого класса описывается пуассоновским процессом с неким, характерным для этого класса нагрузочным параметром lk-тое. Если в момент появления покупателя у Мужика нет коров, то первый не становится в очередь, а удаляется восвояси и обратно уже не возвращается.
- Каждая корова, купленная Мужиком у населения проедает за единицу времени корма на u рублей, поэтому держать большой запас коров не выгодно;
- Мужик может всегда отправить с попутчиком в деревню просьбу привести еще коров, однако выполнение этой просьбы хотя и бесплатно, но требует T времени;
- Ввиду сделанных оговорок, Мужик может и не продать корову, если их у него мало, а шанс встретить клиента побогаче достаточно велик, или наоборот — продать в убыток из излишков запаса лишь бы зря не кормить.
Какова оптимальная на длительном периоде стратегия Мужика при почти бесконечном начальном капитале?
Решение
Для расстрела этой проблемы мы достанем одну из самых замечательных пушек, которыя издавна используется математиками и программистами — «метод чайника».
Пусть имеется пуассоновский поток клиентов c параметром I, каждый клиент платит за корову наценку x, мужик продает корову всегда, когда она есть.
Для дальнейшей работы нам понадобится несколько дополнительных соображений, которые позволят успешно «вылить воду из чайника».
Хлев на рынке может быть очень большого, но всетаки конечного размера m. Клиенты так и остаются клиентами. Коровы же превращаются в устройства обслуживания следующим образом: когда корова стоит в хлеву на рынке то устройство обслуживания не занято, когда мужик продаёт корову устройство обслуживания становится занятым до того момента, пока из деревни на это место не придет новая корова.
Пусть теперь в момент времени t в хлеву находится i коров и происходит продажа коровы. Мужику необходимо решить, заказать корову немедленно или отложить требование. Важным моментом является то, что какое бы решение он не принял корову раньше чем через T он не получит. Таким образом время доставки коровы на освободившееся место является случайной величиной t, принимающей значения из промежутка
и математическим ожиданием 
. Распределение этой величины зависит от стратегии заказа коров. Как справедливо заметили в коментариях, к сожалению придется потребовать независимости времен обслуживания.
Таким образом, мы получаем что исходная задача, при указанных ограничениях, эквивалента системе массого обслуживания без очереди с m устройств обслуживания.
Тогда можно вычислить вероятность того что покупатель уйдет с коровой.
Где
вычисляется по формуле Эрланга. Заметим, что вероятность отказа не зависит от распределения t, важно только среднее время обслуживания.Пусть теперь коровник потребляет u рублей в единицу времения не на корову, а на стойло. Но, когда клиент покупает корову он сверху «платит»
рублей.Тогда средняя прибыль в единицу времени может быть выражена как
А сама задача сводится к нахождению
Анализ полученных результатов
Если максимум r достигается при
то единственно возможная стратегия — заказ коров по факту продажи.Нельзя пытаться менять значение m, так как в силу свойств пуассоновского потока можно вырезать временные интервалы где m не оптимально и склеить их. И в результате получится результат хуже оптимального.