КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД

Постановка задачи нелинейного программирования.

Найти вектор x=(x₁...,xn), что минимизирует (максимизирует) функцию

F(x)= F(x₁...,xn) (18.1)

и удовлетворяет систему ограничений

Gi(x1...,xn) Ri 0, i=1...,m (18.2)

где символ Ri заменяет один из знаков £, =, ³.

Если хотя бы одна из функций F, Gi(i=1...,m) является нелинейной, то указанная постановка определяет задачу нелинейного программирования (ЗНЛП).

Совокупность точек (векторов) x, которые удовлетворяют (18.2), называется допустимой областью (множеством) и отражается через D.

Произвольная точка D зовется допустимым решением (точкой, планом, вектором).

Функция F(x) соотношения (18.1) называется целевой функцией.

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

Найти вектор x=(x₁...,xn), что минимизирует целевую функцию

F(x)= F(x₁...,xn) (18.3)

и удовлетворяет систему ограничений

G_i(x₁...,xn)£0, i=1...,m (18.4)

x_j³0, j=1...,n (18.5)

где функции F, Gi (i=1...,m) — выпуклые.

Таким образом, для задачи выпуклого программирования (ЗОП) целевая функция (18.3) — выпуклая, ограничение (18.4)–(18.5) определяют выпуклое допустимое множество.

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

Найти вектор x, что минимизирует целевую функцию

F(x)= x D xТ + c xТ(18.6)

и удовлетворяет систему ограничений

А xТ £ bТ, x ³ 0 (18.7)

где c=(c₁...,cn), x=(x₁...,xn), D=||d_kl||, k,l=1...n, A=||a_ij||, i=1...,m, j=1...,n, b=(b₁...,bm), матрица D симметричная и неотъемлемо определена.

Таким образом, для задачи выпуклого квадратичного программирования (ЗОКП) целевая функция (18.6) — выпуклая квадратичная, ограничение (18.7) — линейные и определяют выпуклое многогранное допустимое множество.

Заметим, что для случая n=2, m=1 ЗОКП имеет вид:

d₁₁ x₁₂ + d₂₂ x₂₂ + 2 d₁₂ x₁ x₂ + c₁ x₁ + c₂ x₂ ® min

a₁₁ x₁ + a₁₂ x₂ £ a₁₀, x_j ³ 0, j=1,2

к тому же D=||d_kl||, k,l=1,2, d₁₂= d₂₁.

Основные утверждения.

Определение. Множество W зовется выпуклым, если для произвольных точек x,yÎW, и tÎ[0,1] выполняется tx+(1–t)yÎW.

Определение. Функция H(x), xÎWÌEn, где W — выпуклое множество, зовется выпуклой, если для произвольных точек x,yÎW и tÎ[0,1] выполняется неравенство H(tx+(1–t)y)£tH(x)+(1–t)H(y).

Теорема. Множество {x:H(x)£0}, где функция H(x) — выпуклая, является выпуклым.

Теорема.Пересечение выпуклых множеств является выпуклым множеством.

Теорема.Квадратичная функция F(x)=xDxТ+cxТвыпуклая, если матрица D — неотъемлемо определена.

Теорема. Матрица D — неотъемлемо определена, если все ее диагональные миноры неотъемлемые:

det(D(k))³0, D(k)=||dij||, і,j=1...k.

Теорема Куна-Таккера.

Пусть допустимая область D={xÎEn:Gi(x)£0,i=1...,m,x³0} задачи выпуклого программирования (18.3)–(18.5) удовлетворяет условие Слейтера: существует xÎD такое, что для всех i=1...,m G_i(x)<0, то есть множество D имеет внутренние точки.

Тогда для того, чтобы вектор x*был оптимальным решением задачи выпуклого программирования, необходимо и достаточно, чтобы существовал вектор u*³0 такой, что пар (x*,u*) является точкой седла функции Лагранжа:

L(x,u)= F(x)+(u1G1(x) +...+ umGm(x))

x=(x1...,xn)³0, u=(u1...,um)³0.

Говорят, что точка (x*,u*) является точкой седла функции L(x,u), если для всех x³0, u³0 имеют место неравенства

L(x*,u) £ L(x*,u*) £ L(x,u*).

Теорема Куна-Таккера.

Для непрерывно дифференцированных функций F(x), Gi(x), i=1...,m, теорема Куна - Таккера может быть сформулированна так.

Вектор x*является оптимальным решением задачи выпуклого программирования (18.3)–(18.5) тогда и только тогда, когда существует вектор u*³0 такой, что для пары (x*,u*) выполняются условия:

ÑxL(x*,u*)³0 ÑxL(x*,u*)(x*) Т=0, j=1...,n

ÑuL(x*,u*)£0 ÑuL(x*,u*)(u*) Т=0, i=1...,m.

Для задачи (18.6)–(18.7) выпуклое квадратичное программирование последние соотношения приобретают виду

c+2xD+uA ³0 (18. 8)

(c+2xD+uA)xТ=0 (18. 9)

xAТ–b £0 (18.10)

(xAТ–b)uТ=0 (18.11)

x ³ 0, u ³ 0.

Вспомогательная ЗЛП для ЗВКП.

Если ввести векторы y=(y₁...,yn)³0 та v=(v₁...,vm)³0, то соотношение (18.8)–(18.11) будут иметь вид:

c + 2 x D + u А – в = 0 (18.12)

x АО – b + v = 0 (18.13)

в xТ = 0, v uТ = 0 (18.14)

x ³ 0, u ³ 0, в ³ 0, v ³ 0.

Заметим, что для случая n=2, m=1 будем иметь

2 d₁₁ x₁ + 2 d₁₂ x₂ + a₁₁ u – y₁ = – c₁

2 d₁₂ x₁ + 2 d₂₂ x₂ + a₁₂ u – y₂ = – c₂

a₁₁ x₁ + a₁₂ x₂ + v = a₁₀

x₁ y₁ = 0, x₂ y₂ = y₂, u v = 0

x₁, x₂, u, y₁, y₂, v ³ 0.

Система (18.12)–(18.13) состоит из n+m линейных уравнений относительно 2(m+n) неизвестных x_j, y_j (j=1...,n), u_i, v_i (i=1...,m).

Кроме того, как следует из условий (18.14), должно быть:

если x_j > 0, то y_j = 0 (18.15)

если y_j > 0, то x_j = 0 (18.16)

если u_i > 0, то v_i = 0 (18.17)

если v_i > 0, то u_i = 0. (18.18)

Следовательно, искомым решением системы (18.12)–(18.13) может быть произвольное неотъемлемое базисное ее решение, но такой, что переменные x_j и y_j (а также u_i и v_i) с одинаковыми индексами не могут быть в то же время базисными. Для отыскивания такого решения можно применить любой из известных методов ЛП, в частности, метод искусственного базиса. С этой целью запишем систему (18.12)–(18.13) в виде

2 x D + u А – в = – c (18.19)

x АО + v = b. (18.20)

Не ограничивая всеобщности, будем считать, что правые части этой системы неотъемлемые: –c³0, b³0 (поскольку, в другом случае соответствующие уравнения, их правую и левую часть, достаточно умножить на –1). Согласно метода искусственного базиса в каждое уравнение системы (18.19)–(18.20), которое не содержит базисной переменной, вводим искусственную переменную. Поскольку переменные v_i (i=1...,m) можно считать базисными, то искусственные переменные z=(z1...,zn)³0 вводим только в уравнение (18.19) и рассматриваем вспомогательную КЗЛП

z iТ ® min (18.21)

2 x D + u А – в + z = – c (18.22)

x AТ+v = b (18.23)

x ³ 0, u ³ 0, в ³ 0, v ³ 0, z ³ 0 (18.24)

где i=(1,1...,1) — n-мерный единичный вектор.

Квадратичный симплекс-метод.

Задача (18.21)–(18.24) решается симплекс-методом.

Если найденный ДБР этой задачи удовлетворяет условиям дополняющей нежесткости (18.15)–(18.18), то он определяет оптимальное решение исходной ЗВКП. Иначе нужно перейти к новому ДБР. При этом в базисные включается новая переменная с нулевой оценкой.

Симплекс-метод с условиями (18.15)–(18.18) для решения вспомогательной КЗЛП (18.21)–(18.24), построенной на основе задачи выпуклого квадратичного программирования (18.6)–(18.7), и называют квадратичным симплекс-методом (алгоритм обычного симплекс-метода, а также все связанные с ним определения и утверждения приведены в методических указаниях к лабораторной работе №2).

Если в оптимальном решении вспомогательной КЗЛП (18.21)–(18.24) все искусственные переменные zj (j=1...,n) принимают нулевые значения, то, отбрасывая их, получим ДБР системы (18.19)–(18.20). Та его часть, которая отвечает переменным начальной задачи выпуклого квадратичного программирования (18.6)–(18.7), и будет ее оптимальным решением.

Если же в оптимальном решении вспомогательной КЗЛП (18.21)–(18.24) значение хотя бы одной из искусственных переменных отличное от нуля, то система (18.19)–(18.20) решений не имеет, а, следовательно, множество седловых точек функции Лагранжа начальной задачи выпуклого квадратичного программирования пустое.

Программное обеспечение.

Обучающий модуль, с помощью которого задача выпуклого квадратичного программирования Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Геометрическая интерпретация задачи нелинейного программирования осуществляется модулем, который вызывается из того же самого раздела.

Задание.

Решить квадратичным симплекс-методом задачи выпуклого квадратичного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.

Во всех задачах выполняются условия: x₁ ³ 0, x₂ ³ 0.

 

1)	x12 + x22 –2 x1 – 4 x2 ® min	2)	–2 x12 – 3 x22 + 4 x1 x2 + 12 x2 ® max
	2 x1 + 3 x2 £ 6;		3 x1 + 4 x2 £ 12;

 

3)	2 x12 + x22 – x1 x2 – x1 ® min	4)	x12 + 3 x22 – x1 – 2 x2 ®min
	x1 + 2 x2 £ 1;		x1 + 4 x2 £ 7;

 

5)	–2x12 –3x22+16x1+24 x2 ®max	6)	x12 + x22 – 3 x1 – 8 x2 ® min
	2 x1 + x2 £ 4;		x1 +2 x2 £ 4;

 

7)	–x12 – x22 + x1 + 2 x2 ® max	8)	–x12 – x22 + x1 x2 + 5 x1 + 2 x2 ® max
	x1 + 2 x2 £ 16;		2 x1 +3 x2 £ 15.

 

Ответы:

1) x* = (0.69; 1.54). 2) x* = (1.23; 2.07). 3) x* = (0.29; 0.14). 4) x* = (0.5; 0.33).

5) x* = (0.57; 2.86). 6) x* = (0.4; 1.8). 7) x* = (0.5; 1). 8) x* = (3.63; 2.58).

Лабораторная работа 19.