Многокритериальная задача выпуклого программирования. Теорема Куна-Таккера

Рассмотрим задачу векторного выпуклого векторного программирования в виде:

j_i(x) ® min, iÎ M, (3.53)

j_i(x)£ 0, iÎ I, (3.54)

где x = (x(1), x(2),..., x(n))^T - вектор n - мерного евклидова пространства E_n,

j _i (x) - выпуклые дифференцируемые функции, iÎ M È I.

Задача означает, что требуется:

· либо определить множество оптимальных точек при заданном предпочтении (в данной лабораторной работе по Слейтеру);

· либо определить, что множество оптимальных точек при заданном предпочтении пусто;

· либо убедиться, что множество допустимых решений, определяемых ограничениями (3.54), пусто;

Обозначим X = { xÎ E_n, j _i(x) £ 0, i Î I }.

Пусть xÎ X, через I(x) обозначим множество { iÎ I| j _i(x) = 0 }.

Определение 3.21. Будем говорить, что множество X удовлетворяет условиям регулярности R2 по Слейтеру, если существует точка zÎ X такая, что j _i (z) < 0 для всех iÎ I.

Для решения поставленной задачи воспользуемся теоремой Куна – Таккера о необходимом и достаточном условии существования оптимальной точки по Слейтеру.

Теорема Куна–Таккера 3.19

Пусть множество X удовлетворяет условию регулярности R2.

Для того, чтобы точка yÎ X была точкой оптимума по Слейтеру, необходимо и достаточно существование таких u(i), iÎ (M & I(y)), для которых справедлива система

0_n= S { u(i)´ j'_I (y) | iÎ (M & I(y)) }, (3.55)

1 = S { u(i) | iÎ (M & I(y)) }, (3.56)

u(i) ³ 0, i Î (M & I(y)), (3.57)

где 0_n - n- мерный нуль-вектор в E_n.

Чтобы убедиться в справедливости этой теоремы, достаточно вспомнить, что точка локального минимума выпуклой функции является оптимальной(теорема 3.17).В качестве иллюстрации покажем применение теоремы Куна – Таккера к решению следующей задачи

Пример. Для задачи

j₁(x)= x₁² + x₂² ® min,

j₂(x)= x₁² + (x₂ -4)² ® min,

j₃(x)= (x₁ -4)² + x₂² ® min,

j₄(x)= (x₁ -4)² + (x₂ -4)²® min.

проверить на оптимальность точку y = (2, 2)^T.

Решение.

Составим для этой задачи систему вида (3.58). Для этого, подставив в нее значения градиентов j' _i(y), получим

4u(1) + 4u(2) - 4u(3) - 4u(4) = 0,

4u(1) - 4u(2) + 4u(3) - 4u(4) = 0,

u(1) + u(2) + u(3) + u(4) = 1, (3.58)

u(1) ³ 0,

u(2) ³ 0,

u(3) ³ 0,

u(4) ³ 0.

Нетрудно видеть, что составленнаясистема разрешима и имеет следующие решения:

(0.5, 0.0, 0.0, 0.5),

(0.0, 0.5, 0.5, 0.0),

(0.25, 0.25, 0.25, 0.25).

В общем случае проверить ее разрешимость можно симплекс-методом. Воспользуемся методом искусственного базиса. Введем искусственные переменные z(j), j=1, 2, 3 и построим задачу:

F= z(1) + z(2) + z(3) ® min,

4 u(1) + 4 u(2) - 4 u(3) - 4u(4) + z(1) = 0,

4 u(1) - 4 u(2) + 4 u(3) - 4u(4) + z(2) = 0,

u(1) + u(2) + u(3) + u(4) + z(3) = 1,

u(1) ³ 0,

u(2) ³ 0, (3.59)

u(3) ³ 0,

u(4) ³ 0,

z(1) ³ 0,

z(2) ³ 0,

z(3) ³ 0.

 

Если в этой задаче F=0, т.е. z(1) =0, z(2) =0, z(3) =0, то система (3.59) разрешима, если F > 0, то система (3.59) не имеет решения.

Задание. Для задачи

j₁(x)= (x₁ - a₁)² + (x₂ - b₁)² ® min,

j₂(x)= (x₁ - a₂)² + (x₂ - b₂)² ® min,

j₃(x)= (x₁ - a₃)² + (x₂ - b₃)² ® min,

j₄(x)= (x₁ - a₄)² + (x₂ - b₄)² ® min.

 

проверить на оптимальность точки: y=(y₁, y₂)^T, z=(z₁, z₂)^T.

Варианты заданий взять в следующей таблице:

 

№. Вар.

a1

b1

a2

b2

a3

b3

a4

b4

y1

y2

z1

z2

Г л а в а 4.