Дробно-линейное программирование: оптимизация относительных показателей и метод Чарнеса-Купера

Математическая модель задачи дробно-линейного программирования включает целевую функцию вида Z = (C*X + a) / (D*X + b), которую необходимо максимизировать или минимизировать при стандартных линейных ограничениях A*X <= B и условии неотрицательности переменных X >= 0. Очевидно, что поверхность уровня такой целевой функции больше не является гиперплоскостью, как в линейном программировании. Градиент функции постоянно меняет свое направление и величину в зависимости от точки пространства, что делает прямое применение классического симплекс-метода невозможным. При этом знаменатель дроби в области допустимых решений строго не должен обращаться в нуль, чтобы избежать математических сингулярностей.

Величайшим прорывом в решении задач ДЛП стала алгоритмическая трансформация, предложенная математиками Абрахамом Чарнесом и Уильямом Купером в 1962 году. Метод Чарнеса-Купера позволяет свести нелинейную дробную задачу к абсолютно эквивалентной задаче линейного программирования путем введения новой вспомогательной скалярной переменной t. Эта переменная геометрически представляет собой величину, обратную знаменателю целевой функции: t = 1 / (D*X + b). Умножив все исходные переменные X на этот скаляр t, мы получаем новые трансформированные переменные Y = X * t. В результате такого гениального проективного преобразования пространства сложная нелинейная дробь волшебным образом схлопывается в простую линейную функцию.

После преобразования Чарнеса-Купера новая целевая функция принимает строгий линейный вид Z = C*Y + a*t. Исходные ограничения A*X <= B также умножаются на t и переписываются в виде A*Y - B*t <= 0. Главным дополнением становится новое балансовое уравнение-ограничение, гарантирующее правильное масштабирование: D*Y + b*t = 1. Полученная расширенная модель является чистейшей задачей линейного программирования, которую можно мгновенно решить стандартным симплекс-методом в любой аналитической программе. После получения оптимальных значений новых переменных (Y_opt и t_opt), аналитик производит обратное преобразование X_opt = Y_opt / t_opt, восстанавливая истинные значения искомых параметров для реального производственного процесса.

Альтернативным подходом к решению задач дробно-линейного программирования является алгоритм Исибелла-Беллмана, основанный на последовательном (итерационном) обновлении параметров. На каждом шаге алгоритм фиксирует значение знаменателя как константу и решает возникающую линейную задачу, после чего пересчитывает константу и повторяет цикл до достижения сходимости. Дробно-линейное программирование нашло колоссальное применение в банковском секторе для оптимизации портфелей ценных бумаг (максимизация коэффициента Шарпа), в здравоохранении для минимизации стоимости обслуживания одного пациента и в макроэкономике для вычисления оптимальных пропорций распределения государственного бюджета.