Материал: ОиММПР. Практические работы 2019

Если переменные Xi , 1 i s образуют выпуклое множество, то задача (9.6) решается по схеме пп. 1–6. Каждую полученную стационарную точку задачи (9.6) проверяем на седловую точку для исходной задачи. Если мы не обнаружим решения исходной задачи при исследовании всех промежуточных задач (9.6), то такая задача решения не имеет.

Замечания.

1.Если f (x) — строго выпуклая функция, то у задачи (9.1) может быть лишь один оптимальный план.

2.Если при решении задачи (9.1) найдено несколько различных оптимальных планов xi0; i = 1; l, то допустимым решением является также любая

их выпуклая линейная комбинация:

Решение.

1. Составим матрицу вторых производных целевой функции f (x):

f (x) 2 C(2) ;

Так как все главные миноры матрицы неотрицательные, то f (x) — выпуклая функция. Ограничения задачи линейны. Следовательно, исходная задача является задачей выпуклого программирования.

2. Задачу (9.7) записываем в виде (9.1). Введем множество:

Q = fx : x1 0; x2 0; x 2 R3g;

f (x) = 3x12 + x22 + x1x2 7x3 ! min;

4x1 + x2 2x3 = 5; 2x2 + x3 4;

x 2 Q.

3. Так как ограничения задачи линейны, то условие Слейтера (9.3) проверять не нужно.

86

4. Составляем функцию Лагранжа:

F(x;l ) = 3x12 + x22 + x1x2 7x3 + l1(4x1 + x2 2x3 5) + l2(2x2 + x3 4),

x 2 Q; l 2 R2; l2 0.

Для поиска стационарных точек составляем и решаем систему урав-

>

>

>

:

Эта система решения не имеет.

5. Полученную точку fx1;l 1g проверяем на условие (9.4):

87

точка функции Лагранжа (9.2), значит, x0 = x1 — оптимальный план задачи (9.7) и f (x0) = 35.

Пример.

Найдем решение для следующей задачи:

f (x) = x12 + x22 + 2x1 2x2 ! min;

Решение.

1. Эта задача относится к задачам выпуклого программирования, исходя из условия

следовательно f (x) — выпуклая функция. Ограничения задачи линейны, поэтому условие Слейтера (9.3) не проверяем.

2.Введем множество: Q = fx : x1 0; x2 0g:

3.Составляем для задачи функцию Лагранжа:

F(x; l ) = x12 + x22 + 2x1 2x2 + l (x1 + x2 2), x 2 Q; l 0.

4. Для поиска стационарных точек составляем (9.5) и решаем систему уравнений:

8

> 2x1 + l = 2;

>

>

>

>

>

>

> 2x2 + l = 2;

<

>

> l (x1 + x2 2) = 0;

>

>

>

>

>

>

: x 2 Q; l 0:

Если l = 0, то из 1 и 2 уравнения определяем x1 = 1, x2 = 1 и получаем точку, которая не принадлежит множеству Q.

88

Если l 6= 0, то из нашей системы уравнений

8

> 2x1 + l = 2;

>

>

>

<

2x2 + l = 2;

>

>

>

>

: x1 + x2 = 2:

получаем точку: fx1 = 0;x2 = 2;l = 2g, которая также не является стационарной, так как не выполняется условие l 0. Итак, у функции Лагранжа стационарных точек нет.

5. Проверяем решение задачи на границе множества Q . Запишем из условия элементы:

8

<L1 = fx : x2 0; x1 = 0g; L2 = fx : x1 0; x2 = 0g;

: L3 = fx : x1 = x2 = 0g:

Рассматриваем задачу для границы L1. Из условий (9.9) получаем:

f (x) = x22 2x2 ! min;

x2 2; (9.10) x2 0:

Запишем функцию Лагранжа для задачи на границе L1 (9.10):

F(x;l ) = x22 2x2 + l (x2 2);

x1 0; l 0:

Cоставляем (9.5) и решаем систему уравнений:

2x2 + l = 2; l (x2 2) = 0:

Находим стационарную точку: l = 0; x2 = 1.

6. Полученную точку x1 = 0; l = 0; x2 = 1 проверяем на условие (9.4) для исходной задачи:

В полученном выражении левое неравенство в (9.11) выполняется для 8l 0. Кроме этого (x1 + 1)2 1 при x1 0 и (x2 1)2 0, правое неравенство выполняется для 8x 2 Q. Значит, точка f0;1;0g — седловая точка

функции Лагранжа задачи (9.9). Ответ: x0 = (0;1), f (x0) = 1.

89

9.3. Варианты для выполнения задания

Вариант выбирается из табл. 9.1 по номеру студента в журнале группы.