ТОП 10:

Снижение размерности с помощью множителей Лагранжа



Покажем на примере задачи 1, каким образом введение множителей Лагранжа позволяет заменить исходную задачу рядом задач с меньшей размерностью вектора состояния.

В задаче 1 состояние описывалось двумя параметрами, что обусловливалось наличием двух ограничений. Для уменьшения размерности на 1 достаточно из модели (9.40)-(9.43) убрать одно из ограничений, что можно сделать, если удаляемое ограничение включить в критерий задачи с неопределенным множителем Лагранжа l. Тогда модель измененной задачи примет вид:

(9.52)

(9.53)

(9.54)

Как будет доказано ниже, задача (9.52)-(9.54) при определенных условиях эквивалентна исходной задаче (9.40)-(9.43). Так как ограничения (9.53), (9.54) не связывают между собой переменные yj, то есть они стали независимыми, то справедлива следующая цепочка равенств:

где

. (9.55)

Функции hj(xj) имеют смысл, если максимум в (9.55) достигается при конечных значениях yj, что всегда будет, когда

. (9.56)

Это условие ограничивает применение данного способа, но в рассматриваемой задаче оно, очевидно, выполняется, так как при неограниченном возрастании ресурса y рост прибыли будет замедляться.

Как видно из (9.55), вычисление функции hj(xj) при фиксированном значении заключается в нахождении максимума функции одной переменной для всех возможных значений xj, что не вызывает особых затруднений (для дифференцируемых Rj(xj,yj) максимум можно найти аналитически). При известных hj(xj), j=1,N задача (9.52)-(9.54) сводится к следующей:

(9.57)

(9.58)

(9.59)

Получили уже знакомую нам задачу распределения одного ресурса. Для решения ее методом ДП введем последовательность функций

,

где V - параметр состояния, значения которого не превосходят X. Для них справедливо рекуррентное соотношение:

fk(V) = max[hk (xk)+ fk-1(V-xk)], (9.60)

в котором f1(V)= h1(V), =V.

Вычисления по формуле (9.60) проводятся, как обычно, от f1 к fN, затем в обратном порядке - безусловная оптимизация, начиная с V=X, которая дает значения . По последним из функций hj(xj) находятся значения . Теперь следует вспомнить об условии (9.42), которое не вошло в измененную задачу. Если å =Y, то найденное решение , является оптимальным решением задачи (9.40)-(9.43). В противном случае придется продолжить расчеты.

Нетрудно увидеть, что оптимальное решение измененной задачи зависит от принятого значения множителя . Поэтому при невыполнении условия (9.42) нужно изменить значение и повторить весь расчет, начиная с вычисления функций hj(xj). В данной задаче при изменении можно воспользоваться очевидным свойством: с увеличением будет монотонно убывать å и наоборот. В более сложных ситуациях можно воспользоваться одним из методов одномерного поиска нелинейного программирования. Таким образом, равенство (9.42) может быть выполнено с любой заданной точностью.

Чтобы нагляднее представить весь расчет с использованием множителей Лагранжа, приведем его алгоритм в виде блок-схемы (рис.9.11). Как видно из алгоритма, функции fk(V) и hj(xj), участвующие в расчете, зависят от одного параметра состояния, и, следовательно, поставленная цель достигнута.

 

Рис.9.11

Теперь покажем эквивалентность задач (9.40)-(9.43) и (9.52)-(9.54), понимая под этим совпадение решений. Следуя Беллману, доказательство проведем от противного. Имея оптимальное решение измененной задачи , , предположим, что оптимальное решение исходной задачи иное, а именно, , . Тогда для критерия исходной задачи должно выполняться неравенство

. (9.61)

Так как е =Y по условию исходной задачи, а е =Y по алгоритму решения измененной задачи, то е . Вычитание одной и той же величины, умноженной на , из левой и правой частей выражения (9.61) не меняет знак неравенства:

. (9.62)

Но здесь и слева, и справа имеем выражение критерия измененной задачи, по которому оптимальным является решение , . Таким образом, неравенство (9.62), вытекающее из допущения существования разных решений, противоречит исходной посылке и потому такое допущение неверно, что доказывает совпадение решений исходной и измененной (эквивалентной) задач.

Для задачи 2 применение метода множителей Лагранжа реализуется проще. Модель измененной задачи можно записать по аналогии с вышеприведенным случаем в виде:

Для функций последовательности, определенных как

справедливо следующее рекуррентное соотношение

(9.63)

Как видно, здесь нет дополнительных функций hj и вычисления можно проводить сразу по рекуррентной формуле (9.63), задавшись предварительно значением . После нахождения решения проверяется условие (9.48) - е B и, если оно не выполняется, то необходимо изменить значение и повторить расчет. Таким способом достигается эквивалентность исходной и измененной задач и получение оптимального решения с помощью последовательности функций, зависящих только от одного параметра состояния.

В общем случае, когда вектор состояния исходной задачи имеет размерность m, можно использовать q множителей Лагранжа (q<m), что позволит снизить размерность вектора состояния измененной задачи до m-q. При этом выполнение исключенных из условий исходной задачи q ограничений может быть обеспечено управлением таким же числом множителей Лагранжа. Однако увеличение размерности вектора состояния и соответственно числа множителей Лагранжа ведет к значительно более быстрому росту трудоемкости решения измененной задачи. Поэтому проблема "проклятия размерности" остается, ограничивая применение метода ДП задачами с небольшим числом параметров состояния.

Несмотря на указанный недостаток метод динамического программирования находит широкое применение для решения многих задач исследования операций, в том числе задач распределения, замены, кратчайшего пути, упорядочения и др.







Последнее изменение этой страницы: 2016-08-12; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.235.30.155 (0.005 с.)