Сепарабельное программирование (СП)

В СП рассматриваются задачи, в которых целевая функция и все функции ограничений сепарабельны. Функция многих переменных сепарабельна, если она имеет вид суммы функций отдельных переменных: f (x ₁, x ₂,..., x_n) =

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

Возможно 2 варианта записи переменных: l - постановка

Предполагается, что переменные, которые входят в модель нелинейно, ограничены снизу и сверху: d_j £ x_j £ D_j. Для кусочно-линейной аппроксимации в этом диапазоне выбираются узловые точки, чаще там, где сильнее нелинейность функции. При этом первый узел совпадает с нижней границей, а последний – с верхней: X_j1 = d_j, = D_j, где r_j – число интервалов по переменной x_j (r_j +1 – число узлов). Переменная x_j может быть выражена через новые переменные l_jk в виде (1), , (2)

Выражение (1) называют уравнением сетки. С учетом (2) оно представляет переменную x_j в зад. диапазоне без потери точности. С использованием узловых точек и новых переменных кусочно-линейная функция, аппроксимирующая f_j (x_j), записывается в виде где f_j (X_jk) – значение функции в узловых точках. – функция, линей­ная относительно l_jk. Пусть N – множество индексов нелинейных f_j (x_j). Ф-я, аппрокси­мирующая f (X), имеет вид (3)

Алгоритм: 1. для каждой переменной, входящей нелинейно, записать уравнение сетки; 2. во всей модели заменить переменные из п.1, входящие в линейные f_j, соответствующими уравнениями сетки; 3. все функции, содержащие нелинейности, представить в виде (3); 4. добавить ограничения (2) для всех новых переменных.

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