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

Рассмотрим задачу квадратичного программирования, которая состоит в нахождении минимального значения функции Z= Z(x₁, х₂, …,х_n)

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

Она является частным случаем задачи выпуклого программирования, поэтому для ее решения можно использовать необходимые и достаточные условия Куна-Таккера для установления наличия решения. Функция Лагранжа для задачи квадратичного программирования записывается так:

, где - множители Лагранжа,

Теорема Куна-Таккера в аналитической форме может быть представлена следующими выражениями:

Соотношения (3) и (6) определяют условия дополняющей нежесткости.

Для решения данной системы можно использовать следующий прием. Неравенства (1) и (4) преобразуют в равенства, вводя соответственно две группы дополнительных переменных n_j, j=1÷ n и w_i, i= 1÷ m. При этом n_j ≥ 0 и w_i ≥ 0. В результате от системы 1-6 переходим к системе 7-12.

Таким образом, система (7) и (10) содержит (m+n) линейных уравнений с условием неотрицательности переменных (8) и (11) и условием дополняющей нежесткости (9) и (12).

Для решения такой вспомогательной задачи (7 + 10) можно использовать симплексный метод. Для нахождения исходного опорного (допустимого базисного) решения применим метод искусственного базиса (М-метод), введя искусственные переменные у_k ≥0, k =1÷ (m+n), k ≤ (m+n).

Целевая функция М - вспомогательной задачи имеет вид:

Если в результате решения М-вспомогательной задачи min F(y) = 0 и все искусственные переменные у_k принимают нулевые значения, кроме того, выполняются условия дополняющей нежесткости, то опорное решение вспомогательной задачи определяет оптимальное решение задачи квадратичного программирования.

Если условие нежесткости не выполняется, то надо перейти к новому опорному решению, включив в базис переменную с нулевой оценкой.

Если min F(y) > 0, то задача квадратичного программирования не имеет решения. Если хотя бы одна из искусственных переменных не равна нулю, то система основной задачи не имеет решения.

Пример 25

min Z = (x₁ – 5)² + (x₂ -10)²

Решение.

Преобразуем целевую функцию и ограничения.

Min Z =

х₁+ х₂ – 11 ≤ 0

4х₁ – х₂ – 4 ≤ 0

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

.

Находим частные производные и составляем условия Куна-Таккера (1-6).

Посредством введения дополнительных переменных преобразуем неравенства в равенства и составим систему линейных уравнений для дальнейшего решения.

Вводим искусственные переменные в первое и второе уравнения, т.к. в них нет базисных переменных.

Все переменные неотрицательные. Условия дополняющей нежесткости: х₁n₁=0; х₂n₂=0; l₁w₁=0; l₂w₂=0.

Умножим целевую функцию на (-1) и запишем исходное опорное решение в первую симплексную таблицу.

maxZ = -My₁ - My₂

Таблица 9

Симплексная таблица 1

№1

Сj

-M

-M

Ci

П БП

ai0

x1

x2

l1

l2

n1

n2

w1

w2

y1

y2

СО

-M

y1

-1

10:4=2,5*

-M

y2

-1

-1

-

w1

-

w2

-1

-

Dj

-30M

-2M

-2M

-2M

-3M

M

M

*

Таблица 10

Симплексная таблица 2

№2

Сj

-M

-M

Ci

П БП

ai0

x1

x2

l1

l2

n1

n2

w1

w2

y1

y2

СО

l2

5/2

1/2

1/4

-1/4

1/4

-

-M

y2

22,5

1/2

5/4

-1/4

-1

1/4

22,5:2==11,25

w1

11 *

w2

-1

-

Dj

-22,5M

-1/2M

-2M

-5/4M

1/4M

M

3/4M

*

Таблица 11

Симплексная таблица 3

№3

Сj

-M

-M

Ci

П БП

ai0

x1

x2

l1

l2

n1

n2

w1

w2

y1

y2

СО

l2

5/2

1/2

1/4

-1/4

1/4

5/2:1/4=10

-M

y2

1/2

-3/2

5/4

-1/4

-1

-2

1/4

1/2:5/4=2/5 *

x2

-

w2

-

Dj

-1/2M

3/2M

-5/4M

1/4M

M

2M

3/4M

*

Таблица 12

Симплексная таблица 4

№4

Сj

-M

-M

Ci

П БП

ai0

x1

x2

l1

l2

n1

n2

w1

w2

y1

y2

СО

l2

2,4

4/5

-1/5

1/5

2/5

1/5

-1/5

2,4:4/5=3*

l1

2/5

-6/5

-1/5

-4/5

-8/5

1/5

4/5

-

x2

11:1=11

w2

15:5=3

Dj

M

M

*

В четвертой симплексной таблице получено оптимальное решение вспомогательной задачи: minZ = 0, искусственные переменные у не входят в базис и все оценки D_j неотрицательные. Однако не выполняется условие дополняющей нежесткости l₂w₂=0, а именно l₂ и w₂ имеют ненулевые значения. Поэтому введем в базис переменную х₁, т.к. х₁ является свободной переменной и имеет нулевую оценку (альтернативное решение).

Таблица 13

Симплексная таблица 5

№5

Сj

-M

-M

Ci

П БП

ai0

x1

x2

l1

l2

n1

n2

w1

w2

y1

y2

x1

5/4

-1/4

1/4

1/2

1/4

-1/4

l1

3/2

-4/5

-1/2

-1

1/2

1/2

x2

-5/4

1/4

-1/4

1/2

-1/4

1/4

w2

-25/4

5/4

-5/4

-3/2

-5/4

5/4

Dj

M

M

 

В пятой симплексной таблице выполняются все необходимые условия.

- является седловой точкой функции Лагранжа. Следовательно, - оптимальное решение исходной задачи. Min Z = 8.

Замечание. Решение з адачи квадратичного программирования можно выполнить методом Ньютона на персональном компьюторе, использовуя приложение MS Excel «Поиск решения».

Индивидуальные задания 12

Решить квадратичным симплекс-методом, найдя минимум целевой функции, если задача имеет следующий вид:

Коэффициенты целевой функции и системы ограничений берутся из таблицы 8 индивидуального задания 11 в соответствии с номером варианта.

 

Контрольные вопросы и задания

1. Какая функция называется выпуклой?

2. Какая функция называется гладкой?

3. Какая функция называется квадратичной?

4. Какая функция имеет локальный максимум, а какая абсолютный максимум?

5. В чем разница между локальным и абсолютным максимумом?

6. Какие методы поиска Вы знаете?

7. Сформулируйте алгоритм метода последовательного изменения координат и запишите в виде схемы.

8. Сформулируйте алгоритм метода наискорейшего подъема (спуска) и запишите в виде схемы.

9. В чем отличие метода наискорейшего подъема от метода наискорейшего спуска?

10. Какие градиентные методы Вы знаете?

11. В чем отличие метода локального случайног поиска от метода нелокального случайног поиска?

12. В чем отличие метода штрафных функций при решении задачи выпуклого программирования и задачи линейного программирования?

13. Какой вид линий уровня задач квадратичного программирования Вы знаете?

14. Всегда ли задача линейного программирования и задача квадратичного программирования имеют решение?

 

ТЕСТОВЫЕ ЗАДАНИЯ