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

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

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

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

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

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

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

    Подробнее
    Реклама
    Комментарии 212
    • +4
      Мне кажется это тот случай, когда можно использовать генетическое программирование.
      У вас есть некий набор параметров, которые должны вычисляться относительно друг друга с разными коэффициентами, + сама формула неизвестно как должна выглядеть.
      Но есть точное условие выявления правильной формулы — она должна на длительном прогоне, вне зависимости от стартовых значений, выдавать положительный баланс, и чем выше прибыль тем лучше.
      Таким образом, если написать программу, которая будет переставлять стартовые параметры и менять формулы, прогонять её на разных данных и считать итоговый коэффициент успешности формулы, то за несколько тысяч(сотен тысяч, в зависимости от теоретического количества комбинаций) итераций можно найти самый удачный вариант формулы.
      • +1
        Да ну, у такой задачи наверняка должно быть аналитическое решение
        • +1
          Обычного Монте-Карло хватит.
        • 0
          Спасибо за совет. В статье я предполагал, что задача в стиле книг бородатых 50-х годов и интересно прежде всего концептуальное, а не вычислительное решение, с исследованием асимптотик.
          • +2
            ввиду сделанных оговорок, Мужик может и не продать корову, если их у него мало, а шанс встретить клиента побогаче достаточно велик

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


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

            Ну и заодно:


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

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


            • по какой формуле рассчитывается вероятность появления покупателя того или иного класса в каждой момент времени t?
            • может ли в момент t появиться одновременно два покупателя разных классов (и как тогда осуществляется продажа)?
            • +1
              Предположу, что автор имел в виду следующее:
              • Время непрерывно, поэтому вопрос о вероятности появления клиента в определённый момент времени не имеет смысла. Вместо этого можно говорить о вероятности появления клиента за определённый промежуток времени. Поскольку дано распределение Пуассона, то среднее время между двумя последовательными покупателями равно 1/lk (или наоборот — за единицу времени в среднем придут lk покупателей).
              • Процессы для разных классов покупателей независимы. Т.е. вероятность появления клиента одного класса не зависит от потока клиентов других классов.
            • 0
              1) Да есть некоторая неточность языка. Считается, что Мужик всегда способен продать, если захочет.
              2)Вы правы, забыл уточнить: независимые пуассоновские процессы с непрерывным временем(определение можно посмотреть почти в любой книге по теории вероятностей или математической энциклопедии)
              3)Ввиду 2) появление когда либо сразу двух покупателей — событие нулевой вероятности
              • 0

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

                • 0
                  Ввиду 2) появление когда либо сразу двух покупателей — событие нулевой вероятности

                  Это почему?

                  • +3
                    Потому, что появление покупателя, решение о продаже и сама продажа (или отказ) мгновенны. Время непрерывно и вероятность любого события, из рассматриваемых в задаче, за время, стремящееся к нулю, тоже стремится к нулю. Это значит, что одновременно два покупателя не появятся исходя из самой природы вещей. Всегда кто-то из низ был раньше и всегда между ними ненулевое время.
                    Вернее как… вероятность того, что между приходами покупателей пройдёт нулевое время — тоже нулевая.
                    • 0
                      У вас несколько независимых друг от друга по условию Пуассоновских потоков. Вероятность появления покупателей в один и тот же момент времени ненулевая по определению.
                      • +1
                        Какая разница? Вероятность случайно дважды попасть в одну вещественную математическую точку строго нулевая. Не важно к каким Пуассоновским или не пуассоновским процессам относятся эти величины. Если угодно, два вещественных случайных числа не равны с вероятностью строго 1.
                        • –2
                          Это с какого перепугу?
                          • 0
                            Вы путаете (или, скорее, вольно используете) понятия «момент времени» и «интервал/промежуток времени». Из-за этого всё недопонимание между вами и коллегой trapwalker.
                            • –1
                              Интервал — это сумма моментов времени.
                              • 0
                                Не втягивайте меня в ваш спор. Я лишь указал на причину вашего взаимо-непонимания. Вы считаете продолжительность «момента» бесконечно малой, но не нулевой. Ваш оппонент считает продолжительность «момента» пренебрежимо малой, а поэтому нулевой.

                                В любом случае, к решению данной задачи это не имеет отношения.
                                • +1
                                  Именно так. Я определяю момент как математическую точку на оси времени. Это никак не интервал. Если коллега считает моментом некий квант машинного времени, который по определению интервал, то нет смысла говорить об идеальном пуассоновском процессе и его нужно квантифицировать.
                                  Короче, похоже, вы правильно указали на рассогласования, просто немного не очевидно выразились. Однако я неоднократно и достаточно явно говорил, что имею в виду под моментом, а retain не говорил, что считает момент интервалом. То, что интервал — это сумма моментов в интегральном смысле верно в любом случае.
                                  • 0
                                    Я считаю моментом бесконечно малый интервал. Другие определения (точка как нульмерные объект, например), кажется, вообще лишены смысла в рамках подобных задач.
                                    • +1
                                      Это отдельные понятия. Есть точка и есть интервал. Зачем вводить путаницу подразумевая под первым второе? Пуассоновский процесс оперирует и точками и интервалами в разных смыслах.
                                      кажется, вообще лишены смысла в рамках подобных задач

                                      То, что кажется, нужно оговаривать явно. И нет, не лишены.
                              • +2
                                Вот лично я ничего не путаю, а использую строго по назначению.
                                Любое событие происходит мгновенно в момент времени, а пуассоновский процесс определяет вероятность возникновения события на интервале времени. В интервале (любом вещественном диапазоне) бесконечное количество моментов (вещественных точек).
                        • 0
                          Поясню, в пуассоновском потоке вероятность появления следующего события через время 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. А вот в реальной жизни придется учитывать возможность появления очередей.
                          • +1
                            в пуассоновском потоке вероятность появления следующего события через время t

                            Не «через», а «в течение». Разве нет? Вероятность появления события строго «через» время t по определению нулевая. Потому что dt->0.
                            • –2
                              Нет, почитайте матчасть, в том числе про пределы. Ваша ошибка в том, что вы считаете вероятность попадания в заданную математическую точку нулевой (а значит нулевой в любую точку, а значит вероятность попадания в отрезок, который является суммой математических точек — тоже нулевой… Бред.). Она конечно очень мала, но совсем не равна нулю.

                              http://sernam.ru/book_tp.php?id=114 — начиная со слов «Важной характеристикой потока является закон распределения длины промежутка между соседними событиями...»
                              • +2
                                Не передергивайте. Я такого не говорил. А вот эти ваши рассуждения:
                                Ваша ошибка в том, что вы считаете вероятность попадания в заданную математическую точку нулевой (а значит нулевой в любую точку, а значит вероятность попадания в отрезок, который является суммой математических точек — тоже нулевой… Бред.)

                                ошибочны вот в этой части:
                                а значит нулевой в любую точку, а значит вероятность попадания в отрезок, который является суммой математических точек — тоже нулевой… Бред.

                                Нулевая вероятность попадания в конкретную точку. А в любую на заданном отрезке уже не нулевая.
                                Я, конечно, могу ошибаться, но пока что явные логические нестыковки именно в ваших рассуждениях. Готов спорить.
                                Если вас смущает разница между «нулевая» и «стремящаяся к нулю при dt->0». То готов согласиться.
                                • 0
                                  Именно эта разница меня сильно и смущает. Между «нулевая» и «стремящаяся к нулю» есть огромная разница, которая проявляется, например, при попытке эти вероятности сложить. И, например, если пуассоновских потоков МНОГО, то вероятность о которой мы говорим становится вполне заметной.
                                  • +1
                                    Эта вероятность становится заметной только в случае, когда пуассоновских процессов БЕСКОНЕЧНО МНОГО. И то я бы еще подумал над этим. Бесконечности бывают разных порядков.
                                    Подытожу. Математическая точка — это не интервал. Вероятность попадания в конкретную математическую точку строго нулевая, а вот вероятность попадания в отрезок стремящийся по длине к нулю уже не нулевая, а стремящаяся к нулю.
                                    • 0
                                      Хорошо, соглашусь. Только остается вопрос — почему вы считаете событие нульмерной математической точкой?

                                      UPD. В рамках этой задачи. Чем отличается событие от процесса в физических моделях я знаю.
                                      • +1
                                        По определению.
                                        Если мы оперируем пуассоновскими определениями, то и события надо рассматривать в математическом смысле.
                                        К тому же по условию задачи длительность обработки события не обсуждалась, посему имеет смысл считать его нулевым, как математическую абстракцию.
                                        • 0
                                          Ок. Действительно, существует абстрактное понятие элементарного события (https://en.wikipedia.org/wiki/Elementary_event), вероятность которого в непрерывном пространстве всегда равна нулю, из чего в определениях делается вывод, что в непрерывном пространстве имеют вероятность только НЕэлементарные события (а события в пуассоновском потоке, очевидно, вероятность имеют).

                                          И, действительно, определение пуассоновского процесса в русской википедии содержит «Свойство ординарности: вероятностью наступления за элементарный промежуток времени более одного события можно пренебречь по сравнению с вероятностью наступления за этот промежуток не более одного события», с чем я спорить не буду.
                                          Определение свойства из другого источника: Поток событий называется ординарным, если вероятность появления двух или более событий в течении элементарного интервала времени Δt есть величина бесконечно малая по сравнению с вероятностью появления одного события на этом интервале.
                                          Про нулевую вероятность не нашел ничего.

                                          Вот только нигде я не нашел определения того, что пуассоновский поток оперирует именно элементарными событиями. Наоборот, везде рассматривают ТОЛЬКО события попадания в некоторый интервал (тут, например, довольно подробно — https://en.wikipedia.org/wiki/Poisson_point_process).
                                          • +1
                                            Я так понимаю сути дела наш терминологический спор не меняет. Зачем захламлять тред несущественным гиковским буквоедством? Давайте прекратим.
                                            По существу, как я понял мы сошлись. Тем более в классическом паттерне технической реализации подобных систем с «одновременным» приходом покупателей проблем нет. Если таймштампы у них оказались равны, то обрабатываем их по мере поступления запросов. Надо сильно «постараться», чтобы это стало технической проблемой.
                                            • 0
                                              Каждая заявка влияет на стейт нашего продавца, а значит порядок обработки все-таки важен.

                                              Более того, в реальных задачах на operations research есть процесс обработки заявки имеющий конкретную длину и стоимость, а сама заявка — тайм-аут, и стратегия разгребания очереди может очень сильно повлиять на финансовое состояние продавца.

                                              Но да, давайте прекратим.
                                • 0
                                  отрезок, который является суммой математических точек


                                  Откуда вы это взяли? Что вообще значит эта фраза? Отрезок — это просто множество точек прямой лежащие между 2 точками этой прямой + сами эти 2 точки (концы отрезка). Вы имеете ввиду что длинна отрезка это сумма точек(в таком случае это вообще не понятно что)? Единственное опредление длинны отрезка которое мне изветсно дается через меру Жордана, и да мера Жордана конечного набора точек равно 0, а мера бесконечного набора может быть отличной от нуля (та самая длинна отрезка).

                                  P.S Вероятность попадания в конкретную точку равна 0
                                  • –1
                                    P.S Вероятность попадания в конкретную точку равна 0

                                    Важно, что она равна не 0, а бесконечно мала. Первый раз мы ведь в эту точку попали, значит вероятность была ненулевая)
                                    • –1

                                      Вероятность — это число. Действительное число не может быть бесконечно малым. Бесконечно малыми бывают только последовательности или функции.

                                      • 0
                                        То есть вероятность нулевая, но, несмотря на нулевую вероятность, в точку мы все-таки попали?
                                        • 0
                                          Да. Было невероятно, что мы попадём именно в эту точку, но мы сделали это.
                                          По-моему всё вполне интуитивно. А вас, похоже, смущает антропный принцип.
                                        • 0
                                          Просто оставлю это здесь — https://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%B2%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8
                                          • 0

                                            В данном случае, функция вероятности тоже нулевая.

                                  • 0
                                    Правильнее — не «очень мала», конечно, а бесконечно мала.
                              • –1
                                В итоге — по определению непрерывного пуассоновского потока. Событие ненулевой вероятности, но по определению мы этой вероятностью пренебрегаем и считаем, что сумма пуассоновских потоков — это тоже пуассоновский поток.
                            • НЛО прилетело и опубликовало эту надпись здесь
                              • НЛО прилетело и опубликовало эту надпись здесь
                              • 0
                                Первая идея: отсеять те классы покупателей, прибыль от которых не покрывает затраты на содержание коров. Т.е. тех, торговая наценка (x) для которых меньше, чем содержание одной коровы (u), умноженное на среднее отклонение функции распределения (тоже l, ибо для Пуассона дисперсия равна матожиданию).
                                • 0

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

                                  • 0
                                    Если коров скопилось очень много, то за их сбыт Мужик сам даст денег, потому что это выгоднее чем их понапрасну кормить.
                                    • 0
                                      Да, я уже понял, что идея решать задачу для каждого класса отдельно оказалась неверной.

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

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

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

                                        Можно. (делать, а не предсказывать)
                                        Пример: есть 1 корова, пополнение появится через большое время t.
                                        По оценке, самый выгодный тип покупателей придёт раньше чем t c большой вероятностью (Например, 0.9). В таком случае нет смысла прям сейчас продавать корову дёшево.

                                        • 0
                                          Дополню самого себя:

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

                                          … а поток коров зависит от прежних заказов. Итого остаётся только зависимость до-заказа от текущего запаса. Дабы поток коров совпадал с ожидаемым (средним) потоком клиентов, за каждой продажей должен следовать заказ одной коровы. Желательно заказывать прямо в момент продажи. Чем меньше интервал между продажей (изменением состояния запаса) и прибытием заказанной коровы, тем легче управлять запасом — тем быстрее запас возвращается к оптимальному уровню.
                                        • 0
                                          за их сбыт Мужик сам даст денег

                                          Т. е. на рынке появляются ещё и клоны Мужика — клиенты, которым он дал корову и пообещал дать денег за её сбыт другому клиенту?

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

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

                                          • НЛО прилетело и опубликовало эту надпись здесь
                                            • 0

                                              Достаточно словесных рассуждений.
                                              Принимать эмпирический "+ некоторый запас сверх рассчетов." нет смысла так как для этого и предназначен вероятностный расчёт количества коров, и если расчёт вероятности не действует — то его надо править, убирая логический костыль.
                                              Реальные барышники на реальных рынках скота (например — в дореволюционной России, на скотных рынках Аргентины — страна, которая в начале XX века считалась одной из самых процветающих в мире) статистику продаж мусоленным карандашом по обёрточной бумаге наверное вели, а вот обработать её, чтобы избавиться запаса сверх расчётов, не могли — и для этого они не должны были нанимать академика Крылова, достаточно было сообразить заплатить за эту работу бедному учителю математики или студенту тех времён.

                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                • 0
                                                  Целевая функция присутствует неявно. Это максимизация прибыли на интервале 0-бесконечность. Или, если угодно, средней прибыли за единицу времени.
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                            • 0
                                              Как мне представляется, задача достаточно сложная, ее решение с обоснованием, если оно где-то опубликовано,- небольшая глава в книге по алгоритмам. Не стоит торопится с ответом)
                                              • 0

                                                Глава 7? (задача напомнила задачу про ковры скомбинированную с потоками в сетях)

                                                • 0
                                                  Боюсь, сильно мимо…
                                                  • 0
                                                    Я еще раз обдумал Ваше предложение и должен признать, что приближенное решение можно свести к задаче сильно напоминающей поиск максимального по мощности циклического потока в графе, однако на этот поток, в случае чистой стратегии (детерминированной), накладываются ограничения неделимости в узлах, поэтому, как Вы понимаете, вся простота алгоритмов теряется. Если применять смешанные стратегии (зависящие от случая), решение приближенной задачи действительно можно найти указанным способом, однако есть две проблемы:
                                                    а) нужно доказать, что максимум достигается на чистой стратегии (почти очевидно)
                                                    б) вычислительная сложность растет по экспоненте от величины обратной к величине шага дискретизации.
                                                    • +1
                                                      б) можно отбросить: для поиска циклического потока максимальной стоимости есть алгоритм куда проще с вычислительной точки зрения, чем линейное программирования. Еще раз спасибо за идею.
                                                  • 0
                                                    Всё это, конечно, контринтуитивно. Поэтому, на уровне гипотез.
                                                    Если мужик не продает коров совсем, то прибыль -0, но и убытков 0.
                                                    Таким образом, может возникнуть ситуация (например при низкой интенсивности потока покупателей), что стратегия минимизации убытков — не торговать.
                                                    Пусть мужик держит на продажу одну корову. Тогда можно построить что-то типа протокола разборчивой невесты.
                                                    Дальше пока не придумывается.
                                                    • +3
                                                      при почти бесконечном начальном капитале

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

                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                        • 0
                                                          «Бесконечный» начальный капитал вводится чтобы исключить задачу о разорении.
                                                        • 0

                                                          Если все условия можно задать в виде линейных неравенств, можно попробовать применить симплекс-метод.

                                                          • НЛО прилетело и опубликовало эту надпись здесь
                                                          • 0
                                                            В универе похожее решали на «Исследовании операций» (Мат. программирование)
                                                            • +1
                                                              Забавная задачка. Сходу напрашивается ряд «решений», а по зрелому размышлению проявляются интересные нюансы, упрощения и оптимизации.

                                                              Первое, что нам нужно для себя решить — это оптимальный размер буфера коров, который мы будем держать в резерве (S*). Очевидно, что оно будет зависеть от всех параметров этой задачи. Давайте отложим нахождение этой величины.

                                                              Итак, у нас для каждого случая (прихода покупателя; пронумеруем их по i) есть текущий запас коров S_i. Нам нужно:
                                                              1. решить, продавать корову этому покупателю или нет;
                                                              2. решить, сколько заказать коров из деревни (может быть 0, заказ-то бесплатный и, как я понял из задания, асинхронный? Поправьте меня, автор, если ошибаюсь).

                                                              По поводу второго пункта следует заметить, что акт заказа коров, строго говоря, не должен быть привязан к событиям прихода покупателей, то есть не обязательно должен происходить по факту прихода кого-то из них или по факту продажи. Похоже это тоже будет пуассоновский поток событий, параметр которого будет вычисляться из вероятностей потока покупателей. Если вероятности прихода покупателей рассчитаны (даны) верно, то процесс стационарный и, возможно, не придется даже динамически управлять параметром потока заказов. Вернее эффективнее будет не управлять.

                                                              Итак. Декомпозиция выявила три вопроса:
                                                              1. Каков оптимальный размер буфера (S*)?
                                                              2. Продавать ли корову i-му покупателю?
                                                              3. С каким интервалом дозаказывать коров?

                                                              Забавно, что в случае идеального пуассоновского процесса нам, скорее всего, можно вообще в самом начале определить какие классы обслуживать, а какие нет. И в начале же определить четко интервал времени дозаказа коровы. Очевидно, что при бесплатном асинхронном заказе нет смысла заказывать больше одной за раз.

                                                              Ок. С формулами я сейчас уже не осилю, да и тестовый стенд писать уже лень, но предположу, что мы просто откинем некоторые классы покупателей по рентабельности резервирования для них коровы с учетом среднего времени их появления. Остальным продаём корову из буфера, размер которого будет зависеть от вероятного количества обслуживаемых клиентов за время T.
                                                              Возможно следует еще оценить вероятностные характеристики убытка при потере клиента и как-то сравнить их с вероятностными характеристиками убытка от over-резервирования. Но это заметно усложнит формулу расчета глубины резерва.

                                                              Резюме. Задача похоже стационарна и не требует онлайн-управления процессом.
                                                              • 0

                                                                Мне вот тоже пришла в голову идея, что можно просто посчитать, сколько покупателей какого типа к нам (в среднем, но в долгосрочной перспективе только среднее и интересно) приходит за некий (произвольно взятый) интервал времени Q. Столько коров нам и нужно (X). Дальше заказываем по одной корове в Q/X (а начальный резерв берем как T/(Q/X)).

                                                                • 0
                                                                  Многие из ваших замечаний разумны, например, как вы правильно заметили, нужно учитывать, какие коровы уже заказаны и что они придут в будущем. Если же ваши ожидания насчет потока клиентов не оправдываются, действительно не стоит заказывать лишних коров, и поэтому правдоподобно, что заказ, если происходит, то только в момент продажи. Однако процесс требует постоянного управления и не сводится к определению размера буфера, поскольку оптимальность зависит не только от количества коров в вашем распоряжении сейчас но и от именно функции «уже заказанное пополнение»(«время»). С выбраковкой классов тоже не стоит спешить: если все шло как по часам, а затем случайно целый период T не было продаж, то возможно от лишних коров стоит избавится при первой возможности.
                                                                  • 0
                                                                    если все шло как по часам, а затем случайно целый период T не было продаж, то возможно от лишних коров стоит избавится при первой возможности.

                                                                    А если 10 раз подряд выпало красное, то нужно ставить на черное?

                                                                    Согласен с предыдущими ораторами. В силу случайности и полной непредсказуемости все, что происходило до данного момента времени абсолютно неважно. У нас есть только сейчас и будущее. Весь вопрос только в размере буфера. Если буфер забольшой, что приходится продавать корову — значит неправильно посчитан буфер и корову продавать не нужно было.
                                                                    • 0
                                                                      А если 10 раз подряд выпало красное, то нужно ставить на черное?
                                                                      Не совсем так. Тут беда в том, что из-за отсутствия продаж на складе скопилось количество коров выше оптимального.
                                                                      У нас есть только сейчас и будущее
                                                                      Да. Поэтому оптимальное количество не зависит от прошлых продаж/непродаж. Если текущее количество выше/ниже, то его надо вернуть до оптимального.
                                                                      Если буфер забольшой, что приходится продавать корову
                                                                      Нет. При любом (!) буфере будут ситуации, когда коров слишком много, и ситуации, когда продавать нечего.
                                                                      • +1
                                                                        из-за отсутствия продаж на складе скопилось количество коров выше оптимального.

                                                                        оптимальное количество не зависит от прошлых продаж/непродаж. Если текущее количество выше/ниже, то его надо вернуть до оптимального.

                                                                        При любом (!) буфере будут ситуации, когда коров слишком много, и ситуации, когда продавать нечего.

                                                                        Чувствуете в чем подвох? Если размер буфера больше оптимального, издержки на его содержание растут быстрее, чем прибыль от не упущенных (за счет этого увеличения буфера) клиентов. Если размер буфера меньше оптимального, издержки по статье недополученной прибыли из-за упущенных (из-за этого уменьшения буфера) хороших клиентов будут раст быстрее чем выигрыш (экономия) на прокорме буфера.
                                                                        Предполагается наличие седловой точки оптимума размера буфера.
                                                                        Оптимальный размер буфера мы можем в среднем держать за счет установки скорости заказа коров, равной средней скорости сбыта их рентабельным клиентам. Если эта средняя скорость сбыта известна наверняка и точно, то мы всегда будем блуждать около этой точки туда-сюда. Экстренно динамически продавая лишних коров сверх оптимума нерентабельным клиентам вы делаете подстройку только с одной стороны.

                                                                        Во-первых, почему вы тогда не предлагаете явно дозаказывать динамически коров в ускоренном режиме при перерасходе (то есть когда буфер меньшеоптимального)?

                                                                        Во-вторых, зачем вообще эта дополнительная инертная обратная связь нужна, когда по условию задачи четко известна средняя скорость сбыта коров? Дёргая динамически буфер туда-сюда, то есть заказывая коров из деревни с непостоянной скоростью и сбывая их иногда нерентабельным клиентам вы лишь уменьшаете добротность системы внося еще один маятник со всеми вытекающими. У нас нет «тренья» в системе и, может быть ваш такой микроменеджмент и не приведёт в среднем ни к профиту ни к издержкам, но зачем усложнять алгоритм?
                                                                        Полагаю это обосновано было бы только для безопасности на случай внезапного и незадокументированного изменения параметров потока покупателей. А об этом в задаче речи не шло. Потому я и сказал в треде. что на данном этапе хорошо бы уже спуститься в реальность, а не надувать сферического коня в безвоздушном пространстве.
                                                                        • 0
                                                                          Предполагается наличие седловой точки оптимума размера буфера.
                                                                          Ага. Только вот как его расчитать…

                                                                          Оптимальный размер буфера мы можем в среднем держать за счет установки скорости заказа коров, равной средней скорости сбыта их рентабельным клиентам
                                                                          Чуть сложнее: если в какой-то момент мы остались без коров и пропустили покупателя, нам придётся пропускать и заказ. И наоборот: если в какой-то момент мы накопили избыточный запас коров, для нас любой клиент внезапно становится рентабельным.

                                                                          Во-первых, почему вы тогда не предлагаете явно дозаказывать динамически коров в ускоренном режиме при перерасходе (то есть когда буфер меньшеоптимального)?
                                                                          Да, надо. Только вот по какому правилу? В каком количестве? В какой момент времени, учитывая время доставки? Как момент и объём заказа увязать с текущим остатком?

                                                                          Как мне это видится, задача сводится к двум вопросам:
                                                                          * Как определять, когда и сколько коров дозаказывать?
                                                                          * Как определять, продавать текущему клиенту или нет?
                                                                          • 0
                                                                            наоборот: если в какой-то момент мы накопили избыточный запас коров, для нас любой клиент внезапно становится рентабельным.

                                                                            Тогда где остановиться? Характер закона распределения не позволяет нам рассчитывать на 100% от пропуска клиента при любом размере буфера. Да, в какой-то момент вероятность пропуска клиента становится столь малой, что можно пренебречь, но есть же и фиксированная цена заказа коровы a, а условие допускает отрицательную маржинальность. Это делает «любого клиента» ой как нерентабельным.
                                                                        • 0
                                                                          А если 10 раз подряд выпало красное, то нужно ставить на черное?

                                                                          Не совсем так.

                                                                          Совсем не так!

                                                                          Нет. При любом (!) буфере будут ситуации, когда коров слишком много, и ситуации, когда продавать нечего.

                                                                          Нет. Если буфер равен 0 или 1 — коров не будет слишком много. Продавать коров нет смысла. Если вы дошли до ситуации, когда продаете корову по дешевке — значит не нужно было ее покупать.
                                                                          • 0
                                                                            Если буфер равен 0 или 1 — коров не будет слишком много
                                                                            0 коров это не буфер. На счёт 1 не уверен: 1 корова в момент непосредственно после сделки может быть «слишком много», если поток клиентов редкий, рентабельность низкая, а стоимость хранения высокая — в таких условиях можно было бы устроить её доставку ближе к середине среднего интервала между двумя клиентами, чтобы не кормить зря.
                                                                            • +1
                                                                              Просто в этом месте становится понятно, что вы не очень понимаете теорию вероятностей. Если вероятность, что клиент придет в ближайшую минуту — 0.001%, то от того, что клиент не приходил 1000 минут вероятность не изменится.

                                                                              Вы мыслите на классическом обывательском уровне — «редкое событие произошло, значит в ближайшее время вероятность его возникновения понижена».

                                                                              Понимаю, что для вас это контринтуитивно, но, увы, это не так.
                                                                              • 0
                                                                                вы не очень понимаете теорию вероятностей
                                                                                Я даже на «не очень» не претендую. Поэтому и написал в предыдущем комментарии, что «не уверен».

                                                                                Кстати, после вашего наставления у меня прибавилось уверенности. Однозначно есть набор параметров, при котором одна корова в запасе будет «слишком много». Это будет в ситуации, когда для каждого класса покупателей k выполняется неравенство xklk < u :-)
                                                                                • 0
                                                                                  Ну да, конечно, если покупателей, например, 0, то 1 корова уже слишком много)

                                                                                  Я говорил об этом:
                                                                                  в таких условиях можно было бы устроить её доставку ближе к середине среднего интервала между двумя клиентами


                                                                                  Я приведу пример. В рулетке вероятность выпадения числа 13 — 1/37. Если выпало 13 — необходимо ли пропустить пару следующих бросков, чтобы приблизиться к следующим 13?

                                                                                  Вот так и тут. От того, что клиент пришел абсолютно нету никакого резона отступать на какой-то промежуток времени — это не дает выгоды, а только затягивает игру.
                                                                                  • 0
                                                                                    Я говорил об этом:

                                                                                    в таких условиях можно было бы устроить её доставку ближе к середине среднего интервала между двумя клиентами
                                                                                    Да, я ошибся. Хотя у нас по-прежнему нет решения.

                                                                                    Ну да, конечно, если покупателей, например, 0, то 1 корова уже слишком много)
                                                                                    Если покупателей 0, то нет задачи. А вот если торговля в принципе нерентабельна, всё равно нужна стратегия распродажи запасов с наименьшими потерями.
                                                                                    • 0

                                                                                      Ну я так понимаю, вероятность 1/37 говорит о том, что после 37 бросков вероятность выпадения 13 хотя бы 1 раз близка к 1. Но ок, тут может и не так.


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


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

                                                                                      • +1
                                                                                        Вот как раз сравнение с автобусом — ошибочно. Приход автобуса — процесс не случайный, ведь они ходят по графику. Если бы автобусы запускали подбрасыванием монетки — ага, решка, значит 15-й, а орел — 21-й, то ваш пример был бы аналогичен, но снова ошибочен.

                                                                                        Ну я так понимаю, вероятность 1/37 говорит о том, что после 37 бросков вероятность выпадения 13 хотя бы 1 раз близка к 1

                                                                                        Вероятность решки на монетке 1/2, следует ли из этого, что при двух бросках вероятность выбросить решку близка к 1?

                                                                                        А как только событие произошло, вероятность его повторения в следующий момент времени маленькая, иначе это число событий было бы больше.

                                                                                        Нет, нет и еще раз нет. Предыдущее событие НИКАК не влияет на следующее. Серьезно. Возьмите монетку. Киньте ее. А потом считайте, сколько раз выпало то же, что и в предыдущий, а сколько раз иной вариант. И вы увидите, что в 50% случаев выпадает тот же вариант, а в 50% случаев вариант меняется. Потому что неважно, что выпало перед этим. Если вы кинули 5 раз подряд орла — шестой раз ровно так же у орла 50% вероятности, как и у решки. Оно не уменьшается от того, что Пуассон вывел свое распределение.

                                                                                        Смотрите. Допустим мы монетку кидаем дважды. Значит у нас есть такие варианты:
                                                                                        (О-О), (О-Р), (Р-О), (Р-Р). Вероятность того, что выпадет два орла всего 25%, но если перед этим уже выпал орел вероятность того, что снова выпадет орел — 50%, понимаете?
                                                                                        • 0

                                                                                          Да, с монеткой вы правы. Ну я поэтому и сделал оговорку, что возможно это не так. Просто, как мне кажется, здесь 2 принципиально разные ситуации. В случае с рулеткой и монеткой вероятность зависит от количества вариантов, в случае пуассоновских процессов вероятность рассчитывается по отрезкам времени. Если мы знаем, что за час должно прийти 2 покупателя такого типа, то если за полчаса никто не пришел, то в следующие полчаса вероятность появления выше. А если и за час не пришел, то в следующий час можно ожидать 4. Иначе характеристика была бы не "2 покупателя в час", а "1 покупатель в час". А если стабильно никто не приходит, уже надо говорить о том, что характеристика изменилась.


                                                                                          С автобусами аналогично. Автобусы ходят по графику, но в пределах одной остановки появление следующего номера рассматривается как случайная величина. Вернее, обладающая свойствами случайных. Потому что есть светофоры, пробки, поломки, а также другие автобусы, у которых свое расписание и набор остановок. А вот расписание как раз и означает, что за час на эту остановку должно прийти 3 автобуса с этим номером.

                                                                                          • +1
                                                                                            Нет, вам неправильно кажется.

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

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

                                                                                            Нет, не выше. Вы думаете, что за углом стоит Пуассон и считает, сколько именно покупателей к нам заходит и если их меньше чем нужно, то срочно посылает своих агентов? А если пришли 8 вместо 2? То теперь шестеро умрут не выйдя из магазина?

                                                                                            Распределение Пуассона говорит приблизительно следующее. В среднем у нас десять покупателей в час. Следовательно:
                                                                                            11% вероятности, что у нас будет 10 покупателей
                                                                                            10% вероятности, что у нас будет 9 покупателей
                                                                                            9% вероятности, что у нас в ближайший час будет 11 покупателей
                                                                                            и даже 1% вероятности, что у нас будет 20 покупателей за ближайший час.

                                                                                            Все. Больше распределение Пуассона ни о чем не говорит. Только о том с какой вероятностью какой час выпадет. Так вот. Есть 5% вероятности, что придет 5 покупателей и 5% вероятности, что придет 15 покупателей. Если в первые полчаса пришло только двое — может мы попали в неудачные 5%. А если в первые 15 минут пришло 10, то может попали в тот удачный 1% и потом будет еще десять.

                                                                                            Самое главное, что предыдущие события НИКАК не влияют на следующие. То есть пусть у нас предыдущих два часа был полный завал или пустой магазин следующий час с сего момента (и с любого момента) имеет ровно тот же график распределения Пуассона.

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

                                                                                              Ок, почитал комменты ниже, понял, что не прав)

                                                                                          • +3

                                                                                            На самом деле, предел 1-(1-1/n)n стремится не к 1, а к 1-1/e, что составляет примерно 0,63


                                                                                            Именно такова будет вероятность получить хотя бы одно число 13 после 37 вращений рулетки.

                                                                            • 0
                                                                              С выбраковкой классов тоже не стоит спешить: если все шло как по часам, а затем случайно целый период T не было продаж, то возможно от лишних коров стоит избавится при первой возможности.

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

                                                                              В любом случае эти параметры тонкой настройки не гарантируют ничего. Это просто рандомная ставка на риски, те или иные — не важно.

                                                                              Если же ваши ожидания насчет потока клиентов не оправдываются, действительно не стоит заказывать лишних коров

                                                                              Мои ожидания по поводу потока клиентов основаны на данных из условий задачи. Это вектор l. Если эти ожидания не оправдываются на долгосрочной перспективе, то это значит лишь, что исходные данные (тот самый вектор) не описывает распределение событий. В этом случае мы должны корректировать вектор (например, уточнять его статистикой), или агрессивно подстраивать поток заказов. Но это уже не будет исходной задачей.
                                                                              Да и на счет "лишних коров", почему вы однобоко подходите к возможным рискам? А если «неоправдавшиеся ожидания» привели к обратной ситуации и коров не хватило, отчего мы потеряли хороших клиентов и недополучили прибыль? Если скорость пополнения буффера и его размер выбраны верно, а «ожидания» соответствуют характеристикам случайной величины, то риски в ту и другую сторону одинаковы.
                                                                              Ну а вы в данном случае поддались классическому когнитивному искажению отдавая в плане рисков незаслуженный приоритет тому, что имеете по отношению к тому, что могли бы иметь.

                                                                              Подчеркну для ясности.
                                                                              как вы правильно заметили, нужно учитывать, какие коровы уже заказаны и что они придут в будущем.

                                                                              Я не говорил, что это нужно как-то учитывать онлайн-управлением. Это должно быть учтено автоматически в скорости заказа коров из деревни на основе вероятностных зарактеристик потока покупателей.
                                                                            • 0
                                                                              Добавил пояснения в текст статьи.
                                                                              • 0
                                                                                не должен быть привязан к событиям прихода покупателей, то есть не обязательно должен происходить по факту прихода кого-то из них или по факту продажи

                                                                                На самом деле, скорее всего, должен. Смотрите.
                                                                                Допустим, у нас есть состояние (state). В этом состоянии:
                                                                                1. Вероятность прихода покупателя
                                                                                2. Текущее количество коров
                                                                                3. И другая статика типа цены на корову

                                                                                Решение о покупке (покупать или нет) мы делаем только на основе этого состояния, но не того, что было ДО него. У нас полностью случайный рынок, следовательно ситуация как в казино — приход 10 черных цифр все-еще оставляет равную вероятность прихода каждого цвета. Ждать какое-то время после прихода покупателя — все-равно, что ждать, чтобы выпало еще черное, чтобы ставить на красное.

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

                                                                                Значит весь вопрос задачи только в максимальном количестве коров, к которому мы всегда стремимся. Ну и, конечно, определение списка классов, которым мы продаем, но это статика, которая определяется до начала продаж.
                                                                                • 0
                                                                                  И еще на примере. Допустим T=0 (то есть корову могут доставить сразу после заказа). Следовательно в таком случае мы делаем Макс=1 и заказываем корову сразу после того, как у нас забирают ту, что есть. Ждать время — это исключительно игра в рулетку:
                                                                                  — У меня корову только что купили, так что ближашие несколько минут покупателя точно не будет, значит надо немножко подождать, перед тем, как заказывать следующую и плевать на теорию вероятностей.
                                                                                  • +1
                                                                                    На примере. Допустим, цена продажи коровы Ц=100, цена содержание за время доставки — Р=70, а также приходит в среднем 10 человек за время доставки.

                                                                                    Если мы возьмем максимум коров М=10, то получим такое распределение:


                                                                                    Если количество коров М=15, то такое распределение:


                                                                                    Для того, чтобы посчитать среднюю прибыль для каждого количества коров необходимо умножить прибыль каждого варианта на вероятность этого варианта и просуммировать.
                                                                                    К примеру, для 15:
                                                                                    ... + -550*вероятность(5) + ... + -50*вероятность(10) + ... + 450*вероятность(15)

                                                                                    Уверен, для этого есть формула. К сожалению, по образованию гуманитарий, так что вспомнить ее не могу.

                                                                                    Так вот, таким образом мы получим прибыль для каждого варианта. Увеличивая М на 1 будем получать все большую сумму. (при М=0 — С=0, при М=1 — С=~30). И в какой-то момент эта сумма начнет падать. Вот это число М, которое имеет наибольшую сумму — есть наш буфер для данных чисел.
                                                                                    • 0
                                                                                      Я забыл учесть, что коровы продаются, следовательно в расходе необходимо это учитывать. Например для М=15:

                                                                                      Расход в случае  5 покупателей: 70 * (15 -  5/2)
                                                                                      Расход в случае 10 покупателей: 70 * (15 - 10/2)
                                                                                      Расход в случае 15 покупателей: 70 * (15 - 15/2)
                                                                                      

                                                                                      Может показаться странным, что я не беру в рассчет заказанные коровы, но это неважно. Мы рассчитываем буфер и заказываем новую корову при продаже старой. Следовательно за это время буфер обновится и в среднем для новых 15 коров будет та же выгода.
                                                                                    • 0
                                                                                      Никогда не стоит плевать на теорию вероятностей, иначе мы рискуем впасть в азарт и просадить все состояние из-за когнитивных искажений.
                                                                                      Не забывайте, что у нас речь идет о симметричном риске с двух сторон: 1) подержать лишних коров какое-то время на довольствии; 2) пропустить ценного клиента при опустевшем буфере.
                                                                                      Пуассоновский характер поступления покупателей даёт нам понимание, сколько в среднем на большом интервале времени их приходит за единицу времени. Этого (вкупе с прочими параметрами) достаточно, чтобы определить строгую регулярную частоту заказа коров, которая в среднем будет покрывать требования покупателей. Увеличение буфера уменьшает количество упущеных покупателей (недополученная прибыль), зато увеличивает расходы на корм. Уменьшение буфера снижает расходы на корм, зато недополученная прибыль на пропущенных клиентах начнет расти.
                                                                                      • 0
                                                                                        Про «плевать на теорию вероятностей» это был сарказм, конечно. Но если отвязаться от покупателя и просто покупать коров равнораспределенно, то тогда формулы вообще упрощаются.
                                                                                        • 0
                                                                                          Именно! И надежность решения растёт. Надо нарисовать графики рисков по упущению и по перерасходу кормёжки от размера буффера. Там, где они пересекутся и будет оптимальный размер.

                                                                                          Простите, не могу комментировать с вашей скоростью, поэтому отвечу здесь.
                                                                                          Я говорю о том, что по факту покупки необходимо покупать сразу корову, все. Продал корову — заказал новую. Если мы сидим с пустым буфером, то значит у нас в заказах уже висит максимальное количество коров. И такое может быть с абсолютно любой выгодной стратегией — пустой буфер, куча коров в ожидании и новый клиент. Вопрос исключительно в том, какой должен быть буфер.


                                                                                          Нельзя заказывать только по факту продажи из-за возможного очень большого лага T. Интуитивно представьте, что наблюдается времнное затишье и покупатели не идут. Если они потом не усилят частоту прихода, значит у нас неверные данные о потоке, а если верные, то потом покупатели пойдут чаще и мы тупо не сформируем лаг. Я настаиваю на том, что данные о потоке однозначно определяют скорость заказов. И это будет работать при любых соотношениях T и среднего времени появления поупателей. А из-за вашего лага придется неоправданно увеличивать буффер терпя издержки на хавчике.
                                                                                          • 0
                                                                                            На самом деле, что ваш, что мой вариант в долгосрочной перспективе приблизительно одинаковые. Смотрите, что у вас, что у меня будет буфер. И мы с вами в среднем заказываем абсолютно одинаковое количество коров за единицу времени. Вы ведь заказываете в среднем коров столько, сколько клиентов приходит и я заказываю коров столько, сколько клиентов приходит. Следовательно где-то уже через 1Т у нас с вами будут висеть в заказах одинаковое количество коров и равное среднему количеству покупателей.

                                                                                            Вопрос лишь в начальном буфере. С каким количество коров необходимо прийти, чтобы максимизировать прибыль?
                                                                                        • 0
                                                                                          Увеличение буфера уменьшает количество упущеных покупателей (недополученная прибыль), зато увеличивает расходы на корм. Уменьшение буфера снижает расходы на корм, зато недополученная прибыль на пропущенных клиентах начнет расти

                                                                                          Главный вопрос — как правильно рассчитать буфер, чтобы максимизировать прибыль.
                                                                                          • 0
                                                                                            Например, построить график прибыли (упущеной с вероятностью P=const) от размера буфера. И посроить график издержек (с той же зафиксированной вероятностью вероятностью P) от размера буфера. Точка пересечения — идеальный размер с вероятностью P.
                                                                                            Поигравшись с вероятностями и применив волшебные три сигма по гауссу мы получим хорошие показатели.
                                                                                            • 0
                                                                                              У нас есть М (количество коров), Ц (цена продажи), Р (расходы на корову за время, равное времени доставки коровы) и А (среднее количество человек). Какие формулы для этих графиков?
                                                                                              • 0
                                                                                                Формула на самом деле будет еще сложнее, чем кажется, из-за множества категорий клиентов с разной скоростью потоков. Тут можно статистически графики построить оттабулировав настройки. Благо модель не сложная.
                                                                                                Можно заморочиться интегралами и дифурами, конечно, но если задача чисто академиеская, то я лучше спать, а если практическая, то там наверняка не так всё гладко с параметрами потока и лучше сразу строить адативную модель, которая будет инкремнтально уточнять себя по мере накопления данных и даже с учетом их устаревания и инвалидации.
                                                                                                Это тот самый порог, где порой стоит остановиться и решать даьше практическую задачу, вместо сферической в вакууме.
                                                                                                • 0
                                                                                                  Как-то мой товарищ сказал, что в задаче интереснее доказать, что сам факт, что она решаема, чем таки найти решение)
                                                                                      • 0
                                                                                        Решение о покупке (покупать или нет) мы делаем только на основе этого состояния, но не того, что было ДО него.

                                                                                        Нам не нужно принимать такие решения по факту покупки. Из-за T, которое может в том числе сильно превышать средний интервал появления клиентов, мы рискуем замешкаться и пропустить покупателей сидя у пустого буфера. При этом мы халатно не используем данные в условии задачи параметры потока клиентов. Вероятностные характеристики потока однозначно определяют скорость наших заказов коров. Попытка рулить онлайн чревата потерями.
                                                                                        По-прежнему настаиваю, что никаких решений онлайн принимать в задаче не надо, если речь идет о достоверно известных параметрах потока (то есть величины генерируются по этим параметрам). Если параметры распределения собраны статистически, то нужно делать предоханители сверху и снизу, а также агрессивную петлю отрицательной обратной связи для борьбы с неполнотой сведений о реальных параметрах случайных величин.
                                                                                        В реальном мире параметры этих случайных величин не могут быть известны достоверно в принципе. А статистика — это заведомо неполная неточная информация.
                                                                                        • 0
                                                                                          Нам не нужно принимать такие решения по факту покупки. Из-за T, которое может в том числе сильно превышать средний интервал появления клиентов, мы рискуем замешкаться и пропустить покупателей сидя у пустого буфера

                                                                                          Я говорю о том, что по факту покупки необходимо покупать сразу корову, все. Продал корову — заказал новую. Если мы сидим с пустым буфером, то значит у нас в заказах уже висит максимальное количество коров. И такое может быть с абсолютно любой выгодной стратегией — пустой буфер, куча коров в ожидании и новый клиент. Вопрос исключительно в том, какой должен быть буфер.
                                                                                    • 0
                                                                                      Хотел бы добавить несколько соображений.
                                                                                      1. Запрашивать достаточно по одной корове. В любом случае запрос нескольких коров одновременно можно разбить на несколько запросов по одной корове с бесконечно малым промежутком по времени.
                                                                                      • 0
                                                                                        Тогда можно ещё приравнять стоимость коровы к единице (если в исходных данных она ненулевая)
                                                                                        И время доставки тоже нормализовать, пересчитав параметры распределения. Минус два параметра.

                                                                                        Sergey_Kovalenko, Мужик платит за содержание коровы, пока её доставляют на склад или нет?
                                                                                        Это может сильно повлиять на стратегию: коровы ещё в пути, а он уже несет убытки.
                                                                                        • 0
                                                                                          Похоже не платит за еду при доставке. Но, на самом деле, не важно. В случае, если платит,. задача не изменится. Время доставки фиксировано, а значит стоимость еды во время доставки можно заложить в цену коровы.
                                                                                        • –1
                                                                                          Простите, отправил недописанный комментарий! Должно было быть примерно так:
                                                                                          1. Запрашивать достаточно по одной корове. В любом случае запрос нескольких коров одновременно можно разбить на несколько запросов по одной корове с бесконечно малым промежутком по времени.
                                                                                          2. Похоже, что все классы покупателей можно рассматривать по-отдельности.
                                                                                            Пусть у нас есть только один класс k1, пусть для него оптимальной будет стратегия S1.
                                                                                            Стратегия,
                                                                                            … в моём понимании, это некоторый функционал от всех имеющихся на данный момент данных (о клиентах, о коровах, о запросах и т.д.) и времени, который принимает значение 0 или 1. 0 означает, что в этот момент времени мы ждём, 1 — запрашиваем корову.
                                                                                            Аналогично, для класса k2 — стратегия S2. Теперь предположим, что нужно решить задачу для двух классов: k1 и k2. Так вот, я утверждаю, что оптимальной будет просто независимая комбинация двух стратегий S1 и S2 (в одной мы ориентируемся только на данные по клиентам первого класса, во второй — только на второго). Если же предположить, что есть более хорошая стратегия, то она даст больше доходности на одном из классов. Тогда для задачи только с одним классом можно применить эту, улучшенную стратегию (урезанную на один класс) и получить большую доходность, а это противоречие.
                                                                                            Немного сумбурно и не очень строго, но надеюсь, понятна мысль.
                                                                                          3. Можно считать, что параметры распределения известны. Так как интересует матожидание доходности, то любым начальным отрезком времени (конечным) можно пренебречь. А за этот начальный отрезок можно с любой заданной точностью найти параметры распределения.

                                                                                          Таким образом, как мне кажется, задача сводится к одному классу клиентов с известным параметром l, и это уже значительно более поддающаяся решению задача.
                                                                                          • +1
                                                                                            Думаю, независимость стратегий стоит обосновать получше: когда на рынке два продавца, каждый на свою аудиторию, иногда им будет выгодно кредитовать друг друга коровами.
                                                                                            • –1
                                                                                              Продавец ведь всегда один, разве нет? Я про классы покупателей
                                                                                              • +1
                                                                                                Применение двух независимых стратегий эквивалентно двум не взаимодействующим продавцам, ориентирующимся каждый на свой класс покупателей.
                                                                                              • –1
                                                                                                Если A кредитует B, то B получает выгоду в виде неупущенного клиента, но зато у A образуется дефицит и увеличивается вероятность отказать своему клиенту. С другой стороны, B придётся когда-то отдавать корову, и в момент отдачи у него тоже образуется дефицит и вероятность отказа, зато у A в этот момент увеличится буфер и уменьшатся риски. На круг, риски скомпенсируют бенефиты, и все останутся при своих, как если бы стратегии были полностью независимыми.
                                                                                                • 0

                                                                                                  Не будет у B дефицита и вероятности отказа, потому что ту корову, которую он будет отдавать обратно, он закажет дополнительно.

                                                                                                  • 0
                                                                                                    В любом решении этой задачи должен соблюдаться закон сохранения среднего потока, иначе коровы будут либо накапливаться, либо склад опустеет. Если A и B оба держат поток заказов в среднем равным потоку продаж, то количество коров на складе у них в среднем не растёт и не падает, а держится вблизи оптимума, задаваемого соотношением средней цены потери клиента и средней стоимости корма для коровы до её продажи.

                                                                                                    Если кто-то начинает заказывать коров вне очереди, значит где-то должно быть накопление коров и отклонение от оптимума — либо у А, либо у B. Заказ дополнительной коровы для покрытия кредита эквивалентен экстренному заказу дополнительной коровы для покрытия внезапного опустошения буфера в сценарии объединённого буфера.
                                                                                                    • 0

                                                                                                      Смотрите еще раз:


                                                                                                      1. А отдал Б корову
                                                                                                      2. Б продал корову и заказал новую
                                                                                                      3. Б получил корову и вернул ее А

                                                                                                      Где тут нарушился баланс-то?

                                                                                                      • –1
                                                                                                        Если бы кредитования не было, то вышло бы так:
                                                                                                        1) А продал единственную корову первому миллионеру
                                                                                                        2) А отказал второму миллионеру
                                                                                                        3) А некоторое время не заказывает новую корову, потому что по его оптимальной стратегии делать это ещё рано: средний поток миллионеров мал, и если заказывать корову немедленно, то её придётся долго кормить. А должен поддерживать достаточно низкий поток коров. Делать это он может лишь меняя частоту заказов (он не может заказывать пол-коровы)

                                                                                                        Но в случае с кредитованием Б приносит А корову через день, и теперь у А больше коров, чем его оптимум, и он тратит деньги на корм, хотя, возможно, следующего миллионера после двух первых придётся ждать очень долго. Эффективная частота заказов увеличилась из-за Б, и на бесконечно большом промежутке времени А проиграет примерно столько, сколько выиграл.
                                                                                                        • –1
                                                                                                          Но в случае с кредитованием Б приносит А корову через день,

                                                                                                          Прошу прощения, в последнем абзаце напутал чутка. Б даёт корову А немедленно. После этого А заказывает и отдаёт корову Б, а также должен решить, заказывать ли корову для себя или нет. Если он закажет, то эффективная частота заказов будет выше оптимума, и он будет терять на корме. Оптимальной стратегией будет пропустить один запланированный заказ, чтобы скомпенсировать незапланированное увеличение потока заказов — но это увеличивает риск отказа. На бесконечном промежутке времени… и т.д.
                                                                                                  • 0

                                                                                                    Вот вам простейший пример. Допустим, есть два типа покупателей. Первый покупает задорого (например, за миллион), но настолько редко, что для него выгодно держать только 1 корову. Второй покупает чаще, но с наценкой всего в 1 рубль.


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

                                                                                                    • 0
                                                                                                      Это равносильно тому, что у мы смешиваем два буфера (для редких богачей, длиной 1 и для частых бедняков, длиной L) в один, и берём коров не глядя. В смешанном буфере будет L+1 корова, и если L настроено правильно, чтобы обслуживать большой поток бедняков, то у нас практически всегда найдётся корова для внезапного зашедшего богача (что увеличит риск отказа более часто заходящему бедняку). Пока не вижу отличий.
                                                                                                      • 0

                                                                                                        Вот именно в этом "берем коров не глядя" — и отличие, которое не дает свести задачу к двум независимым.

                                                                                                      • –1
                                                                                                        Два потока с интенсивностью I и J и маржой x и y соответственно смешиваются в один с интнсивностью I+J и маржой (x*I+y*J)/(I+J).
                                                                                                        Что позволяет из двух нерентабельных классов сделать один рентабельный.
                                                                                                        • 0

                                                                                                          Докажите что так можно делать.

                                                                                                          • 0
                                                                                                            В смысле? То что интенсивность двух потоков равна сумме интенсивностей? Это доказано в учебнике. А то что средняя маржа будет такая — так это потому что у вас биномиальное распределение, с вероятностью I/(I+J) один клиент, J(I+J) второй. Вот оно так и получается.
                                                                                                            • 0

                                                                                                              Но оптимальная стратегия-то для двух разных типов клиентов и для одного "среднего" типа может отличаться!

                                                                                                        • –1
                                                                                                          А вообще, вы тут неявно пронесли дополнительное условие: якобы первый продавец не может спокойно ждать появления ещё одного покупателя, пока второй торгует вовсю. Т.е. вы задали граничное условие: конечность времени.

                                                                                                          В случае с бесконечным временем нет проблем подождать своего покупателя хоть ещё миллиард лет — так как средний поток покупателей неизменен, то на длинном промежутке все отказы из-за дефицита коровы будут скомпенсированы удачными продажами сразу после прибытия новой коровы (без необходимости кормить её слишком долго).
                                                                                                • 0

                                                                                                  Ваша задача происходит из экономики. И решается, как правило не математически, а организационным-экономическим путем, с помощью новых вводных.


                                                                                                  В общем виде задача сводится к уменьшению количества связанного капитала. Или пропускной способности предприятия. Классическая книжка по теме: Голдрейт, Цель.


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

                                                                                                  • 0
                                                                                                    В общем виде задача сводится к уменьшению количества связанного капитала
                                                                                                    А может и не сводится…

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

                                                                                                      Зачем максимизировать то, что даётся по условию в неограниченном количестве? Без ограничения по капиталу задача не имеет смысла в принципе. Экономика должна быть экономной, иначе это не экономика. Вы же не будете продавать людям снег зимой, и стараться просто максимизировать прибыль от этого занятия..?

                                                                                                      процентная ставка подразумевается нулевой

                                                                                                      в реальной жизни ставка уже давно отрицательная, лишь бы клиент нашелся, что бы было на кого риски спихнуть))
                                                                                                      • 0
                                                                                                        Зачем максимизировать то, что даётся по условию в неограниченном количестве?

                                                                                                        Затем, что это требуется по условию задачи :-)

                                                                                                    • 0
                                                                                                      Можно как-нибудь поделится ссылкой на электронную версию книги?
                                                                                                  • 0
                                                                                                    Есть классическая задача об обслуживании кораблей в порту. Возможно покупателей можно рассматривать как корабли, а коров — как причалы.
                                                                                                    • 0
                                                                                                      Буду благодарен за ссылку.
                                                                                                      • 0
                                                                                                        К сожалению эта штука у меня только в виде конспекта. Как доберусь до него — посмотрю какие там отражены результаты.
                                                                                                      • 0
                                                                                                        Да, задача похожа на теорию массового обслуживания. Только здесь нет точек обслуживания (Мужик один, а корова после покупки выходит из игры), нет задержек на обслуживание (мгновенная продажа) и нет очередей (мгновенный отказ).
                                                                                                        • 0
                                                                                                          Начну с конца. Системы массового обслуживания бывают без очередей. Корову можно считать устройством обслуживания, время обслуживания — Т (время доставки очредной коровы после продажи)
                                                                                                          • 0

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

                                                                                                            • 0
                                                                                                              Если вы закажете корову до продажи то число устройств обслуживания какое-то время будет больше чем нужно. А если после то меньше. Как то так.
                                                                                                              • 0
                                                                                                                "… что оптимальная стратегия всегда заказывает новую корову в момент продажи старой."-Это весьма правдоподобно, но не верно.
                                                                                                                • 0
                                                                                                                  не верно.

                                                                                                                  Аргументируйте
                                                                                                                  • 0
                                                                                                                    Всего один класс, разумные предположения о прибыли и расходах, T много больше среднего ожидания клиента, скажем минута и месяц, тогда стоит заказывать на месяц вперед одну корову в минуту почти независимо от текущего состояния дел.
                                                                                                                    • +1
                                                                                                                      Черт, классный пример. Как говорится, вместо тысячи слов. При заказе только по факту продажи мы будем продавать корову раз в месяц, а при ежеминутном раз в минуту начиная через месяц.
                                                                                                                      Но предвосхищу возражения и патчи алгоритма любителей интуитивных оптимизаций.
                                                                                                                      Они скажет, что заказывать надо только по факту прихода хорошего клиента независимо от того продали мы ему корову или нет.
                                                                                                                      На это возразить будет сложнее.

                                                                                                                      Сморите. Клиенты приходят в среднем раз в минуту, а это эквивалентно 60 раз в час.
                                                                                                                      Представьте, что так уж вышло, что пол часа было затишье, а потом они на какое-то время повалили быстрее. Вполне вероятная ситуация для пуассоновского процесса.
                                                                                                                      Фишка в том, что все эти пол часа мы не заказывали коров, но это никак не отразилось на размере буфера. Получасовое затишье в приходе коров произойдёт аж через месяц, а все эти пол часа приходили коровы, которые были заказаны месяц назад. То есть, мы зачем-то отодвинули затишье на месяц вперёд, когда оно может и не наступить, а может через месяц напротив на это получасовое затишье придет наплыв клиентов.
                                                                                                                      Понятно, что в среднем мы на этом потеряем не так много, но определённо потеряем. И бессмысленно усложним процесс закупки. Вместо заказов раз в минуту будем делать заказы именно в момент продажи.
                                                                                                                      Что это. как не суеверная интуитивная «оптимизация» (в кавычках, потому что нет, не оптимизация это).
                                                                                                                      • +1
                                                                                                                        Черт, классный пример. Как говорится, вместо тысячи слов. При заказе только по факту продажи мы будем продавать корову раз в месяц, а при ежеминутном раз в минуту начиная через месяц.

                                                                                                                        Плохой пример. Он проигнорировал необходимость буфера, который как раз на это и рассчитан. Мы берем столько коров, чтобы за этот месяц «ожидания» получить максимальную прибыль. Ровно так же, как и закупая их случайным образом. Необходим одинаковый буфер для обоих случае и число заказов для обоих случаев будет в среднем одинаковым.

                                                                                                                        Они скажет, что заказывать надо только по факту прихода хорошего клиента независимо от того продали мы ему корову или нет.

                                                                                                                        Глупость какая-то. Заказывать необходимо по факту продажи.