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


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

Глава вторая. Общая методология нелинейного программирования. Гладко-выпуклые структуры

2.1. Особенности нелинейных задач. Классические условия экстремума

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

- наличие только абсолютного (глобального) экстремума целевой функции, что устраняет необходимость дополнительных проверок результата решения;

- выпуклость области определения задачи и возможность выбирать значения xj среди всех действительных неотрицательных чисел, что позволяет формировать условия существования экстремальных точек Х° или X*;

- гладкость функций f(X), gi (X), облегчающую применение аппарата классической математики для поиска оптимальных решений и для разработки новых подходов к задачам математического программирования.

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

Проблема отыскания условного экстремума скалярной функции многих переменных была изучена еще Лагранжем, предложившим так называемый метод множителей применительно к задаче с ограничениями-равенствами gi (X) = bi, t = 1,....,m. Представляя большой самостоятельный интерес, этот метод позволил получить в более позднее время ряд обобщений, которые привели к разработке алгоритмов решения задач с неклассическими условиями (в первую очередь - задач выпуклого квадратичного программирования).

Изучение метода множителей Лагранжа удобно провести на следующем примере: дана целевая функция z = = f(x1, х2) и единственное ограничение g(x1, х2) = b, наложенное на рассматриваемые x1, х2 (требования не отрицательности и целочисленности x1, х2 отсутствуют); f(х1, х2) и g(x1, х2) принадлежат по крайней мере второму классу гладкости, а для g(x1, x2) = b верна теорема существования неявных функций; требуется получить необходимые условия, которым должна удовлетворять точка локального экстремума z в задаче: найти x1, x2→max{z = f (х1, х2)} при g(x1, x2) = b.

В этой ситуации с помощью равенства g(x1, x2) = b можно представить х2 как x2 = φ(x1) и прийти к выражению z = f[х1, φ(x1)] = h(x1). Необходимость учета ограничения g(x1, x2) = b приводит к тому, что из всех точек плоскости х1, х2 интерес представляют лишь те, которые лежат на линии, определяемой уравнением x2=φ(x1) (рис. 2.1). Если в какой-либо из этих точек z достигает локального экстремума, то и h(x1) достигает экстремума в некоторой точке x°1 являющейся первой координатой Х°. Экстремум h(x1) - локальный, но он не является условным, поскольку способ построения функции h(x1) предусматривает учет исходного ограничения и никаких

дополнительных требований к х1 предъявлять не нужно, Следовательно, величина х°1 может быть найдена из уравнения [dh(x1)/dx1]x01 = 0.

Имея в виду равенства h(x1) = f[x1, φ]; dh/dx1 = df/dx1+df/dφ×dφ/dx1, dφ/dx1 = dg/dx1(dg/dx1)-1, получаем


или [df/dx1-λdg/dx1) = 0, где X - новое обозначение df/dx2/dg/dх2 (оно допустимо, если dg/dx2 = 0), это дает df/dx2-λdg /dх2 = 0.

Рис. 2.1
Рис. 2.1

Искомые необходимые условия существования Х° представляются теперь в виде уравнений

(df/dх1 - λdg/dx1) = 0, (df/dх2 - λdg/dx2) = 0,
g(X*) - b = 0, (2.1)

совместное решение которых относительно x1, х2, λ по-

зволит указать все точки Х°.

Главное удобство найденной формы записи состоит в том, что система (2.1) может быть получена более коротким и чисто формальным путем. Для этого достаточно составить выражение вида f(x1, х2) + λ[b - g(x1, х2)] = Φ(x1, х2, λ), а затем найти и приравнять

нулю частные производные ∂Φ/∂x1, ∂Φ/∂x2, ∂Φ/∂λ, считая x1, х2, λ, независимыми переменными. Функция Φ(x1, х2, λ) называется функцией Лагранжа, множитель X - множителем Лагранжа. Ниже приведен пример применения метода.

Пример: найти длину сторон ирямоугальннка с максимальней площадью S, вписанного в круг х21+x22≤r2.

Решение: если x1B и х - координаты вершины рассматриваемого прямоугольника, то целевая функция S есть 4x1Bx2B; ограничение, которому должны удовлетворять переменные x и х, представляет собой уравнение окружности х22 = r2; dg/dx2 = 2x2B≠0; функция Лагранжа в данном случае имеет вид Φ(x, x2B, λ) = 4x1Bx2B + λ[r222]; приравнивание нулю ее производных дает

∂Φ/∂x1B=4x2B-2λx1B=0
∂Φ/∂x2B=4x1B-2λx2B=0
∂Φ/∂λ=r2-x22B-x21B=0

решая совместно эти три уравнения, получаем х° = r/√2 , х° = = r/√2,λ° = 2 (прямоугольник с S = Smax должен быть квадратом); полезно отметить, что решение задачи представлено в виде набора оптимальных значений x°1B, х°2B, λ°.

Выше был изучен частный вариант классической задачи математического программирования, для которого n = 2, m = 1. Существует обобщение метода множителей на случай произвольного числа переменных n и ограничений-равенств m (m<n). Здесь функция Лагранжа есть


символами X и Λ обозначены векторы (x1, х2, ...,хn) и (λ1, λ2,...,λm). Необходимые условия локального экстремума представляются как

(2.2)

Таким образом, для отыскания точек Х° приходится решать систему m+n уравнений вида (2.2), причем необязательно, чтобы любое допустимое решение системы (2.2) доставляло относительный условный экстремум функции f(X), но каждая точка, в которой такой экстремум достигается, должна удовлетворять условиям (2.2).

Преимущество рассмотренного метода в том, что можно не учитывать взаимную зависимость переменных; недостатком является необходимость решения громоздких уравнений (2.2), что далеко не всегда просто. Разработанный применительно к классической постановке задачи этот метод, как выяснилось, допускает обобщение на случай ограничений-неравенств вида gi(X)≤bi, а также ∀xj≥0, что позволяет использовать его модификации в решениях неклассических задач.

Прежде всего полезно выяснить, какую роль играют множители λ0i (или λ*i) в решениях, получаемых из

(2.2). Иногда возникает вопрос: не лучше ли как-то разумно изменить ограничения и получить за счет этого заметный выигрыш в величине z*, чем довольствоваться тем значением z*, которое следует из решения задачи с исходными фиксированными ограничениями? Подобная ситуация часто встречается при варьировании характеристик систем с целью отыскания компромиссных сочетаний их полезных свойств.

Пусть найдена совокупность величин х*1, х*2, ... ,х*n, λ*1, λ*2, ...., λ*m, доставляющих целевой функции z = f(X) абсолютный экстремум z* при определенных условиях задачи (предполагается, что использован метод множителей Лагранжа). В общем случае x*j (j = 1,....,n) и λ*i(i = 1,...,m) зависят от значений bi (правые части строк-ограничений). Следовательно, и величина z* должна зависеть от bi (i = 1,...,m). Рассмотрим выражение

(2.3)

допуская существование входящих в него частных производных в окрестности точки В = (b1, b2,..., bm). Составим и обозначим через δ*ik аналогичную сумму


так что


или

(2.4)

Если теперь сложить почленно (2.3) и (2.4) и провести очевидные преобразования, то в полученном соотношении


разность в квадратных скобках равна нулю (как производная функции Лагранжа в экстремальной точке). Обращаясь к выражению δ*ik и учитывая, что gi(x*1, x*2, ..., x*n) = bi, приходим к выводу: b*ik = 0 при i ≠ k. Таким образом, dz*/dbi = λ*i, т. е. каждый множитель λ*i(i = 1,...,m) определяет "реакцию" значения z* на изменение соответствующего параметра bi. По величине λ*i можно судить о том, какое из ограничений задачи лучше всего изменить, чтобы получить максимальное приращение |z*|.

Обратимся теперь к некоторым обобщениям метода множителей.

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





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


Диски от INNOBI.RU




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