Пример 20.2.5

Рассмотрим задачу при ограничении

минимизировать z = х,2 + xl + xl

4х +xl +2х,-14 = 0.

Функция Лагранжа имеет вид

L(X,\) = xf +х21+х1

-Х(4дг, + х2 + 2х, -14).

Отсюда получаем необходимые условия экстремума в виде системы

= 2х,-4Х = 0,

= 2х2 - 2Ъ:2 = 0,

-= 2*3

2Х = 0,

- = -(4х, + xl + 2л% -14) = 0, дХ v 2 3 >

решениями которой являются векторы

(Х , А0), = (2, 2,1,1), (Х0,Л0)2 = (2,-2, 1, 1), (Х0,А0)3 = (2,8,0, 1,4, 1,4). Используя достаточные условия, вычислим элементы матрицы

0 4 2х2 2Л 4 2 0 0 2х2 0 2-2Х 0 \2 0 0

Так как /и = 1 и и = 3, то для того, чтобы стационарная точка была точкой минимума, знак последних 3-1 = 2 угловых миноров должен определяться знаком множителя (-1) = -1. Таким образом, в точке (X , Л0)1 = (2, 2, 1, 1) имеем

0 4 4 4 2 0 4 0 0

-32 < 0

0 4 4 2

4 2 0 0

4 0 0 0

2 0 0 2

= -64<0.

Вточке(Х0Д0)2 = (2, -2, 1, 1)

0 4 4 2 0 -4 0 0

= -32<0

0 4-42

4 2 0 0

-4 0 0 0

2 0 0 2

= -64<0.

Наконец, в точке (Х0, А0)3 = (2,8, 0, 1,4, 1,4)

0 4 0 4 2 0 0 0 -0,8

= 12,8 > 0 и

0 4 0 2

4 2 0 0

О 0 -0,8 О

2 0 0 2

= 32>0.

Отсюда следует, что (ХД и (Х )2 - точки минимума. Тот факт, что в точке (Х )3 не удовлетворяются достаточные условия максимума или минимума, не означает, что эта точка не является экстремальной. Это следствие того, что используемые условия являются лишь достаточными.

Для иллюстрации схемы проверки достаточных условий экстремума, которая использует корни полинома, рассмотрим матрицу

0 4 2х2 2

4 2-й 0 0

2х2 0 2-2X-U 0

к2 0 0 2-й,

В точке (Х , А0), = (2, 2, 1,1) имеем

Д = V- 26/+16 = 0,

откуда получаем ju= 2 и =8/9. Так как все ju> 0, то (Х0), = (2, 2, 1) - точка минимума. В точке (Х0, Л0)2 = (2, -2, 1,1)

Д = 9 - 26 + 16 = 0,

что совпадает с рассмотренным выше случаем. Следовательно, (Х0)2 = (2,-2, 1) является точкой минимума. Наконец, в точке (Х , Л0)3 = (2,8, 0, 1,4, 1,4)

Д = 5 -6 -8 = 0,

откуда получаем ju=2 и =-0,8, что свидетельствует о том, что точка (Х ), = (2,8, 0, 1,4) не является экстремальной.

УПРАЖНЕНИЯ 20.2.3

1. Методом Якоби и методом множителей Лагранжа решите следующую задачу линейного программирования.

Максимизировать /(X) = 5х, + Зх2

при ограничениях

g,(X) = х, + 2х2 + х3 - 6 = О, g2(X) = Зх, + х2 + х4 - 9 = 0,

1* 2 3> 4 -

2. Найдите оптимальное решение следующей задачи.

Минимизировать /( X) = х2 + 2х2 + 1 Ох2

gl(X) = x,+x2+x3-5 = 0, £2(Х) = лг, +5дг2 + х3-7 = 0.

Пусть g,(X) = 0,01 и g2(X) = 0,02. Найдите величину соответствующего изменения оптимального значения функции /(X).

3. Решите упражнение 20.2.2.6 методом множителей Лагранжа и проверьте, что полученные значения множителей Лагранжа совпадают со значениями коэффициентов чувствительности, полученными ранее при решении этого упражнения.

20.2.2. Ограничения в виде неравенств

В данном разделе показано, как метод множителей Лагранжа можно обобщить на случай задачи с ограничениями в виде неравенств. Основную часть раздела составляет вывод условий Куна-Таккера, которые играют важную роль в нелинейном программировании.

Обобщенный метод множителей Лагранжа. Пусть дана задача, в которой требуется

максимизировать г = /(X)

при ограничениях

£(Х)<0, j = 1,2.....т.

Если в рассматриваемой задаче имеются условия неотрицательности переменных X > 0, то предполагается, что они включены в указанные т ограничений.

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

Шаг 1. Решается задача без учета ограничений

максимизировать 2=/(Х).

Если полученное оптимальное решение удовлетворяет всем ограничениям задачи, вычисления заканчиваются, так как все ограничения являются избыточными. Иначе следует положить k = 1 и перейти к шагу 2.

Шаг 2. Активизируются любые k ограничений задачи (т.е. преобразовываются в равенства), и оптимизируется функция /(X) при наличии k ограничений методом множителей Лагранжа. Если оптимальное решение этой задачи является допустимым по отношению к остальным ограничениям исходной задачи, вычисления заканчиваются: полученная точка является локальным оптимумом2. Иначе нужно сделать активными другие k ограничений исходной задачи и повторить данный шаг. Если все подмножества, состоящие из k активных ограничений, не приводят к допустимому решению, следует перейти к шагу 3.

Шаг 3. Если k = m, вычисления прекращаются: задача не имеет допустимых решений. Иначе необходимо положить k - k + 1 и перейти к шагу 2.

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

Локальный оптимум определяется из множества оптимумов, полученных в результате оптимизации целевой функции f(X.) при учете всех комбинаций из k ограничений-равенств, k = 1, 2, т.