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

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

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

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

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

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

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

Для решения данной системы можно использовать следующий прием. Неравенства (1) и (4) преобразуют в равенства, вводя соответственно две группы дополнительных переменных nj, j=1÷ n и wi , i= 1÷ m. При этом nj ≥ 0 и wi ≥ 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 = (x1 – 5)2 + (x2 -10)2

Решение.

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

Min Z =

х1+ х2 – 11 ≤ 0

4х1 – х2 – 4 ≤ 0

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

.

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

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

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

Все переменные неотрицательные. Условия дополняющей нежесткости: х1n1=0; х2n2=0; l1w1=0; l2w2=0.

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

maxZ = -My1 - My2

Таблица 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, искусственные переменные у не входят в базис и все оценки Dj неотрицательные. Однако не выполняется условие дополняющей нежесткости l2w2=0, а именно l2 и w2 имеют ненулевые значения. Поэтому введем в базис переменную х1, т.к. х1 является свободной переменной и имеет нулевую оценку (альтернативное решение).

Таблица 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. Всегда ли задача линейного программирования и задача квадратичного программирования имеют решение?

 

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