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

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

Определение

Пусть — действительные функции, определенные на множестве . Пусть . Нелинейная программа ${\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}$

Характеристики

Функция является полустрого квазивогнутой на S . Если f и g дифференцируемы, то q является псевдовогнутой . В дробно-линейной программе целевая функция является псевдолинейной . ${\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 аффинен, первое ограничение изменяется на и предположение о том, что g положителен, может быть отброшено. Кроме того, это упрощается до . ${\displaystyle tg({\frac {\boldsymbol {y}}{t}})=1}$ ${\displaystyle g({\boldsymbol {y}})=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}}}$

Примечания

1. Шайбле, Зигфрид (1974). «Выпуклые эквивалентные и двойственные программы без параметров». Zeitschrift für Operations Research . 18 (5): 187–196. дои : 10.1007/BF02026600. MR  0351464. S2CID  28885670.

Ссылки

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