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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle \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 }}.}$

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

Примечания

1. Чарнс, А.; Купер, WW (1962). «Программирование с линейными дробными функционалами». Naval Research Logistics Quarterly . 9 (3–4): 181–186. doi :10.1002/nav.3800090303. MR  0152370.
2. Бойд, Стивен П.; Ванденберг, Ливен (2004). Выпуклая оптимизация (PDF) . Cambridge University Press. стр. 151. ISBN 978-0-521-83378-3. Получено 15 октября 2011 г. .
3. Шайбле, Зигфрид (1974). «Выпуклые эквивалентные и двойственные программы без параметров». Zeitschrift für Operations Research . 18 (5): 187–196. дои : 10.1007/BF02026600. MR  0351464. S2CID  28885670.
4. Шайбл, Зигфрид (1976). «Дробное программирование I: Двойственность». Наука управления . 22 (8): 858–867. doi :10.1287/mnsc.22.8.858. JSTOR  2630017. MR  0421679.
5. Глава пятая: Craven, BD (1988). Дробное программирование . Серия Sigma в прикладной математике. Том 4. Берлин: Heldermann Verlag. С. 145. ISBN 978-3-88538-404-5. МР  0949209.
6. Крук, Серж; Волкович, Генри (1999). «Псевдолинейное программирование». SIAM Review . 41 (4): 795–805. CiteSeerX 10.1.1.53.7355 . doi :10.1137/S0036144598335259. JSTOR  2653207. MR  1723002. 
7. Матис, Фрэнк Х.; Матис, Ленора Джейн (1995). «Алгоритм нелинейного программирования для управления больницей». Обзор SIAM . 37 (2): 230–234. doi :10.1137/1037046. JSTOR  2132826. MR  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. Препринт постскриптума. 

Источники

• Murty, Katta G. (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.
• Stancu-Minasian, IM (1997). Дробное программирование: теория, методы и приложения . Математика и ее приложения. Том 409. Перевод Виктора Джурджуциу с румынского 1992 года. Дордрехт: Kluwer Academic Publishers Group. стр. viii+418. ISBN 978-0-7923-4580-0. МР  1472981.