Я думаю, эта задача очень близка к задачам теории оптимального управления. А именно — задача поиска оптимального программного управления. Если рассмотреть эту задачу в непрерывном времени, а также исключить для простоты займы в банке, то ее можно выразить следующим образом. Пусть состояние системы выражается вектором x[i] = {x1, x2, x3}, где:
x1 — количество фабрик кредитов
x2 — количество танков (юнитов)
x3 — количество кредитов в кассе
Тогда имеем следующие уравнения:
dx1/dt = u1 — скорость покупки новых фабрик кредитов. Эта величина задается регулятором, ее требуется найти по условию задачи
dx2/dt = u2 — скорость покупки новых танков. Аналогично, величина задается регулятором, ее требуется найти
dx3/dt = k1*x1 — k2*x2 — k3*u1 — k4*u2, где:
k1 — скорость производства кредитов фабриками
k2 — стоимость содержания танка за единицу времени
k3 — стоимость фабрик
k4 — стоимость танков
По условию задачи требуется минимизировать затраты, поэтому эффективность управления можно выразить с помощью интеграла. Для начала запишем затраты в каждый момент времени:
s = k2*x2 + k3*u1 + k4*u2
Общие затраты будут интегралом от этой функции:
I = integral from 0 to t1 of s * dt.
Далее, на управление и переменные состояния накладываются ограничения:
x3 >= 0 — баланс должен быть положительным;
u1 >= 0 — продажа фабрик запрещена;
u2 >= 0 — продажа танков запрещена.
В такой формулировке задача о поиске оптимального программного управления приводится на первых страницах учебников по теории оптимального управления.
Диф. уравнения, описывающие систему, являются, к счастью, линейными, поэтому ТОУ дает относительно легкие способы решения такой задачи. Разобравшись с решением задачи в непрерывном времени, можно будет перейти к решению в дискретном времени, хотя я думаю, оно будет сложнее.
Замечу, что в исходной формулировке в непрерывном времени решение задачи можно получить из эвристических соображений. Во-первых, танки требуют расходов на содержание. Поэтому, для минимизации затрат, нет смысла держать танки. Лучше купить их все в самый последний момент.
С танками разобрались. Получается, что до самого конца функционирования системы необходимо работать только на кредиты. Количество кредитов в кассе к концу работы должно равняться стоимости всех приобретаемых танков. Запишем все это в виде уравнений:
x2(t) = 0 при t<T, x2(T)=N — количество танков к концу работы
где T — время конца работы.
u2(t) = 0 при t<T, u2(T) = N*delta(t-T) — дельта-функция Дирака.
lim(t->T) x3(t) = k4*N — после покупки танков нет смысла оставлять деньги в кассе, поэтому количество денег в кассе к концу работы должно быть равно стоимости всех приобретаемых танков.
Остается решить вопрос с покупкой фабрик кредитов. Очевидно, фабрики есть смысл строить только до тех пор, пока они окупаются. Поскольку стоимость фабрик равна k3, а их производительность равна k1, то приравняем и получим:
k1*to = k3, где to — время окупаемости фабрик. Отсюда:
to = k3/k1.
В каких количествах надо строить фабрики? Если мы хотим максимизировать количество танков N — то нам следует максимизировать количество кредитов к концу работы. Следовательно, фабрики нужно строить по максимуму до тех пор, пока они окупаются. По максимуму — это значит, что весь начальный капитал и всю текущую прибыль необходимо вкладывать в фабрики, и перестать это делать в момент T-to. Во время T-to идет чистое накопление, а до этого времени деньги равны нулю. Следовательно:
lim(x3->0) = 0 — весь начальный капитал полностью пускаем на фабрики
x3(t)=0 при 0<t<T-to
x3(t)=k1*x1o*t при to<=t<T
где x1o — количество фабрик к моменту начала фазы накопления.
В каждый момент прибыль, приносимая фабриками, будет равна k1*x1(t). Вся эта прибыль до начала фазы накопления будет инвестироваться в покупку новых фабрик. Следовательно, имеем уравнение:
k1*x1 = k3*dx1/dt
Это простейшее диф. уравнение первого порядка, его решением является экспонента. Следовательно, количество фабрик во время фазы постройки будет расти экспоненциально, и таким же образом будет расти скорость покупки новых фабрик.
Но это я рассмотрел случай максимизации N при заданном T. по исходному условию задачи у нас заданы как T, так и N. Хоть это и менее интересный случай, желание заказчика — закон! Рассмотрим и его.
Поскольку затраты на постройку танков при заданном N минимизировать уже некуда, то из других затрат остаются только затраты на постройку фабрик. Их можно минимизировать исходя из того, чтобы иметь минимально возможное количество фабрик для накопления необходимого количества кредитов. Когда лучше покупать фабрики? Очевидно, в начале игры, так как чем дольше существуют фабрики — тем больше они дают прибыли. Поэтому и здесь все функционирование системы разобьется на 3 этапа: фаза постройки, фаза накопления и финальный аккорд по покупке танков. Количество денег в кассе в конце также будет равно стоимости приобретаемых танков. В свою очередь, в фазе накопления сумма в кассе будет линейно расти начиная от нуля в момент начала фазы накопления. Несложно составить уравнения, аналогичные приведенным выше, и рассчитать моменты перехода между фазами.
Средний