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

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

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

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

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

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

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

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

${\displaystyle \sum _{j=1}^{n}c_{j}x_{j}\to \min }$ (1)

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

${\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}\leq b_{i},\;i=1,\dots ,m_{1}}$, (2)

${\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}=b_{i},\;i=m_{1}+1,\dots ,m}$, (3)

${\displaystyle x_{j}\geq 0,\;j=1,\dots ,n_{1}}$, (4)

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

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

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

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

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

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

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

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

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

Кожній задачі лінійного програмування^[1] вигляду

${\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}\leqslant c_{i},\;i={\overline {1,\;m}};}$

${\displaystyle x_{j}\geqslant 0,\;j={\overline {1,\;n}};}$

${\displaystyle F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max }$

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

Початкова задача	Двоїста задача
${\displaystyle \sum _{j=1}^{n}a_{ij}x_{j}\leqslant c_{i},\;i={\overline {1,\;m}}}$	${\displaystyle y_{i}\geqslant 0,\;i={\overline {1,\;m}}}$
${\displaystyle x_{j}\geqslant 0,\;j={\overline {1,\;n}}}$	${\displaystyle \sum _{i=1}^{m}a_{ij}y_{i}\geqslant b_{j},\;j={\overline {1,\;n}}}$
${\displaystyle F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max }$	${\displaystyle T(y)=\sum _{i=1}^{m}c_{i}y_{i}\to \min }$

Якщо вектори ${\displaystyle x}$ і ${\displaystyle y}$ — допустимі розв'язки прямої та двоїстої задач, то ${\displaystyle F(x)\leqslant T(y)}$, причому рівність досягається тоді й лише тоді, коли ${\displaystyle x}$ і ${\displaystyle y}$ — оптимальні розв'язки. Якщо ж цільова функція однієї з пари двоїстих задач не обмежена (для початкової — зверху, для двоїстої — знизу), то область допустимих розв'язків іншої задачі — порожня.

Якщо вектори ${\displaystyle x^{*}}$ і ${\displaystyle y^{*}}$ — оптимальні розв'язки прямої та двоїстої задачі, відповідно, то виконуються такі рівності

${\displaystyle x_{j}^{*}(\sum _{i=1}^{m}a_{ij}y_{i}^{*}-b_{j})=0,\;j={\overline {1,\;n}};}$

${\displaystyle y_{i}^{*}(\sum _{j=1}^{n}a_{ij}x_{j}^{*}-c_{i})=0,\;i={\overline {1,\;m}}.}$

Тобто, для оптимальних розв'язків прямої та двоїстої задач, ненапруженим (виконується строга нерівність) обмеженням відповідають нульові змінні, а ненульовим змінним (що входять в опорний план) відповідають напружені (нестрога нерівність реалізується, як рівність) обмеження. Але можуть бути й нульові змінні, що відповідають напруженим обмеженням.

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

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

• Цілочислові задачі лінійного програмування
• Задача математичного програмування
• Задача оптимізації
• Опорний план
• Модель «витрати — випуск»
• Геометричне програмування

• Енциклопедія кібернетики, Трубін В. А., т. 2, с. 232-234.

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

• Linear Program Solver (LiPS) [Архівовано 6 червня 2011 у Wayback Machine.] — розв'язувач задач лінійного цілочисельного программирования.
• Двоїстість у лінійному програмуванні - тлумачення [Архівовано 28 січня 2020 у Wayback Machine.].
• Динамічні математичні моделі^{[недоступне посилання з липня 2019]}

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

Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки. Матеріал без джерел може бути піддано сумніву та вилучено. (грудень 2018)

В іншому мовному розділі є повніша стаття Linear programming(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. Дивитись автоперекладену версію статті з мови «англійська». Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії! Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії. Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті. Докладні рекомендації: див. Вікіпедія:Переклад.