Задача дробово-лінійного програмування

Зада́ча дробо́во-ліні́йного програмува́ння — задача мінімізації (максимізації) дробово-лінійної функції

$\!R(x)=\frac{L_{1}(x)}{L_{2}(x)}=\frac{d_{1}+(c_{1},x)}{d_{2}+(c_{2},x)}\,\,\,\,(1)$
при лінійних обмеженнях

$\!Ax=b,\,\,x\ge 0,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(2)$

де $\!A$ — матриця $\!m\times n$ , $\!c_{1}$ і $\!c_{2}$ — n-мірні вектори, $\!b$ — m-мірний вектор, $\!d_{1}$ і $\!d_{2}$ — дійсні числа, $\!x\ge 0$ означає додатність всіх компонент вектора $\!x$ . Один з можливих підходів до дослідження задачі дробово-лінійного програмування полягає ось в чому: нехай $\!X$ — множина, визначувана обмеженнями (2). Задачу дробово-лінійного програмування назвемо допустимою, якщо $\!X$ не порожня і $\!L_{2}(x)$ відмінне від нуля хоча б в одній точці цієї множини. При розв'язку задачі мінімізації розглядаються дві допоміжні задачі лінійного програмування:

$\!\begin{matrix} 1.\,\,\min \,\{d_{1}z_{0}+(c_{1},z)\}\left| \begin{matrix} Az=bz_{0}; \\ \begin{align} & d_{2}z_{0}+(c_{2},z)=1; \\ & z_{0}\ge 0;\,\,z\ge 0\, \\ \end{align} \\ \end{matrix} \right.\, \\ 2.\,\,\min \,\{-d_{1}z_{0}-(c_{1},z)\}\left| \begin{matrix} Az=bz_{0}; \\ \begin{align} & d_{2}z_{0}+(c_{2},z)=-1; \\ & z_{0}\ge 0;\,\,z\ge 0\, \\ \end{align} \\ \end{matrix} \right. \\ \end{matrix}$

Доведено, що для того, щоб задача дробово-лінійного програмування була допустимою, необхідно і достатньо, щоб принаймні у однієї із задач — у 1-й або у 2-й — існував допустимий план з $\!z_{0}>0$ ; при цьому, якщо допустимий план у задачі 1-й або 2-й існує, то у відповідної задачі існує і допустимий план з $\!z_{0}>0$ ; якщо задача дробово-лінійного програмування допустима, а множина допустимих планів однієї із задач — 1-й або 2-й — порожня, то $\!\underset{X}{\mathop{\inf }}\,\frac{L_{1}(x)}{L_{2}(x)}$ збігається із оптимальним значенням цільової функції іншої задачі. Якщо задача дробово-лінійного програмування допустима, а задачі 1-а і 2-а мають допустимі плани, то $\!\underset{X}{\mathop{\inf }}\,\frac{L_{1}(x)}{L_{2}(x)}$ збігається з мінімумом серед оптималних значень цільових функцій обох задач — і 1-ї і 2-ї. Ці твердження зводять задачу дробово-лінійного програмування до розв'язку двох задач лінійного програмування. Перехід від змінних $\!z_{0}$ , $\!z$ до змінних $\!x$ здійснюється за формулами $\!z_{0}=\frac{-1}{\left| L_{2}(x) \right|};$ $\!z=\frac{x}{\left| L_{2}(x) \right|}.$ Задачі дробово-лінійного програмування часто виникають в економічних додатках, коли цільовою функцією приймається «відносна ефективність» (наприклад, прибуток, віднесений до одиниці витрат).