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

В математической оптимизации , дробным программирование представляет собой обобщение дробно-линейного программирования . Целевая функция в программе дробной представляет собой отношение двух функций, вообще говоря, нелинейные. Оптимизируемый коэффициент часто описывает некоторую эффективность системы.

Определение [ править ]

Позвольте быть действительными функциями, определенными на множестве . Пусть . Нелинейная программа${\ displaystyle f, g, h_ {j}, j = 1, \ ldots, m}$${\ Displaystyle \ mathbf {S} _ {0} \ subset \ mathbb {R} ^ {n}}$${\displaystyle \mathbf {S} =\{{\boldsymbol {x}}\in \mathbf {S} _{0}:h_{j}({\boldsymbol {x}})\leq 0,j=1,\ldots ,m\}}$

${\displaystyle {\underset {{\boldsymbol {x}}\in \mathbf {S} }{\text{maximize}}}\quad {\frac {f({\boldsymbol {x}})}{g({\boldsymbol {x}})}},}$

где на , называется дробной программой.${\displaystyle g({\boldsymbol {x}})>0}$${\displaystyle \mathbf {S} }$

Вогнутые дробные программы [ править ]

Дробная программа, в которой f неотрицательна и вогнута, g положительна и выпукла, а S - выпуклое множество , называется вогнутой дробной программой . Если g аффинно, знак f не должен быть ограничен. Дробно-линейная программа - это частный случай дробно-вогнутой программы, в которой все функции аффинны.${\displaystyle f,g,h_{j},j=1,\ldots ,m}$

Свойства [ править ]

Функция является semistrictly квазивогнутая на S . Если е и г дифференцируемы, то д является псевдовогнутым . В дробно-линейной программе целевая функция является псевдолинейной .${\displaystyle q({\boldsymbol {x}})=f({\boldsymbol {x}})/g({\boldsymbol {x}})}$

Преобразование в вогнутую программу [ править ]

Путем преобразования любую вогнутую дробную программу можно преобразовать в эквивалентную вогнутую программу без параметров ^[1]${\displaystyle {\boldsymbol {y}}={\frac {\boldsymbol {x}}{g({\boldsymbol {x}})}};t={\frac {1}{g({\boldsymbol {x}})}}}$

${\displaystyle {\begin{aligned}{\underset {{\frac {\boldsymbol {y}}{t}}\in \mathbf {S} _{0}}{\text{maximize}}}\quad &tf\left({\frac {\boldsymbol {y}}{t}}\right)\\{\text{subject to}}\quad &tg\left({\frac {\boldsymbol {y}}{t}}\right)\leq 1,\\&t\geq 0.\end{aligned}}}$

Если g аффинно, первое ограничение изменяется на, и предположение о неотрицательности f может быть отброшено.${\displaystyle tg({\frac {\boldsymbol {y}}{t}})=1}$

Двойственность [ править ]

Лагранжиан, двойственный к эквивалентной вогнутой программе, есть

${\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{subject to}}\quad &u_{i}\geq 0,\quad i=1,\dots ,m.\end{aligned}}}$

Заметки [ править ]

Ссылки [ править ]

• Авриэль, Мардохей; Diewert, Walter E .; Шейбл, Зигфрид; Занг, Израиль (1988). Обобщенная вогнутость . Пленум Пресс.
• Schaible, Зигфрид (1983). «Дробное программирование». Zeitschrift für Operations Research . 27 : 39–54. DOI : 10.1007 / bf01916898 .