3.3 Нахождение экстремального значения функции f(X) с учетом системы ограничений задачи

3.3.1 Метод допустимых направлений Зойтендейка

F(x)= x₁²+x₂²-x₁x₂-8x₁+7x₂ (min).

3x₁ -x₂-40

x₁+3x₂-180

x_1,2 0

x⁰=[1;5].

Первый шаг осуществляется в направлении вектора-градиента, вычисленного в точке x⁰. Координаты точкиx¹вычисляются в соответствии с выражением

x ¹= x ⁰ -α⁰F(x ⁰).

Вектор-градиент:

Величина шага выбирается по двум условиям:

1. Очередная точка x ¹ должна принадлежать ОДЗП. Чтобы это условие выполнялось, должна выполняться система неравенств:

Решая систему, получим интервал .

2. Находится значение α⁰, которое максимизирует функцию F- α^0*.

Если , тоα⁰= α^0*, в этом случае очередная точка x ¹ будет лежать внутри ОДЗП и очередной шаг нужно будет делать опять в направлении вектор-градиента. Если же , то выбираетсяα⁰= α^0”, в этом случае очередная точкам x ¹ будет находиться на границе ОДЗП.

Найдем вектор-градиент в точке x ⁰:

Определим очередную точку x ¹:

Подставив х¹ в функцию цели и вычислив производную, найдем α⁰:

.

Найдем интервал . Для этого подставим координаты точкиx ¹ в ограничения:

.

Поэтому принимаем что

Так как , то точкаx ¹ лежит на границе ОДЗП. Тогда из точки x ¹ в направлении вектора-градиента двигаться нельзя, так как градиент выходит за пределы области. Нужно найти то направление, по которому нужно двигаться.

Очередное направление S^k должно удовлетворять двум условиям:

1. Очередная точка должна принадлежать ОДЗП.

2. Направление S^k выбирается так, чтобы функция цели при переходе к очередной точке увеличивалось максимальным образом.

Координаты очередной точки записываются:

x ^k+1= x ^k +α^k S ^k.

Точка x ¹ лежит на линии 3x₁-x₂=4. Найдем направление S, используя выражения

Найдем очередную точку:

Найдем α¹ .

,.

Графическая интерпретация:

Рисунок 3.3 - Графическая интерпретация метода допустимых направлений Зойтендейка

3.3.2 Метод линейных комбинаций

F(x)= x₁²+x₂²-x₁x₂-8x₁+7x₂ (min).

3x₁ -x₂-40

x₁+3x₂-180

x_1,2 0

x⁰=[1;5].

Первая итерация.

Зададимся точностью

Вычисляется вектор-градиент

Осуществляется линеаризация F(x) относительно точки x⁰ в соответствии с выражением

Решается задача ЛП

min{-11x₁+16x₂ |3x₁ -x₂4; x₁+3x₂ 18;x_1,20}.

Процедура решения задачи иллюстрируется последовательностью симплекс-таблиц.

БП	СЧ	НП
		x1	x2
x3	4	3	-1
x4	18	1	3
F	0	-11	16

БП	СЧ	НП
		x3	x2
x1	1.333	0.333	-0.333
x4	16.666	-0.333	3.333
F	14.666	3.666	12.333

Найдено оптимальное решение

,

Далее производится корректировка найденного решения в соответствии с выражением

Или

Осуществляется минимизация F(x) по параметру . Подставляяx¹ в функцию цели, получим

Так как значение в шаге не может превышать 1 по абсолютному значению, то примем

Искомая точка минимума найдена.

3.3.3 Условия теоремы Куна-Таккера

F(x)= x₁²+x₂²-x₁x₂-8x₁+7x₂ (min).

3x₁ -x₂-40

x₁+3x₂-180

x_1,2 0

x⁰=[4;5].

Прежде, чем составить функцию Лагранжа, нужно привести ограничения к нулевой правой части. Анализируем экстремум: так как в условии минимум, то будет минимум по x и максимум по λ.

Тогда ии

g₁(x)= 3x₁ -x₂-40

g₂(x)= x₁+3x₂-180

Тогда L(x, λ)= x₁²+x₂²-x₁x₂-8x₁+7x₂ + λ₁ (3x₁ -x₂-4)+ λ₂ (x₁+3x₂-18)

Найдем

-x₂+2x₁+3λ₁+λ₂ -v₁=8 x₂-2x₁ -3λ₁-λ₂ +v₁=-8

-x₁+2x₂-λ₁ +3λ₂ -v₂=-7 x₁-2x₂+λ₁ -3λ₂+v₂=7

3x₁-x₂+w₁=4 3x₁-x₂+w₁=4

x₁+3x₂+w₂=18 x₁+3x₂+w₂=18

СЛАУ с неизвестными x₁, x₂, λ₁, λ₂, v₁, v₂, w₁, w₂.

x_1,2 0; λ_1,20; v_1,20; w_1,20.

Решив эту систему с помощью симплекс-метода, мы можем найти допустимое базисное решение и то решение, которое удовлетворяет x^Tv=0 и λ^Tw=0 или x₁ v₁= x₂v₂=0

λ₁ w₁=λ₂w₂=0

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

БП	СЧ	НП
		x1	x2
v1	-8	-2	1	-3	-1
v2	7	1	-2	1	-3
w1	4	3	-1	0	0
w2	18	1	3	0	0

БП	СЧ	НП
		v1	x2
x1	4	-0.5	-0.5	1.5	0.5
v2	3	0.5	1.5	-0.5	-3.5
w1	-8	1.5	0.5	-4.5	-1.5
w2	14	0.5	3.5	-1.5	-0.5

БП	СЧ	НП
		v1	x2	w1
x1	1.333	0	-0.333	0.333	0
v2	3.888	0.333	-1.555	-0.111	-3.333
	1.777	-0.333	-0.111	-0.222	0.333
w2	16.666	0	3.333	-0.333	0

Таким образом, получили решение:

x₁ = 1.333, v₂ =3.888, λ ₁ = 1.777, w₂= 16.666.

λ₂ = v₁ = x₂ = λ ₁ = 0.

Исходя из полученного решения, определим экстремум функции:

F_min =-8.8889.