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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

\!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|}. Задачі дробово-лінійного програмування часто виникають в економічних додатках, коли цільовою функцією приймається «відносна ефективність» (наприклад, прибуток, віднесений до одиниці витрат).

М. З. Шор.

Література[ред.ред. код]