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

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

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

$A x = 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)} | \begin{matrix} A z = b z_{0}; \\ \begin{matrix} d_{2} z_{0} + (c_{2}, z) = 1; \\ z_{0} \geq 0; z \geq 0 \end{matrix} \end{matrix} \\ 2 . \min {- d_{1} z_{0} - (c_{1}, z)} | \begin{matrix} A z = b z_{0}; \\ \begin{matrix} d_{2} z_{0} + (c_{2}, z) = - 1; \\ z_{0} \geq 0; z \geq 0 \end{matrix} \end{matrix} \end{matrix}$

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

М. З. Шор.

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

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

Література

Шаблон:ЕК

Шаблон:ВП-портали Шаблон:Math-stub

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

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

Література

Навігаційне меню

Пошук