В нашем распоряжении имеется какой-то запас дополнительных средств (ресурсов) К, который должен быть распределен между m популяциями животных П1, П2, …, Пm. Каждая из популяций Пi при вложении в нее средств (например, дополнительного корма) в размере х приносит дополнительный доход, зависящий от х, то есть φi(х). Все функции φi(х)(i=1, 2,…, m) заданы (эти функции неубывающие и, возможно, нелинейные). Спрашивается, как нужно распределить средства К между популяциями, чтобы в сумме они дали максимальный дополнительный доход?
Эта задача легко решается методом динамического программирования. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в популяцию П1, за второй – в П2 и т.д. (хотя их можно поменять местами).
Управляемая система S в данном случае – дополнительные средства (ресурсы), которые обязательно распределяются до конца. Состояние системы S перед каждым «шагом» характеризуется одним числом s– наличным запасом еще не вложенных средств. В этой задаче «шаговыми управлениями» являются средства х1, х2,…хm, выделяемые популяциям. Требуется найти оптимальное управление, то есть такую совокупность чисел х1, х2,…хm (∑xi = К), при которой суммарный доход максимален:
Перейдем к предпоследнему, (m-1)-му «шагу» (популяции). Пусть мы подошли к нему с запасом средств s (остаток к шагу m-1). Обозначим Wm-1(S) условный оптимальный выигрыш на двух последних шагах: (m-1)-м и m-м (который, как предполагается, уже оптимизирован). Если мы выделим на (m-1)-м шаге (m-1)-ой популяции средства х, то на последний шаг останется s – x. Выигрыш на двух последних «шагах» будет равен
φm-1(x)+Wm(S – x),
и нужно найти такое х, при котором этот выигрыш максимален:
Знак max означает, что меняя х от 0 до s, ищем максимальное значение выигрыша, то есть max выражения, стоящего в фигурных скобках. Этот максимум и есть условный оптимальный выигрыш за два последних шага, а найденное значение х, при котором этот максимум достигается, - условное оптимальное управление на (m-1)-м шаге.
Далее оптимизируем (m-2)-ой, (m-3)-й и т.д. шаги. Вообще, для любого i-го шага (i – ой популяции) будем находить условный оптимальный выигрыш за все шаги с этого и до конца по формуле
и соответствующее ему условное оптимальное управление xi – то значение х, при котором этот максимум достигается.
Продолжая таким образом, дойдем, наконец, до 1-ой популяции П1. Здесь нам не нужно будет варьировать значения S: мы точно знаем, что запас средств перед первым шагом равен К:
Итак, максимальный выигрыш (доход) от всех популяций найден. Теперь остается только «прочесть рекомендации». То значение х, при котором достигается максимум (W*), и есть оптимальное управление х1* на первом шаге. После того, как мы вложим эти средства в 1-ю популяцию, у нас их останется К – х1*. «Читая» рекомендацию для этого значения s, выделяем второй популяции оптимальное количество средств х2* и т.д. до конца.
Пример. Исходный запас дополнительных средств К=10 (единиц кормов). Требуется его оптимальным образом распределить между пятью популяциями (m=5). Для простоты предположим, что вкладываются только целые количества средств. Значения функции дохода φi(х) (например, в тыс. руб.) приведены в таблице.
В каждом столбце, начиная с какой-то суммы вложений, доходы перестают возрастать (реально это соответствует тому, что каждая популяция способна «потребить» лишь ограниченное количество кормов).
х
φ1(х)
φ2(х)
φ3(х)
φ4(х)
φ5(х)
0,5
0,1
0,6
0,3
1,0
1,0
0,5
1,1
0,6
1,2
1,4
1,2
1,2
1,3
1,3
2,0
1,8
1,4
1,4
1,3
2,5
2,5
1,6
1,5
1,3
2,8
2,9
1,7
1,5
1,3
3,0
3,5
1,8
1,5
1,3
3,0
3,5
1,8
1,5
1,3
3,0
3,5
1,8
1,5
1,3
3,0
3,5
1,8
1,5
1,3
Для получения ответа вначале произведем условную оптимизацию так, как это было описано выше, начиная с последнего, 5-го шага. Каждый раз, когда мы подходим к очередному шагу, имея запас средств s, мы пробуем выделить на этот шаг то или другое количество средств. Берем доход на данном шаге по таблице и складываем с уже оптимизированным доходом на всех последующих шагах до конца (учитывая, что средств у нас осталось уже меньше, как раз на такое количество средств, которое мы выделили). Находим то вложение для очередного шага, при котором эта сумма достигает максимума. Такое вложение и есть условное оптимальное управление на данном шаге, а сам максимум – условный оптимальный доход. В таблице даны результаты условной оптимизации по всем шагам.
s
i=5
i=4
i=3
i=2
i=1
x5(s)
W5(s)
x4(s)
W4(s)
x3(s)
W3(s)
x2(s)
W2(s)
x1(s)
W1(s)
1
1,0
0
1,0
1,0
1,0
1,2
1,3
1,6
1,6
1,3
1,6
2
2,1
2,1
1,3
2,3
2,4
2,4
1,3
2,5
2,9
2,9
1,3
2,6
3,4
3,5
1,3
2,7
3,6
4,1
1,3
2,8
3,7
5
4,6
1,3
2,8
3,9
5,1
1,3
2,8
4,1
5,6
2
5,6
Таблица построена так: в первом столбце даются возможные значения запаса средств s, с которыми мы подходим к данному шагу. Далее таблица разделена на пять пар столбцов, соответственно номеру шага. В первом столбце каждой пары приводится значение условного оптимального управления, во втором – условного оптимального выигрыша. Таблица заполняется слева направо, сверху вниз. Решение на пятом – последнем шаге вынужденное: выделяются все оставшиеся средства. На всех остальных шагах решение приходится оптимизировать.
В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W* за всю операцию – в данном случае он равен 5,6. В последних двух столбцах таблицы заполнена только одна строка, так как состояние системы перед началом первого шага нам в точности известно (к нему подходим с полным запасом ресурсов): s0=K=10. Оптимальные управления на всех шагах подчеркнуты.
Таким образом, мы получили окончательный вывод: надо выделить первой популяции две единицы из десяти, второй – пять единиц, третьей – две, четвертой– ни одной, пятой – одну единицу. При этом распределении доход будет максимален и равен 5,6 тыс. руб.
Чтобы было понятно, как заполняется таблица, продемонстрируем это на одном образце расчета. Пусть, например, нужно оптимизировать решение х3(7) – как поступать на третьем шаге, если мы подошли к нему с запасом средств s=7, и сколько максимум мы можем выиграть на всех оставшихся шагах, включая третий? Предположим, что все шаги после третьего (4-й, 5-й) уже оптимизированы, то есть, заполнены две первые пары столбцов таблицы. Найдем х3(7) и W3(7). Для этого составим вспомогательную таблицу.
х
7-х
φ3(х)
W4(7-х)
φ3(х)+ W4(7-х)
1,8
1,8
1,7
1,0
2,7
1,6
1,3
2,9
1,4
1,6
3,0
1,2
2,3
3,5
1,1
2,5
3,6
0,6
2,6
3,2
2,7
2,7
В первом столбце таблицы перечислены все возможные вложения (х) на третьем шаге, не превосходящие s=7. В третьем столбце – выигрыш на третьем шаге, то есть от вложения средств х в третью популяцию (заполняется по столбцу φ3(х) исходной таблицы доходов). В четвертом столбце – оптимальный выигрыш на всех оставшихся шагах (четвертом и пятом) при условии, что мы подошли к четвертому шагу с оставшимися средствами (заполняется по столбцу i=4 таблицы). В пятом столбце – сумма двух выигрышей: шагового и оптимизированного дальнейшего при данном вложении (х) на третьем шаге. Из всех выигрышей последнего столбца выбирается максимальный (в таблице он равен W3(7)=3,6, а соответствующее управление х(7)=2). Подобные алгоритмы несложно реализовать на ЭВМ.
