Структура решения и условия оптимальности усредненных задач

В качестве задачи А рассмотрим задачу нелинейного программирования, в которой для простоты ограничения имеют форму равенств:

Д.

где х g Ш^п; /₀ — скалярная функция, полунепрерывная сверху и ограниченная на V_x;f— вектор-функция размерности т < п; множество V_x замкнуто и ограничено. Сопоставим задаче (3.8) задачу вида

Решение x (t) ищется в классе измеримых функций.

Задача (3.9) является расширением для (3.8), так как из множества ее допустимых решений можно выделить подмножество функций, постоянных для почти всех t е [0, т], и каждому вектору х₀ е V_x в задаче (3.8) сопоставить x (t) =х₀.

Каждой функции x (t) можно поставить в соответствие распределение Р (х) ее значений, определяющееся временем, в течение которого функция пребывает в сколь угодно малой окрестности каждого из принимаемых ею значений. Так, линейной функции, меняющейся за время Т от нуля до единицы, соответствует распределение, равное единице на отрезке [0, 1] и равное нулю за его пределами. Функции, постоянной на [О, Т] и равной х₀, соответствует Р (х) = 8(х — х₀) и т. д. Переход от усреднения по времени к усреднению по множеству значений х позволяет переписать задачу (3.9) в форме.

Задача (3.10) представляет собой расширение для задачи (3.8). Ее обозначают как НП. Оптимальному решению задачи (3.10) Р*(х) соответствует сколь угодно много функций х*(0 в задаче (3.8), для каждой из которых Р (х) = Р*(х). Связано это с тем, что Р*(х) зависит от того, какую долю времени функция х*(0 изменяется в окрестности некоторого значения х°, но совершенно не зависит от того, когда она мало отлична от х°, в начале, в конце или в середине отрезка [0, т]. Исключение составляет случай, когда Р*(х) = 5(хх°). В этом случае функция х*(0 = х° постоянна и единственна.

Справедливо следующее утверждение.

Утверждение. 1. Оптимальное решение Р*(х) задачи НП имеет вид где

2. Если Р*(х) — искомое решение, то найдется такой ненулевой вектор множителей Лагранжа А, = (А₀, …, А_т) (А₀равно нулю или единице), что в точках x^v функция

достигает абсолютного максимума по х е V_x.

Значения x^v называют базовыми значениями х. Если оптимальное решение задачи НП реализуется во времени, то функция х (0 скачкообразно изменяется между базовыми значениями, принимая v-e из них в течение доли y_v от общего интервала времени Т. При этом порядок, в котором решение принимает то или иное из базовых значений, роли не играет.

Таким образом, условия оптимальности усредненного расширения НП задачи нелинейного программирования имеют форму «принципа максимума Лагранжа». При этом функция Лагранжа соответствует исходной неусредненной задаче.

Справедлива следующая теорема.

Теорема 3.1. Необходимые условия оптимальности в форме требования максимума функции Лагранжа справедливы для тех задач НП, для которых усредненное расширение эквивалентно, т. е. значение усредненной задачи совпадает со значением исходной.

И обратно, расширение (3.9) эквивалентно задаче (3.8) тогда, когда расширение Лагранжа для этой задачи эквивалентно.

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

Поясним, с чем это связано. Пусть на базовом решении x^v векторфункция / равна c^v, тогда можно утверждать, что значение функции/₀ на этом решении больше или равно ее значению на любом допустимом х, для которого Дх) = c^v. Так что в базовых точках x^v значение/₀ равно значению функции достижимости /₀4c^v). Действительно, если бы максимум /о при условии, что Дх) = c^v, достигался в другой точке, то и среднее значение /₀ не было бы максимально возможным. Таким образом усредненная задача становится задачей о максимуме среднего значения функции достижимости /₀* © при условии, что среднее значение с равно нулю, т. е. о построении выпуклой оболочки функции достижимости задачи НП в нуле. Неудивительно, что число базовых решений зависит только от размерности т вектора с. В соответствии с теоремой Каратеодори их число не превышает т + 1.

В свою очередь, задача о построении выпуклой оболочки функции достижимости в нуле.

эквивалентна задаче.

Цирлин А. М. Методы усредненной оптимизации и их приложения.

В той и другой задаче выполнены условия (3.12).

Как у всякой задачи нелинейного программирования, необходимые условия оптимальности решения состоят в том, что найдется ненулевой вектор множителей Лагранжа, для которого на оптимальном решении задачи (3.14), (3.12) ее функция Лагранжа локалъно-неулучшаема по переменным y_v.

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

в точках x_v была максимальна, а значит, одинакова.

Усреднение в задаче НП может производиться не по всем, а по части переменных. Разобьем переменные в задаче (3.8) на две группы — детерминированные х и рандомизированные и. Усреднение проводится.

-U

только по и. Задача НП имеет форму.

При этом.

Функции fpj = 1, 2, …, т, непрерывны по и и непрерывно дифференцируемы по х.

Условия оптимальности задачи (3.15) имеют следующую форму.

1. Оптимальное распределение рандомизированных переменных имеет вид.^[1]

Здесь 8x — вариация, допустимая no условиям x e V_x.

Условия оптимальности для задачи с усреднением по части переменных вытекают из того, что при любом значении х она является усредненной задачей по и, а при любом распределении Р (п) она является задачей нелинейного программирования по х.

• [1] Если (х*, Р" '(п)) — искомое решение, то найдется такой ненулевой вектор X = (А, 0, …, Хт), что образованная с его помощью функция т Лагранжа R- ^ jfj (x, u) локалъно-неулучшаема по детермированным j=о переменным и достигает максимума на множестве Vu для каждогоиз базовых значений uv: