14 марта 2017 г.
Сергей_Коваленко опубликовано задача что чрезвычайно взбудоражило умы жителей Хабры.
За пару вечеров было сломано много копий и, вероятно, было бы сломано много голов, если бы встреча была личной.
Ниже вы найдете условие задачи и рассмотрение одного из подходов к решению.
Состояние
Некий Мужчина занимается перепродажей коров: он покупает их за фиксированную небольшую цену в рублях у местного населения и пытается продать с наценкой посетителям рынка.Предположим для простоты, что покупатели разделены на n классов по их платежеспособности и что любому покупателю из k-го класса, обратившемуся к Человеку, он продает любую из имеющихся у него коров с наценкой в xk рублей.
Будем считать, что появление покупателя каждого класса описывается пуассоновским процессом с определенным параметром нагрузки lk-toe, характерным для этого класса.
Если в момент появления покупателя у Мужика нет коров, то первый не встает в очередь, а идет домой и больше не возвращается.
- Каждая корова, купленная человеком у населения, съедает корма на сумму u рублей в единицу времени, поэтому держать большой запас коров невыгодно;
- Мужчина всегда может отправить с товарищем в деревню просьбу привести больше коров, но выполнение этой просьбы хоть и бесплатное, но требует времени T;
- Ввиду сделанных оговорок, Мужчина может и не продавать корову, если их у него мало, но шанс встретить более богатого клиента достаточно велик, или наоборот - продать в убыток из излишков, просто чтобы не кормите зря.
Решение
Для решения этой задачи мы достанем один из самых замечательных пистолетов, который издавна используют математики и программисты – «метод чайника».Пусть существует пуассоновский поток клиентов с параметром I, каждый клиент платит премию x за корову, человек продает корову, если она у него есть.
Чтобы двигаться дальше, нам понадобится несколько дополнительных соображений, которые позволят нам успешно «вылить воду из чайника».
Конюшня на рынке может быть очень большой, но при этом иметь окончательный размер m. Клиенты остаются клиентами.
Коровы превращаются в служебные устройства следующим образом: когда корова находится в коровнике на рынке, служебное устройство не занято, когда человек продает корову, служебное устройство становится занятым до тех пор, пока из села в это не придет новая корова.
место.
Пусть теперь в коровнике находится i коров и корова продается.
Мужчине необходимо решить, заказывать корову немедленно или отложить требование.
Важным моментом является то, что какое бы решение он ни принял, корову он не получит раньше Т.
Таким образом, время доставки коровы на освободившееся место является случайной величиной t, принимающей значения из интервала 
и математическое ожидание 
.
Распределение этой величины зависит от стратегии заказа коров.
Как справедливо отмечено в комментариях, к сожалению, нам придется потребовать независимости сроков обслуживания.
Таким образом, получаем, что исходная задача при указанных ограничениях эквивалентна безочередной системе массового обслуживания с m обслуживающими устройствами.
Тогда вы сможете вычислить вероятность того, что покупатель уйдет с коровой.
Где 
рассчитывается по формуле Эrlang. Обратите внимание, что вероятность отказа не зависит от распределения t, важно только среднее время обслуживания.
Пусть теперь коровник потребляет u рублей в единицу времени, не на корову, а на одно стойло.
Но когда клиент покупает корову, он «платит» сверху 
рублей
Тогда среднюю прибыль в единицу времени можно выразить как 
А сама задача сводится к поиску 
.
Анализ полученных результатов
Если максимум r достигается при
тогда единственная возможная стратегия — заказывать коров на продажу.
Нельзя пытаться изменить значение m, так как благодаря свойствам пуассоновского потока можно вырезать интервалы времени, где m не является оптимальным, и склеить их.
И результатом будет результат, далекий от оптимального.
Теги: #математика #теория вероятностей #системы массового обслуживания #метод чайника #математика
-
Топ-5 Лучших Дешевых Планшетов
19 Oct, 24 -
Respondu.net Угадывает Мысли
19 Oct, 24
