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

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

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

{\begin{aligned}{\text{maximize}}\quad &{\frac {\mathbf {c} ^{T}\mathbf {x} +\alpha }{\mathbf {d} ^{T}\mathbf {x} +\beta }}\\{\text{subject to}}\quad &A\mathbf {x} \leq \mathbf {b} ,\end{aligned}}

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

Мотивация в сравнении с линейным программированием

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

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

Любую дробно-линейную программу можно преобразовать в линейную программу, предполагая, что допустимая область непуста и ограничена, с помощью преобразования Чарнса-Купера . ^[1] Основная идея состоит в том, чтобы ввести новую неотрицательную переменную. $t$ в программу, которая будет использоваться для изменения масштаба констант, задействованных в программе ( $\alpha ,\beta ,\mathbf {b}$ ). Это позволяет потребовать, чтобы знаменатель целевой функции ( $\mathbf {d} ^{T}\mathbf {x} +\beta$ ) равно 1. (Чтобы понять преобразование, полезно рассмотреть более простой частный случай с $\alpha =\beta =0$ .)

Формально линейная программа, полученная с помощью преобразования Чарнса-Купера, использует преобразованные переменные $\mathbf {y} \in \mathbb {R} ^{n}$ и $t\geq 0$ :

{\begin{aligned}{\text{maximize}}\quad &\mathbf {c} ^{T}\mathbf {y} +\alpha t\\{\text{subject to}}\quad &A\mathbf {y} \leq \mathbf {b} t\\&\mathbf {d} ^{T}\mathbf {y} +\beta t=1\\&t\geq 0.\end{aligned}}

Решение $\mathbf {x}$ к исходной дробно-линейной программе можно перевести к решению преобразованной линейной программы посредством равенств

\mathbf {y} ={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}\cdot \mathbf {x} \quad {\text{and}}\quad t={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}.

И наоборот, решение для $\mathbf {y}$ и $t$ преобразованной линейной программы можно перевести в решение исходной дробно-линейной программы через

\mathbf {x} ={\frac {1}{t}}\mathbf {y} .

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

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

{\begin{aligned}{\text{minimize}}\quad &\lambda \\{\text{subject to}}\quad &A^{T}\mathbf {u} +\lambda \mathbf {d} =\mathbf {c} \\&-\mathbf {b} ^{T}\mathbf {u} +\lambda \beta \geq \alpha \\&\mathbf {u} \in \mathbb {R} _{+}^{m},\lambda \in \mathbb {R} ,\end{aligned}}

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

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

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

Примечания

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

Источники

Мурти, Катта Г. (1983). «3.10 Дробное программирование (стр. 160–164)». Линейное программирование . Нью-Йорк: John Wiley & Sons, Inc., стр. xix+482. ISBN 978-0-471-09725-9 . МР 0720547 .

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

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

[CC-1] Jump up to: ^а ^б Чарнс, А.; Купер, WW (1962). «Программирование с использованием дробно-линейных функционалов». Ежеквартальный журнал военно-морских исследований по логистике . 9 (3–4): 181–186. дои : 10.1002/nav.3800090303 . МР 0152370 .

[BV-2] Бойд, Стивен П.; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF) . Издательство Кембриджского университета. п. 151. ИСБН 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. Берлин: Хелдерманн Верлаг. п. 145. ИСБН 978-3-88538-404-5 . МР 0949209 .

[6] Крук, Серж; Волкович, Генри (1999). «Псевдолинейное программирование». Обзор СИАМ . 41 (4): 795–805. CiteSeerX 10.1.1.53.7355 . дои : 10.1137/S0036144598335259 . JSTOR 2653207 . МР 1723002 .

[7] Матис, Фрэнк Х.; Матис, Ленора Джейн (1995). «Алгоритм нелинейного программирования для управления больницей». Обзор СИАМ . 37 (2): 230–234. дои : 10.1137/1037046 . JSTOR 2132826 . МР 1343214 . S2CID 120626738 .

[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 . Збл 0953.90055 . Препринт постскриптума .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]