Перегляд вихідного коду сторінки Лінійне програмування

{{не плутати|Лінійна програма|лінійною програмою}}
[[Файл:Linear optimization in a 2-dimensional polytope.svg|thumb|Графічне представлення простої лінійної програми з двома змінними і шістьма нерівностями. Множина допустимих розв'язків зображена світло жовтим і утворює багатогранник, 2-вимірний політоп. Цільова функція представлена червоною лінією і стрілкою. Червона лінія це [[множина рівня]] цільової функції і стрілка позначає в якому напрямку ми оптимізуємо]]
'''Лінійне програмування''' або '''лінійна оптимізація''' ('''LP''', {{lang-en|Linear Programming}})&nbsp;— метод досягнення найліпшого виходу (такого як найбільший прибуток або найменша вартість) у [[математична модель|математичній моделі]], чиї вимоги подані через лінійні відношення. Лінійне програмування є особливим випадком математичного програмування ([[оптимізація (математика)|математичної оптимізації]]).

Формальніше, лінійне програмування є технікою для [[оптимізація (математика)|оптимізації]] [[лінійна функція|лінійної]] [[цільова функція|цільової функції]], що [[Обмеження (математика)|обмежена]] [[Лінійне рівняння|лінійними рівняннями]] і лінійними нерівностями. Її [[Допустимий розв'язок|допустима множина]] є [[Опуклий політоп|опуклим політопом]], який є множиною визначеною як перетин скінченної кількості [[півпростір]]ів, кожен з яких визначає лінійна нерівність. Її цільова функція є [[дійсне число|дійсно]]-значима [[Афінне перетворення|афінна функція]] визначена на цьому багатограннику. [[Алгоритм]] лінійного програмування знаходить точку на багатограннику, де ця функція набуває найбільшого чи найменшого значення, якщо така точка існує.

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

== Задача лінійного програмування ==
'''Зада́ча ліні́йного програмува́ння'''&nbsp;— [[задача оптимізації]] з [[Лінійна функція|лінійною]] [[цільова функція|цільовою функцією]] та [[допустима множина|допустимою множиною]] обмеженою лінійними рівностями або нерівностями.

Її можна виразити в [[канонічна форма|канонічній формі]]:
:{|
|-
| '''максимізувати''' || <math>\mathbf{c}^\mathrm{T} \mathbf{x}</math>
|-
| '''за умов''' || <math>A \mathbf{x} \leq \mathbf{b}</math>
|-
| '''і також''' || <math>\mathbf{x} \ge \mathbf{0}</math>
|}
де '''x''' представляє вектор змінних (треба визначити), '''c''' і '''b''' це [[Векторний простір|вектори]] (відомих) коефіцієнтів, ''A'' це (відома) [[Матриця (математика)|матриця]] коефіцієнтів і <math>(\cdot)^\mathrm{T}</math> це [[транспонована матриця]]. Вираз, який необхідно максимізувати або мінімізувати називають ''цільова функція'' (тут '''c'''<sup>T</sup>'''x'''). Нерівності ''A'''''x'''&nbsp;≤&nbsp;'''b''' і '''x''' ≥ '''0''' є обмеженнями, які визначають опуклий [[політоп]] над яким оптимізують цільову функцію.

Тобто, необхідно мінімізувати
: <math> \sum_{j=1}^n c_j x_j \to \min </math> (1)
при обмеженнях
: <math> \sum_{j=1}^n a_{ij} x_j \leq b_i,\; i = 1, \dots, m_1</math>, (2)
: <math> \sum_{j=1}^n a_{ij} x_j = b_i, \; i = m_1+1, \dots, m</math>, (3)
: <math> x_j \geq 0, \; j = 1, \dots, n_1</math>, (4)
де ''c''<sub>j</sub> (''j'' = 1, …, ''n''), ''a''<sub>ij</sub>(''i'' = 1, …, ''m'')&nbsp;— задані числа.

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

== Методи розв'язання ==
* [[Метод потенціалів]] — розроблений в [[1940]] радянськими вченими [[Канторович Леонід Віталійович|Канторовичем]] та [[Гавурін М. К.|Гавуріним Л. В.]] в застосуванні до [[Транспортна задача|транспортної задачі]];
* [[Симплекс-метод]] — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим [[Джордж Данціг|Данциґом Дж.-Б.]] в [[1949]] році.
* [[Двоїстий симплекс-метод]] розроблений згодом після прямого [[симплекс-метод]]у, і який є, за сутністю, симплекс-методом розв'язання [[Двоїстість (оптимізація)|двоїстої]] задачі лінійного програмування, але сформульованої в термінах вихідної задачі.
Усі ці методи скінченні. Крім того, існують, також, ітеративні методи розв'язання, які дають можливість обчислювати розв'язки задачі із наперед заданою точністю.

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

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

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

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

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

== Двоїсті задачі лінійного програмування ==
{{Див. також|Двоїстість (оптимізація)}}
Кожній задачі лінійного програмування<ref>Электронный учебник [http://www.math.mrsu.ru/text/courses/method/dvoistvennost_v_lineinom_programmirovanii.htm «Экономико-математические методы». Двойственность в линейном программировании] {{Webarchive|url=https://web.archive.org/web/20160617221600/http://www.math.mrsu.ru/text/courses/method/dvoistvennost_v_lineinom_programmirovanii.htm |date=17 червня 2016 }}</ref> вигляду
: <math>\sum_{j=1}^n a_{ij}x_j\leqslant c_i,\;i=\overline{1,\;m};</math>
: <math>x_j\geqslant 0,\;j=\overline{1,\;n};</math>
: <math>F(x)=\sum_{j=1}^n b_jx_j\to\max</math>
можна певним чином зіставити деяку іншу задачу лінійного програмування, звану двоїстою або спряженою відносно початкової або прямої. Зв'язок вихідної початкової та двоїстої задач полягає головним чином у тому, що розв'язок однієї з них можна легко отримати безпосередньо з розв'язку іншої. Дамо визначення двоїстої задачі відносно до початкової задачі лінійного програмування
{| class="wikitable"
|-
! Початкова задача !! Двоїста задача
|-
| <math>\sum_{j=1}^n a_{ij}x_j\leqslant c_i,\;i=\overline{1,\;m}</math> || <math>y_i\geqslant 0,\;i=\overline{1,\;m}</math>
|-
| <math>x_j\geqslant 0,\;j=\overline{1,\;n}</math> || <math>\sum_{i=1}^m a_{ij}y_i\geqslant b_j,\;j=\overline{1,\;n}</math>
|-
| <math>F(x)=\sum_{j=1}^n b_jx_j\to\max</math> || <math>T(y)=\sum_{i=1}^m c_iy_i\to\min</math>
|}
Якщо вектори <math>x</math> і <math>y</math>&nbsp;— допустимі розв'язки прямої та двоїстої задач, то <math>F(x)\leqslant T(y)</math>, причому рівність досягається [[тоді й лише тоді]], коли <math>x</math> і <math>y</math>&nbsp;— оптимальні розв'язки. Якщо ж цільова функція однієї з пари двоїстих задач не обмежена (для початкової&nbsp;— зверху, для двоїстої&nbsp;— знизу), то область допустимих розв'язків іншої задачі&nbsp;— порожня.

Якщо вектори <math>x^*</math> і <math>y^*</math>&nbsp;— оптимальні розв'язки прямої та двоїстої задачі, відповідно, то виконуються такі рівності
: <math>x_j^*(\sum_{i=1}^m a_{ij} y_i^*-b_j)=0,\;j=\overline{1,\;n};</math>
: <math>y_i^*(\sum_{j=1}^n a_{ij} x_j^*-c_i)=0,\;i=\overline{1,\;m}.</math>
Тобто, для оптимальних розв'язків прямої та двоїстої задач, ненапруженим (виконується строга нерівність) обмеженням відповідають нульові змінні, а ненульовим змінним (що входять в опорний план) відповідають напружені (нестрога нерівність реалізується, як рівність) обмеження. Але можуть бути й нульові змінні, що відповідають напруженим обмеженням.

Ці властивості двоїстих розв'язків дозволяють істотно скоротити час розв'язування, якщо доводиться розв'язувати задачу з кількістю обмежень значно більшою від кількості змінних. Тоді можна, розв'язавши двоїсту задачу, знайти її опорний план, після чого, відібравши у прямій задачі лише обмеження, що відповідають опорному плану (всі ці обмеження мають бути напруженими), розв'язати для них звичайну [[Система лінійних алгебраїчних рівнянь|систему лінійних рівнянь]].

== Використання ==

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

== Див. також ==
{{Портал|Математика}}
* [[Цілочислові задачі лінійного програмування]]
* [[Задача математичного програмування]]
* [[Задача оптимізації]]
* [[Опорний план]]
* [[Витрати — випуск (модель)|Модель «витрати — випуск»]]
* [[Геометричне програмування]]

== Примітки ==
{{примітки}}

== Джерела інформації ==
* [[Енциклопедія кібернетики]], [[Трубін В. А.]], т. '''2''', с. 232-234.

== Література ==
* ''Цегелик Г.Г''. Лінійне програмування. – Львів: Світ, 1995. – 215 с. – ISBN 5-7773-0217-3

== Посилання ==
* [http://sourceforge.net/projects/lipside/ Linear Program Solver (LiPS)] {{Webarchive|url=https://web.archive.org/web/20110606043239/http://sourceforge.net/projects/lipside/ |date=6 червня 2011 }}&nbsp;— [[розв'язувач]] задач лінійного цілочисельного программирования.
* [https://maiachia.blogspot.com/2017/11/blog-post.html Двоїстість у лінійному програмуванні - тлумачення] {{Webarchive|url=https://web.archive.org/web/20200128035149/http://maiachia.blogspot.com/2017/11/blog-post.html |date=28 січня 2020 }}.
* [http://www.mdtvm.rv.ua/matem/matprog.html Динамічні математичні моделі]{{Недоступне посилання|date=липень 2019 |bot=InternetArchiveBot }}
{{Методи оптимізації}}
{{Math-stub}}
{{додаткові джерела|дата=грудень 2018}}

{{Перекласти|en|Linear programming}}

[[Категорія:Теорія оптимізації]]
[[Категорія:Лінійне програмування| ]]
[[Категорія:Геометричні алгоритми]]