Как я уже писал habrahabr.ru/post/323930, недавно, при анализе структуры одного специфического рынка услуг, обнаружилась довольно занимательная задача, решение которой на тот момент было для меня совсем не очевидно, и, как показал опыт предыдущей публикации, совсем не очевидным он оказался для многих здешних читателей. Настоящим решением я немало обязан вашим замечаниям и советам. Для меня довольно поучительным видится то, что задача, на первый взгляд, из теории массового обслуживания нашла решение привлечением далеко стоящей от нее области знания, показывая тем самым единство всех разделов математики. Прежде всего, я хотел бы отметить, что приводимые ниже рассуждения, хотя и дают верные рекомендации к действию с достаточной для практики точностью, а так же является концептуально правильным, к сожалению, не претендует на простоту качественного описания характерных типов стратегий. Можно сравнить предлагаемый здесь способ поиска стратегии с решение квадратного уравнения методом Ньютона: результат верный, а характер решения скрыт.
Для начала давайте попытаемся узнать, есть ли вообще способ действовать на рынке без убытка для себя. Единственная причина убытков содержится в необходимости нести расходы на содержание коров. Понятное дело, что продавец применяет максимально бережливую стратегию, когда в стойле у него находиться не более чем одна корова, и только после ее продажи он заказывает следующую. Применяя такой подход, нужно продавать имеющуюся корову первому же покупателю, принадлежащему любому классу, рентабельному с точки зрения Мужика. Остается решить, какие классы признать рентабельными. Для примера возьмем два класса покупателей: представители первого пусть появляются в среднем 3 раза за час и дают 1 рублей, а представители второго – 2 раза и дают 7. Не сложно смекнуть, что продавая только первому классу, можно заработать 3 руля на каждый час простоя, только второму классу покупателей – 14 рублей, а если продавать любому представителю из этих классов, то 14+3 рубля на каждый час оплаченного простоя коровы. Действительно, в среднем придет 3+2 покупателя на час простоя, при этом в среднем 3 из них будут из первого класса, а 2 из второго. Из этих рассуждений можно заключить, что оптимальной по прибыли бережливая стратегия будет тогда, когда корову продают любому покупателю, дающему неотрицательную надбавку к закупочной цене. Если величина средней прибыли час меньше стоимости прокорма, то вряд ли имеет смысл оставаться на рынке.
Давайте теперь перейдем к дискретному по времени аналогу. Чтобы получить хорошее приближение, разобьем ось времени на столь малые одинаковые промежутки, чтобы их величина не превосходила 1/10 времени доставки коров из деревни и при этом вероятность появится хотя бы одному покупателю, не важно, какого класса, за такой промежуток не превосходила все ту же 1/10. Напрашивается еще условие, которое каким-то образом должно ограничивать размер ошибки дискретизации траты на относительно дорогой прокорм, как, например, в случае с очень богатым и редко появляющимся покупателем и постоянно имеющейся возможности при желании очень быстро продать корову по закупочной цене. Однако условие выбора столь малого промежутка, что в его течение в среднем появляется 1/10 покупателя, ограничивает оперативность реакции на лишнюю корову, делая дальнейшее уменьшение временного промежутка нецелесообразным.
Следующий этап построения аналогии состоит в переходе от независимых пуассоновских потоков к зависимым дискретным потокам покупателей. Пусть в непрерывной модели вероятности появится за бесконечно малый промежуток времени покупателям каждой категории относились как a: b: …: h, а вероятность появится хотя бы одному покупателю в промежутке времени, полученном при разбиении, равнялась p, тогда в дискретной модели в начале каждого шага будем проводить однократное испытание Бернули на «Успех» с вероятностью p, и в случае «Успеха» — какое-нибудь испытание с множеством несовместных исходов: одним для каждого класса покупателей и таким же отношением вероятностей между исходами. В силу того, что в непрерывной модели вероятность появиться сразу двум покупателям в течение одного промежутка разбиения по сравнению с вероятностью появления в точности одному была крайне низкой, построенная таким образом дискретная модель, даже не смотря на зависимость между потоками, будет давать хорошее приближение.
Настало время описать сам процесс действий на дискретном рынке. Пусть время доставки T оказалось разбитым на r интервалов. Далее приведен порядок действий внутри каждого интервала разбиения, называемых далее турами или ходами. В начале каждого тура Мужик получает заказанных на это время коров и оплачивает прокорм всего имеющегося у него скота, затем описанными выше испытаниями определяется, пришел ли покупатель и какова с него возможная прибыль. В конце тура Мужику предстоит выполнить два действия: продать корову, либо отказать в сделке и заказать необходимое количество коров, которых ему доставят ровно через r ходов. На этом ход закончен и начинается новый.
В описанной схеме функционирования рынка состояние Мужика на момент принятия решения полностью описывается
1) количеством имеющихся у него в стойле коров,
2) распределением всех заказанных им коров по ближайшим r ходам,
3) наличием и классом покупателя на текущем ходу.
Я должен здесь особо подчеркнуть, что в 2) важно не только суммарное количество коров в заказе, но и их распределение по ближайшим ходам, на которые заказ уже невозможен.
Гипотетически Мужик имеет счетное количество возможных состояний, однако кажется вполне очевидным, что существует такое количество коров M, иметь в заказе, сверх которого, не выгодно независимо от распределения их доставки по r ближайшим ходам. В результате количество состояний, которые действительно участвуют в игре при сколько-нибудь оптимальной стратегии, оказывается конечным.
Еще одно почти очевидное утверждение, используемое ниже, состоит в следующем: давайте расширим класс допустимых стратегий, позволив мужику действовать еще и опираясь на случайные эксперименты, наподобие подбрасывания монетки. Такие стратегии в теории игр называются смешенными и позволяют не дать возможности оппоненту, достаточно хорошо изучив стиль вашей игры, сделать свою стратегию более эффективной. Кажется достаточно правдоподобным, что поскольку в описанном эксперименте нет оппонента, то заменив в любой оптимальной стратегии все результаты подбрасывания монетки на «орла», вы не ухудшите саму стратегию.
Перейду, наконец, к описанию алгоритма. Вычертим на бумаге отдельно все допустимые состояния Мужика на начало тура, когда коровы уже прибыли, и в его конце перед принятием решения с общим количеством имеющихся и заказанных коров не превышающих M. Нашей целью будет доопределить между этими состояниями направленные ребра с хитро подобранными стоимостями, чтобы для решения задачи можно было применить алгоритм поиска замкнутого потока единичной мощности (входящий в каждую вершину поток равен потоку, исходящему из нее, сумма по всем вершинам интенсивностей входящих потоков равна 1). Итак, рассмотрим какое-нибудь состояние на начало хода. Из него проведем направленные ребра к состояниям, возможным в его конце. Каждое такое ребро соответствует классу пришедшего клиента либо их полному отсутствию. Припишем этим ребрам веса, равные их вероятностям и стоимости равные величине затрат на прокорм. Теперь рассмотрим состояния, соответствующие моменту перед принятием решения о продаже и заказе. Для каждой пары (величина заказа, продать/нет) вычертим стрелку в состояние, к которому приведут эти действия. Этим стрелкам мы не будем приписывать фиксированный вес, а их стоимость положим равной величине цены заказа минус величина стоимости заказа. Для большинства практических приложений, по всей видимости, можно заказывать не более одной коровы за раз.
Сведем задачу к анализу марковских цепей. Выбору стратегии при таком подходе соответствует приписывание в каждой вершине, соответствующей состоянию на конец хода, вероятностного веса всем исходящим из нее ребрам. Найдя предельное распределение вероятностей (в невырожденных случаях все вершины достижимы и непериодичны), определим предельный вероятностный поток и по нему — мощность дохода или убытков. Стратегия будет оптимальной, если она максимизирует мощность дохода.
Поиск предельного потока и максимизацию прибыли целесообразно решать одновременно методом линейного программирования, который по средней на опытах вычислительной сложности ощутимо лучше метода прямого перебора, также применимого для решения дискретной задачи, по крайней мере, теоретически.
Автор: Sergey_Kovalenko
