Algorithms
Mathematics
Comments 62
0
Если у нас есть полные данные о спросе на каждый день, то задача решается легко.

Например, есть таблички:

«Ожидаемый спрос»
Поля:
— Дата
— ID варианта спроса
— Вероятность варианта в этот день

«Варианты спроса»
Поля:
— ID варианта спроса
— номер строки
— цена продажи
— количество продаж по данной цене

(Предполагаем, что у нас есть конечное число вариантов с ненулевой вероятностью.)

Если у нас есть полные данные (сумма вероятностей разных вариантов на конкретный день всегда равна 1), то алгоритм расчета закупок с максимальной прибыльностью достаточно простой. Проблема в прогнозе спроса. :)))

0
То есть, вот это вот решение никак не проверялось?
Возможно для вас будет новостю, но теория массового обслуживания состоит из марковских цепей чуть более чем на половину.
Если окажется, что алгоритм генерирует эргодическое распределение для времени задержки доставки коров, у меня для вас плохие новости.
Если окажется что времена задержек доставки коров получаются независимые, тоже плохие новости.
0
Хм…
Это не стратегия, и наверно даже не комбинаторика. Просто теория вероятностей.
А сыграть против…
Когда мне эту задачу пришлось решать на практике (работал аналитиком по управлению запасами), я вспоминал вузовский курс по учебнику с очень прикольными задачками.
Примерно такими:
«Ведется пристрелка орудия по цели. Вероятность попадания в
цель при первом выстреле равна 0,7, при последующих выстрелах эта ве-
роятность каждый раз увеличивается на 0,05. Какова вероятность того,
что цель будет поражена лишь третьим выстрелом?»

В мире очень много мест, где можно сыграть против. Но вы уверены, что хотите играть в такие игры? :)))
UFO landed and left these words here
0
Я не про сложность расчета. Я про саму задачу — как пример того, где работает теория вероятностей.
И лично у меня нет ни малейшего желания играть в такие игры в реальной жизни.
UFO landed and left these words here
UFO landed and left these words here
UFO landed and left these words here
+1
Парикмахерская эконом класса в условиях сильной конкуренции. Товар один — руки парикмахеров, остальные роли можете назначить сами. Похоже моя модель неплохо описывает этот жизненный случай.
-2
К сожалению, не все задачи решаются делением одной величины на другую, как обычно думают про математику обыватели. Между публикацией условий и решения прошло около недели, а простую задачу за этот срок, по мнению здешних же читателей решить никто так и не смог.
+1
Так и вы не решили. Вы разбили Т на 10 кусков, может быть больше, но пусть будет 10.
Для простоты согласимся с ординарностью, в каждый кусок не больше одного клиента (очевидная лажа) и не больше одной коровы под заказ. Тогда вариантов распределения коров 2^10, клиентов 2^10, всего 2^20 состояний, а значит 22^40 переходных вероятностей. Линейностью там и не пахнет, откуда взялось линейное программирование?
-1
Боюсь, вы пропустили то место в моей публикации, где явно было оговорено, что вероятность появления клиента в интервале разбиения, без учета принадлежности к классу, не более 1/10. А если, как в Вашем комментарии, действительно «лажа» получается. Еще смотрите на верхнюю оценку M, ее обычно просто получить, она совсем не велика даже при сравнительно малой стоимости прокорма и больших прибылях. В этом случае, состояний по порядку величины r в степени M. Про линейность я не говорил, я говорил о методах решения задачи линейного программирования.
0
Вероятность появления хотя бы одному не превосходила 0.1. тогда Вероятность что ни одного 0.9. Тогда вероятность что 1 — 0.094, 2- 0.0049, 3 — 0.000175.
Теперь о состояниях. Как вы умудряетесь просто получить верхнюю оценку М непонятно, что такое не велика, я не понимаю. Имея r раундов вы можете, опираясь на предположение об ординарности, заказать за них от 0 до r коров. Вот и получается 2^r.
Хорошо, пусть m=1. Это все еще 2^10 состояний и 2^20 переходных вероятностей.
И как вы собираетесь применять методы решения задач линейного программирования к нелинейной системе?
UFO landed and left these words here
+2
1/10, с потолка.
Рассуждения о продажах с потолка, с ошибкой.
Линейным программированием решать что? Что целевая функция, что ограничения?
Что вообще такое предельный вероятностный поток? (из какой это книги).
Что такое мощность дохода?
0
1/10 — просто достаточно малое число, квадрат которого достаточно мал, по сравнению с ним самим. Если у оптимальной стратегии выигрыш над бережливым алгоритмом меньше 1/10, то действительно дискретная модель с таким шагом будет грубовата, да и усилия по оптимизации не то, чтобы оправданы. В этом месте повествования, учитывая интерес и с практической стороны, мне не хотелось писать «эпсилон большее нуля», хотя именно эта фраза здесь и подразумевается с дальнейшим взятием придела.
0
Не стала. Попробую зайти с другой стороны, процедура поиска максимума скалярного произведения, выполняется один раз для заданных параметров задачи, или каждый раунд?
0
Так вроде бы я сразу написал, уделив этому несколько абзацев, что все возможные из разумных раунды и переходы между ними объединяются в граф. Для него ровно один раз и решается задача на экстремум.
0
Прекрасно, вот этот вот поток, это произведение предельной вероятности на вероятность перехода. И дальше вы его сворачиваете с вектром стоимости.
Предельные вероятности откуда взялись?
0
В той же статье выше написано, что выбор смешанной стратегии задается вероятностями выбора действий в каждом конкретном состоянии. По этим вероятностям можно найти предельные потоки, но можно и наоборот: если поток установлен, как, опять же, описано в статье, то отношение величин его составляющих, выходящих из фиксированной вершины, будут как раз теми самыми вероятностями, для которых поток является равновесным.
0
Как же вас тяжело читать, вы себе не представляете. Предельные вероятности в вычислении
скалярного произведения участвуют?
0
Представляю. В скалярном произведении участвует предельный поток, напрямую предельные вероятности не входят в выражение. Можно считать, что я просто заменил координаты параметризации стратегий: вместо вероятностей перехода марковской цепи использовал находящийся с ними во взаимнооднозначном соответствии предельный поток. Для математики это стандартная процедура.
0

Да Риман с ней с процедурой. Значение скалярного произведения явно или неявно зависит от предельных вероятностей?

0
Так же как выбор азимута и длины радиуса в полярных координатах зависит от декартовых координат на евклидовой плоскости. Если выбраны первые, то вторые определены. В этом случае свободный выбор полярных координат зависит от декартовых, как по-вашему?
0

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

-2
Откуда взялись эти альтернативы, кода в статье изложен способ достижения всего, что Вы отвергаете. По потоку очень легко определить, какому же распределению вероятностей он соответствует. Статья рассчитана на людей знакомых с теорией марковских процессов.
0
Вы корону то снимите, пожалуйста. Если конечно реально хотите консенсуса.
Приведите пожалуйста ссылку на статью, монографию, учебник, где написано определение потока и как по этому потоку найти вероятности переходов.
А то у вас все легко, 2^40 легко, М оценить легко, оно почему-то должно быть мало.
И что делать с вероятностью прихода 2, 3 а может быть и большего числа клиентов за один раунд вы тоже не стали объяснять.
0
Ваше решение слишком сложное.
У меня к вам предложение пойти от обратного:
Предположить, что стратегия прошлого дозаказа и наличие будущего покупателя не влияет на систему (поскольку мы ими не можем управлять, как и не можем в вашей модели сказать посетителю «придите через час»), и оптимизировать следующие вещи:
1) у меня 0 коров на складе => стратегия дозаказа, стратегия обслуживания
2) у меня 1 корова на складе => стратегия дозаказа, стратегия обслуживания
3) у меня 2 коровы на складе => стратегия дозаказа, стратегия обслуживания

Мне кажется, каждый раз эти оптимальные стратегии могут быть вычислены явным образом, исходя из входных данных (в т.ч. они могут ссылаться друг на друга, получая систему линейных уравнений).
А во-вторых, если хотите, чтобы вам реально помогли, предложите набор тестовых данных, на которых можно сравнить стратегии (хотя бы несколько случаев). Тогда можно будет проверить ваше решение, выяснить его оптимальность, и сравнить с предложенными решениями.
0

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


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

0
Представте, что вы играете в рулетку. Но ставки делаете на 10 раундов вперед.
И вот прямо сейчас, у вас уже распланировано 10 ставок вперед и вы планируете 11ю ставку, исходя из того, что выпало прямо сейчас и выпадет в ближайшие 10 раундов.
Убедите меня что тут пытаются сделать не то же самое.
-1
Всё верно, и, например, при игре в покер именно так и делается: стратегия зависит не только от текущих карт, но и от количества денег у игроков.
-1
Уважаемый минусующий, пожалуйста, просветите, что не так.
Любая стратегия опирается на планирование, а идеальная стратегия — на планирование на бесконечный срок вперёд.
Если у нас есть возможность посмотреть «то, что выпало прямо сейчас» только через 10 ставок, то подобное планирование имеет вполне реальный смысл.
Если же вы имели в виду, что можно построить более хорошую стратегию, имея возможность сразу же посмотреть то, что выпало прямо сейчас — то вы частично правы, иногда это можно сделать, иногда — стратегию улучшить таким образом нельзя.
Например, представьте, что у вас 1000 монет, и вы можете делать только ставки стоимостью 1 монету. Тогда вы вполне можете делать ставки на 10 раундов вперёд.
0
Убедите меня что тут пытаются сделать не то же самое.

Не убежу, потому что я вообще не понимаю что пытается сделать автор этого поста.

0
>оптимальная стратегия дозаказа — заказывать новую корову в момент продажи старой.
При некоторых условиях — да, так и есть. Но и контрпример легко подобрать.

> Дело в том, что зависит она не только он остатка коров на складе — но и от ожидаемых поступлений.
Тут согласен. Интуитивно кажется, что в момент за 10 минут до поставки новых коров продавец будет кричать «распродажа! скидки!» и продавать оставшихся коров всем подряд, но с другой стороны, если это будет выгодно, то мы знали это и тогда, когда заказывали ещё коров, и, значит, могли заказать коров ещё раньше, за исключением случая дозаказа при продаже… (Более того — если бы мы продали корову раньше, это было бы ещё выгоднее — ещё меньше затраты на хранение!)

Будет ли оптимальным планирование «заранее», или же оно будет зависеть от реального прибытия покупателей — мне кажется, для всех случаев в конкретно этой задаче будет оптимальным планирование «заранее».
0
При некоторых условиях — да, так и есть. Но и контрпример легко подобрать.

Будьте добры, подберите. А то у меня не получилось.




По поводу же распродаж и планирования заранее — не понял вашей мысли.

0
>При некоторых условиях — да, так и есть. Но и контрпример легко подобрать.
>Будьте добры, подберите. А то у меня не получилось.
Если покупатели приходят раз в час, а доставка коров занимает неделю, то заказ коров по расписанию будет ничуть не хуже, чем дозаказ в момент покупки. Если числа некратные (доставка — 4 часа, покупка — раз в 3 часа), то дозаказ по расписанию может быть лучше дозаказа в момент покупки.
+1
Докажите ваше утверждение, в условиях задачи. Хотя бы второй пункт.
0
Нет, я тоже имел в виду пуассонов процесс, при нём вполне можно посчитать среднее время покупки.
На суть рассуждения это не повлияет — дозаказ в момент покупки может иметь упущенную выгоду из-за наличия момента, когда коровы ещё не пришли, и лучше бы их заказать и не дожидаться очередной продажи.
0

Но зачем? Дозаказанные коровы все равно же не придут раньше

0
А дозаказ по расписанию приводит к тому, что если клиентов мало то вы терпите убытки из-за содержания, а если много то терпите убытки из-за недостачи.
А если строго — дозаказ по расписанию приводит вас к независимым, одинаково распределенным временам обслуживания. Так что вы удовлетворяете условиям работы Севастьянова, можете применять формулы Эрланга и результат у вас получится хуже.
0
>А дозаказ по расписанию приводит к тому, что если клиентов мало то вы терпите убытки из-за содержания, а если много то терпите убытки из-за недостачи.
То же самое рассуждение применимо и к дозаказу в момент покупки.
Но я всё же говорил про крайние случаи, когда оптимальное количество товаров на складе — единица.
Если у нас случай, когда много заказов и много покупок — то
а) нет существенного колебаний количества клиентов
б) выгоды от дозаказа только в момент начала очередного часа от дозаказа в момент покупки я не вижу никакой.
Возможно, я неудачно выразился, под дозаказом по расписанию я имел в виду дозаказ в определённые моменты времени, но не фиксированный по количеству.
0
Ок. В выходные, если будет время, сделаю формулы и вычисления для крайних случаев.
Давайте ещё тогда пройдёмся по условиям задачи.
Время за простой коровы — оно считается по факту наличия коровы на начало каждого конкретного часа или за фактическое время её нахождения в стойле до момента продажи? (дискретное или вещественное?) Я считал дискретным, ибо сказано «проедает корма на u рублей за единицу времени».
0
Непрерывно все. За время t корова съедает u*t. С формулами сложности. Для некоторых случаев они есть. Для некоторых можно добыть из марковских моделей. В некоторых случаях может помочь моделирование. А есть случаи когда на текущем уровне развития математики и вычислительной техники ничего нельзя сделать.
0
А что автор говорит по поводу непрерывности этой величины? Подтверждает? Я быстро просматривал, но нигде не нашёл.
Если непрерывно, то тогда формулы будут другими и крайним мой рассмотренный случай скорее всего не будет.
0
Спросите автора. В исходной постановке всё непрерывно.
И будте осторожны с экспонентой и факториалом, они коварны.
+1
Но я всё же говорил про крайние случаи, когда оптимальное количество товаров на складе — единица.

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

0
А может ли быть оптимальное сочетание коров быть «1 на складе + 1 в процессе доставки»? Тогда вы будете говорить, что дозаказывать нужно в момент предпоследней продажи? Может ли быть заказ в момент предпоследней продажи плюс K*T часов выгоднее?
0

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


Сейчас у вас 1 корова. Допустим, за 5 минут покупатели не пришли и через 5 минут у вас тоже одна корова. Что изменилось-то? Почему в одной ситуации с 1 коровой на руках вы решаете подождать, а в другой точно такой же ситуации вы решаете заказать корову?

0
Посмотрите с другой стороны: Допустим к вам пришло 2 покупателя, а у вас всего одна корова…
Распределение Пуассона не означает всюду нулевую плотность вероятности, просто вместо «1 клиент придёт в течение 10 минут» у нас есть «1 клиент придёт в течение 10 минут с вероятностью 95%», «два клиента за 10 минут с вероятностью 50%» и мы можем на эти проценты уже делать ставки.
Я ещё не добрался до выч. моделирования, поэтому могу только рассуждать устно и приблизительно.
0

Никакие вероятности за эти 5 минут не изменились. Почему через 5 минут вы решили купить корову, а в момент продажи — нет?

-1
>Никакие вероятности за эти 5 минут не изменились.
Прям уж никакие? Посмотрите сами на график, разве у него нулевая плотность в какой-либо точке?
https://ru.wikipedia.org/wiki/Распределение_Пуассона
Да, если мы выкинули решку, то вероятность в следующий раз выпадения орла та же. Но вероятность выпадения орла за эти два раза — больше вероятности выпадения орла за один раз.
0
А во-вторых, если хотите, чтобы вам реально помогли, предложите набор тестовых данных, на которых можно сравнить стратегии (хотя бы несколько случаев). Тогда можно будет проверить ваше решение, выяснить его оптимальность, и сравнить с предложенными решениями.

Да нет у него решения, одни запутанные математикообразные расуждения

Only those users with full accounts are able to leave comments., please.