1
Геометричний метод — виробнича задача
Підприємство виробляє два типи продукції. Продукт A приносить прибуток 5 грн/од., продукт B — 4 грн/од. Обмеження: ресурс I: 6A + 4B ≤ 24; ресурс II: A + 2B ≤ 6; A,B ≥ 0. Знайти максимальний прибуток.
1
Записати задачу: max Z = 5A + 4B при 6A+4B≤24, A+2B≤6, A,B≥0.
2
Знайти вершини допустимої множини: перетин обмежень і осей.
// Перетини з осями та між собою:
O = (0, 0):
A ≥ 0 і B ≥ 0
Обмеження 1 (при B=0): 6A=24 → A=4 → точка (4, 0)
Обмеження 2 (при A=0): 2B=6 → B=3 → точка (0, 3)
// Перетин двох прямих:
6A + 4B = 24
A + 2B = 6 ×3 → 3A + 6B = 18
Із другого: A = 6 − 2B
Підставляємо: 6(6−2B) + 4B = 24 → 36 − 12B + 4B = 24 → −8B = −12 → B = 1.5
A = 6 − 2(1.5) = 3
Точка перетину: (3, 1.5)
O = (0, 0):
A ≥ 0 і B ≥ 0
Обмеження 1 (при B=0): 6A=24 → A=4 → точка (4, 0)
Обмеження 2 (при A=0): 2B=6 → B=3 → точка (0, 3)
// Перетин двох прямих:
6A + 4B = 24
A + 2B = 6 ×3 → 3A + 6B = 18
Із другого: A = 6 − 2B
Підставляємо: 6(6−2B) + 4B = 24 → 36 − 12B + 4B = 24 → −8B = −12 → B = 1.5
A = 6 − 2(1.5) = 3
Точка перетину: (3, 1.5)
3
Обчислити Z у кожній вершині:
| Вершина (A, B) | Z = 5A + 4B |
|---|---|
| (0, 0) | 0 |
| (4, 0) | 20 |
| (3, 1.5) | 5·3 + 4·1.5 = 21 |
| (0, 3) | 12 |
Відповідь: максимум Z = 21 при A = 3, B = 1.5. Обидва обмеження активні (зв'язальні).
2
Симплекс-метод у табличній формі
Розв'язати задачу: max Z = 3x₁ + 5x₂ при: x₁ ≤ 4; 2x₂ ≤ 12; 3x₁ + 5x₂ ≤ 25; x₁,x₂ ≥ 0.
1
Стандартна форма: додати slack-змінні s₁, s₂, s₃ ≥ 0.
x₁ + s₁ = 4
2x₂ + s₂ = 12
3x₁ + 5x₂ + s₃ = 25
// Початковий базис: {s₁, s₂, s₃}, Z = 0
2x₂ + s₂ = 12
3x₁ + 5x₂ + s₃ = 25
// Початковий базис: {s₁, s₂, s₃}, Z = 0
2
Ітерація 1: вхідна змінна x₂ (коеф. −5 у рядку Z). Мін. 12/2=6, 25/5=5 → вихідна s₃.
| База | x₁ | x₂ | s₁ | s₂ | s₃ | b |
|---|---|---|---|---|---|---|
| s₁ | 1 | 0 | 1 | 0 | 0 | 4 |
| s₂ | 0 | 2 | 0 | 1 | 0 | 12 |
| s₃ | 3 | 5 | 0 | 0 | 1 | 25 |
| -Z | -3 | -5 | 0 | 0 | 0 | 0 |
3
Зведення: ділимо рядок s₃ на 5, потім обнуляємо стовпець x₂.
// Після ітерації 1 (введено x₂, виведено s₃):
Рядок x₂: [3/5, 1, 0, 0, 1/5 | 5]
Рядок s₂: [−6/5, 0, 0, 1, −2/5 | 2] (← знімаємо 2·рядок x₂)
Рядок s₁: [1, 0, 1, 0, 0 | 4]
Рядок Z: [−3+3, 0, 0, 0, 1 | 25] → рядок Z: [0, 0, 0, 0, 1 | 25]
// Перевірка: ще є від'ємні коефіцієнти? Ні → оптимум!x₂ = 5, s₁ = 4, s₂ = 2, x₁=0
Рядок x₂: [3/5, 1, 0, 0, 1/5 | 5]
Рядок s₂: [−6/5, 0, 0, 1, −2/5 | 2] (← знімаємо 2·рядок x₂)
Рядок s₁: [1, 0, 1, 0, 0 | 4]
Рядок Z: [−3+3, 0, 0, 0, 1 | 25] → рядок Z: [0, 0, 0, 0, 1 | 25]
// Перевірка: ще є від'ємні коефіцієнти? Ні → оптимум!x₂ = 5, s₁ = 4, s₂ = 2, x₁=0
Відповідь: max Z = 25 при x₁ = 0, x₂ = 5. Обмеження 3 активне (s₃=0), обмеження 1 та 2 — ні (s₁=4, s₂=2).
3
Двоїста задача та тіньові ціни
Для задачі з прикладу 2 (max 3x₁+5x₂, x₁≤4, 2x₂≤12, 3x₁+5x₂≤25) скласти двоїсту задачу та знайти тіньові ціни.
1
Записати матричну форму прямої: A = [[1,0],[0,2],[3,5]], b = [4,12,25], c = [3,5].
// Двоїста задача: min bᵀy = 4y₁ + 12y₂ + 25y₃
Aᵀy ≥ c:
y₁ + 3y₃ ≥ 3 (для x₁)
2y₂ + 5y₃ ≥ 5 (для x₂)
y₁, y₂, y₃ ≥ 0
Aᵀy ≥ c:
y₁ + 3y₃ ≥ 3 (для x₁)
2y₂ + 5y₃ ≥ 5 (для x₂)
y₁, y₂, y₃ ≥ 0
2
Тіньові ціни з оптимальної симплекс-таблиці: y* — коефіцієнти рядка Z у стовпцях slack-змінних.
// З оптимальної таблиці (кроки вище):
Стовпець s₁: коеф. у рядку Z = 0 → y₁* = 0
Стовпець s₂: коеф. у рядку Z = 0 → y₂* = 0
Стовпець s₃: коеф. у рядку Z = 1 → y₃* = 1
// Перевірка: bᵀy* = 4·0 + 12·0 + 25·1 = 25 = Z* ✓
// Тіньова ціна y₃* = 1: якщо b₃ збільшити на 1 (до 26),
// то max Z зросте на 1 (до 26)
Стовпець s₁: коеф. у рядку Z = 0 → y₁* = 0
Стовпець s₂: коеф. у рядку Z = 0 → y₂* = 0
Стовпець s₃: коеф. у рядку Z = 1 → y₃* = 1
// Перевірка: bᵀy* = 4·0 + 12·0 + 25·1 = 25 = Z* ✓
// Тіньова ціна y₃* = 1: якщо b₃ збільшити на 1 (до 26),
// то max Z зросте на 1 (до 26)
3
Доповнюваність: x₁=0 (не активна) → двоїстий: y₁+3y₃≥3, тобто 0+3≥3 виконується рівністю? 3=3 — так! (вироджений випадок). Обмеження 1 і 2 неактивні (s₁=4>0, s₂=2>0) → y₁*=y₂*=0 ✓.
Відповідь: Двоїсте оптимальне рішення: y₁*=0, y₂*=0, y₃*=1. Тіньова ціна третього ресурсу = 1 грн на одиницю. Перші два ресурси нелімітуючі.
4
Транспортна задача методом потенціалів
Два постачальники (запаси: a₁=30, a₂=20) і три споживачі (попит: b₁=20, b₂=15, b₃=15). Матриця витрат: c = [[2,3,1],[5,4,2]]. Знайти план мінімальних транспортних витрат.
1
Початковий план методом мінімального елементу:
// Матриця витрат: b₁=20 b₂=15 b₃=15
// ↓ ↓ ↓
a₁=30: [ 2 ] [ 3 ] [ 1 ] ← мін. c=1: x₁₃=15 (a₁→30-15=15)
a₂=20: [ 5 ] [ 4 ] [ 2 ]
// Наступний мін. c=2 (позиція 1,1): x₁₁=15 (a₁→0)
// Лишок b₁=20-15=5 → x₂₁=5
// Наступний: x₂₂=15 (a₂→20-5-15=0)
Початковий план:
x₁₁=15, x₁₃=15, x₂₁=5, x₂₂=15
Вартість = 2·15 + 1·15 + 5·5 + 4·15 = 30+15+25+60 = 130
// ↓ ↓ ↓
a₁=30: [ 2 ] [ 3 ] [ 1 ] ← мін. c=1: x₁₃=15 (a₁→30-15=15)
a₂=20: [ 5 ] [ 4 ] [ 2 ]
// Наступний мін. c=2 (позиція 1,1): x₁₁=15 (a₁→0)
// Лишок b₁=20-15=5 → x₂₁=5
// Наступний: x₂₂=15 (a₂→20-5-15=0)
Початковий план:
x₁₁=15, x₁₃=15, x₂₁=5, x₂₂=15
Вартість = 2·15 + 1·15 + 5·5 + 4·15 = 30+15+25+60 = 130
2
Метод потенціалів (перевірка оптимальності): uᵢ+vⱼ=cᵢⱼ для базисних клітинок.
// Базисні клітинки: (1,1),(1,3),(2,1),(2,2)
u₁+v₁ = 2
u₁+v₃ = 1
u₂+v₁ = 5
u₂+v₂ = 4
// Задаємо u₁=0:
v₁=2, v₃=1, u₂=5-2=3, v₂=4-3=1
// Перевірка небазисних:
(1,2): Δ₁₂ = c₁₂−u₁−v₂ = 3−0−1 = 2 ≥ 0 ✓
(2,3): Δ₂₃ = c₂₃−u₂−v₃ = 2−3−1 = −2 < 0 ✗ → НЕ оптимум!
u₁+v₁ = 2
u₁+v₃ = 1
u₂+v₁ = 5
u₂+v₂ = 4
// Задаємо u₁=0:
v₁=2, v₃=1, u₂=5-2=3, v₂=4-3=1
// Перевірка небазисних:
(1,2): Δ₁₂ = c₁₂−u₁−v₂ = 3−0−1 = 2 ≥ 0 ✓
(2,3): Δ₂₃ = c₂₃−u₂−v₃ = 2−3−1 = −2 < 0 ✗ → НЕ оптимум!
3
Покращення: введемо x₂₃ в базис. Цикл перерозподілу: (2,3)→(1,3)→(1,1)→(2,1). Мін. у від'ємних вершинах: min(x₁₃,x₂₁)=min(15,5)=5. Перераховуємо.
// Нові значення після одного кроку:
x₂₃ = 0+5 = 5; x₁₃ = 15−5 = 10
x₁₁ = 15+5 = 20; x₂₁ = 5−5 = 0 ← виходить з базису
Новий план: x₁₁=20, x₁₃=10, x₂₂=15, x₂₃=5
Вартість = 2·20 + 1·10 + 4·15 + 2·5 = 40+10+60+10 = 120
x₂₃ = 0+5 = 5; x₁₃ = 15−5 = 10
x₁₁ = 15+5 = 20; x₂₁ = 5−5 = 0 ← виходить з базису
Новий план: x₁₁=20, x₁₃=10, x₂₂=15, x₂₃=5
Вартість = 2·20 + 1·10 + 4·15 + 2·5 = 40+10+60+10 = 120
Відповідь: Оптимальний план: x₁₁=20, x₁₃=10, x₂₂=15, x₂₃=5, мінімальна вартість = 120 (покращення на 10 порівняно з початком). Всі потенціали задовольняють умову оптимальності.
5
Аналіз чутливості — вплив зміни ресурсів
В оптимальному рішенні задачі 2 (x₁=0, x₂=5, Z=25) активним є лише обмеження 3: 3x₁+5x₂≤25. Тіньова ціна y₃*=1. Знайти діапазон стабільності b₃ та визначити нове оптимальне рішення при b₃=28.
1
Діапазон стабільності для b₃: поки s₁ та s₂ залишаються невід'ємними.
// При зміні b₃ → b₃+δ оптимальний базис {x₂} зберігається,
// якщо нове рішення залишається допустимим:
x₂ = (b₃+δ)/5 ≥ 0 → b₃+δ ≥ 0 → δ ≥ −25
2x₂ ≤ 12: 2(b₃+δ)/5 ≤ 12 → b₃+δ ≤ 30 → δ ≤ 5
x₁ = 0 (необмежено)
// Діапазон: b₃ ∈ [0, 30], тобто δ ∈ [−25, 5]
// При поточному b₃=25: від 0 до 30
// якщо нове рішення залишається допустимим:
x₂ = (b₃+δ)/5 ≥ 0 → b₃+δ ≥ 0 → δ ≥ −25
2x₂ ≤ 12: 2(b₃+δ)/5 ≤ 12 → b₃+δ ≤ 30 → δ ≤ 5
x₁ = 0 (необмежено)
// Діапазон: b₃ ∈ [0, 30], тобто δ ∈ [−25, 5]
// При поточному b₃=25: від 0 до 30
2
Нове рішення при b₃=28: δ=3, y₃*=1 → ΔZ=1·3=3.
// b₃=28 ∈ [0,30] → базис стабільний
x₂* = 28/5 = 5.6
Z* = 5·5.6 = 28 = 25 + 1·3 ✓
// Якщо b₃=31 (поза діапазоном) — входить обмеження 2 в базис
// і тіньова ціна змінюється
x₂* = 28/5 = 5.6
Z* = 5·5.6 = 28 = 25 + 1·3 ✓
// Якщо b₃=31 (поза діапазоном) — входить обмеження 2 в базис
// і тіньова ціна змінюється
Відповідь: Діапазон стабільності b₃: [0, 30]. При b₃=28: x₁=0, x₂=5.6, Z=28. Збільшення ресурсу 3 на 1 одиницю підвищує прибуток на 1 грн (тіньова ціна).
6
Цілочисельне ЛП — метод гілок і меж
Розв'язати цілочисельну задачу: max Z = 3x₁ + 4x₂ при: x₁ + x₂ ≤ 4; x₁ + 3x₂ ≤ 6; x₁,x₂ ≥ 0, цілі.
1
ЛП-релаксація (без умови цілочисельності):
// Вершини допустимої множини:
(0,0): Z=0
(4,0): Z=12
(3,1): Z=13 ← перетин x₁+x₂=4 і x₁+3x₂=6
(0,2): Z=8
// Знаходимо перетин:
x₁+x₂=4 і x₁+3x₂=6 → 2x₂=2 → x₂=1, x₁=3
Z_LP* = 3·3 + 4·1 = 13 (ціле рішення! перевіримо інші)
// x₁=3, x₂=1 — вже цілі числа!
Перевірка: 3+1=4 ≤ 4 ✓, 3+3=6 ≤ 6 ✓
(0,0): Z=0
(4,0): Z=12
(3,1): Z=13 ← перетин x₁+x₂=4 і x₁+3x₂=6
(0,2): Z=8
// Знаходимо перетин:
x₁+x₂=4 і x₁+3x₂=6 → 2x₂=2 → x₂=1, x₁=3
Z_LP* = 3·3 + 4·1 = 13 (ціле рішення! перевіримо інші)
// x₁=3, x₂=1 — вже цілі числа!
Перевірка: 3+1=4 ≤ 4 ✓, 3+3=6 ≤ 6 ✓
2
Уточнення: оскільки оптимум ЛП потрапив у цілу точку (3,1), то вона і є оптимумом ЦЛП. Перевіримо сусідні цілі точки:
// Усі допустимі цілі точки та Z:
(0,0): Z=0 (0,1): Z=4 (0,2): Z=8
(1,0): Z=3 (1,1): Z=7 (1,2)? 1+6=7>6 ✗
(2,0): Z=6 (2,1): Z=10 (2,2)? 2+6=8>6 ✗
(3,0): Z=9 (3,1): Z=13 (3,2)? 3+6=9>6 ✗
(4,0): Z=12
// Максимум: (3,1) → Z=13 ✓
(0,0): Z=0 (0,1): Z=4 (0,2): Z=8
(1,0): Z=3 (1,1): Z=7 (1,2)? 1+6=7>6 ✗
(2,0): Z=6 (2,1): Z=10 (2,2)? 2+6=8>6 ✗
(3,0): Z=9 (3,1): Z=13 (3,2)? 3+6=9>6 ✗
(4,0): Z=12
// Максимум: (3,1) → Z=13 ✓
3
Коли потрібне гілкування: якби оптимум ЛП був дробовим, наприклад x₂=1.5, то:
// Метод гілок і меж при дробовому x₂*=1.5:
Гілка A: додаємо x₂ ≤ 1 → нова ЛП-задача
Гілка B: додаємо x₂ ≥ 2 → нова ЛП-задача
// Розв'язуємо кожну підзадачу і порівнюємо
// (якщо оптимум дробовий — розгалужуємо далі)
// Нижня оцінка (lower bound) — краще знайдене ціле рішення
// Верхня оцінка (upper bound) — значення ЛП-релаксації
Гілка A: додаємо x₂ ≤ 1 → нова ЛП-задача
Гілка B: додаємо x₂ ≥ 2 → нова ЛП-задача
// Розв'язуємо кожну підзадачу і порівнюємо
// (якщо оптимум дробовий — розгалужуємо далі)
// Нижня оцінка (lower bound) — краще знайдене ціле рішення
// Верхня оцінка (upper bound) — значення ЛП-релаксації
Відповідь: Оптимальне ціле рішення: x₁=3, x₂=1, max Z=13. У цьому прикладі ЛП-релаксація дала ціле рішення одразу, тому гілкування не знадобилось.