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