ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ЗАДАЧА

— задача минимизации (максимизации) дробно-линейной функции

при линейных ограничениях

где А — матрица - -мерные векторы, b — -мерный вектор, вещественные числа, означает неотрицательность всех компонент вектора

Один из возможных подходов к исследованию п. з. состоит в следующем: пусть X — множество, определяемое ограничениями (2). Д.-л. п. з. назовем допустимой, если X не пусто и отлично от нуля хотя бы в одной точке этого множества. При решении задачи минимизации рассматриваются две вспомогательные задачи программирования линейного.

Доказано, что для того, чтобы Д.-л. п. з. была допустимой, необходимо и достаточно, чтобы по крайней мере у одной из задач — у 1-й или у 2-й — существовал допустимый план с при этом, если допустимый план у задачи 1-й или 2-й существует, то у соответствующей задачи существует и допустимый план с если п. з. допустима, а множество допустимых планов одной из задач — 1-й или пусто, то совпадает с оптим. значением целевой ф-ции другой задачи. Если Д.-л. п. з. допустима, а задачи 1-я и 2-я имеют допустимые планы, то совпадает с минимумом среди оптим. значений целевых ф-ций обеих задач — и 1-й и 2-й. Эти утверждения сводят Д.-л. п. з. к решению двух задач линейного программирования. Переход от переменных к переменным осуществляется по ф-лам

Д.-л. п. з. часто возникают в эконом, приложениях, когда в качестве целевой ф-ции принимается «относительная эффективность» (напр., прибыль, отнесенная к единице затрат).

Н. 3. Шор.