Постановка задачі лінійного програмування
Задача лінійного програмування (ЛП) — знайти мінімум або максимум лінійної цільової функції на допустимій множині, заданій лінійними нерівностями та рівностями.
max cᵀx = c₁x₁ + c₂x₂ + ... + cₙxₙ
при обмеженнях:
Ax ≤ b (m нерівностей)
x ≥ 0 (невід'ємність)
// де: x ∈ ℝⁿ — вектор змінних рішення
// c ∈ ℝⁿ — коефіцієнти цільової функції
// A ∈ ℝᵐˣⁿ — матриця обмежень
// b ∈ ℝᵐ — вектор правих частин
Геометрична інтерпретація (n=2)
При двох змінних допустима множина — опуклий многокутник (поліедр) у площині. Максимум лінійної функції завжди досягається у вершині цього многокутника або на його ребрі.
max 5x₁ + 4x₂ ← прибуток
при: 6x₁ + 4x₂ ≤ 24 ← ресурс A
x₁ + 2x₂ ≤ 6 ← ресурс B
x₁,x₂ ≥ 0
// Вершини допустимої множини:
(0, 0): Z = 0
(4, 0): Z = 20
(3, 3): Z = 27 ← оптимум!
(0, 3): Z = 12
// Оптимальне рішення: x₁=3, x₂=3, Z=27
Теорема про крайні точки
// досягається в крайній точці (вершині) допустимої множини.
Крайня точка (вершина) допустимої множини ↔
базисне допустиме рішення системи Ax = b, x ≥ 0
Кількість вершин ≤ C(m+n, m) = (m+n)! / (m!·n!)
// де m — кількість обмежень, n — кількість змінних
Симплекс-метод
Симплекс-метод Данцига (1947) — найвідоміший алгоритм оптимізації. Він рухається по вершинах поліедра, поліпшуючи значення цільової функції на кожному кроці.
Алгоритм у стандартній формі
Спочатку задачу переводять у стандартну рівняльну форму, додаючи slack-змінні:
6x₁ + 4x₂ + s₁ = 24
x₁ + 2x₂ + s₂ = 6
max 5x₁ + 4x₂
// Початкове базисне рішення: x₁=0, x₂=0, s₁=24, s₂=6
// Базис = {s₁, s₂}, Z = 0
Симплекс-таблиця (tableau)
| База | x₁ | x₂ | s₁ | s₂ | b |
|---|---|---|---|---|---|
| s₁ | 6 | 4 | 1 | 0 | 24 |
| s₂ | 1 | 2 | 0 | 1 | 6 |
| −Z | −5 | −4 | 0 | 0 | 0 |
Вибираємо стовпець з найбільшим від'ємним коефіцієнтом у рядку Z: x₁ (−5). Мінімальне відношення b/a: min(24/6, 6/1) = 4 → виводимо s₂. Після зведення:
| База | x₁ | x₂ | s₁ | s₂ | b |
|---|---|---|---|---|---|
| s₁ | 0 | −8 | 1 | −6 | −12 |
| x₁ | 1 | 2 | 0 | 1 | 6 |
| −Z | 0 | 6 | 0 | 5 | 30 |
📝 Повний алгоритм симплекс-методу
2. Початкове базисне рішення (slack-змінні = b, прим. = 0)
3. Перевірка оптимальності: всі коефіц. у рядку Z ≥ 0?
Якщо так → оптимум знайдено. СТОП.
4. Вхідна змінна: найбільший від'ємний коефіцієнт в Z
5. Вихідна змінна: мін. відношення b_i/a_ij (тільки a_ij > 0)
(Якщо всі a_ij ≤ 0 → задача необмежена)
6. Зведення (pivot): виконати елементарні перетворення рядків
7. Перейти до кроку 3
Теорія двоїстості
До кожної задачі ЛП (прямої) відповідає двоїста задача. Між ними виконується фундаментальна симетрія.
max cᵀx
s.t. Ax ≤ b, x ≥ 0
// Двоїста задача (Dual):
min bᵀy
s.t. Aᵀy ≥ c, y ≥ 0
// де y ∈ ℝᵐ — вектор двоїстих змінних (тіньових цін)
Теорема про слабку двоїстість
cᵀx ≤ bᵀy
// Наслідок: якщо cᵀx* = bᵀy*, то обидва оптимальні
Теорема про сильну двоїстість (Strong Duality)
// то двоїста теж має оптимум y*, і:
cᵀx* = bᵀy*
// Інтерпретація: тіньова ціна yᵢ = ∂Z*/∂bᵢ
// (приріст оптимуму при збільшенні обмеження bᵢ на 1)
Теорема про доповнюваність (Complementary Slackness)
(b − Ax*)ᵢ · yᵢ* = 0 для всіх i (пряма доповнюваність)
(Aᵀy* − c)ⱼ · xⱼ* = 0 для всіх j (двоїста доповнюваність)
// Тобто: якщо обмеження не активне (slack > 0),
// то відповідна тіньова ціна = 0.
| Пряма задача | Двоїста задача |
|---|---|
| max cᵀx | min bᵀy |
| Ax ≤ b, x ≥ 0 | Aᵀy ≥ c, y ≥ 0 |
| n змінних | m змінних |
| m обмежень | n обмежень |
| Оптимум Z* | Рівний Z* |
Аналіз чутливості
Аналіз чутливості відповідає на питання: як зміниться оптимальне рішення, якщо параметри задачі трохи зміняться?
cⱼ може змінюватись у межах [cⱼ - Δcⱼ⁻, cⱼ + Δcⱼ⁺]
зберігаючи оптимальний базис (не змінюючи структуру рішення)
// Діапазони для правих частин bᵢ (Resource RHS):
bᵢ може змінюватись у межах [bᵢ - δᵢ⁻, bᵢ + δᵢ⁺]
зберігаючи допустимість
// Тіньова ціна (shadow price):
yᵢ* = ΔZ*/Δbᵢ
// = на скільки зросте максимум при додаванні 1 одиниці ресурсу i
Транспортна задача
Транспортна задача — спеціальний клас ЛП з матричною структурою. Є m постачальників з запасами aᵢ та n споживачів з попитом bⱼ. Треба мінімізувати вартість перевезень.
min ΣΣ cᵢⱼ·xᵢⱼ
s.t. Σⱼ xᵢⱼ = aᵢ (запас постачальника i)
Σᵢ xᵢⱼ = bⱼ (попит споживача j)
xᵢⱼ ≥ 0
// Умова збалансованості: Σaᵢ = Σbⱼ
Метод північно-західного кута
// Починаємо з клітинки (1,1), заповнюємо max можливим:
Матриця витрат cᵢⱼ: Запаси aᵢ:
j=1 j=2 j=3 a₁=20, a₂=30, a₃=25
i=1 [2 3 1]
i=2 [5 4 8] Попит bⱼ: b₁=10, b₂=28, b₃=27, b₄=10
i=3 [5 6 8]
// (пр. від пн-зах кута: x₁₁=min(20,10)=10, x₁₂=min(10,28)=10...)
Метод потенціалів (MODI) для оптимізації
uᵢ + vⱼ = cᵢⱼ (для базисних клітинок)
// Для небазисних обчислити:
Δᵢⱼ = cᵢⱼ − uᵢ − vⱼ
// Якщо всі Δᵢⱼ ≥ 0 → оптимум досягнуто
// Інакше ввести в базис клітинку з min Δᵢⱼ < 0
Цілочисельне лінійне програмування (ILP)
Якщо деякі або всі змінні повинні бути цілими (x ∈ ℤⁿ), задача стає NP-складною.
1. Розв'язати ЛП-релаксацію (xᵢ ∈ ℝ)
2. Якщо всі xᵢ цілі − оптимум знайдено
3. Вибрати дробову xᵢ* = a.b
4. Розгалуження: задача A: xᵢ ≤ ⌊a.b⌋
задача B: xᵢ ≥ ⌈a.b⌉
5. Рекурсивно вирішити A і B
// Метод відсічень Гоморі: додати cutting planes
Σ⌊rᵢⱼ⌋xⱼ ≤ ⌊rᵢ₀⌋
// де rᵢⱼ — коефіцієнти поточного рядка таблиці, rᵢ₀ — права частина
Про цю статтю
Ця стаття є частиною бази знань calculator.party — освітнього ресурсу, що поєднує теорію з практичними інструментами. Матеріал орієнтований на студентів, учнів і фахівців, що прагнуть глибокого розуміння теми. Тут зібрані ключові концепції, формули та реальні приклади застосування.
Інформатика та алгоритміка лежать в основі сучасного світу: від пошукових алгоритмів до нейронних мереж та квантових обчислень.
Навіщо читати цю статтю
Після прочитання ви зможете впевнено пояснити тему, вирішувати практичні задачі та застосовувати знання у навчанні й роботі. Стаття охоплює теоретичне підґрунтя і числові приклади, що полегшують запам'ятовування матеріалу.