Сепарабельное программирование: кусочно-линейная аппроксимация нелинейных моделей

Математическая суть метода заключается в замене каждой нелинейной функции одной переменной $f_j(x_j)$ ее кусочно-линейной аппроксимацией. Для этого интервал возможных значений переменной разбивается на ряд отрезков точками сетки. Значение функции в любой точке аппроксимируется как выпуклая линейная комбинация значений функции в соседних узлах сетки. Вводятся новые неотрицательные переменные $\lambda_{kj}$, представляющие собой веса каждого узла, причем сумма весов для каждой исходной переменной должна быть равна единице. Таким образом, исходная нелинейная задача трансформируется в задачу линейного программирования относительно переменных $\lambda$, размерность которой зависит от густоты выбранной сетки.

Ключевым математическим нюансом сепарабельного программирования является условие смежности: в оптимальном решении для каждой исходной переменной не более двух весовых коэффициентов $\lambda$ могут быть строго положительными, и они обязательно должны соответствовать соседним узлам сетки. Если целевая функция подлежит минимизации и является строго выпуклой (или максимизируется вогнутая функция), а допустимая область выпукла, симплекс-метод автоматически удовлетворяет условию смежности благодаря геометрии выпуклых оболочек. В этом случае аппроксимированная задача решается стандартным симплекс-методом, и найденный локальный оптимум гарантированно является глобальным оптимумом аппроксимирующей задачи.

Однако, если условие выпуклости нарушается (например, в производственных задачах с экономией на масштабе, где функция издержек вогнута, а мы ее минимизируем), стандартный симплекс-метод может выбрать несмежные узлы сетки, что приведет к физически бессмысленному решению. Для преодоления этой проблемы используется модифицированный симплекс-метод (Restricted Basis Entry). Правило ввода новой переменной в базис жестко контролируется: переменная $\lambda$ допускается в базис только в том случае, если это не нарушает условие смежности с уже находящимися в базисе переменными. Хотя модифицированный метод гарантирует получение лишь локального оптимума, на практике он часто находит решения, удовлетворяющие инженерным и экономическим требованиям.

Приложения сепарабельного программирования охватывают планирование работы каскадов гидроэлектростанций, оптимизацию распределения воды в ирригационных сетях и моделирование налоговых ставок. В современных коммерческих решателях концепции сепарабельного программирования интегрированы в алгоритмы ветвей и отсечений через использование специальных упорядоченных множеств (SOS - Special Ordered Sets), в частности SOS2. Переменные типа SOS2 формализуют условие смежности на уровне дискретной оптимизации, позволяя солверу эффективно ветвиться и находить строгий глобальный оптимум даже для сильно невыпуклых сепарабельных функций, обеспечивая непревзойденную точность технико-экономического моделирования.

Список литературы:
1. Данциг Д. Линейное программирование, его обобщения и применения. — М.: Прогресс, 1966.
2. Хедли Дж. Нелинейное и динамическое программирование. — М.: Мир, 1967.
3. Beale E.M.L. Mathematical Programming in Practice. — Pitman, 1968.