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

Пусть требуется найти максимальное значение вогнутой функции

¦(х₁, х₂, х₃,…, х_n) (57)

при условиях

_n___

å a_ijx_j £ b_i(i = 1, m), (58)

^j⁼¹___

x_j ³ 0 (j = 1, n). (59)

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

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

Ñ¦(Х^(k) ) = [¶¦(Х^(k) ) / ¶х₁, ¶¦(Х^(k) ) / ¶х₂, …, ¶¦(Х^(k) ) / ¶х_n] и строят линейную функцию

F = (¶¦(Х^(k) ) / ¶х₁)·x₁ + (¶¦(Х^(k) ) / ¶х₂)·x₂ + … + (¶¦(Х^(k) ) /¶х_n)·x_n. (60)

Затем находят максимальное значение этой функции при ограничениях (58) и (59). Пусть решение данной задачи определяется точкой Z⁽^k⁾. Тогда за новое допустимое решение исходной задачи принимают координаты точки Х⁽^k⁺¹⁾:

Х⁽^k⁺¹⁾ = Х⁽^k⁾ + l_k(Z⁽^k⁾– Х⁽^k⁾ ), (61)

где l_k – некоторое число, называемое шагом вычислений и заключенное между нулем и единицей (0 £ l_k £ 1). Это l_k берут произвольно или определяют таким образом, чтобы значение функции в точке Х⁽^k⁺¹⁾¦(Х⁽^k⁺¹⁾), зависящее от l_k , было максимальным. Для того необходимо найти решение уравнения

d¦ \ dl_k = 0 и выбрать его наименьший корень. Если его значение больше единицы, то следует положить l_k = 1. После определения числа l_k находят координаты точки Х⁽^k⁺¹⁾, вычисляют значение целевой функции в ней ми выясняют необходимость перехода к новой точке Х⁽^k⁺²⁾. Если такая необходимость имеется, то вычисляют в точке х⁽^k⁺¹⁾ градиент целевой функции, переходят к соответствующей задаче линейного программирования и находят ее решение. Определяют координаты точки Х⁽^k⁺²⁾и исследуют необходимость проведения дальнейших вычислений. После конечного числа шагов получают с необходимой точностью решение исходной задачи.

Итак, процесс нахождения решения задачи (57) – (59) методом Франка-Вульфа включает следующие этапы:

1°. Определяют исходное допустимое решение задачи.

2°. Находят градиент функции (57) в точке допустимого решения.

3°. Строят функцию (60) и находят ее максимальное значение при условиях (58) и

(59).

4°. Определяют шаг вычислений.

5°. По формулам (61) находят компоненты нового допустимого решения.

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

П р и м е р. Методом Франка-Вульфа найти решение задачи, состоящей в определении максимального значения функции

¦ = 2х₁ + 4х₂ – х₁² – х₂² (62)

при условиях

ì х₁ + х₂ £ 8,

í (63)

î 2х₁ – х₂ £12,

х₁, х₂ ³ 0. (64)

Р е ш е н и е. Найдем градиент функции

Ñ¦ = [ ¶¦ \ ¶х₁, ¶¦ \ ¶х₂ ] = (2 – 2х₁, 4 – 4х₂)

и в качестве исходного допустимого решения задачи возьмем точку х(0) = (0, 0), а в качестве критерия оценки качества получаемого решения – неравенство

½¦(Х⁽^k⁺¹⁾ ) - ¦(Х⁽^k⁾ )½ < e, где e = 0,01.

I и т е р а ц и я. В точке Х⁽⁰⁾ градиент Ñ¦(Х⁽⁰⁾ ) = (2, 4). Находим максимум функций

F₁ = 2х₁ + 4х₂(65)

При условиях (63) и (64)

ì х₁ + х₂ £ 8,

í (66)

î 2х₁ – х₂ £12,

х₁, х₂ ³ 0. (67)

Задача (65) – (67) имеет оптимальный план Z⁽⁰⁾ = (0, 4).

Найдем новое допустимое значение исходной задачи по формуле (61):

Х⁽¹⁾ = Х⁽⁰⁾ + l₁(Z⁽⁰⁾ – Х⁽⁰⁾ ), где 0 £ l₁£ 1. (68)

Подставив вместо Х(0) и Z(0) их значения, получим

ì х₁⁽¹⁾ = 0 + l₁×0,

í (69)

î х₂⁽¹⁾ = 0 + l₁×4.

Определим теперь число l₁. Подставив в равенство (62) вместо х₁ и х₂ их значения в соответствии с соотношениями (69) ¦(l₁) = 16l₁ - 32l₁², найдем производную этой функции по l₁ и приравняем ее нулю ¦¢(l₁) = 16 - 64l₁ = 0. Решая это уравнение, получим l₁ = 1/4 = 0,25. Поскольку найденное значение l₁ заключено между 0 и 1, принимаем его за величину шага. Таким образом, Х⁽¹⁾ = (0, 1), ¦(Х⁽¹⁾) = 2,

¦(Х⁽¹⁾) - ¦(Х⁽⁰⁾) = 2 > e = 0,01.

II и т е р а ц и я. Градиент целевой функции исходной задачи в точке Х⁽¹⁾ есть

Ñ¦( Х⁽¹⁾) = (2, 0). Находим максимум функции F₂ = 2х₁ при условиях (63) и (64). Решением является Z⁽¹⁾ = (6,4; 0,8).

Определяем теперь Х⁽²⁾ = Х⁽¹⁾ + l₂(Z⁽¹⁾ – Х⁽¹⁾). Последнее равенство перепишем следующим образом:

ì х₁⁽²⁾ = 6,4 l₂,

í (70)

î х₂⁽²⁾ = 1 – 0,2l₂.

Подставляя теперь в функцию (62) вместо х1 и х2 их значения в соответствии с соотношениями (70), получаем

¦(l₂) = 2 + 12,8l₂ - 41,04l₂²,

откуда ¦¢(l₂) = 12,8 - 41,04l₂. Приравнивая ¦¢(l₂) нулю и решая полученное уравнение, находим l₂ »0,16. Таким образом,

ì х₁⁽²⁾ = 1,02,

î х₂⁽²⁾ = 0,97,

т.е. Х⁽²⁾ = (1,02; 0,97), ¦(Х⁽²⁾) = 2,9978, ¦(Х⁽²⁾) - ¦(Х⁽¹⁾) = 2,9978 – 2 = 0,9978 > e = 0,01.

III и т е р а ц и я. Градиент функции ¦ в точке Х⁽²⁾ есть

Ñ¦(Х⁽²⁾) = (-0,04; 0,12). Находим максимум функции F₃ = -0,04х₁ + 0,12х₂ при условиях (63) и (64). Решением является Z⁽²⁾ = (0; 4).

Определяем Х⁽³⁾ = Х⁽²⁾ + l₃(Z⁽²⁾ – X⁽²⁾). Имеем

ì х1⁽³⁾ = 1,02 + l₃(0 – 1,02) = 1,02 – 1,02l₃,

î х₂⁽³⁾ = 0,97 + l₃(4 – 0,97) = 0,97 + 3,03l₃;

¦(l₃) = 2,9978 + 0,4044l₃ – 19,4022l₃²,

¦¢(l₃) = 0,4044 – 38,8044l₃.

Решая уравнение ¦¢(l₃) = 0, находим l₃» 0,010. Следовательно,

Х⁽³⁾ = (1,0098; 1,0003), ¦(Х⁽³⁾) = 2,99991,

¦(Х⁽³⁾) - ¦(Х⁽²⁾) = 2,99991 – 2,9978 = 0,00211 < e = 0,01.

Таким образом, Х⁽³⁾ = (1,0098; 1,0003) является искомым решением исходной задачи. Задав меньшую величину e, можно было бы, совершив дополнительные приближения, еще ближе подойти к точке максимального значения целевой функции.