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

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

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

${\displaystyle \!Ax=b,\,\,x\geq 0,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(2)}$

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

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

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

М. З. Шор.

Стосунок до лінійного програмування

І лінійне і дробово-лінійне програмування представляють задачі із використанням лінійних рівнянь або нерівностей, які для кожного примірника проблеми визначають . Доробово-лінійні програми мають багатшу множину цільових функцій. Неформально, лінійне програмування обчислює поведінку, що приносить найбільший вихід, наприклад, найбільший прибуток або найменші витрати. Натомість дробов-лінійне програмування використовується для отримання найбільшого співвідношення прибутку до витрат, співвідношення, що представляє найбільшу ефективність. Наприклад, у контексті ЛП ми максимізуємо цільову функцію прибуток = дохід − витрати і може отримати найбільший прибуток у $100 (= $1100 of дохід − $1000 вартості). Отже, у ЛП ми маємо ефективність $100/$1000 = 0.1. Використовуючи ЛДП ми можливо отримали б ефективність у $10/$50 = 0.2 з прибутком у лише $10, який, однак, потребує лише $50 інвестицій.

Література

• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.