Основная проблема планирования

Люди доказывают, что планирование невозможно. Как доказывают? Вот так.

…приведу пример, с которого я обычно разъясняю людям мало сведущим в чем тут проблема, а проблема действительно серьезнейшая, общепризнанная как одна из самых тяжелых алгоритмически. Примитивная, обыденная задача — инвест компания или банк, портфель из 30 разных предприятий, строим решетку размером минимум двадцать точек в соответствии с потенциальной долей (от нуля до ста процентов). Сколько всего возможно портфелей? 20^30 Уже хорошо? Погодите, это вообще пока ничего. Дальше, возможная отдача по каждому предприятию допустим вектор в 10 значений, повторю — все по минимуму, не пытаемся счесть ряби на гребне океанской волны. Каков размер получаемого массива по всем предприятиям? 10^30. Таким образом чтобы посчитать оптимизационную задачку нам надо в каждой временной точке посчитать некую функцию полезности 20^30*10^30 раз. Подождите, и это еще не все. Плюс все эти вычисления должны быть пересчитаны в каждой точке пространства возможных действий, набор которых ограничен только безграничной человеческой фантазией.

Такое вот доказательство.

Человек решает задачу, как имея фиксированную сумму денег наиболее выгодно её потратить на инвестиции. Что он делает? Считает полное количество вариантов. Не ограниченное даже имеющейся у него суммой. И не завязанное на неё. Просто «можно по ноль акций каждого предприятия купить, а можно по 100%». Вот так вот.

Далее. Как предлагается искать решение такой задачи? Человеку очевидно — полным перебором всех состояний. Если его спросить (что уже проделывалось), он ответит: «любой метод будет работать так же долго». В общем, вы поняли. Нельзя найти решение, например, квадратного уравнения — перебор всех вещественных чисел и вычисление функции на них займёт бесконечное количество времени, поскольку этих чисел — бесконечное количество. Даже на фиксированном отрезке. С этого он «начинает разъяснение малосведущим».

Другой бы написал линейную целевую функцию для оптимизации, вида, например

Σ ((r_i - p_i)* n_i) ,

где суммирование идёт по всем интересующим его предприятиям, r — прогнозируемый доход с акции за интересующий его срок времени, p — цена акции, а n — неизвестная. То есть, количество покупаемых акций каждого предприятия, которое и надо найти в процессе оптимизации.

Наложил бы ограничение

Σ (p_i * n_i) ≤ S, где S — средства, которыми он располагает,

а потом бы нашёл максимум целевой функции давно всем известными средствами. Градиентным спуском, скажем. Решение заняло бы полчаса, включая поиск софта и ввод данных.

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

При этом, само собой, банк каким-то образом с инвестиционным портфелем угадывает. Хотя, казалось бы, экспериментальное, рыночное решение — тоже полный перебор  (раз уж никто не знает, как такие задачи решать). И поиск решения таким способом занял бы ещё больше времени — уже потому, что ставить эксперимент в реале дольше, чем на компе варианты перебирать. И больше ведь чем что? Чем время жизни вселенной! Но банки всё равно как-то справляются. Потому что, надо думать, при наличии Частного Собственника с небес опускается Чудесная Рука Рынка, дарующая ему Невидимую Бумажку С Ответом.

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