Метод Баранкина и Дорфмана для задачи квадратичного программирования

Рассматривается задача квадратичного программирования вида:

, (1)

в которой - положительно полуопределенная матрица размерности , - матрица размерности . Условия Куна-Таккера для задачи (1) будут иметь вид

(2)

и

(3)

где

,

.

Условие (3) может выполняться только для допустимого базисного решения системы (2), то есть для решения, в котором самое большее переменных из переменных системы положительны.

Задача формулируется следующим образом: среди допустимых базисных решений системы (2) найти такое, которое обращает в нуль величину .

Баранкин и Дорфман начинают с некоторого базисного решения системы (2), необязательно удовлетворяющему условию (3), и с помощью симплексных преобразований сводят к нулю выпуклую функцию .

 

Алгоритм

Все переменные систем представим в виде -мерного вектора

.

Каждому такому вектору соответствует вектор

, то есть .

Очевидно, ,

и условия (2) и (3) можно записать в следующем виде

, (4)

,

. (5)

Метод Баранкина и Дорфмана состоит в том, что исходя из некоторого базисного решения системы (4), совершают ряд симплексных преобразований, в результате каждого из которых выпуклая функция уменьшается пока, наконец, не будет получено базисное решение со значением .

Пусть имеется некоторое допустимое базисное решение системы (4). Переменные входящие в базис обозначим , независимые переменные (небазисные) . Соответствующая симплексная таблица отразит функциональную зависимость от :

. (6)

Число таких равенств . Их можно заменить векторным равенством, если дополнить симплексную таблицу строками для независимых переменных, в которых 1 будет стоять в столбце с этой переменной, а все остальные элементы строки – 0. Тогда переменные , , будут входить в направляющий столбец (самый левый) в своей естественной последовательности. Таким образом в симплексной таблице для небазисных переменных , , . В векторной форме ,

где ­– -й столбец таблицы.

Для базисного решения, в котором независимые переменные равны нулю,

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

Переменную можно увеличивать до тех пор, пока какая-нибудь базисная переменная не обратится в нуль. Это произойдет при . (7)

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

, (8)

а – новое значение

. (9)

Так как , (10)

то можно записать , (10)

где , (11)

, (12)

. (13)

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

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

Вычисления.

В первую очередь получают некоторое базисное решение, затем дополняют симплексную таблицу строками для небазисных переменных, упорядочивают таблицу, строят дополнительную таблицу (в соответствии с (15)).

В дополнительной таблице .

Если , то таблица оптимальна и вектор есть решение. В противном случае отыскиваем

, .

Для тех , где , вычисляем ,

, .

Таблица (15)

			...
			...
...	...	...	...	...
			...
			...
...	...	...	...	...
			...
			...
			...
Дополнительная			...
таблица			...

 

В качестве заменяющего столбца выбираем столбец с минимальным по модулю отрицательным значением . Эту переменную включаем в базис. Элемент , по которому определили , становится опорным элементом.

Примечание: Если все , а , то метод далее неприменим (невозможно перейти в другую вершину из-за увеличения ). В этом случае включаем в базис какую-нибудь переменную и пытаемся выйти из «мертвой зоны», либо выбираем в качестве начального другое базисное решение.

 

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

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

1. Наверху -го столбца записываем переменную, стоящую слева в -й строке.

2. Делим -й столбец на и записываем на соответствующее место новой таблицы.

3. Для того, чтобы получить остальные столбцы новой таблицы необходимо из соответствующих столбцов старой таблицы вычесть новый -й столбец, умноженный на коэффициент, стоящий на пересечении соответствующего столбца и -й строки. -я строка при этом превращается в строку, состоящую из всех нулей и одной 1.

Пример 1. Решить задачу квадратичного программирования вида:

,

где , , , .

Решение. Расширенная матрица, определяющая линейную систему

,

.

Найдем базисное решение (опорный план), с которого продолжим решение методом Баранкина и Дорфмана. Воспользуемся для этого методом последовательного улучшения плана.

Исходная таблица

		–	–	–	–	–	–	–	–
0=
0=
0=						-1
0=							-1

Исключаем 0-строки.

		–	–	–	–	–	–	–
=		1.5	0.5
0=		2.5	-0.5
0=	-2	-1.5	-0.5		-1
0=						-1

 

		–	–	–	–	–	–
=	1.8	0.8	-0.6
=	0.8	-0.2	0.4
0=	-0.8	-0.8	0.6	-1
0=	1.2	0.2	-0.4		-1

 

 

		–	–	–	–	–
=	1.8	0.8	-0.6
=	0.8	-0.2	0.4
=	0.8	0.8	-0.6		-2	-1
0=	1.2	0.2	-0.4	-1

 

		–	–	–	–
=	1.8	0.8	-0.6
=	0.8	-0.2	0.4
=	1.6	14/15	-13/15	-2/3	5/3
=	0.4	1/15	-2/15	-1/3	4/3

 

Найден опорный план. Составляем расширенную таблицу для метода Баранкина-Дорфмана.

Исходная таблица метода Баранкина-Дорфмана

=	1.8	-0.8	0.6
=	0.8	0.2	-0.4
=
=
=	1.6	-0.93333	0.866667	0.666667	-1.66667
=
=	0.4	-0.06667	0.133333	0.333333	-1.33333
=
,	5.76	-2.56	2.52		-3
		1.36
		1.714286			0.3
		-2.78857			-6
*		-4.78041			-1.8

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

 

=	1.8	-0.8	0.6
=	0.8	0.2	-0.4
=
=
=	1.1	-0.85	0.7	0.25	1.25
=
=
=	0.3	-0.05	0.1	0.25	-0.75
,	3.96	-2.41	2.22	1.25	2.25
		1.36
		1.294118
		-3.06
*		-3.96

Следующая таблица должна быть оптимальной, так как

=	0.764706 =13/17	0.941176 =16/17	-0.05882 =-1/17	-0.23529 =-4/17	-1.17647 =-20/17
=	1.058824 =18/17	-0.23529 =-4/17	-0.23529 =-4/17	0.058824 =1/17	0.294118 =5/17
=	1.294118 =22/17	-1.17647 =-20/17	0.823529 =14/17	0.294118 =5/17	1.470588 =25/17
=
=
=
=
=	0.235294 =4/17	0.058824 =1/17	0.058824 =1/17	0.235294 =4/17	-0.82353 =-14/17

 

Оптимальный план задачи: , , , .