4. Покажите, каким образом приведенная ниже задача может быть приведена к сепарабельному виду.

Максимизировать г = х,х2 + х3 + х,х3

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

х,х2 + хг + х,х3 < 10,

5. Покажите, каким образом следующую задачу можно преобразовать в задачу сепарабельного программирования.

Минимизировать z = е2 * *2 + (х3 - 2)2

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

х, + х2 + х3 < 6, хх,х2, х3>0.

6. Покажите, как следующую задачу можно преобразовать в задачу сепарабельного программирования.

Максимизировать z = eVl + XjX3 + х4

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

хх + х2х3 + х3 < 10,

х4 не ограничена в знаке.

7. Покажите, что при реализации метода выпуклого сепарабельного программирования оптимальное решение не содержит переменной хк1 > 0, если переменная хк Х1 не достигает своей верхней границы.

8. Решите представленную ниже задачу как задачу выпуклого сепарабельного программирования.

Минимизировать z-xf + 2х2 + х]

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

х2 + х, + Хз < 4,

х,+х,<0,

х х3>0, х2 не ограничена в знаке.

9. Решите как задачу выпуклого сепарабельного программирования следующую задачу.

Минимизировать г = (х, - 2)2 + 4(х2 - б)2 при ограничениях

6х, + 3(х2 + 1)2< 12, хх, х2>0.

21.2.2. Квадратичное программирование

Задача квадратичного программирования имеет следующий вид.

Максимизировать (или минимизировать) г = СХ + XTDX

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

АХ<Ь, Х>0

X - (х х2.....xJT,

С - (Cj, с2, сь), b = (b b2, ...,bm)T,

tin J

Функция XTDX, где D - симметрическая матрица, является квадратичной формой (см. раздел А.З). Матрица D будет отрицательно определенной в задаче максимизации и положительно определенной - в задаче минимизации. Это означает, что функция z является строго выпуклой по переменным X в задаче минимизации и строго вогнутой - в задаче максимизации. Ограничения в этой задаче предполагаются линейными, что гарантирует выпуклость области допустимых решений.

Решение сформулированной задачи основано на использовании необходимых условий Куна-Таккера. Так как целевая функция z строго выпуклая (или вогнутая) и область допустимых решений задачи является выпуклым множеством, эти условия (как показано в разделе 20.2.2) также достаточны для установления наличия глобального оптимума.

Задачу квадратичного программирования рассмотрим для ситуации, когда целевая функция подлежит максимизации. Изменение формулировки задачи при минимизации целевой функции является тривиальным. Общая постановка задачи имеет следующий вид.

Обозначим через X = (Я Л2, Лт)т и U = ( цг, рУ множители Лагранжа, связанные с ограничениями АХ - b < 0 и -X < 0 соответственно. Применяя условия Куна-Таккера, получаем

Максимизировать г = СХ + XTDX

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

X>0,U>0, Vz - (Х\ UT)VG(X) = 0,

= 0, I = 1, 2,т,

UjXj = 0,j = l, 2, ...,п, АХ<Ь, -Х<0.

Отсюда имеем

VG(X) =

Vz = С + 2XTD,

Обозначим через S = b - АХ > 0 вектор дополнительных (остаточных) переменных. Тогда приведенные выше условия принимают следующий вид.

-2XTD + ХТА - UT = С, AX + S=b, UjXj = 0 = XiSi для всех i и j, X,U,X,S>0.

Так как DT = D, в результате транспонирования первой системы уравнений получим

-2DX + АТХ - U = Ст. Следовательно, необходимые условия можно записать в виде

-2D А -I 0 АО 0 1

гс>л

4°,

= 0 = XiSi для всех i и j, X, U, X, S > 0.

Все уравнения, за исключением pxj = О = ЯД, являются линейными относительно переменных X, X, U и S. Следовательно, исходная задача сводится к поиску решения системы линейных уравнений, удовлетворяющему дополнительным условиям fipc! = 0 = \St. Поскольку функция z строго вогнутая, а область допустимых решений представляет собой выпуклое множество, допустимое решение, удовлетворяющее всем этим условиям, должно быть единственным и оптимальным.

Решение рассматриваемой системы находится путем реализации этапа I двух-этапного метода (раздел 3.4.2). При этом единственным ограничением является необходимость удовлетворения условий ЯД = 0 = х. Выполнение этого условия означает, что если переменная Я( в базисном решении принимает положительное значение, то переменная S, не может быть базисной и принимать положительное значение. Аналогично переменные Ц. и х. не могут одновременно принимать положительные значения. Это обстоятельство подобно правилу ограниченного ввода в базис, которое было использовано в разделе 21.2.1.

Этап1 завершается обращением в нуль всех искусственных переменных только в том случае, если исходная задача имеет непустое множество допустимых решений.