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

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

В общем случае целевая функция имеет вид (28)

Такая функция легко преобразуется в линейную, если ее знаменатель при всех допустимых значениях переменных строго положителен. Для этого введем новую переменную r (29). Очевидно, что при оговоренном условии она может быть только больше нуля. Тогда функция (28) принимает вид Произведя замену произведения переменных (30) окончательно имеем (31) Получили линейную функцию от n неотрицательных переменных y_j и одной положительной переменной r. Эта функция должна рассматриваться вместе с условием, следующим из (29): или после замены (30) (32) Следует ограничения задачи записать в новых переменных. Для этого умножим обе части каждого ограничения на r и, произведя замену, получаем (33) В результате преобразований имеем задачу ЛП с критерием (31), ограничениями (32), (33) и переменными r > 0, y_j ³ 0, " j. Воспользовавшись (30) вернемся к исходным переменным. Возможность перехода к линейной задаче геометрически обусловлена тем, что линии уровня дробно-линейной функции описываются линейным уравнением. , из (28) следует или . (34) При изменением возникает поворот вокруг мн-ва вращения. Мн-во вращения – это множество точек, образованное пересечением нулевых линий уровня числителя и знаменателя: n=2 – точка, n=3 - прямая