В математической оптимизации дробное программирование является обобщением дробно-линейного программирования . Целевая функция в дробной программе представляет собой отношение двух функций, которые в общем случае нелинейны. Оптимизируемое соотношение часто описывает некоторую эффективность системы.
Определение
Пусть – вещественные функции , определенные на множестве . Позволять . Нелинейная программа![{\ displaystyle f, g, h_ {j}, j = 1, \ ldots, m}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbf {S} _{0}\subset \mathbb {R} ^{n}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbf {S} =\{{\boldsymbol {x}}\in \mathbf {S} _{0}:h_{j}({\boldsymbol {x}})\leq 0,j=1 ,\ldots ,м\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\underset {{\boldsymbol {x}}\in \mathbf {S} }{\text{maximize}}}\quad {\frac {f({\boldsymbol {x}})}{g( {\boldsymbol {x}})}},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
где на , называется дробной программой.![{\displaystyle g({\boldsymbol {x}})>0}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbf {S} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Вогнутые дробные программы
Дробная программа, в которой f неотрицательна и вогнута, g положительна и выпукла, а S — выпуклое множество , называется вогнутой дробной программой . Если g аффинен, f не обязательно должен быть ограничен по знаку. Дробно-линейная программа — это частный случай вогнутой дробной программы, в которой все функции аффинны.![{\ displaystyle f, g, h_ {j}, j = 1, \ ldots, m}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Характеристики
Функция полустрого квазивогнутая на S. _ Если f и g дифференцируемы, то q псевдовогнутая . В дробно-линейной программе целевая функция псевдолинейна .![{\displaystyle q({\boldsymbol {x}})=f({\boldsymbol {x}})/g ({\boldsymbol {x}})}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Преобразование в вогнутую программу
Путем преобразования любую вогнутую дробную программу можно преобразовать в эквивалентную вогнутую программу без параметров [1]![{\displaystyle {\boldsymbol {y}}={\frac {\boldsymbol {x}}{g({\boldsymbol {x}})}};t = {\frac {1}{g({\boldsymbol { Икс}})}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle {\begin{aligned}{\underset {{\frac {\boldsymbol {y}}{t}}\in \mathbf {S} _{0}}{\text{maximize}}}\quad &tf \left({\frac {\boldsymbol {y}}{t}}\right)\\{\text{с учетом}}\quad &tg\left({\frac {\boldsymbol {y}}{t}} \right)\leq 1,\\&t\geq 0.\end{aligned}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Если g аффинно, первое ограничение заменяется на и предположение о положительности g может быть отброшено. Кроме того, это упрощается до .![{\displaystyle tg({\frac {\boldsymbol {y}}{t}})=1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle g({\boldsymbol {y}})=1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Двойственность
Лагранжев, двойственный эквивалентной вогнутой программе, равен
![{\displaystyle {\begin{aligned}{\underset {\boldsymbol {u}}{\text{minimize}}}\quad &{\underset {{\boldsymbol {x}}\in \mathbf {S} _{ 0}}{\operatorname {sup} }}{\frac {f({\boldsymbol {x}})-{\boldsymbol {u}}^{T}{\boldsymbol {h}}({\boldsymbol {x }})}{g({\boldsymbol {x}})}}\\{\text{с учетом}}\quad &u_{i}\geq 0,\quad i=1,\dots ,m.\end {выровнено}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Примечания
- ^ Шайбле, Зигфрид (1974). «Выпуклые эквивалентные и двойственные программы без параметров». Zeitschrift für Operations Research . 18 (5): 187–196. дои : 10.1007/BF02026600. MR 0351464. S2CID 28885670.
Рекомендации
- Авриэль, Мордехай; Диверт, Уолтер Э.; Шайбле, Зигфрид; Занг, Израиль (1988). Генерализованная вогнутость . Пленум Пресс.
- Шайбле, Зигфрид (1983). «Дробное программирование». Zeitschrift für Operations Research . 27 : 39–54. дои : 10.1007/bf01916898. S2CID 28766871.