Eng | Rus | Ukr
Исследование операций
16.06.2009

<< prev | ^up^ | next >>

5.5. КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ

К задачам квадратичного программирования относят специальный класс задач НП, для которых целевая функция - квадратичная и вогнутая (или выпуклая), а все ограничения линейны.

Применив к этой задаче теорему Куна-Таккера, получим условия для оптимального решения в виде системы линейных уравнений, решить которые можно симплекс-методом.

В матричном виде эта задача записывается так:

максимизировать

           (5.5.1)

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

                                      (5.5.2)

где  - симметричная, отрицательно определенная матрица,

Заметим, что если - отрицательно определенная матрица, то квадратичная форма  вогнута (выпукла вверх). Следовательно, задача (5.5.1), (5.5.2) является задачей вогнутого программирования.

Приведем примеры квадратичных функций:

           

Будем предполагать, что - строго вогнута. Применив к задаче (5.5.1) - (5.5.2) теорему Куна-Таккера, получим необходимые и достаточные условия оптимальности в виде теоремы [18; 23].

Теорема 5.14. Вектор  является оптимальным решением задачи квадратичного программирования тогда и только тогда, когда существуют такие -мерные вектора  и -мерный вектор , что выполняются следующие условия:

       

Заметим, что условия 1), 2) образовывают относительно переменных  систему  уравнений с  неизвестными.

Доказательство. Составим функцию Лагранжа для задачи (5.5.1):

                (5.5.3)

Заметим, что

                        (5.5.4)

                                (5.5.5)

Применив теорему Куна-Таккера к функции (5.5.3) и воспользовавшись выражениями (5.5.4), (5.5.5), получим:

     

причем, если

     

причем, если

       Введем два вспомогательных вектора:  . Причем выберем , если  и , если . Аналогично выберем ,

если  и , если .

       Прибавив вектор  к условию а) и вычтя  из б), получаем равенства

                                                    (5.5.6)

Сравнив компоненты векторов  и , а также  и , получим два условия дополняющей нежесткости:

 Теорема доказана.

Из условий 3), 4) следует, что по меньшей мере  переменных из и  переменных среди  обращаются в  нуль.

Как уже отмечалась, система (5.5.6) состоит из  уравнений с  неизвестными. Таким образом, если  существует оптимальное решение задачи (5.5.1), то оно должно быть одним из базисных решений (5.5.6). Поскольку для нахождения допустимого базисного решения можно применить симплекс-метод Данцига, то этот метод (как и другие методы ЛП) пригоден для решения задач квадратичного программирования.

Перепишем (5.5.6) в виде

                                 (5.5.7)

Для нахождения начального базиса системы (5.5.7) применим метод искусственных переменных. Введем искусственные переменные  и . Приходим к  следующей системе:

                          (5.5.8)

При этом знаки перед компонентами векторов  выбираем одинаковыми со знаками соответствующих компонентов свободных членов -  и .

Составив псевдоцелевую функцию выводим из базиса искусственные переменные  и вводим . При этом следует учитывать условия дополняющей нежесткости

Если удается вывести из базиса все искусственные переменные и при этом удовлетворяются условия 3), 4) теоремы 5.14, то найденное базисное решение есть оптимальной.

Пример 5.6. Решить следующую задачу

максимизировать                 (1)

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

                                         (2)

Поскольку      

               

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

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

 Применив теорему Куна-Таккера, получим следующие условия для оптимального решения:

                                        (3)

и условия дополняющей нежесткости

                          (4)

Введя в систему (3) свободные переменные  получим следующую систему:

                                           (5)

и условия дополняющей нежесткости

                             (6)

Второе ограничение в условиях (2) выполняется как строгое равенство, поэтому нет ограничения на знак переменной . Тем не менее поскольку симплекс-метод позволяет находить лишь неотрицательные базисные решения, то сделаем замену переменных: . Запишем систему (5) в эквивалентном виде

                                         (7)

Необходимо найти ДБР системы (7), удовлетворяющее всем условиям (6). Для этого применим метод искусственных переменных. Введем искусственные переменные  в первое, второе и четвертое ограничения. В результате получим следующую задачу ЛП:

минимизировать                                      (8)

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

                                     (9)

Решаем задачу (8), (9) симплекс-методом при дополнительном ограничении (6) на выбор базиса.

Результаты последовательных итераций приведен в табл. 5.1-5.5. После четвертой итерации получаем оптимальное решение, удовлетворяющее условиям дополняющей нежесткости:

                 

                Таблица 5.1

 

0

0

0

0

0

0

0

0

0

M

M

M

 

Bx

0

20

2

5

0

0

0

0

0

1

0

0

0

M

8

2

-1

0

0

0

0

0

0

1

0

0

M

32

8

0

2

2

-2

-1

0

0

0

1

0

M

120

0

30

5

-1

1

0

-1

0

0

0

1

 

D

160M

10M

29M

7M

M

-M

-M

-M

0

0

0

0

Таблица 5.2

 

0

0

0

0

0

0

0

0

0

M

M

 

Bx

0

0

2

0

-5/6

1/6

-1/6

0

1/6

1

0

0

M

12

2

0

1/6

-1/30

1/30

0

-1/30

0

1

0

M

32

8

0

2

2

-2

-1

0

0

0

1

0

4

0

1

1/16

-1/30

1/30

0

-1/30

0

0

0

 

D

44M

10M

0

-M

-

0

0

0

Таблица 5.3

 

0

0

0

0

0

0

0

0

0

M

M

 

Bx

0

0

1

0

-5/12

1/2

-1/2

0

1/12

1/2

0

0

M

12

0

0

1

-1/5

1/5

0

-1/5

-1

1

0

M

32

0

0

16/3

4/3

-4/3

-1

-2/3

-4

0

1

0

4

0

1

1/6

-1/30

1/30

0

-1/30

0

0

0

 

D

44M

0

0

19M/3

17M/5

-17M/5

-M

-13M/15

-5M

0

0

 
 
 
Таблица 5.4

 

0

0

0

0

0

0

0

0

0

M

 

Bx

0

5/2

1

0

0

3/16

-3/16

-5/64

1/32

3/16

0

M

6

0

0

0

-9/20

9/20

3/16

-3/40

-1/4

1

0

6

0

0

1

1/4

-1/4

-3/16

-1/8

-3/4

0

0

3

0

1

0

-3/40

3/40

1/32

-1/80

1/9

0

 

D

6M

0

0

0

-9M/20

9M/20

3M/16

-3M/40

M/4

0

 
Таблица 5.5

 

0

0

0

0

0

0

0

0

0

 

Bx

0

5

1

0

0

0

0

0

0

1/12

0

40/3

0

0

0

-1

1

5/12

1/6

-5/9

0

28/3

0

0

1

0

0

1/12

-1/6

-8/9

0

2

0

1

0

0

0

0

0

0

 

D

0

0

0

0

0

0

0

0

0

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004