Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания

5.2.1. Метод Франка – Вульфа

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

f(x1, x2, …, xn) (5.13)

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

shukaev265.wmf i = 1, 2, …, m; (5.14)

xj ≥ 0, j = 1, 2, …, n, (5.15)

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

Процесс решения задачи начинается с определения точки xk, принадлежащей допустимой области решений [2]. В этой точке вычисляют градиент целевой функции f(x)

shukaev266.wmf

и строят линейную функцию

shukaev267.wmf (5.16)

Затем находят максимум этой функции при ограничениях (5.14) и (5.15), где переменные xj заменены на zj. Пусть решению такой задачи соответствует точка zk. Тогда за новое допустимое решение исходной задачи принимают

xk+1 = xk + λk(zk – xk), (5.17)

где λk – шаг вычисления и лежит в пределах (0 ≤ λk ≤ 1). Это число берут произвольно или так, чтобы f(xk+1) было максимальным. Для этого необходимо найти решение уравнения

shukaev268.wmf

и выбрать его наименьший корень. Если его значение больше единицы, то принять λk = 1.

Затем находят координаты точки xk+1, значение целевой функции и выясняют необходимость перехода к новой точке xk+2 по указанным выше признакам. Если такой переход необходим, то в точке xk+1 вычисляют градиент целевой функции и снова формируют и решают задачу линейного программирования. Затем определяют координаты точки xk+2 и исследуют необходимость проведения дальнейших вычислений и т.д.

Таким образом укрупненный алгоритм Франка – Вульфа состоит из следующих шагов.

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

Шаг 1. Вычисляют градиент функции f(x).

Шаг 2. Формируют дополнительную линейную целевую функцию (5.16) и находят ее максимальное значение при ограничениях (5.14) и (5.15).

Шаг 3. Определяют шаг вычислений λk.

Шаг 4. По формуле (5.17) находят новое допустимое решение.

Шаг 5. Проверяют необходимость перехода к следующему допустимому решению и при таковой переходят к шагу 1. В противном случае найдено оптимальное решение задачи.

Пример 5.2. Пусть необходимо найти максимум целевой функции

shukaev269.wmf

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

x1 + 2x2 ≤ 8;

2x1 – x2 ≤ 12;

x1 ≥ 0, x2 ≥ 0.

Решение.

Шаг 0. В качестве исходного допустимого решения можно взять точку x0 = (0; 0), а в качестве критерия оценки оптимальности найденного решения неравенство

shukaev270.wmf

Первая итерация.

Шаг 1. Вычислим градиент функции f(x)

shukaev271.wmf

В точке x0 = (0; 0) градиент равен ∇f(x0) = (2; 4).

Шаг 2. Формируем дополнительную задачу линейного программирования

max F = 2z1 + 4z2;

z1 + 2z2 ≤ 8;

2z1 – z2 ≤ 12;

x1, x2 ≥ 0.

Оптимальное решение этой задачи z0 = (0; 4).

Шаг 3. Определим шаг вычислений λ1. Для этого полученное решение z0 = (0; 4) подставим в формулу (5.17)

shukaev272.wmf

shukaev273.wmf

Тогда целевая функция исходной задачи примет вид

shukaev274.wmf

Приравняв производную от целевой функции нулю вычислим значение

shukaev275.wmf

Так как λ1 ∈ [0; 1] принимаем его за шаг вычисления.

Шаг 4. По формуле (5.17) находим новое допустимое решение

shukaev276.wmf

shukaev277.wmf

f(x1) = 2.

Шаг 5. Проверяем необходимость перехода к следующему допустимому решению

shukaev278.wmf

Условие оптимальности нарушено и, следовательно, переходим к следующей итерации.

Вторая итерация.

Шаг 1. Вычислим новый градиент функции f(x)

shukaev279.wmf

Шаг 2. Формируем дополнительную задачу линейного программирования

max F = 2z1;

z1 + 2z2 ≤ 8;

2z1 – z2 ≤ 12;

z1, z2 ≥ 0.

Оптимальное решение этой задачи

z1 = (6,4; 0,8).

Шаг 3. По аналогии с первой итерацией решая уравнение

shukaev280.wmf

определим следующее значение шага вычислений

λ = 0,15.

Шаг 4. Находим новое допустимое решение и значение целевой функции

shukaev281.wmf shukaev282.wmf f(x2) = 2,9966.

Шаг 5. Для полученного решения также не выполняется условие оптимальности:

shukaev283.wmf

Третья итерация.

Шаг 1. Вычислим очередной градиент функции f(x)

∇f(x2) = (0,08; 0,12).

Шаг 2. Формируем и решаем дополнительную задачу линейного программирования

max F = 0,08z1 + 0,12z2,

z1 + 2z2 ≤ 8;

2z1 – z2 ≤ 12; z2 = (6; 0);

z1, z2 ≥ 0.

Шаг 3. Находим λ3

shukaev284.wmf

λ3 = 0,007.

Шаг 4. Находим новое допустимое решение и значение целевой функции

x3 = (0,9953;0,9632);

f(x3) = 2,99957.

Шаг 5. Полученное решение принимается за оптимальное решение, так как выполняется условие оптимальности:

shukaev285.wmf

Это решение близок к действительно оптимальному решению x* = (1; 1) полученному в разделе 5.1 на основе условий Куна – Таккера (пример 5.1).


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074