Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

3.2. Динамическое программирование и задачи с сепарабельной целевой функцией. Основное функциональное уравнение

Цель, преследуемая здесь, состоит в изучении особенностей метода динамического программирования и соответствующих вычислительных схем, приводящих к отысканию X*, z*. Этим оправданы упрощающие предположения, вводимые на разных этапах исследования в исходную общую задачу: найти


при gi(X)≤bi (i = 1,..., m), ∀xj ≥ 0 (j = 1,..., n).

Предположим сначала, что в интересующей нас задаче присутствует только одно линейное ограничение, а сама она формулируется следующим образом: найти


∀xj≥0 - целые числа, ∀aj>0 (j = 1,...,n).

Вид функций fj(xj) известен, искомый абсолютный максимум z обозначается как


Пусть из совокупности xj (j = 1,....,n) выбрана и зафиксирована величина хn. Если в этой ситуации найти максимум z по остальным переменным х1, х2, ..., xn-1, то окажется, что полученное решение будет зависеть от выбранного хn. Действительно, вследствие сепарабельности z справедливо равенство


которое подтверждает предыдущее высказывание (слагаемое fn можно вынести за знак max, поскольку оно связано только с хn). При любом постоянном целом значении хп^0 переменные x1, х2, ..., хn-1 должны ) удовлетворять неравенству


вытекающему из исходного ограничения, а также требованиям не отрицательности и целочисленности. Это влечет за собой зависимость от хn и второго слагаемого выражения

maxx1, x2,....,xn-1 z; таким образом вводится функция


Если указанные операции проведены и Ψn-1(bn-1) найдена, то можно утверждать, что искомая величина x* = maxx1, x2,....,xn z есть

(3.1)

где хn может принимать значения 0, 1,..., [bn/an] (равенство хn = 1 + [bn/an] недопустимо, так как приводит к нарушению ограничения


при ∀xj≥0, ∀aj>0).

Здесь важно заметить, что знание Ψn-1(bn-1) сводит задачу поиска z* к одномерной задаче оптимизации.

Имея в виду определение Ψn-1(bn-1), потребуем найти


при


∀xj ≥ 0 (целое), ∀aj > 0 (j = 1,...,n - 1).

Очевидно, это требование полностью совпадает с исходной постановкой задачи (различие лишь в числе переменных xj). Следовательно, отделив хn-1 и повторив все предыдущие рассуждения, приходим к выводу:

(3.2)

По аналогии с первым случаем здесь хn-1 может принимать значения 0, 1, ..., [bn-1/an-1], а функция Ψn-2 определяется как


Если известна Ψn-2, можно найти Ψn-1, используя соотношение (3.2) и решая одномерную оптимизационную задачу подобно тому, как это делалось бы применительно к равенству (3.1). Ясно, что рассмотренный процесс может быть продолжен с целью выразить Ψn-2(bn-2) через Ψn-3(bn-3), Ψn-3 - через Ψn-4 и далее до тех пор, пока не будет найдена функция Ψ1 (b1) = maxx1 f1 (x1) при x1 ∈ = {0, 1,...., [b1/a1], b1 = b2-a2x2. Таким образом, исходная задача с n переменными распадается на ряд однотипных задач с одной переменной, а процесс решения становится пошаговым.

Теперь можно дать следующие рекомендации по отысканию z*:

- составляется последовательность функций



в которой Ψ1 = maxx1 f2(x1) определяется непосредственно, а остальные функции - с помощью рекуррентного соотношения


-отыскивается z* = maxx1, x2,.....,xn z в виде Ψn(bn.

Соотношение

(3.3)

представляет собой основное функциональное уравнение метода динамического программирования (уравнение Веллмана) в представленной здесь задаче с сепарабельной целевой функцией.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"