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

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

(1)

при условиях

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

(4)

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

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

Причем

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

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

Пример 6.2

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

max F = x2 – x12 + 6x1 – 9;

2x1 + 3x2 £ 24;

x1 + 2x2 £ 15;

3x1 + 2x2 £ 24;

x2 £ 4;

x1, x2 ³ 0.

Решение.

В данной задаче целевую функцию F можно представить как сумму двух функций f1(x1) = –x12 + 6x1–9 и f2(x2) = x2, каждая из которых есть функция одной переменной. Следовательно, функция F – сепарабильная.

Здесь нелинейной функцией является только целевая функция. Значит, кусочно-линейной функцией следует заменить только ее. При этом так как функция f2(x2) линейная, то аппроксимируется только функция f1(x1).

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

Из графика ОДЗ следует, что переменная x1 может принимать значения в промежутке [0; 8]. Этот промежуток может быть разбит на восемь частей точками: x01 = 0; x11 = 1; x21 = 2; x31 = 3; x41 = 4; x51 = 5; x61 = 6; x71 = 7; x81 = 8. В этих точках вычисляются значения функции f1(x1) (табл. 7.2).

Таблица 6.2

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

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

Для полученной задачи линейного программирования пять векторов P01, P3, P4, P5, P6 являются единичными. Значит, ее решение может быть найдено симплекс-методом. Из симплекс–таблицы находят x20= 4, а по найденному lk1 находят x10= 3, Fmax = 4.