Лінійне програмування

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Графічне представлення простої лінійної програми з двома змінними і шістьма нерівностями. Множина допустимих розв'язків зображена світло червоним і утворює багатогранник, 2-вимірний політоп. Цільова функція представлена червоною лінією і стрілкою. Червона лінія це множина рівня цільової функції і стрілка позначає в якому напрямку ми оптимізуємо

Лінійне програмування або лінійна оптимізація (LP, англ. Linear Programming) — метод досягнення найліпшого виходу (такого як найбільший прибуток або найменша вартість) у математичній моделі чиї вимоги представлені через лінійні відношення. Лінійне програмування є особливим випадком математичного програмування (математичної оптимізації).

Більш формально, лінійне програмування є технікою для оптимізації лінійної цільової функції, що обмежена лінійними рівняннями і лінійними нерівностями. Її допустима множина є опуклим політопом, який є множиною визначеною як перетин скінченної кількості півпростірів, кожен з яких визначає лінійна нерівність. Її цільова функція є дійсно-значима афінна функція визначена на цьому багатограннику. Алгоритм лінійного програмування знаходить точку на багатограннику де ця функція набуває найбільшого чи найменшого значення якщо така точка існує.

Лінійну програму можна виразити в канонічній формі:

максимізувати \mathbf{c}^\mathrm{T} \mathbf{x}
за умов A \mathbf{x} \leq \mathbf{b}
і також \mathbf{x} \ge \mathbf{0}

де x представляє вектор змінних (треба визначити), c і b це вектори (відомих) коефіцієнтів, A це (відома) матриця коефіцієнтів і (\cdot)^\mathrm{T} це транспонована матриця. Вираз, який необхідно максимізувати або мінімізувати називають цільова функція (тут cTx). Нерівності Ax ≤ b і x0 є обмеженнями, які визначають опуклий політоп над яким оптимізують цільову функцію.

Лінійне програмування можна застосувати у різноманітних галузях науки. Його використовують в економіці і бізнесі, але можна використати і в інженерних задачах. Серед галузей які використовують лінійне програмування можна згадати перевезення, енергетику, телекомунікації і виробництво. Воно довело свою корисність у моделюванні різних типів проблем у плануванні, маршрутизації, призначенні задач і дизайні.

Див. також[ред.ред. код]

Посилання[ред.ред. код]