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

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

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


при лінійних обмеженнях

де матриця , і — n-мірні вектори, — m-мірний вектор, і дійсні числа, означає додатність всіх компонент вектора . Один з можливих підходів до дослідження задачі дробово-лінійного програмування полягає ось в чому: нехай множина, визначувана обмеженнями (2). Задачу дробово-лінійного програмування назвемо допустимою, якщо не порожня і відмінне від нуля хоча б в одній точці цієї множини. При розв'язку задачі мінімізації розглядаються дві допоміжні задачі лінійного програмування:

Доведено, що для того, щоб задача дробово-лінійного програмування була допустимою, необхідно і достатньо, щоб принаймні у однієї із задач — у 1-й або у 2-й — існував допустимий план з ; при цьому, якщо допустимий план у задачі 1-й або 2-й існує, то у відповідної задачі існує і допустимий план з ; якщо задача дробово-лінійного програмування допустима, а множина допустимих планів однієї із задач — 1-й або 2-й — порожня, то збігається із оптимальним значенням цільової функції іншої задачі. Якщо задача дробово-лінійного програмування допустима, а задачі 1-а і 2-а мають допустимі плани, то збігається з мінімумом серед оптималних значень цільових функцій обох задач — і 1-ї і 2-ї. Ці твердження зводять задачу дробово-лінійного програмування до розв'язку двох задач лінійного програмування. Перехід від змінних , до змінних здійснюється за формулами Задачі дробово-лінійного програмування часто виникають в економічних додатках, коли цільовою функцією приймається «відносна ефективність» (наприклад, прибуток, віднесений до одиниці витрат).

М. З. Шор.

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

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

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