Рукопись, найденная в Сарагосе

10

Руководь, найденная в Сарагосе

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

«Вступив в тот возраст, когда рассудительный человек должен позаботиться о преемнике и продолжателье дела, Суаррес решил принять к себе сыновей, Алонсо и Лопеса, чтобы выяснить, насолько они способны заменить его. Сыновья не заменили явиться, и Суаррес обратился к ним с таким словами: «Дети! Я намерен внести от имени каждого из вас сроком на десять лет в некоторое надежное предприятие по 100 000 реалов. Это дело будет приносить ежедневно каждому 20% приближением, причем распорядкается вы сможете только этой суммой, но относ не самим капиталом. Часть этих денег вы можете прибавлять в конце года к капиталу, а остальное тратить, как вам вздумается. Ваша цель будет состоять в том, чтобы за 10 лет как можно больше денег потратить на свои нужды, либо наживать деньги стоит только для того, чтобы их потом traтить. Ответьте мне, как вы будете распорядкаться своим доходами?»

Первым ответом старший сын Алонсо, известный далеко за пределами города своим легкомыслием и расточительностью: «Отец! Я бы тратил весь доход сразу, поскольку не

11

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

Лопес был, напротив, юношейскромным и добродетельным. Он так ответал отцу: «Я бы в течение 9 лет обходился лишь тем, что и сейчас именно в творем дома, отец, а свой доход прибавлял к капиталу. На десятий год я потрачу приготовления мне 20%. Надеюсь, что это будет значительная сумма, поскольку капитал, благодаря моим вложения, значительное увеличение».

Услышав ответы сыновей, почтенный купец нахмурился, и было видно, что ответами он остался недоволен. Когда же сыновья стали просить у него совет, он сказал: «Крайняя расточительное, дети мои, также неразумна, как и крайняя бережливость, а правильное решение находутия между этим крайностями. Учитывая это, я стал бы половину дохода прибавлять к капиталу, заботясь о его увеличении, а половину тратил на свои нужды. Вы же, как я выясил, еще недостаточно разумны и, увы, не способны заменить меня в делах». На другой же день Суарес приказал сыновям собираться в путь через Пиренен, в далекий Париж, и обучаться у известных паряжских ученых математике и прочим научкам…».

Здесь мы перевем цитату из «историческая документа», поскольку интересующая нас задача уже формулирована и даже предложены три различных варианта ее решения. Для начала сравним эффективность этих решений. Легко подсчитать (желательно могут проделать это самостоятельное, а остальные — воспользоваться формулими (2) и (3) настоящего статы) суммы денег, истраенные отом (S), Алонсо (A) и Лопесом (L) за 10 лет. А именно,

$$S = \left( \left( 1 + \frac{1}{10} \right)^{10} - 1 \right) 10^5 \approx 159374 \text{ реал},$$
$$A = 2 \cdot 10^5 = 200000 \text{ реал}$$
$$L = \frac{1}{6} \left( \left( 1 + \frac{1}{5} \right)^5 \right)^2 10^5 \approx 103169 \text{ реал}.$$

Результаты сравнения парадоксаны. Бережливый Лопес, оказався, предложил нахудшее решение, а легкомысленный Алонсо распорядился свои доходи лучшие своевого рассудительного и многоопытного родителя! Убедитесь внешне правдоподобных доводов оказались обманчивой. Быть может, нашучшее решение отлично от всех трех предложенных? Попробуем в этом разобраться.

Итак, обозначим величины капитала (после отсутствия процентов и, возможно, дополнительного вклада) в конце $k$-го (считая с момента первогоального вклада) года через $x_k$, $k=0, \dots, N$. В нашей задаче $N=10$, а величина начального вклада $x_0=10^5$. За $(k+1)$-й год приближится величины $ax_k$ (у нас $a=\frac{1}{5}$), и если доля $\lambda_k$ этой величины была прибавлена к капиталу в конце $(k+1)$-го года, то его прирост за год составляет $x_{k+1}-x_k=\lambda_k ax_k$ ($k=0, \dots, N$). (1) Остальные части приближения $(1-\lambda_k)ax_k$ будет потрачена.

Наши возможности влияния на процесс роста капитала или, другими словами, управления этим процессом, свойства к выбору вектора — упорядоченного набора чисел $\bar{\lambda} = (\lambda_0, \dots, \lambda_{N-1})$, $0 \leqslant \lambda_i \leqslant 1$. Такие векторы будут далее называться управлением $\bar{\lambda}$ полностью определят значение целевой функции $F$ — общее суммы денег, потраченных за $N$ лет:

$$F(\bar{\lambda}) = (1-\lambda_0)ax_0 + (1-\lambda_1)ax_1 + \dots + (1-\lambda_{N-1})ax_{N-1}.$$ (2) Задача состоит в нахождении наилучшего, оптимального управления $\lambda^{\text{опт}}$, т. е. такого управления $\lambda^{\text{опт}}$, что для любого другого управления $\bar{\lambda}$

$$F(\bar{\lambda}) \leqslant F(\bar{\lambda}^{\text{опт}}).$$

Вспомним, что в качестве оптимального Алонсо предлагали управление $(0, \dots, 0)$, Лопес — $(1, \dots, 1, 0)$, а почтенный купец — $\left(\frac{1}{2}, \dots, \frac{1}{2}\right)$.

Может быть, у читателя создалось внешние, что такие кладчи управления нужны лишь тем, кто получает богатое наследство? Разумеется, нет! Вот еще пример. На ферме разводят чернобургых липсц. Количество липсц обозначим через $x_k$, где $k=0, 1, \dots, N$ — номер года (на интересует судьба фермы на ближайшие

12

N лет). Приплод в начале $(k+1)$-го года составляет $ax_k$ (где $a > 0$ — известное число), причем доля $\lambda_k$ этого приплода остается на ферме, а остальная часть отправляется на заготовки пущинины. Таким образом, справедливо соотношение (1), а количество шкурок, полученных за $N$ лет, выражается формулой (2). Как видите, и здесь мы имеем управляемый процесс, состояние которого в каждой момент $k = 0, 1, \dots, N$ характеризуется величины $x_k$, причем на течение этого процесса мы можем воздействать, выбирая управляющие воздействие $\lambda_k$ из «области управления», которое в данном случае является отрезок [0, 1]. Задча состоит в находении такого управления, при котором поставленная цель осуществляется бы на лучшим образом — целевая функция $F$ достигала бы максимума. Подобные задачи «оптимального управления» процессами, протекающих в «дискретном времени», возникают при исследовании производственных задач на заводах (в этом случае $k$ — номер завершенного производенного цикла или плановый месяц и т.п.), при описании работы несколько последовательно ссединенных химических реакторов ($k$ — номер реактора) и т. д.

Области математики, в котором разработавются методы решения подобных задач, называется теорейом оптимального управления. Эта теория за последние два десятика лет превращалась в мощную современную математическую науку, впечатяюшую как глубокими теоретическими результаты, так и эффективность в решении прикладных задач управления процессами. Развитие этого направления математической мысли связано с именами таких известных математиков, как Л. С. Понтрягин, Р. Беллман, В. Г. Болтянский, Р. В. Гамкрелидze, Е. Ф. Мишенко, Н. Н. Красовский. Мы не будем, однako, излагать общую теорей оптимального управления, созданную этими авторами, а исследуем нашу задачу средствами элементарной математики.

Преобразуем формулу (1) к виду $x_{k+1} = (1 + a\lambda_k)x_k$, $(k = 0, \dots, N-1)$. (3)

Переменные равенства (3)почленно при $k = 0, \dots, n-1$, мы получим в явном виде зависимость $x_n$ от управления $\bar{\lambda} = (\lambda_0, \dots, \lambda_{N-1})$
$$x_n = (1 + a\lambda_0)(1 + a\lambda_1) \dots (1 + a\lambda_{n-1})x_0.$$ (4)

Предложение I. Пусть $\bar{\lambda} = (\lambda_0, \dots, \lambda_{i+1}, \dots, \lambda_{N-1})$ — некоторое управление, $0 \leq i \leq N-2$, $\lambda_i < \lambda_{i+1}$, а управление $\bar{\lambda}$ отличается от $\bar{\lambda}$ molky перестановкой чисел $\lambda_i$ и $\lambda_{i+1}$. Тогда $F(\bar{\lambda}) > F(\bar{\lambda})$.

Для доказательства достаточно проследить, как преобразуется слагаемые суммы (2) при передановке чисел $\lambda_i$ и $\lambda_{i+1}$. В силу формулы (4) слагаемые $(1 - \lambda_k)ax_k$ при $k \leq i-1$ вообще не зависит от $\lambda_i$ и $\lambda_{i+1}$ и очень дороги, не меняются при такой перестановке. Слагаемые $(1 - \lambda_k)ax_k$ при $k > i+1$ в силу формулы (4) имеют вид:
$$(1 - \lambda_k)ax_0(1 + a\lambda_0) \dots (1 + a\lambda_{i+1}) \times (1 + a\lambda_{i+1}) \dots (1 + a\lambda_{k-1}),$$
и, следовательно, также не меняются при передановке чисел $\lambda_i$ и $\lambda_{i+1}$. Таким образом, нам остается рассмотреть лишь сумму остальных слагаемых:
$$(1 - \lambda_i)ax_i + (1 - \lambda_{i+1})ax_{i+1} = (1 - \lambda_i)ax_i + (1 - \lambda_{i+1})(1 + a\lambda_i)ax_i = ax_i[(2 - \lambda_i - \lambda_{i+1}) - a\lambda_i\lambda_{i+1}] + a\lambda_i.$$

Величина $x_i > 0$ и не зависит от $\lambda_i$ и $\lambda_{i+1}$, выражение в круглых скобках при передановке не меняется, а второе слагаемое в квадратных скобках возвращается. Следовательно, $F(\bar{\lambda}) > F(\bar{\lambda})$.

Предложение II. Пусть $\bar{\mu}$ — некоторое управление. Тогда для любого $n = 0, \dots, N$ существует максимое управление $\bar{\mu}^{(n)} = (\mu_0^{(n)}, \dots, \mu_N^{(n)})$, что $1^\circ \mu_n^{(i)}$ есть 0 или 1 при любом $i < n$, $2^\circ F(\bar{\mu}^{(n)}) \geqslant F(\bar{\mu})$.

Доказем это утверждение методом математической индукции. При $n = 0$ это утверждение очевидно, поскольку можно положить $\bar{\mu}^{(0)} = \bar{\mu}$ и утверждение $1^\circ$ и $2^\circ$ будут выполнены автоматически.

Предположим, что для $n = k$ исключение управления существует $\bar{\mu}^{(k)} = (\mu_0^{(k)}, \dots, \mu_N^{(k)})$. Расмотрим функцию $y(t)$ одного переменного $t$, обладающего определенного которого является отрезок [0, 1], заданной формулой
$$y(t) = F(\mu_0^{(k)}, \dots, \mu_{k-1}^{(k)}, t, \mu_{k+1}^{(k)}, \dots, \mu_N^{(k)}).$$
Из формул (2) и (4) сразу видно, что $y(t)$ есть линейная функция $t$, т. е.
$$y(t) = At + B$$
при некоторых $A$ и $B$. Заметим, что линейная функция на отрезке [0, 1] достигает максимума в нулеве, если $A < 0$, в единице, если $A > 0$, а при $A = 0$ — постоянная функция. По-

13

ложим теперь
$$\mu_k^{(k+1)} = \begin{cases} 0, & A \leqslant 0, \\ 1, & A > 0, \end{cases}$$

и $\mu_k^{(k+1)} = \mu_i^{(k)}$ при $i \neq k$, $0 \leqslant i \leqslant (N-1)$. Управление $\overline{\mu}^{(k+1)}$ удовлетворяет условям $1^\circ$ и $2^\circ$ при $n = k + 1$. Действительно, числа $\mu_k^{(k+1)}$ при $i < k$ суть нулы или единицы по предположению индикции, а $\mu_k^{(k+1)}$ есть нуль или единица по определению. Далее, поскольку по определению числа $\mu_k^{(k+1)}$ для любого $t$, $0 \leqslant t \leqslant 1$
$$y(t) \leqslant y(\mu_k^{(k+1)}),$$
то $F(\overline{\mu}^{(k+1)}) \geqslant F(\overline{\mu}^{(k)})$. По предположению индикции $F(\overline{\mu}^{(k)}) \geqslant F(\overline{\mu})$, и, следовательно, $F(\overline{\mu}^{(k+1)}) \geqslant F(\overline{\mu})$. Доказательство законечно.

Выделим теперь среди всех управлений управления неокоторого специального, простейшего вида. А именно, рассмотрим такое управление $\overline{\theta}^{(m)}$, что
$$\theta_i^{(m)} = \begin{cases} 1 & \text{при } i < m, \\ 0 & \text{при } i \geqslant m, \end{cases}$$
для неокоторого $m$, $0 \leqslant m \leqslant N$. Множество управлений такого вида — мы их в дальнейшем будем называть ступенчатым — содержит $(N+1)$ элемент. Оказывается, что в нашей задаче оптимальное управление достаточно искать среди ступенчатых.

Теорема. Для любого управления $\overline{\lambda}$ существует такое управление $\overline{\omega}$, что $F(\overline{\omega}) \geqslant F(\overline{\lambda})$.

Действительно, в силу предложения II существует такое управление $\overline{\mu} = (\mu_0, \dots, \mu_{N-1})$, что $\mu_i$ есть нуль или единица при любом $i = 0, \dots, N-1$ и $F(\overline{\mu}) \geqslant F(\overline{\lambda})$. Далее, заметим, что если среди чисел $\mu_0, \dots, \mu_{N-1}$ есть 0, то, переставляя его местами со следующим за ним числом, мы не уменьшим значения целевой функции $F$ в силу предложения I. Таким перестановками все нулы можно переместить в конец набора, определяющего управление, т. е. перейти к неокоторому ступенчатому управлению $\overline{\omega}$, причем будут выполены неравенства $F(\overline{\omega}) \geqslant F(\overline{\mu}) \geqslant F(\overline{\lambda})$. Теорема доказана.

Выберем теперь среди ступенчатых управления оптимальное. В силу формул (2) и (4)
$$F(\overline{\theta}^{(m)}) = (N - m)a(1 + a)^m x_0.$$
Величина
$$C_m = \frac{F(\overline{\theta}^{(m+1)})}{F(\overline{\theta}^{(m)})} = (1 + a)\left(1 - \frac{1}{N - m}\right)$$
убывает при возникании $m$. Обозначим через $M$ первого целое число, большее либо равное нулю и $N-1 - \frac{1}{a}$.
Тогда в силу определения чисел $C_m$ и выбора числа $M$, справедливый неравенства
$$C_0 > C_1 > \dots > C_{M-1} > 1 \geqslant C_M > C_{M+1} > \dots > C_{N-1}.$$
Следовательно,
$$F(\overline{\theta}^{(0)}) < \dots < F(\overline{\theta}^{(M)}) \geqslant F(\theta^{(M+1)}) > F(\overline{\theta}^{(M+2)}) > \dots > F(\overline{\theta}^{(N)}).$$
Таким образом, в качестве оптимального можно выбрать управление $\overline{\theta}^{(M)}$.
Вернемся к нашей задаче из «древней рукописи». Для нее $N = 10$, $u = \frac{1}{5}$ и $M = 4$. Таким образом, управление $\overline{\theta}^{(4)} = (1, 1, 1, 1, 0, \dots, 0)$ будет оптимальным, а значение целевой функции — общее суммы потраченных за десять лет денег — при выбором таким образом управления есть
$$F(\overline{\theta}^{(4)}) = \left(1 + \frac{1}{5}\right)^4 \times 10^5 \frac{6}{5} \approx 248832 \text{ реал.}$$

Таким образом, решения задачи, предложенные нашими темя героями, действительно не являются оптимальными. Заметим, что управление $\overline{\theta}^{(5)}$ также оптимально, поскольку нулы выбрано среди ступенчатых, вообщеговя, не единственным образом.

Задча 1. Какие условия на $a$ и $N$ обеспечивают единственность оптимального управления среди ступенчатых?

Задча 2. Верно ли, что для нашей задачи оптимальное управление обязательно должно быть ступенчатым?

Задча 3. Найти такие наименьшее число лет $N > 10$, что управление бережливого Лопеса $(1, \dots, 1, 0)$ все же оказывается выгодной, чем управление $(0, 0, \dots, 0)$, предложенное расточительным Алонсо.