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

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

• 1 Определение
• 2 Вогнутые дробные программы
  • 2.1 Свойства
  • 2.2 Преобразование в вогнутую программу
  • 2.3 Двойственность
• 3 Примечания
• 4 Ссылки

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

$максимизировать\; x\; \in \; S\; f\; (x)\; g\; (x),\; \{\backslash \; displaystyle\; \{\backslash \; underset\; \{\{\backslash \; boldsymbol\; \{x\}\}\; \backslash \; in\; \backslash \; mathbf\; \{S\}\}\; \{\backslash \; text\; \{maximize\}\; \}\}\; \backslash \; quad\; \{\backslash \; frac\; \{f\; (\{\backslash \; boldsymbol\; \{x\}\})\}\; \{g\; (\{\backslash \; boldsymbol\; \{x\}\})\}\},\}$

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

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

Свойства

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

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

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

$maximize\; yt\; \in \; S\; 0\; tf\; (yt)\; при\; условии\; tg\; (yt)\; \le \; 1,\; t\; \ge \; 0.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \{\backslash \; underset\; \{\{\backslash \; frac\; \{\backslash \; boldsymbol\; \{y\}\}\; \{t\}\}\; \backslash \; in\; \backslash \; mathbf\; \{S\}\; \_\; \{\; 0\}\}\; \{\backslash \; text\; \{maximize\}\}\}\; \backslash \; quad\; tf\; \backslash \; left\; (\{\backslash \; frac\; \{\backslash \; boldsymbol\; \{y\}\}\; \{t\}\}\; \backslash \; right)\; \backslash \backslash \; \{\backslash \; text\; \{subject\; to\}\}\; \backslash \; quad\; tg\; \backslash \; left\; (\; \{\backslash \; frac\; \{\backslash \; boldsymbol\; \{y\}\}\; \{t\}\}\; \backslash \; right)\; \backslash \; leq\; 1,\; \backslash \backslash \; t\; \backslash \; geq\; 0.\; \backslash \; end\; \{align\}\}\}$

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

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

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

$минимизирует\; u\; sup\; x\; \in \; S\; 0\; f\; (x)\; -\; u\; T\; h\; (x)\; g\; (x)\; с\; учетом\; ui\; \ge \; 0,\; i\; =\; 1,\dots ,\; m.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \{\backslash \; underset\; \{\backslash \; boldsymbol\; \{u\}\}\; \{\backslash \; text\; \{minim\}\}\}\; \backslash \; quad\; \{\backslash \; underset\; \{\{\backslash \; boldsymbol\; \{x\}\}\; \backslash \; in\; \backslash \; mathbf\; \{S\}\; \_\; \{\; 0\}\}\; \{\backslash \; operatorname\; \{sup\}\}\}\; \{\backslash \; frac\; \{f\; (\{\backslash \; boldsymbol\; \{x\}\})\; -\; \{\backslash \; boldsymbol\; \{u\}\}\; ^\; \{T\}\; \{\backslash \; boldsymbol\; \{h\}\}\; (\{\backslash \; boldsymbol\; \{x\; \}\})\}\; \{g\; (\{\backslash \; boldsymbol\; \{x\}\})\}\}\; \backslash \backslash \; \{\backslash \; text\; \{subject\; to\}\}\; \backslash \; quad\; u\_\; \{i\}\; \backslash \; geq\; 0,\; \backslash \; quad\; i\; =\; 1,\; \backslash \; dots,\; m.\; \backslash \; end\; \{выровнено\}\}\}$

1. ^Schaible, Siegfried (1974). "Выпуклые эквивалентные и двойные программы без параметров". Zeitschrift für Operations Research. 18 (5): 187–196. doi : 10.1007 / BF02026600. MR 0351464. CS1 maint: ref = harv (ссылка )

• Avriel, Mordecai; Diewert, Walter E.; Schaible, Siegfried; Zang, Israel (1988). Generalized Concavity. Plenum Press.
• Schaible, Siegfried (1983). «Дробное программирование». Zeitschrift für Operations Research. 27 : 39– 54. doi :10.1007/bf01916898.