Метод линеаризации Франка-Вульфа

Метод линеаризации – один из наиболее эффективных методов решения задач математического программирования. Данный метод базируется на идее линейной или квадратичной аппроксимации целевой функции в окрестностях очередной точки. Поэтому в качестве вспомогательных возникают задачи линейного или квадратичного программирования.

Общая постановка задачи:

(5.45)

(5.46)

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

Суть метода при линейной аппроксимации заключается в том, что:

1. Нелинейная функция (5.45) заменяется линейной в точке ^(к), принадлежащей допустимой области G

(5.47)

2. Решается задача линейного программирования:

(5.48)

Пусть решением этой задачи является точка ^(k).

3. Из точки в направлении смещаемся с некоторым шагом в точку (5.49)

Так как и принадлежат допустимой области G, а область G, определяемая ограничениями (5.46) выпукла и , то ^{(k + 1)} G.

Шаг можно выбирать по-разному:

1) шаг - произвольное, достаточно малое число ;

2) шаг выбирается таким, при котором функция принимает наибольшее значение при всех . Если найденное значение принадлежит концам отрезка [0;1], то необходимо выбрать один из концов этого отрезка.

3. Итерации продолжаются до тех пор, пока

(5.50)

где -положительное, малое число.

Пример 5.2 Требуется максимизировать функцию

(5.51)

при условиях (5.52)

с точностью 0,1.

В качестве начального допустимого вектора берем ⁽⁰⁾ = (0,0). Значение целевой функции в этой точке F ⁽⁰⁾ = 0. Нелинейную функцию (5.51) заменяем линейной и F ^* (0,0) в соответствии с (5.47)

Далее решаем задачу: х₁ + 8х₂ ® mах

Здесь ограничения (5.52) приведены к каноническому виду.

БП	Cб	В
			X1	X2	X3	X4
X1
X4
					-1
X1						-1
X2
					-1	-7

Итак, . Вектор находим по формуле (5.49): Шаг найдем из условия максимума f ( ⁽¹⁾ ) при .

F ( ⁽¹⁾) = - (2 )²- (5 ) ² + 2 + 8*5 = -29 ² + 42 .

( ⁽¹⁾) = - 58 + 42 = 0. Откуда = 0,724.

Следовательно ⁽¹⁾ = (1,448; 3,62). Значение целевой функции в этой точке F ⁽¹⁾ = 15,207.

Вторая итерация: F * (1,448; 3,62) = -1,896 х ₁ + 0,76 х ₂; ⁽¹⁾ = (0,5);

⁽²⁾ = ((1- ) 1,448; 5 + (1- ) 3,62); = 0,474;

⁽²⁾ = (0,762; 4,27); F ⁽²⁾ = 16,108.

Третья итерация: F * (0,762; 4,27) = -0,524 х ₁-0,54 х ₂; ⁽²⁾ = (0,0);

⁽³⁾ = ((1- ) 0,762; (1- ) 4,27); = 0,072;

⁽³⁾ = (0,707; 3,963); F ⁽³⁾ = 16,206.

| F ⁽³⁾ - F ⁽²⁾ | = | 16,206-16,108 | = 0,098 < 0,1. То есть приближенно можно считать, что F_мax = 16,206; _opt = (0,707; 3,963).Точное решение этой задачи: F_мax = 16,25; _opt = (0,5; 4).