L - постановка

Предполагается, что переменные, которые входят в модель нелинейно, ограничены снизу и сверху:

d_j £ x_j £ D_j. (8.19)

Для кусочно-линейной аппроксимации в этом диапазоне выбираются узловые точки, чаще в той части, где сильнее нелинейность функции. При этом первый узел совпадает с нижней границей, а последний – с верхней:

X_j1 = d_j, = D_j,

где r_j – число интервалов по переменной x_j (r_j +1 – число узлов). Тогда рассматриваемая переменная x_j может быть выражена через новые переменные l_jk в виде

, (8.20)

, (8.21)

. (8.22)

Выражение (8.20) называют уравнением сетки. С учетом (8.21) и (8.22) оно представляет переменную x_j в диапазоне (8.19) без потери точности. С использованием узловых точек и новых переменных кусочно-линейная функция, аппроксимирующая f_j (x_j), записывается в виде

(8.23)

где f_j (X_jk) – значение функции в узловых точках (рис. 8.5). Очевидно, что – функция, линей­ная относительно l_jk. Пусть N – множество индексов нелинейных f_j (x_j). Тогда функция, аппрокси­мирующая f (X), имеет вид

(8.24)

Итак, чтобы построить линейную аппроксимирующую модель, необходимо:

1. для каждой переменной, входящей нелинейно, записать уравнение сетки;

2. во всей модели заменить переменные из п.1, входящие в линейные f_j, соответствующими уравнениями сетки;

3. все функции, содержащие нелинейности, представить в виде (8.24);

4. добавить ограничения (8.21), (8.22) для всех новых переменных.

Если переменная x_j входит нелинейно в несколько функций, узлы сетки выбираются с учетом нелинейности всех таких функций, так как для одной переменной может быть только одно уравнение сетки.

Поясним запись ограничений. Пусть имеется исходное ограничение

S j_ij (x_j) £ b_i

со всеми нелинейными j_ij. Тогда после аппроксимации оно принимает вид

В общем случае левая часть ограничения записывается аналогично (8.24).

Хотя аппроксимирующая задача линейная, получаемое на ней решение не всегда является приближением к решению исходной задачи. Дело в том, что одно и то же значение x_j можно получить по уравнению сетки при разных l_jk, то есть представить через разные пары узлов. Например, некоторое значение x_j можно выразить через смежные узлы, в интервале которых находится значение, а можно через любую другую пару узлов, лежащих слева и справа, в том числе через первый и последний узел. Во всех случаях,кроме первого аппроксимация функции будет грубой и тем грубее, чем дальше отстоят узлы от данного значения x_j.

Отсюда следует правило смежных весов: из одного уравнения сетки отличными от нуля могут быть не более 2-х переменных l_jk со смежными значениями k.

Если аппроксимирующая задача является задачей выпуклого программирования, то это правило выполняется автоматически и решение находится методом ЛП без каких-либо дополнений. Оптимальное решение аппроксимирующей задачи будет приближением глобального решения исходной задачи.

В противном случае алгоритм ЛП должен включать правило ограниченного ввода:

если в базисном решении находится l_jk, то допустимыми для ввода могут быть только l_{jk +1} или l_{jk -1}.

При этом нельзя утверждать, что получаемое решение является приближением к глобальному оптимуму исходной задачи. Скорее оно будет приближением локального оптимума.

Свойства задачи зависят от всех функций модели:

1. Если все ограничения линейные, то для выпуклости задачи достаточно, чтобы были вогнутыми все f_j критерия (выпуклы при минимизации

2. При нелинейности критерия и ограничений для выпуклости задачи должны быть вогнуты все f_j и выпуклы все j_ij.

3. Если хотя бы одна f_j не вогнута при максимизации и/или одна j_ij не выпукла, задача не является выпуклой.

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

Пример 8.3. Задача

f = 6 x ₁ – x ₁²+ 7 x ₂ à max,

2 x ₁² – 5 x ₁ + 3 x ₂² £ 8,

1 £ x ₁ < 4, x ₂ ³ 0

является задачей сепарабельного программирования. Здесь

f ₁(x ₁) = 6 x ₁ – x ₁²; f ₂(x ₂) = 7 x ₂;

j ₁₁(x ₁) = 2 x ₁² – 5 x ₁; j ₁₂(x ₂)=3 x ₂².

Так как f ₁(x ₁) и f ₂(x ₂) – вогнутые, а j ₁₁(x ₁) и j ₁₂(x ₂) – выпуклые, имеем задачу выпуклого программирования. Обе переменные входят нелинейно, поэтому нужно строить две сетки. Оценим верхний предел x ₂: находим min j ₁₁=-3.125, затем из ограничения получаем максимально возможное значение x ₂=1.93. Берем D ₂=2. Пусть узловыми будут значения по x ₁: 1, 2, 3, 4; по x ₂: 0, 1, 2. Записываем уравнения сеток: x ₁= l ₁₁ +2 l ₁₂+3 l ₁₃+4 l ₁₄, x ₂= l ₂₂+2 l ₂₃. В итоге получаем модель аппроксимирующей задачи в виде

5 l ₁₁+8 l ₁₂+9 l ₁₃+8 l ₁₄+7 l ₂₂+14 l ₂₃ à max,

-3 l ₁₁-2 l ₁₂+3 l ₁₃+12 l ₁₄ +3 l ₂₂+12 l ₂₃£ 8,

l ₁₁ +2 l ₁₂+3 l ₁₃+4 l ₁₄³ 1,

l ₁₁ +2 l ₁₂+3 l ₁₃+4 l ₁₄£ 4,

l ₁₁ + l ₁₂+ l ₁₃+ l ₁₄=1,

l ₂₁ + l ₂₂+ l ₂₃=1,

" l_jk ³ 0.

Эта задача решается любым универсальным методом ЛП без добавления правила ограниченного ввода.