Динамическое программирование

k

T = ∑ ti

I = 1

В начале периода T на развитие предприятий выделены основные средства D. В начале каждого хозяйственного года производится финансирование всей системы предприятий, т.е. выделяется доля основных средств. Известны первоначальное состояние системы S0, характеризуемое количеством средств, уже вложенных в предприятия, и конечное состояние Sk, характеризуемое всей дополнительно вложенной суммой D. Как следует распределить по предприятиям и годам основные средства D, чтобы к концу периода T суммарный доход W от всей системы предприятий был максимальным?

Решение. Обозначим через xij сумму, выделяемую в начале i-ого года j-ому предприятию (i=1, 2, …, k; j=1, 2, …, n). Предположим, что средства на i-ом этапе распределены, т.е. выбрано определенное управление Ui, которое состоит в том, что в начале i-ого года предприятию P1 выделены средства xi1, предприятию P2 - средства xi2 и т.д. Тогда вектор Ui = (xi1, xi2, …, xin) определяет распределение средств на i-ом этапе. Совокупность выделенных средств на k шагах выразится системой векторов n-мерного векторного пространства

U1= (x11; x12; …; x1n),2= (x21; x22; …; x2n),

………………………

Uk= (xk1; xk2; …; xkn).

Суммарный доход за k лет зависит от совокупности управлений, т.е. является функцией от U1, U2, …, Uk:

= W (U1, U2, …, Uk).

Задача состоит в следующем: на каждом этапе необходимо выбрать такое управление, чтобы суммарный доход от всей системы предприятия был максимальным. Сформулированную задачу, на первый взгляд, можно решить непосредственно, объединив все этапы. Действительно, W можно рассматривать как функцию от элементов управлений на каждом этапе:

W = (x11; x12; …; x1n; x21; x22; …; x2n; xk1; xk2; …; xkn),

т.е. как функцию многих переменных. Теперь решение задачи заключается в нахождении такой совокупности значений аргументов xij, при которой функция W достигает максимального значения. Казалось бы, найдя частные производные функции по всем аргументам, приравняв их к нулю и решив систему уравнений = 0, получим значение xij, при которых функция W имеет локальный максимум.

Однако этот метод имеет существенные недостатки: во-первых, при большом количестве этапов решение полученной системы довольно громоздко; во-вторых, с его помощью можно найти критические точки только внутри области, так как метод не позволяет исследовать граничные точки; в-третьих, метод вообще неприменим, если xij - дискретные величины.