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

В математической оптимизации линейно -дробное программирование ( ЛДП ) является обобщением линейного программирования (ЛП). В то время как целевая функция в линейной программе является линейной функцией , целевая функция в линейно-дробной программе является отношением двух линейных функций. Линейную программу можно рассматривать как частный случай линейно-дробной программы, в которой знаменатель является постоянной функцией 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 \альфа ,\бета \in \mathbb {R} } { х | г Т х + β > 0 } {\displaystyle \{\mathbf {x} |\mathbf {d} ^{T}\mathbf {x} +\бета >0\}}

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

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

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

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

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

максимизировать с Т у + α т при условии А у ≤ б т г Т у + β т = 1 т ≥ 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} }

у = 1 г Т х + β ⋅ х и т = 1 г Т х + β . {\displaystyle \mathbf {y} ={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}\cdot \mathbf {x} \quad {\text{и}}\quad t={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}.}

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

х = 1 т у . {\displaystyle \mathbf {x} ={\frac {1}{t}}\mathbf {y} .}

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

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

минимизировать λ при условии А Т ты + λ г = с − б Т ты + λ β ≥ α ты ∈ Р + м , λ ∈ Р , {\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. ^ ab Чарнс, А.; Купер, 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 . doi : 10.1007/BF02026600. MR  0351464. S2CID  28885670.
  4. ^ Шайбл, Зигфрид (1976). «Дробное программирование I: Двойственность». Management Science . 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. Bibcode :1999SIAMR..41..795K. 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Linear-fractional_programming&oldid=1262820222"