Пусть необходимо найти максимальное значение целевой функции
f(x1, x2, …, xn) (5.13)
при ограничениях
i = 1, 2, …, m; (5.14)
xj ≥ 0, j = 1, 2, …, n, (5.15)
где f(x) – вогнутая функция, а ограничения линейны. Эта особенность системы ограничений является принципиально важной для замены (в окрестности исследуемой точки) нелинейной целевой функции линейной функцией. Такая замена позволяет свести решение исходной задачи к последовательному решению задач линейного программирования.
Процесс решения задачи начинается с определения точки xk, принадлежащей допустимой области решений [2]. В этой точке вычисляют градиент целевой функции f(x)
и строят линейную функцию
(5.16)
Затем находят максимум этой функции при ограничениях (5.14) и (5.15), где переменные xj заменены на zj. Пусть решению такой задачи соответствует точка zk. Тогда за новое допустимое решение исходной задачи принимают
xk+1 = xk + λk(zk – xk), (5.17)
где λk – шаг вычисления и лежит в пределах (0 ≤ λk ≤ 1). Это число берут произвольно или так, чтобы f(xk+1) было максимальным. Для этого необходимо найти решение уравнения
и выбрать его наименьший корень. Если его значение больше единицы, то принять λ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. Пусть необходимо найти максимум целевой функции
при ограничениях
x1 + 2x2 ≤ 8;
2x1 – x2 ≤ 12;
x1 ≥ 0, x2 ≥ 0.
Решение.
Шаг 0. В качестве исходного допустимого решения можно взять точку x0 = (0; 0), а в качестве критерия оценки оптимальности найденного решения неравенство
Первая итерация.
Шаг 1. Вычислим градиент функции f(x)
В точке 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)
Тогда целевая функция исходной задачи примет вид
Приравняв производную от целевой функции нулю вычислим значение
Так как λ1 ∈ [0; 1] принимаем его за шаг вычисления.
Шаг 4. По формуле (5.17) находим новое допустимое решение
f(x1) = 2.
Шаг 5. Проверяем необходимость перехода к следующему допустимому решению
Условие оптимальности нарушено и, следовательно, переходим к следующей итерации.
Вторая итерация.
Шаг 1. Вычислим новый градиент функции f(x)
Шаг 2. Формируем дополнительную задачу линейного программирования
max F = 2z1;
z1 + 2z2 ≤ 8;
2z1 – z2 ≤ 12;
z1, z2 ≥ 0.
Оптимальное решение этой задачи
z1 = (6,4; 0,8).
Шаг 3. По аналогии с первой итерацией решая уравнение
определим следующее значение шага вычислений
λ = 0,15.
Шаг 4. Находим новое допустимое решение и значение целевой функции
f(x2) = 2,9966.
Шаг 5. Для полученного решения также не выполняется условие оптимальности:
Третья итерация.
Шаг 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
λ3 = 0,007.
Шаг 4. Находим новое допустимое решение и значение целевой функции
x3 = (0,9953;0,9632);
f(x3) = 2,99957.
Шаг 5. Полученное решение принимается за оптимальное решение, так как выполняется условие оптимальности:
Это решение близок к действительно оптимальному решению x* = (1; 1) полученному в разделе 5.1 на основе условий Куна – Таккера (пример 5.1).