Дробно-линейное программирование

Дробно-линейное программирование (ДЛП) — математическая дисциплина, посвящённая теории и методам решения задач об экстремумах отношений линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

ДЛП является обобщением линейного программирования (ЛП) и, в то же время, частным случаем математического программирования. Как и в ЛП, принято разделение на общую задачу ДЛП и специальные задачи ДЛП (например, транспортная задача ДЛП, целочисленная задача ДЛП и т. д.).

Алгоритмы решения общей задачи ДЛП

Наиболее известным и широко применяемым на практике алгоритмом решения общей задачи ДЛП является специальное обобщение симплексного метода, разработанное венгерским математиком B.Martos в начале 1960-х годов. Кроме того, для решения задачи ДЛП может быть применён подход предложенный американскими математиками A.Charnes и W.W.Cooper — суть их метода состоит в использовании специального преобразования. В результате этого преобразования вместо исходной задачи ДЛП получается некоторая задача ЛП со специальной структурой ограничений, которая может быть решена соответствующими методами линейного программирования. Из полученного решения задачи ЛП путём обратного преобразования получается решение исходной задачи. Известны также параметрический метод Динкельбаха (W.Dinkelbach) и метод зигзага Иллеша (T.Illés)

Литература

Erik Bajalinov, Linear-Fractional Programming: Theory, Methods, Applications and Software. «Kluwer Academic Publishers», 2003.