Дробное программирование - Википедия - Fractional programming

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

Определение

Позволять ${ 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}}$ , называется дробной программой.

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

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

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

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

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

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

{ displaystyle { begin {align} { 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 {align}}}

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

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

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

{ displaystyle { begin {align} { underset { boldsymbol {u}} { text {minim}}} 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 {выровнено}}}

Примечания

^ Шейбл, Зигфрид (1974). "Выпуклые эквивалентные и двойные программы без параметров". Zeitschrift für Operations Research. 18 (5): 187–196. Дои:10.1007 / BF02026600. МИСТЕР 0351464.CS1 maint: ref = harv (связь)