На рынке корову мужик продавал

Недавно столкнулся с интересной задачкой. Позволю себе предложить и Вам над ней поразмыслить. Не уверен, что подобное встречалась где-нибудь раньше, поэтому, если Вы увидите в ней какую-то известную проблему, освещенную в научной литературе, буду признателен за предоставленную информацию. Какое-то вычислительное решение мне получить удалось, правда, достаточно изящным его не назовешь, и, поскольку, целью здесь является побудить читателя к самостоятельному поиску, я не буду его сейчас публиковать.

Итак, задача вполне себе житейская.

Некий Мужик занимается перепродажей коров: он скупает их за фиксированную небольшую цену a рублей у местного населения и пытается продать с наценкой посетителям рынка. Предположим для простоты, что покупатели по своей платежеспособности делятся на n классов, и, что любому, подошедшему к Мужику покупателю из k -го класса, он продает любую из имеющихся у него коров с наценкой xk-тое рублей. Будем считать, что появление покупателя каждого класса описывается пуассоновским процессом с неким, характерным для этого класса нагрузочным параметром lk-тое. Если в момент появления покупателя у Мужика нет коров, то первый не становится в очередь, а удаляется восвояси и обратно уже не возвращается. Задачи бы попросту не было, если бы не два правдоподобных условия:

1) каждая корова, купленная Мужиком у населения проедает за единицу времени корма на u рублей, поэтому держать большой запас коров не выгодно;
2) мужик может всегда отправить с попутчиком в деревню просьбу привести еще коров, однако выполнение этой просьбы хотя и бесплатно, но требует T времени;
3)ввиду сделанных оговорок, Мужик может и не продать корову, если их у него мало, а шанс встретить клиента побогаче достаточно велик или наоборот продать в убыток из излишков запаса — лишь бы зря не кормить.

Какова оптимальная на длительном периоде стратегия Мужика при почти бесконечном начальном капитале?

Комментарии (14)

  • 14 марта 2017 в 18:05

    +2

    Мне кажется это тот случай, когда можно использовать генетическое программирование.
    У вас есть некий набор параметров, которые должны вычисляться относительно друг друга с разными коэффициентами, + сама формула неизвестно как должна выглядеть.
    Но есть точное условие выявления правильной формулы — она должна на длительном прогоне, вне зависимости от стартовых значений, выдавать положительный баланс, и чем выше прибыль тем лучше.
    Таким образом, если написать программу, которая будет переставлять стартовые параметры и менять формулы, прогонять её на разных данных и считать итоговый коэффициент успешности формулы, то за несколько тысяч (сотен тысяч, в зависимости от теоретического количества комбинаций) итераций можно найти самый удачный вариант формулы.
  • 14 марта 2017 в 18:12

    0

    Спасибо за совет. В статье я предполагал, что задача в стиле книг бородатых 50-х годов и интересно прежде всего концептуальное, а не вычислительное решение, с исследованием асимптотик.
  • 14 марта 2017 в 18:58

    +2

    ввиду сделанных оговорок, Мужик может и не продать корову, если их у него мало, а шанс встретить клиента побогаче достаточно велик

    противоречит


    любому, подошедшему к Мужику покупателю из k -го класса, он продает любую из имеющихся у него коров с наценкой xk-тое рублей

    Ну и заодно:


    появление покупателя каждого класса описывается пуассоновским процессом с неким, характерным для этого класса нагрузочным параметром lk-тое

    Можете для тех, кто не в теме, рассказать о характеристиках этого процесса, а именно:


    • по какой формуле рассчитывается вероятность появления покупателя того или иного класса в каждой момент времени t?
    • может ли в момент t появиться одновременно два покупателя разных классов (и как тогда осуществляется продажа)?
    • 14 марта 2017 в 19:13

      0

      Предположу, что автор имел в виду следующее:
      • Время непрерывно, поэтому вопрос о вероятности появления клиента в определённый момент времени не имеет смысла. Вместо этого можно говорить о вероятности появления клиента за определённый промежуток времени. Поскольку дано распределение Пуассона, то среднее время между двумя последовательными покупателями равно 1/lk (или наоборот — за единицу времени в среднем придут lk покупателей).
      • Процессы для разных классов покупателей независимы. Т.е. вероятность появления клиента одного класса не зависит от потока клиентов других классов.
  • 14 марта 2017 в 19:10

    0

    1) Да есть некоторая неточность языка. Считается, что Мужик всегда способен продать, если захочет.
    2)Вы правы, забыл уточнить: независимые пуассоновские процессы с непрерывным временем (определение можно посмотреть почти в любой книге по теории вероятностей или математической энциклопедии)
    3)Ввиду 2) появление когда либо сразу двух покупателей — событие нулевой вероятности
    • 14 марта 2017 в 19:27

      0

      События все независимы, совместны, но некоторые зависимы (и наверное даже — вероятностная зависимость есть и цепочках из n событий), а другие — нет.
      Надо понять, какое событие случается в модели чаще всего и тогда можно определится как действовать/решать — так как это событие задаёт поведение всей системы.

  • 14 марта 2017 в 19:23 (комментарий был изменён)

    0

    В самом начале покеупаем количество коров которое можно продать за 2Т времени + некоторый запас.
    Случайные величины на то и случайные, что при вероятности события 1к10 млн за час, оно может произойти трижды в течении минуты…
    В дальнейшем, после продажи каждой коровы запрашиваем еще одну.
    В итоге имеем фиксированные издежки содержания коров, при 100% реализации за время ~2Т.

    Если данная стратегия убыточна, то следует установить планку минимальной цены продажи с исключением продаж классам, которые не могут купить за указанную цену.
    Как следствие пропорционально уменьшится максимальный запас коров и издержки их содержания при увеличении средней выручки с коровы.

    Конкуренции можно не бояться, конкурентам так же невыгодно продавать задешево.

    • 14 марта 2017 в 19:32

      0

      ошибся с 2Т, там 1Т
  • 14 марта 2017 в 19:42

    0

    Первая идея: отсеять те классы покупателей, прибыль от которых не покрывает затраты на содержание коров. Т.е. тех, торговая наценка (x) для которых меньше, чем содержание одной коровы (u), умноженное на среднее отклонение функции распределения (тоже l, ибо для Пуассона дисперсия равна матожиданию).
    • 14 марта 2017 в 19:54

      0

      Это уже есть в задаче — мужик продаёт коров с наценкой, а этот термин подразумевает ненулевую прибавку к ненулевой денежной сумме себестоимиости (т. е. это все равно что сказать, что у всех классов всегда есть минимальная или большая платежеспособность, равная сумме себестоимости и минимальной наценки).

    • 14 марта 2017 в 20:00

      0

      Если коров скопилось очень много, то за их сбыт Мужик сам даст денег, потому что это выгоднее чем их понапрасну кормить.
      • 14 марта 2017 в 20:11

        0

        Да, я уже понял, что идея решать задачу для каждого класса отдельно оказалась неверной.

        В общем, пока так. Решение, продавать ли корову текущему покупателю, зависит от:
        * Класса покупателя
        * Количества коров на складе
        * Потока коров из деревни (количества и времени поступления на склад)

        Решение, заказывать ли ещё коров (или корову), зависит от:
        * Количества коров на складе
        * Потока коров из деревни

        Поскольку процесс пуассоновский, предсказать появление следующего клиента на основе данных о предыдущих клиентах не получается и делать что-либо «в ожидании богатого клиента» нельзя.

  • 14 марта 2017 в 19:58

    0

    Боюсь, оба решения вкладывают в вероятность совсем не тот смысл, который принят для этого понятия в математике. Вы никогда не знаете, сколько придет покупателей в ближайший час и каких: у вас есть лишь вероятности каждого их набора, которые оправдываются в среднем и то лишь по вероятности. Пусть, например, класс покупателей только один, их количество за час имеет распределение Пуассона с математическим ожиданием 1. Если вы собираетесь закупать раз в час корову, то учтите, что более чем в четверти случаев по истечению часа не сможете продать купленную в прошлый раз, и с довольно большой вероятностью, если на начало очередного часа у вас будет только одна корова, то по крайней мере один клиент будет потерян.
    • 14 марта 2017 в 20:16

      0

      Тогда нужно уравнять вероятности получения сопоставимых дохода от продажи коровы и потери от потери клиентов и расходов на содержание у мужика. Другое дело — избавится от потерь совсем и получить всю возможную прибыль — не получится в принципе.

© Habrahabr.ru