В математическая оптимизация , дробное программирование является обобщением дробно-линейное программирование . В целевая функция в дробной программе - это соотношение двух функций, которые, в общем, являются нелинейными. Оптимизируемый коэффициент часто описывает некоторую эффективность системы.
Определение
Позволять ж , грамм , час j , j = 1 , … , м { displaystyle f, g, h_ {j}, j = 1, ldots, m} действительные функции определен на множестве S 0 ⊂ р п { Displaystyle mathbf {S} _ {0} subset mathbb {R} ^ {n}} S = { Икс ∈ S 0 : час j ( Икс ) ≤ 0 , j = 1 , … , м } { displaystyle mathbf {S} = {{ boldsymbol {x}} in mathbf {S} _ {0}: h_ {j} ({ boldsymbol {x}}) leq 0, j = 1 , ldots, m }} нелинейная программа
максимизировать Икс ∈ S ж ( Икс ) грамм ( Икс ) , { displaystyle { underset {{ boldsymbol {x}} in mathbf {S}} { text {maximize}}} quad { frac {f ({ boldsymbol {x}})} {g ( { boldsymbol {x}})}},} куда грамм ( Икс ) > 0 { displaystyle g ({ boldsymbol {x}})> 0} S { displaystyle mathbf {S}}
Вогнутые дробные программы
Дробная программа, в которой ж неотрицательный и вогнутый, грамм положительный и выпуклый, а S это выпуклый набор называется вогнутая дробная программа . Если грамм аффинно, ж не должно быть ограничено знаком. Дробно-линейная программа - это частный случай дробно-вогнутой программы, в которой все функции ж , грамм , час j , j = 1 , … , м { displaystyle f, g, h_ {j}, j = 1, ldots, m}
Характеристики Функция q ( Икс ) = ж ( Икс ) / грамм ( Икс ) { displaystyle q ({ boldsymbol {x}}) = f ({ boldsymbol {x}}) / г ({ boldsymbol {x}})} квазивогнутый на S . Если ж и грамм дифференцируемы, то q является псевдовогнутая . В дробно-линейной программе целевая функция псевдолинейный .
Преобразование в вогнутую программу Преобразованием у = Икс грамм ( Икс ) ; т = 1 грамм ( Икс ) { displaystyle { boldsymbol {y}} = { frac { boldsymbol {x}} {g ({ boldsymbol {x}})}}; t = { frac {1} {g ({ boldsymbol { Икс}})}}} вогнутая программа [1]
максимизировать у т ∈ S 0 т ж ( у т ) при условии т грамм ( у т ) ≤ 1 , т ≥ 0. { 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}}} Если грамм аффинно, первое ограничение заменяется на т грамм ( у т ) = 1 { displaystyle tg ({ frac { boldsymbol {y}} {t}}) = 1} ж неотрицательный может быть опущен.
Двойственность Лагранжиан, двойственный к эквивалентной вогнутой программе, есть
свести к минимуму ты Как дела Икс ∈ S 0 ж ( Икс ) − ты Т час ( Икс ) грамм ( Икс ) при условии ты я ≥ 0 , я = 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 (связь ) Рекомендации
Авриэль, Мардохей; Diewert, Walter E .; Шейбл, Зигфрид; Занг, Израиль (1988). Обобщенная вогнутость . Пленум Пресс. Шейбл, Зигфрид (1983). «Дробное программирование». Zeitschrift für Operations Research . 27 : 39–54. Дои :10.1007 / bf01916898 . 
