Метод кусочно-линейной аппроксимации

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

(1)

при условиях

Чтобы найти решение задачи (1)–(3) функции f_j (x_j) и g _ij (x_j) заменяют кусочно-линейными функциями и и переходят к задаче

(4)

В задаче (4)–(6) пока не определен вид функций. Чтобы определить их, считают, что переменная x_j может принимать значения из промежутка [0; a _j ], где a _j – максимальное значение переменной x_j. Промежуток [0; a _j ] разбивается на r_j промежутков с помощью r_j + 1 точек так, что

Тогда функции и можно записать в виде

Причем

Подставляя теперь в (4), (5) выражения функций и в соответствии с формулой (7), приходят к задаче ЛП:

Эта задача может быть решена симплекс-методом и точность зависит от принятого шага разбиения промежутка [0; a _j ]: чем меньше шаг, тем точнее решение.

Пример 6.2

Решить задачу нелинейного программирования методом кусочно-линейной аппроксимации:

max F = x 2 – x 12 + 6 x ₁ – 9;

2 x 1 + 3 x 2 £ 24;

x 1 + 2 x ₂ £ 15;

3 x 1 + 2 x 2 £ 24;

x 2 £ 4;

x 1, x 2 ³ 0.

Решение.

В данной задаче целевую функцию F можно представить как сумму двух функций f ₁(x ₁) = – x ₁² + 6 x ₁–9 и f ₂(x ₂) = x ₂, каждая из которых есть функция одной переменной. Следовательно, функция F – сепарабильная.

Здесь нелинейной функцией является только целевая функция. Значит, кусочно-линейной функцией следует заменить только ее. При этом так как функция f ₂(x ₂) линейная, то аппроксимируется только функция f ₁(x ₁).

Далее строится область допустимых решений задачи (рис. 7.1).

Рис. 6.1

Из графика ОДЗ следует, что переменная x ₁ может принимать значения в промежутке [0; 8]. Этот промежуток может быть разбит на восемь частей точками: x ₀₁ = 0; x ₁₁ = 1; x ₂₁ = 2; x ₃₁ = 3; x ₄₁ = 4; x ₅₁ = 5; x ₆₁ = 6; x ₇₁ = 7; x ₈₁ = 8. В этих точках вычисляются значения функции f ₁(x ₁) (табл. 7.2).

Таблица 6.2

xk 1
f 1(xk 1)	–9	–4	–1		–1	–4	–9	–16	–25

По формулам (7), (8) можно найти

Найденные выражения и x ₁ подставляются в исходные данные:

Для полученной задачи линейного программирования пять векторов P ₀₁, P ₃, P ₄, P ₅, P ₆ являются единичными. Значит, ее решение может быть найдено симплекс-методом. Из симплекс–таблицы находят x ₂⁰ = 4, а по найденному l _{k 1} находят x ₁⁰ = 3, F_max = 4.