Метод решения задач квадратичного программирования

 

Задачей квадратичного программирования называют задачу НЛП, в которой находиться экстремум суммы линейной и квадратичных форм при ограничениях типа линейных неравенств и неотрицательности переменных. Эта задача имеет вид:

(5.34)

(5.35)

Здесь R – отношение вида

Методика решения задачи квадратичного программирования заключается в следующем:

1. Функция f( ) проверяется на выпуклость или на вогнутость в зависимости от постановки задачи на максимум или на минимум.

2. Записывается функция Лагранжа

3. Вычисляются частные производные и

4. Записываются необходимые условия существования седловой точки в

соответствии с типом ограничений (табл. 5.2.). Например, для задачи на максимум и ограничениях типа условия Куна-Таккера ≤0, ≥0, xj=0, , i=0, xi≥0, i≥0.

Примечание: Если типу ограничений соответствуют требования отрицательности множителей Лагранжа, то данные ограничения должны быть преобразованы к типу, для которых или не имеет ограничений. Например, для задачи на максимум с ограничениями типа требования к множителям Лагранжа . Тогда ограничения типа приводятся к виду , для которых .

5. Условия Куна-Таккера записываются в виде равенств путем введения дополнительных переменных.

(5.36)

(5.37)

 

6. Находим координаты седловой точки используя симплекс-метод.

Система (5.36) содержит линейных уравнений с переменными из которых являются свободными и равны нулю. Остальные переменные образуют при этом допустимое базисное решение, если выполняется условие (5.37).

Если в исходной системе (5.36) можно выделить начальное допустимое базисное решение, то его улучшение производят на основании симплекс-метода, аналогичного рассмотренному в задаче линейного программирования. Отличие здесь заключается в том, что при выборе новой базисной переменной каждый раз должны проверяться условия которые означают, что если в базисе имеются или то в него не могут быть введены переменные и соответственно.

Если в системе (5.36) нельзя сразу выделить начальное допустимое базисное решение, то оно может быть получено введением в систему фиктивных переменных .

+uj=0,

- vi +zi=0 (5.38)

В этом случае для улучшения начального допустимого баланса решения используют М-метод (подробнее алгоритм М-метода см. в п.3.5). То есть решают задачу максимизации функции F= при ограничениях (5.37) и (5.38). Здесь М – сколь угодно большое положительное число. Оптимальное решение может быть получено, если фиктивные переменные перейдут в разряд свободных, то есть будут выведены из базиса в процессе улучшения начального допустимого базисного решения.

Пример 5.1 Требуется максимизировать

(5.39)

при условиях:

(5.40)

 

1. Функция f представляет собой сумму линейной функции 4x1+10x2+x3, которую можно рассматривать как выпуклую и квадратичной –x12-4x22-4x33. Последняя является отрицательно определенной, следовательно также выпуклой.

2. В соответствии с типом оптимизации (5.39) и видом ограничений (5.40), ограничения, накладываемые на переменные - табличные. Поэтому условия (5.40) должны быть записаны в виде:

(5.41)

для которых .

3. Функция Лагранжа

и условие Куна-Таккера (таблица 2):

4. Частные производные от функции Лагранжа по переменным и

=

=

=

=

=

5. Условия Куна-Таккера

(5.42)

6. Условия (5.42) приводим к каноническому виду (ограничения равенства) путем введения дополнительных переменных u1 0, u2 0, u3 0, v1 0, v2 0.

(5.43)

7. Формируем исходный базис путем введения фиктивных переменных в ограничения (5.43):

(5.44)

и решаем задачу максимизации функции при ограничениях (5.44) симплекс-методом (решение в виде последовательности симплекс-таблиц представлено ниже).

БП Cб В -м -м -м
X1 X2 X3 l1 l2 U1 U2 U3 V1 V2 Z1 Z2 Z3
Z1 -м -1
Z2 -м -1
Z3 -м -1
V1
V2
  -15м 2м 8м 8м 5м 3м -м -м -м

 

БП Cб В -м -м -м
X1 X2 X3 l1 l2 U1 U2 U3 V1 V2 Z1 Z2 Z3
Z1 -м -1  
X2 1.25 0.125 0.125 -0.125  
Z3 -м 0,12  
V1 13.5 -0.25 -0.25 0.25  
V2 28.75 -0.125 -0.125 0.125  
  -5м 2м 8м 4м 2м -м -0.12м  

 

БП Cб В -м -м -м
X1 X2 X3 l1 l2 U1 U2 U3 V1 V2 Z1 Z2 Z3
Z1 -м -1    
X2 1.25 0.125 0.125 -0.125    
X3 0.125 0.375 0.125 -0.016    
V1 13.125 -1.375 -0.625 0.25 0.047    
V2 28.625 -0.5 -0.25 0.125 0.016    
  -4м 2m m m -m    

 

БП Cб В -м -м -м
    X1 X2 X3 l1 l2 U1 U2 U3 V1 V2 Z1 Z2 Z3
X1 0.5 0.5 -0.5 0.5      
X2 1.25 0.125 0.125 -0.125      
X3 0.125 0.375 0.125 -0.016      
V1 11.125 -1.875 -1.125 0.5 0.25 0.047      
V2 26.625 -1 -0.75 0.5 0.125 0.016      
         

 

return false">ссылка скрыта

Оптимальный план opt= (2; 1.25; 0.125; 0; 0; 0; 0; 0; 11.125; 26.625).

Целевая функция Fmax= 4*2+10*1.25+0.125-22-4*0.1252 = 10.3125

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