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

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

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

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

де $\!A$ — матриця $\!m\times n$ , $\!c_{1}$ і $\!c_{2}$ — n-мірні вектори, $\!b$ — m-мірний вектор, $\!d_{1}$ і $\!d_{2}$ — дійсні числа, $\!x\geq 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{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-й — існував допустимий план з $\!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|}}.$ Задачі дробово-лінійного програмування часто виникають в економічних додатках, коли цільовою функцією приймається «відносна ефективність» (наприклад, прибуток, віднесений до одиниці витрат).

М. З. Шор.

Стосунок до лінійного програмування[ред. | ред. код]

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