2015-03-22
690
Статические задачи распределения ресурсов возникают при одноразовом распределении ограниченных ресурсов X (капитальные вложения, сырье, оборудование, фонды и т.д.) между несколькими объектами i=1, 2,..., n (объединениями, предприятиями, проектами и т.д.). Эффективность использования ресурсов по объектам gi(хi) различна и для каждого объекта зависит только от объема выделенных ресурсов xi. Необходимо таким образом распределить ресурсы между объектами, чтобы суммарная эффективность их использования была максимальной.
При изучении линейного программирования мы решали подобные задачи при линейной целевой функции и линейных ограничениях. Ряд задач распределения ресурсов (например, при аналитическом задании непрерывных целевых функций) может быть решен методами нелинейного программирования. Динамическое программирование позволяет решать статические задачи распределения ресурсов практически для любого класса целевых функций, в том числе и для целочисленных, разрывных, недифференцируемых.
|
|
|
При решении статической задачи распределения ресурсов методом динамического программирования за этап (шаг) принимается выделение ресурсов дополнительно одному объекту.
Решение задачи начинается с последнего шага – то есть с предположения, что у нас остался один объект для инвестирования (для вложения прочих распределяемых ресурсов). При этом находятся условно-оптимальное управление Ut (xt1,xt2, …, xti, …, xtn) и значение критерия при выделении определенного количества ресурсов этому объекту Wt(S,Ut).
Обозначим значение критерия (условно-оптимального выигрыша) при распределении X ресурсов по k объектам Wk(X). Так как за этап (шаг) принимается выделение ресурсов дополнительно одному объекту, то Wk(X)=Wt(S,Ut). Тогда на первом этапе решения задачи – выделение средств одному предприятию (T=k=1) получим:
(7.7)
На втором этапе определяем условно-оптимальное распределение ресурсов при их выделении на два объекта. При общем количестве ресурсов X второму объекту выделяется x2, а первому, следовательно, (X – x2).
Тогда
(7.8)
Рассуждая аналогично, получим основное функциональное уравнение динамического программирования для данной задачи.
(7.9)
Пользуясь основным функциональным уравнением, постепенно находят условно-оптимальные значения хk вплоть до подключения всех объектов (k = 1,2,..., n).
Соответствующее значение xn, максимизирующее Wn(X), дает безусловно оптимальное управление. Далее, возвращаясь к (n-1)-му этапу и зная хn, определяем оптимальное значение хn-1 и так далее.
