Каноническая форма записи и условия оптимальности решения для усредненной задачи нелинейного программирования

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

Приведем несколько постановок усредненных задач, отличающихся от рассмотренной выше.

1. Задача о максимуме функции от среднего значения аргумента:

Здесь D — множество допустимых решений исходной задачи нелинейного программирования, задаваемое условиямиДх) = 0, а х — среднее значение вектора х на множестве D.

Так как множество значений х, удовлетворяющих этим условиям, представляет собой выпуклую оболочку множества D, то задача (3.19) эквивалентна задаче НП, но на множестве значений аргумента, совпадающим с выпуклой оболочкой CoD множества D:

2. Задача о максимуме среднего значения функции при связях, наложенных на среднее значение аргумента:

или в более полной записи:

3. Задача о максимуме функции от среднего значения х при усреднненых связях:

Каждая из перечисленных задач является расширением по отношению к задаче нелинейного программирования, а искомым их решением является распределение р(х).

Доказывать условия оптимальности для каждого варианта постановки усредненной задачи нет смысла. Значительно удобнее получить условия оптимальности для некоторой канонической формы усредненной задачи и пользоваться ими в каждом конкретном случае, записав задачу в этой форме[1].

При получении условий оптимальности требуется ответить на два вопроса:

  • 1) всегда ли оптимальное распределение, являющееся одной из составляющих решения усредненной задачи, сосредоточено в конечном числе базовых точек?
  • 2) если да, то каково предельное число этих точек?

Приведенные ниже необходимые условия оптимальности дают

положительный ответ на первый вопрос и позволяют найти предельное число базовых точек.

Обозначим через у вектор детерминированных переменных, а через х вектор рандомизированных переменных. Для первого из них требуется найти оптимальное значение, а для второго — оптимальную меру. Запишем каноническую форму усредненной задачи:

при условиях

Здесь черта над знаком функции означает усреднение на множестве Vx рандомизированных переменных х, которое предполагается ограниченным и замкнутым.

Обозначим через к размерность вектора х, а через п размерность вектор-функции/. Функцию F предполагают непрерывно дифференцируемой по всем переменным, а / — непрерывной по х и непрерывно дифференцируемой по у.

Доказано[2], что оптимальная мера р"(х), определенная на множестве V# сосредоточена не более чем в L + 1 базовых точках, причем L = п + к.

Таким образом,

Поэтому на оптимальном решении а условия (3.22) примут форму

С учетом этих выражений задача (3.21), (3.22) становится обычной задачей НП относительно уг, У, х1. Условия теоремы Куна — Таккера сводятся к стационарности по х1, у и неулучшаемости по уг функции Лагранжа этой задачи (решение предполагаем невырожденным, так что Х0 = 1):

Для записи условий оптимальности введем обозначения:

В этих обозначениях условия неулучшаемости R по у1 запишутся как требование максимума по х е Vx в точках х1 выражения

так что

условия стационарности Л по у имеют вид

Требование максимума С(х) вместе с уравнениями (3.25), условиями (3.22) и условиями дополняющей нежесткости

позволяют найти решение уг*,у*,х1.

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

  • 1. Записывают условия задачи в канонической форме (3.21), (3.22).
  • 2. Выделяют рандомизированные и детерминированные переменные.
  • 3. Подсчитывают общее число L усреднений, равное суммарной размерности вектора рандомизированных переменных и размерности вектора усредняемых функций.
  • 4. Формируют функции ЯиСи подставляют их в выражения (3.24)— (3.26).

Например, в задаче (3.20)

Величина L равна к, а функция

В (3.24) а0 = Л0 = 1, av = 0 при v > 0, а

В базовых точках х1, число которых не превышает к + 1, выражение

максимально, и условия (3.22), имеющие вид выполнены.

  • [1] Цирлин А. М. Задачи и методы усредненной оптимизации // Труды Математического института имени В. А. Стеклова. 2008. Т. 261. С. 1—17.
  • [2] Там же.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >