ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ЗАДАЧА
— задача минимизации (максимизации) дробно-линейной функции
при линейных ограничениях
где А — матрица
-
-мерные векторы, b —
-мерный вектор,
вещественные числа,
означает неотрицательность всех компонент вектора
Один из возможных подходов к исследованию
п. з. состоит в следующем: пусть X — множество, определяемое ограничениями (2). Д.-л. п. з. назовем допустимой, если X не пусто и
отлично от нуля хотя бы в одной точке этого множества. При решении задачи минимизации рассматриваются две вспомогательные задачи программирования линейного.
Доказано, что для того, чтобы Д.-л. п. з. была допустимой, необходимо и достаточно, чтобы по крайней мере у одной из задач — у 1-й или у 2-й — существовал допустимый план с
при этом, если допустимый план у задачи 1-й или 2-й существует, то у соответствующей задачи существует и допустимый план с
если
п. з. допустима, а множество допустимых планов одной из задач — 1-й или
пусто, то
совпадает с оптим. значением целевой ф-ции другой задачи. Если Д.-л. п. з. допустима, а задачи 1-я и 2-я имеют допустимые планы, то
совпадает с минимумом среди оптим. значений целевых ф-ций обеих задач — и 1-й и 2-й. Эти утверждения сводят Д.-л. п. з. к решению двух задач линейного программирования. Переход от переменных
к переменным
осуществляется по ф-лам
Д.-л. п. з. часто возникают в эконом, приложениях, когда в качестве целевой ф-ции принимается «относительная эффективность» (напр., прибыль, отнесенная к единице затрат).
Н. 3. Шор.