Усложненная задача

Выше рассматривались задачи, в которых метод ДП позволял переходить от исходной задачи с N переменными к N одномерным задачам. Однако могут быть и более сложные случаи. Покажем это на примере задачи распределения ассигнований в некоторой крупной корпорации.

Корпорация включает N предприятий, производящих продукцию с номенклатурой m_j каждое (j = ). Прибыль, приносимая i -й продукцией j -го предприятия, определяется по известной зависимости , где x_ij - объем выделенных ассигнований. Задача состоит в оптимальном распределении ассигнований в размере A между предприятиями и видами продукции при условии, что предприятию может быть выделено на все виды продукции не более B_j средств.

Критерием оптимальности здесь является суммарная прибыль корпорации. Прибыль j -го предприятия

. (9.29)

Тогда модель задачи запишется в виде:

(9.30)

(9.31)

(9.32)

(9.33)

Ограничения (9.32) связывают переменные, относящиеся к одному предприятию. Поэтому в качестве шага берем выделение ассигнований одному предприятию, и задача становится N -шаговой. При этом состояние определяется только величиной ассигнований a (a Ј A), распределяемых между рассматриваемыми предприятиями. Ассигнования B_j не могут быть параметрами состояния, так как их значения на последующих шагах не зависят от решения на текущем шаге. Таким образом, функции последовательности будут зависеть от одного параметра состояния:

(9.34)

и представлять собой максимальную прибыль k предприятий при суммарных ассигнованиях в пределах a. Рассуждения на основе принципа оптимальности приводят к следующему рекуррентному соотношению:

(9.35)

Существенное отличие этого соотношения от рассмотренных в предыдущих разделах состоит в том, что правая часть зависит более чем от одной переменной (в данном случае от m _k переменных) и поэтому придется искать условный максимум функции многих переменных. В результате решение задачи значительно усложняется.

Облегчить решение можно с помощью декомпозиции задачи подобно тому, как было сделано в примере на применение множителей Лагранжа (гл.3). Согласно такому подходу сначала найдем параметрические оптимальные решения для каждого предприятия в отдельности, а затем рассмотрим их совместно.

На уровне предприятия имеем такую модель:

Очевидно, что данная задача может решаться также методом ДП. Она представима как m_j -шаговая с одним параметром состояния b_j (b_j Ј B_j). Используя представление (9.29), введем последовательность функций

,

которая подчиняется рекуррентному соотношению

(9.36)

выводимому из принципа оптимальности. Первая функция этой последовательности вычисляется непосредственно:

(9.37)

Для каждого предприятия по формулам (9.37) и (9.36) находится последовательность функций F_v^j (b_j). Зная F ^j_mj (b_j) – максимальную прибыль j -го предприятия от всех видов продукции, рекуррентное соотношение (9.35) можно представить в виде

(9.38)

для которого

(9.39)

Расчет проводим в следующем порядке. Сначала выполним вычисления по формулам (9.38) и (9.39). Имея результаты условной оптимизации (например, в виде таблиц), переходим к этапу безусловной оптимизации на верхнем уровне (на уровне корпорации). По исходному состоянию a = A входим в таблицу функции f_N (a) и находим максимальную прибыль от всех N предприятий и оптимальный объем ассигнований , выделяемый предприятию N. В результате состояние изменяется с A на . С этим значением параметра состояния входим в таблицу функции f_{N -1}(a) и извлекаем , снова пересчитываем состояние и продолжаем движение по таблицам f_k вплоть до получения . После этого проводится безусловная оптимизация на нижнем уровне. При этом каждое предприятие рассматривается независимо от других. Для примера возьмем j -е предприятие. По найденному выше значению из таблицы функции F ^j_mj (b_j) берем прибыль j -го предприятия при оптимальном распределении ассигнований и оптимальные ассигнования на продукцию m _j. По новому состоянию входим в таблицу функции и находим

Точно так же последовательно проходим по остальным таблицам функций , в результате чего определяются все x^*_ij. Повторив аналогичную процедуру для всех предприятий, получим оптимальное решение исходной задачи.

Как видно из формул (9.36)-(9.39), на каждом шаге условной оптимизации как верхнего, так и нижнего уровня, отыскивался максимум функции одной переменной. Такое упрощение решения явилось следствием декомпозиции исходной задачи.