Научная электронная библиотека

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

Прикладные методы оптимизации

Шукаев Д. Н.,

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

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

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

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

i = 1, 2, …, m; (5.14)

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

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

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

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

(5.16)

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

x^k+1 = x^k + λ^k(z^k – x^k), (5.17)

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

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

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

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

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

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

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

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

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

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

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

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

x1 + 2x₂ ≤ 8;

2x1 – x₂ ≤ 12;

x1 ≥ 0, x2 ≥ 0.

Решение.

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

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

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

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

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

max F = 2z₁ + 4z₂;

z1 + 2z₂ ≤ 8;

2z1 – z2 ≤ 12;

x1, x2 ≥ 0.

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

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

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

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

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

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

f(x1) = 2.

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

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

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

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

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

max F = 2z₁;

z1 + 2z₂ ≤ 8;

2z1 – z₂ ≤ 12;

z1, z2 ≥ 0.

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

z¹ = (6,4; 0,8).

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

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

λ = 0,15.

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

f(x²) = 2,9966.

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

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

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

∇f(x²) = (0,08; 0,12).

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

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

z1 + 2z₂ ≤ 8;

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

z1, z2 ≥ 0.

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

λ₃ = 0,007.

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

x³ = (0,9953;0,9632);

f(x³) = 2,99957.

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

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