Задачи дробно-линейного программирования

Если целевая функция представляет собой отношение линейных функций, а все условия линейные, то задача относится к классу задач дробно-линейного программирования. Целевая функция имеет вид:

Такая функция легко преобразуется в линейную, если ее знаменатель при всех допустимых значениях переменных строго положителен. Для этого введем новую переменную r следующим образом:

При оговоренном условии она может быть только больше нуля. Тогда функция принимает вид Замена: -> Получили линейную функцию от n неотрицательных переменных y_j и одной положительной переменной r. Эта функция должна рассматриваться вместе с условием: или после замены

Чтобы завершить построение эквивалентной линейной модели, следует ограничения задачи записать в новых переменных. Для этого умножим обе части каждого ограничения

на r: (замена) ->

В результате преобразований имеем задачу ЛП. Получив ее решение одним из методов ЛП, вычисляем исходные переменные:

Возможность перехода к линейной задаче геометрически обусловлена тем, что линии уровня дробно-линейной функции описываются линейным уравнением. Пусть . Тогда: или - уравнения уровня, с изменением они не перемещаются параллельно, а поворачиваются вокруг мн-ва вращения– это мн-во точек размерности n -2, образов. пересечением нулевых линий уровня числителя и знаменателя:

Пример: Представим графически следующую задачу

; 3x₁ + 2x₂ ³ 6, 0£ x₁ £ 3, 0£ x₂ £ 3.

Ур-я нулевых линий уровня числителя и знаменателя образуют систему:

из которой находим точку вращения: x ₁= x ₂=1/3. На рис. это точка А. Нулевые линии показаны пунктиром, а направление поворота, в котором целевая функция возрастает, – стрелками. Отсюда ясно, что оптимальное решение достигается в вершине B: