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

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

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

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

Загальні відомості[ред.ред. код]

Лінійне програмування (та дослідження задачі лінійного програмування) є однією із найрозвинутишіх галузей математичного програмування та теорії оптимізації. Загальна постановка задачі лінійного програмування, та один із підходів до її розв'язання (ідея розрішаючих множників або двоїстих оцінок) вперше наведено в роботі радянського вченого Канторовича Л. В. в 1939. В цій же роботі намічено один із методів розв'язання задачі — метод послідовного зменшення нев'язок.

Задача лінійного програмування[ред.ред. код]

Зада́ча ліні́йного програмува́ння — задача оптимізації з лінійною цільовою функцією та допустимою множиною обмеженою лінійними рівностями або нерівностями.

Її можна виразити в канонічній формі:

максимізувати
за умов
і також

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

Тобто, необхідно мінімізувати

(1)

при обмеженнях

, (2)
, (3)
, (4)

де cj (j = 1, …, n), aij(i = 1, …, m) — задані числа.

Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіцієнтів cj на протилежні.

Методи розв'язання[ред.ред. код]

Усі ці методи скінченні. Крім того, існують, також, ітеративні методи розв'язання, які дають можливість обчислювати розв'язки задачі із наперед заданою точністю.

Близький зв'язок між лінійним програмуванням та теорією ігор дає змогу використовувати для розв'язання задач лінійного програмування чисельні методи теорії ігор.

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

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

Методів лінійного програмування недостатньо при накладанні додаткових обмежень на цілочисельність значень змінних. Вивченням таких задач займається цілочисельне програмування.

Поряд з основною задачею лінійного програмування, розглядають різноманітні окремі задачі лінійного програмування, такі як транспортні, задачі розподілу, задачі теорії розкладів, вибору тощо.

Використання[ред.ред. код]

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

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


Джерела інформації[ред.ред. код]

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


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.