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

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

Определение

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

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

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

Вогнутые дробные программы

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

Свойства

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

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

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

${\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 аффинно, первое ограничение меняется на $tg({\frac {\boldsymbol {y}}{t}})=1$ и предположение о g положительности можно отбросить. Кроме того, это упрощает $g({\boldsymbol {y}})=1$.

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

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

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

Ссылки

• Авриэль, Мордехай; Диверт, Уолтер Э.; Шайбле, Зигфрид; Занг, Израиль (1988). Генерализованная вогнутость . Пленум Пресс.
• Шайбле, Зигфрид (1983). «Дробное программирование». Журнал исследования операций . 27 :39–54. дои : 10.1007/bf01916898 . S2CID   28766871 .