Линейно-дробное программирование - Linear-fractional programming

В математическая оптимизация, дробно-линейное программирование (LFP) является обобщением линейное программирование (LP). В то время как целевая функция в линейной программе - это линейная функция, целевая функция в дробно-линейной программе представляет собой отношение двух линейных функций. Линейную программу можно рассматривать как частный случай дробно-линейной программы, в которой знаменателем является постоянная функция.

Отношение к линейному программированию

И линейное программирование, и дробно-линейное программирование представляют задачи оптимизации с использованием линейных уравнений и линейных неравенств, которые для каждого экземпляра задачи определяют возможный набор. У дробно-линейных программ более богатый набор целевых функций. Неформально линейное программирование вычисляет политику, обеспечивающую наилучший результат, например максимальную прибыль или наименьшие затраты. Напротив, дробно-линейное программирование используется для достижения наивысшего соотношение От результата к затратам - соотношение, представляющее наивысшую эффективность. Например, в контексте LP мы максимизируем целевую функцию прибыль = доход - стоимость и может получить максимальную прибыль в размере 100 долларов (= 1100 долларов дохода - 1000 долларов затрат). Таким образом, в LP мы имеем эффективность 100 $ / 1000 $ = 0,1. Используя LFP, мы можем получить эффективность 10 долларов / 50 долларов = 0,2 с прибылью всего в 10 долларов, но для этого потребуется всего 50 долларов инвестиций.

Определение

Формально дробно-линейная программа определяется как проблема максимизации (или минимизации) отношения аффинные функции через многогранник,

${displaystyle {egin{aligned}{ ext{maximize}}quad &{frac {mathbf {c} ^{T}mathbf {x} +alpha }{mathbf {d} ^{T}mathbf {x} +eta }}{ ext{subject to}}quad &Amathbf {x} leq mathbf {b} ,end{aligned}}}$

куда ${displaystyle mathbf {x} in mathbb {R} ^{n}}$ представляет собой вектор переменных, которые необходимо определить, ${displaystyle mathbf {c} ,mathbf {d} in mathbb {R} ^{n}}$ и ${displaystyle mathbf {b} in mathbb {R} ^{m}}$ - векторы (известных) коэффициентов, ${displaystyle Ain mathbb {R} ^{m imes n}}$ - (известная) матрица коэффициентов и ${displaystyle alpha ,eta in mathbb {R} }$ являются константами. Ограничения должны ограничивать возможный регион к ${displaystyle {mathbf {x} |mathbf {d} ^{T}mathbf {x} +eta >0}}$, т.е. область, на которой знаменатель положителен.^[1][2] В качестве альтернативы знаменатель целевой функции должен быть строго отрицательным во всей допустимой области.

Преобразование в линейную программу

В предположении, что допустимая область непуста и ограничена, преобразование Чарнса-Купера^[1]

${displaystyle mathbf {y} ={frac {1}{mathbf {d} ^{T}mathbf {x} +eta }}cdot mathbf {x} ;;;;t={frac {1}{mathbf {d} ^{T}mathbf {x} +eta }}}$

переводит дробно-линейную программу выше в эквивалентную линейную программу:

${displaystyle {egin{aligned}{ ext{maximize}}quad &mathbf {c} ^{T}mathbf {y} +alpha t{ ext{subject to}}quad &Amathbf {y} leq mathbf {b} t&mathbf {d} ^{T}mathbf {y} +eta t=1&tgeq 0.end{aligned}}}$

Тогда решение для ${displaystyle mathbf {y} }$ и ${displaystyle t}$ дает решение исходной задачи как

${displaystyle mathbf {x} ={frac {1}{t}}mathbf {y} .}$

Двойственность

Пусть двойные переменные связанные с ограничениями ${displaystyle Amathbf {y} -mathbf {b} tleq mathbf {0} }$ и ${displaystyle mathbf {d} ^{T}mathbf {y} +eta t-1=0}$ обозначать ${displaystyle mathbf {u} }$ и ${displaystyle lambda }$, соответственно. Тогда двойственный к LFP выше будет ^[3][4]

${displaystyle {egin{aligned}{ ext{minimize}}quad &lambda { ext{subject to}}quad &A^{T}mathbf {u} +lambda mathbf {d} =mathbf {c} &-mathbf {b} ^{T}mathbf {u} +lambda eta geq alpha &mathbf {u} in mathbb {R} _{+}^{m},lambda in mathbb {R} ,end{aligned}}}$

которая является ЛП и совпадает с двойственной эквивалентной линейной программы, полученной в результате преобразования Чарнса-Купера.

Свойства и алгоритмы

Целевая функция в дробно-линейной задаче одновременно является квазивогнутой и квазивыпуклый (следовательно, квазилинейный) с монотонный свойство, псевдовыпуклость, что является более сильным свойством, чем квазивыпуклость. Дробно-линейная целевая функция бывает как псевдовыпуклой, так и псевдовогнутой, поэтому псевдолинейный. Поскольку LFP может быть преобразован в LP, его можно решить с помощью любого метода решения LP, такого как симплексный алгоритм (из Джордж Б. Данциг ),^[5][6][7][8] то перекрестный алгоритм,^[9] или же методы внутренней точки.

Примечания

1. Charnes, A .; Купер, У. (1962). «Программирование с помощью дробно-линейных функционалов». Ежеквартально по логистике военно-морских исследований. 9 (3–4): 181–186. Дои:10.1002 / nav.3800090303. МИСТЕР  0152370.
2. Бойд, Стивен П .; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF). Издательство Кембриджского университета. п. 151. ISBN  978-0-521-83378-3. Получено 15 октября, 2011.
3. Шейбл, Зигфрид (1974). "Выпуклые эквивалентные и двойные программы без параметров". Zeitschrift für Operations Research. 18 (5): 187–196. Дои:10.1007 / BF02026600. МИСТЕР  0351464. S2CID  28885670.
4. Шейбл, Зигфрид (1976). «Дробное программирование I: Двойственность». Наука управления. 22 (8): 858–867. Дои:10.1287 / mnsc.22.8.858. JSTOR  2630017. МИСТЕР  0421679.
5. Глава пятая: Крейвен, Б. Д. (1988). Дробное программирование. Сигма-серия в прикладной математике. 4. Берлин: Heldermann Verlag. п. 145. ISBN  978-3-88538-404-5. МИСТЕР  0949209.
6. Крук, Серж; Волкович, Генри (1999). «Псевдолинейное программирование». SIAM Обзор. 41 (4): 795–805. CiteSeerX  10.1.1.53.7355. Дои:10.1137 / S0036144598335259. JSTOR  2653207. МИСТЕР  1723002.
7. Матис, Фрэнк Х .; Матис, Ленора Джейн (1995). «Алгоритм нелинейного программирования для управления больницей». SIAM Обзор. 37 (2): 230–234. Дои:10.1137/1037046. JSTOR  2132826. МИСТЕР  1343214.
8. Мурти (1983), Глава 3.20 (стр. 160–164) и стр. 168 и 179)
9. Иллеш, Тибор; Сирмаи, Акос; Терлаки, Тамаш (1999). «Метод конечных крестов для гиперболического программирования». Европейский журнал операционных исследований. 114 (1): 198–214. CiteSeerX  10.1.1.36.7090. Дои:10.1016 / S0377-2217 (98) 00049-6. Zbl  0953.90055. Постскриптум препринт.

Рекомендации

• Крейвен, Б. Д. (1988). Дробное программирование. Сигма-серия в прикладной математике. 4. Берлин: Heldermann Verlag. п. 145. ISBN  978-3-88538-404-5. МИСТЕР  0949209.
• Иллеш, Тибор; Сирмаи, Акос; Терлаки, Тамаш (1999). «Метод конечных крестов для гиперболического программирования». Европейский журнал операционных исследований. 114 (1): 198–214. CiteSeerX  10.1.1.36.7090. Дои:10.1016 / S0377-2217 (98) 00049-6. Zbl  0953.90055. Постскриптум препринт.
• Крук, Серж; Волкович, Генри (1999). «Псевдолинейное программирование». SIAM Обзор. 41 (4): 795–805. Дои:10.1137 / S0036144598335259. JSTOR  2653207. МИСТЕР  1723002.
• Матис, Фрэнк Х .; Матис, Ленора Джейн (1995). «Алгоритм нелинейного программирования для управления больницей». SIAM Обзор. 37 (2): 230–234. Дои:10.1137/1037046. JSTOR  2132826. МИСТЕР  1343214.
• Мурти, Катта Г. (1983). «3.10 Дробное программирование (стр. 160–164)». Линейное программирование. Нью-Йорк: John Wiley & Sons, Inc., стр. Xix + 482. ISBN  978-0-471-09725-9. МИСТЕР  0720547.

дальнейшее чтение

• Баялинов, Э. Б. (2003). Дробно-линейное программирование: теория, методы, приложения и программное обеспечение. Бостон: Kluwer Academic Publishers.
• Баррос, Ана Изабель (1998). Методы дискретного и дробного программирования для моделей местоположения. Комбинаторная оптимизация. 3. Дордрехт: Kluwer Academic Publishers. С. xviii + 178. ISBN  978-0-7923-5002-6. МИСТЕР  1626973.
• Мартос, Бела (1975). Нелинейное программирование: теория и методы. Амстердам-Оксфорд: издательство North-Holland Publishing Co., стр. 279. ISBN  978-0-7204-2817-9. МИСТЕР  0496692.
• Шейбл, С. (1995). «Дробное программирование». В книге Райнера Хорста и Паноса М. Пардалоса (ред.). Справочник по глобальной оптимизации. Невыпуклая оптимизация и ее приложения. 2. Дордрехт: Kluwer Academic Publishers. С. 495–608. ISBN  978-0-7923-3120-9. МИСТЕР  1377091.
• Станку-Минасян, И. М. (1997). Дробное программирование: теория, методы и приложения. Математика и ее приложения. 409. Перевод Виктора Джурджутиу с румынского 1992 года. Дордрехт: Kluwer Academic Publishers Group. С. viii + 418. ISBN  978-0-7923-4580-0. МИСТЕР  1472981.

Программного обеспечения

• WinGULF - обучающий интерактивный решатель линейного и дробно-линейного программирования с множеством специальных опций (поворот, ценообразование, переменные ветвления и т. Д.)
• JOptimizer - библиотека выпуклой оптимизации Java (с открытым исходным кодом)