Лекція 07. Транспортна задача як структуроване лінійне програмування

Коротко про лекцію

Тут транспортна задача будується з реальної схеми «склади — споживачі». Ви навчитеся задавати постачання, потреби, транспортні витрати, баланс і спеціальні обмеження так, щоб отримати коректну LP-модель.

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

Постановка та базові поняття

1. Яку проблему описує транспортна задача

Уявімо мережу з кількома складами та магазинами. Кожний склад має обмежений запас. Кожний магазин має задану потребу. Для кожної пари «склад — магазин» відома вартість перевезення однієї одиниці вантажу.

Потрібно визначити потоки між усіма парами. Відправки зі складу не можуть перевищувати доступний запас. Кожний магазин повинен отримати потрібний обсяг. Загальна транспортна вартість має бути мінімальною.

Така структура виникає у логістиці, розподілі матеріалів, постачанні магазинів, плануванні перевезень і мережевих потоках.

1.1. Чому транспортна задача має окремі терміни

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

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

Ці величини не є новими фізичними даними. Вони є інструментами перевірки оптимальності. У сучасному обчислювальному розв’язанні їх зазвичай отримує чисельний розв’язувач, а ручний приклад потрібен для розуміння змісту.

2. Наскрізний приклад

Маємо два склади та три магазини.

Запаси складів:

\[ a_1=20,\qquad a_2=30 \]

Потреби магазинів:

\[ b_1=10,\qquad b_2=25,\qquad b_3=15 \]

Вартість перевезення одиниці вантажу:

Постачальник	Магазин 1	Магазин 2	Магазин 3	Запас
Склад 1	4	6	8	20
Склад 2	5	3	7	30
Потреба	10	25	15	—

Сума запасів:

\[ 20+30=50 \]

Сума потреб:

\[ 10+25+15=50 \]

Баланс виконується. Таку модель називають закритою або збалансованою транспортною задачею.

3. Що означає індексована змінна

Позначимо через \(x_{ij}\) кількість вантажу, яку постачальник \(i\) відправляє споживачу \(j\).

Наприклад:

\[ x_{12}=7 \]

означає, що зі складу 1 до магазину 2 відправляють 7 одиниць.

Для двох складів і трьох магазинів маємо шість змінних:

\[ x_{11},x_{12},x_{13},x_{21},x_{22},x_{23} \]

Усі вони невід’ємні:

\[ x_{ij}\ge0 \]

4. Матриця транспортного плану

Змінні природно розмістити в таблиці:

\[ X= \begin{pmatrix} x_{11} & x_{12} & x_{13}\\ x_{21} & x_{22} & x_{23} \end{pmatrix} \]

Рядок відповідає одному постачальнику. Стовпець відповідає одному споживачу.

Ця матрична форма допомагає контролювати порядок даних. Один і той самий порядок потрібно зберігати в цільовій функції, балансах і Python-масивах.

5. Баланси постачальників

Перший склад має 20 одиниць. Сума всіх його відправок повинна дорівнювати 20:

\[ x_{11}+x_{12}+x_{13}=20 \]

Другий склад має 30:

\[ x_{21}+x_{22}+x_{23}=30 \]

У закритій транспортній задачі весь запас розподіляється. Тому в базовій моделі використовуються рівності.

6. Баланси споживачів

Магазин 1 потребує 10 одиниць:

\[ x_{11}+x_{21}=10 \]

Для другого магазину:

\[ x_{12}+x_{22}=25 \]

Для третього:

\[ x_{13}+x_{23}=15 \]

Ці рівності гарантують точне виконання попиту.

7. Цільова функція

Кожне перевезення має вартість «кількість × ціна за одиницю».

Для маршруту зі складу 1 до магазину 1:

\[ 4x_{11} \]

Повна вартість:

\[ C= 4x_{11}+6x_{12}+8x_{13} +5x_{21}+3x_{22}+7x_{23} \]

Потрібно мінімізувати:

\[ C\rightarrow\min \]

Математична логіка

8. Загальний запис транспортної моделі

Нехай є \(m\) постачальників та \(n\) споживачів.

\(a_i\) — запас постачальника \(i\).

\(b_j\) — потреба споживача \(j\).

\(c_{ij}\) — вартість перевезення одиниці з \(i\) до \(j\).

\(x_{ij}\) — обсяг перевезення.

Тоді ціль:

\[ \min \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij}x_{ij} \]

Баланси постачальників:

\[ \sum_{j=1}^{n}x_{ij}=a_i, \qquad i=1,\dots,m \]

Баланси споживачів:

\[ \sum_{i=1}^{m}x_{ij}=b_j, \qquad j=1,\dots,n \]

Невід’ємність:

\[ x_{ij}\ge0 \]

9. Закрита та відкрита модель

Закрита модель виконує баланс:

\[ \sum_i a_i= \sum_j b_j \]

Якщо запасів більше, ніж потреб, додають фіктивного споживача. Його попит дорівнює надлишку запасу.

Якщо потреб більше, додають фіктивного постачальника. Його запас дорівнює дефіциту.

Вартість фіктивних перевезень залежить від змісту задачі. Нульова вартість підходить тільки тоді, коли така інтерпретація справді коректна.

10. Що таке допустимий транспортний план

Допустимий план задовольняє всі рядкові та стовпчикові баланси й умови невід’ємності.

Розглянемо план:

\[ X= \begin{pmatrix} 10 & 0 & 10\\ 0 & 25 & 5 \end{pmatrix} \]

Перевіримо рядки.

Перший склад:

\[ 10+0+10=20 \]

Другий склад:

\[ 0+25+5=30 \]

Перевіримо стовпці.

Магазин 1:

\[ 10+0=10 \]

Магазин 2:

\[ 0+25=25 \]

Магазин 3:

\[ 10+5=15 \]

Усі баланси виконуються.

11. Вартість допустимого плану

Обчислимо сумарну вартість:

\[ C= 4\cdot10+ 6\cdot0+ 8\cdot10+ 5\cdot0+ 3\cdot25+ 7\cdot5 \]

\[ C=40+80+75+35=230 \]

Число 230 є вартістю цього плану.

Для твердження про оптимальність потрібна додаткова перевірка або чисельний розв’язувач.

12. Базисні клітини

Для транспортної таблиці базисний план зазвичай має \(m+n-1\) базисних клітин за невиродженого випадку.

У нашій задачі:

\[ m+n-1=2+3-1=4 \]

План має чотири додатні клітини:

\[ x_{11},x_{13},x_{22},x_{23} \]

Ця структура дозволяє використати метод потенціалів для перевірки оптимальності.

13. Для чого потрібні потенціали

Вводимо потенціали \(u_i\) для рядків і \(v_j\) для стовпців.

Для базисної клітини виконується:

\[ u_i+v_j=c_{ij} \]

Одна змінна може бути вибрана довільно, бо система має одну ступінь свободи. Зручно покласти:

\[ u_1=0 \]

Для клітини \((1,1)\):

\[ u_1+v_1=4 \]

Тому:

\[ v_1=4 \]

Для \((1,3)\):

\[ u_1+v_3=8 \]

Отже:

\[ v_3=8 \]

Для \((2,3)\):

\[ u_2+v_3=7 \]

Звідси:

\[ u_2=-1 \]

Для \((2,2)\):

\[ u_2+v_2=3 \]

Тому:

\[ v_2=4 \]

Отримали:

\[ u= \begin{pmatrix} 0\\ -1 \end{pmatrix} \]

\[ v= \begin{pmatrix} 4\\ 4\\ 8 \end{pmatrix} \]

14. Знижені вартості небазисних клітин

Для небазисної клітини визначимо:

\[ \Delta_{ij}=c_{ij}-u_i-v_j \]

Для \((1,2)\):

\[ \Delta_{12}=6-0-4=2 \]

Для \((2,1)\):

\[ \Delta_{21}=5-(-1)-4=2 \]

Обидва значення додатні.

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

15. Чому транспортна задача є спеціальним LP

Усі змінні, ціль і баланси лінійні. Тому транспортна задача є лінійною програмою.

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

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

Алгоритм і покроковий розбір

16. Робочий маршрут розв’язання

Для навчальної транспортної задачі зручно діяти так:

1. перевірити баланс запасів і потреб;
2. визначити змінні \(x_{ij}\);
3. записати рядкові та стовпчикові баланси;
4. побудувати цільову функцію;
5. знайти допустимий план;
6. перевірити його вартість;
7. перевірити оптимальність потенціалами або чисельним розв’язувачем;
8. повторно перевірити всі баланси.

Кожний крок має окрему математичну перевірку.

17. Візуальна структура оптимального плану

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

Мережеве подання показує ті самі значення \(x_{ij}\) як потоки між двома групами вузлів.

Програмна реалізація та перевірка

18. Як перетворити матрицю рішень на вектор чисельного розв’язувача

Загальний розв’язувач лінійного програмування працює з одновимірним вектором змінних.

Зафіксуємо порядок:

\[ x= \begin{pmatrix} x_{11}\\ x_{12}\\ x_{13}\\ x_{21}\\ x_{22}\\ x_{23} \end{pmatrix} \]

Вектор вартостей має той самий порядок:

\[ c= \begin{pmatrix} 4\\ 6\\ 8\\ 5\\ 3\\ 7 \end{pmatrix} \]

Порядок є частиною моделі. Його зміна тільки в одному масиві створить іншу математичну задачу.

19. Розв’язання через linprog

# Імпортуємо NumPy, SciPy для обчислень, розв’язання моделі та її перевірки.
import numpy as np
from scipy.optimize import linprog


# Задаємо коефіцієнти цільової функції в тому самому порядку, що й компоненти вектора змінних.
transport_cost = np.array([
    4.0, 6.0, 8.0,
    5.0, 3.0, 7.0,
])

# Порядок змінних:
# x11, x12, x13, x21, x22, x23
balance_matrix = np.array([
    [1, 1, 1, 0, 0, 0],  # склад 1
    [0, 0, 0, 1, 1, 1],  # склад 2
    [1, 0, 0, 1, 0, 0],  # магазин 1
    [0, 1, 0, 0, 1, 0],  # магазин 2
    [0, 0, 1, 0, 0, 1],  # магазин 3
], dtype=float)

# Обчислюємо план, баланс або вартість транспортної задачі.
balance_values = np.array([
    20.0,
    30.0,
    10.0,
    25.0,
    15.0,
])

# Запускаємо linprog: ціль, матрицю нерівностей, праві частини та межі передаємо у фіксованому порядку.
result = linprog(
    c=transport_cost,
    A_eq=balance_matrix,
    b_eq=balance_values,
    bounds=(0.0, None),
    method="highs",
)

# Перевіряємо статус розв’язувача до читання числового плану; невдалий запуск не є розв’язком.
if not result.success:
    raise RuntimeError(result.message)

# Зчитуємо числовий результат розв’язувача, але ще не вважаємо його перевіреним розв’язком.
plan = result.x.reshape(2, 3)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("План:")
print(plan)
print("Мінімальна вартість:", result.fun)

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

20. Очікуваний результат

Один оптимальний план:

\[ X^*= \begin{pmatrix} 10 & 0 & 10\\ 0 & 25 & 5 \end{pmatrix} \]

Мінімальна вартість:

\[ C^*=230 \]

21. Незалежна перевірка в Python

Після чисельного розв’язувача окремо перевіряємо суми рядків і стовпців:

# Задаємо праві частини, запаси або спостереження у порядку, узгодженому з рядками матриці.
supply = np.array([20.0, 30.0])
demand = np.array([10.0, 25.0, 15.0])

# Обчислюємо план, баланс або вартість транспортної задачі.
tolerance = 1e-6

# Обчислюємо нев’язку або запас безпосередньо з початкових формул для незалежної перевірки.
row_residual = plan.sum(axis=1) - supply
column_residual = plan.sum(axis=0) - demand

# Обчислюємо нев’язку або запас безпосередньо з початкових формул для незалежної перевірки.
is_balanced = (
    np.max(np.abs(row_residual)) <= tolerance
    and np.max(np.abs(column_residual)) <= tolerance
)

# Обчислюємо план, баланс або вартість транспортної задачі.
verified_cost = np.sum(
    plan * np.array([
        [4.0, 6.0, 8.0],
        [5.0, 3.0, 7.0],
    ])
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Баланс виконується:", is_balanced)
print("Перевірена вартість:", verified_cost)

Очікуємо True і 230.

Інтерпретація, межі та підсумок

22. Що означає оптимальний план предметно

Склад 1 відправляє 10 одиниць у магазин 1 і 10 одиниць у магазин 3.

Склад 2 відправляє 25 одиниць у магазин 2 і 5 одиниць у магазин 3.

Усі запаси використані. Усі потреби виконані. Загальна транспортна вартість дорівнює 230.

23. Чому найдешевша клітина не визначає весь план

Найменша вартість у таблиці дорівнює 3 для маршруту склад 2 → магазин 2.

Можна відправити туди 25 одиниць, але після цього залишаються інші потреби та запаси. Тому рішення формується системою взаємопов’язаних балансів.

Локально дешевий маршрут корисний, але його вибір впливає на залишкову структуру всієї таблиці.

24. Типова помилка

Типова помилка. Після отримання плану перевіряють тільки сумарну вартість. Транспортний план спочатку повинен виконувати кожний рядковий і стовпчиковий баланс.

25. Межі моделі

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

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

У таких випадках можуть знадобитися MILP, CP-SAT або спеціалізовані моделі маршрутизації.

25.1. Початковий план методом північно-західного кута

Перед перевіркою оптимальності транспортний метод потребує допустимого опорного плану. Один простий спосіб — метод північно-західного кута.

Починаємо з клітини \((1,1)\). Запас першого складу дорівнює 20, а потреба першого магазину — 10. Тому відправляємо:

\[ x_{11}=\min(20,10)=10 \]

Потребу магазину 1 виконано. На складі 1 залишається:

\[ 20-10=10 \]

Переходимо до клітини \((1,2)\). Магазину 2 потрібно 25, а склад 1 має залишок 10:

\[ x_{12}=10 \]

Склад 1 вичерпано. Для магазину 2 залишається потреба:

\[ 25-10=15 \]

Переходимо до складу 2:

\[ x_{22}=15 \]

Після цього в складі 2 залишається 15, а магазин 2 повністю забезпечений.

Останній магазин отримує:

\[ x_{23}=15 \]

Початковий план:

\[ X^{NW}= \begin{pmatrix} 10 & 10 & 0\\ 0 & 15 & 15 \end{pmatrix} \]

Його вартість:

\[ C^{NW}= 4\cdot10+ 6\cdot10+ 3\cdot15+ 7\cdot15 \]

\[ C^{NW}=40+60+45+105=250 \]

План допустимий, але дорожчий за оптимальні 230. Це корисний приклад різниці між допустимістю та оптимальністю.

25.2. Чому один балансовий рядок є залежним

У закритій транспортній задачі сумарний запас дорівнює сумарній потребі.

Якщо виконані всі рядкові баланси та перші \(n-1\) стовпчикових балансів, останній стовпчиковий баланс уже випливає з загального балансу.

У нашому прикладі сума двох рядків дорівнює 50. Якщо магазини 1 і 2 разом отримали 35, то для третього магазину автоматично залишається:

\[ 50-35=15 \]

Тому матриця рівностей транспортної задачі має лінійну залежність.

Ця властивість не означає помилку моделі. Вона походить із балансової структури. У ручних методах одну рівність часто не використовують як незалежну.

25.3. Цикл як допустимий напрям зміни плану

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

Тому транспортні методи використовують замкнений цикл із чергуванням знаків «плюс» і «мінус».

Нехай небазисна клітина входить у план із приростом \(\theta\). У тому самому рядку одна базисна клітина зменшується на \(\theta\). Далі в її стовпці інша клітина збільшується на \(\theta\).

Замикання циклу гарантує, що кожний рядок і кожний стовпець отримує однаковий приріст і спад. Тому баланси зберігаються.

Ця ідея є транспортним аналогом допустимого опорного переходу в симплекс-методі.

25.4. Як знижена вартість передбачає зміну вартості

Для небазисної клітини:

\[ \Delta_{ij}=c_{ij}-u_i-v_j \]

У задачі мінімізації від’ємне значення показує потенційне зменшення цілі при введенні клітини у базис.

Додатне значення означає, що локальна зміна через цю клітину збільшуватиме вартість.

У нашому оптимальному плані:

\[ \Delta_{12}=2 \]

і:

\[ \Delta_{21}=2 \]

Тому обидві небазисні клітини мають додатні оцінки. Жодна з них не дає напрям зменшення вартості.

25.5. Чому потенціали визначені з точністю до сталої

Рівності базисних клітин мають форму:

\[ u_i+v_j=c_{ij} \]

Якщо до всіх \(u_i\) додати одну й ту саму константу \(k\), а від усіх \(v_j\) відняти \(k\), суми \(u_i+v_j\) не зміняться.

Тому система потенціалів має одну ступінь свободи.

Зручно покласти один потенціал рівним нулю:

\[ u_1=0 \]

Це не змінює знижені вартості. Такий вибір тільки фіксує конкретне представлення потенціалів.

25.6. Виродження транспортного плану

Невироджений базисний план має:

\[ m+n-1 \]

базисних клітин.

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

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

У навчальному прикладі маємо чотири додатні клітини для \(2\times3\) задачі, тому базис невироджений.

25.7. Як транспортна таблиця переходить у загальний LP

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

Важливо зафіксувати спосіб розгортання. У лекції використовується порядок за рядками:

\[ (x_{11},x_{12},x_{13},x_{21},x_{22},x_{23}) \]

Кожний рядковий баланс перетворюється на рядок матриці \(A_{eq}\). Кожний стовпчиковий баланс також перетворюється на окремий рядок.

Наприклад, баланс магазину 2:

\[ x_{12}+x_{22}=25 \]

має коефіцієнти:

\[ (0,1,0,0,1,0) \]

Цей конкретний зв’язок корисно вміти побудувати вручну. Після цього API чисельного розв’язувача перестає виглядати як набір незрозумілих масивів.

25.8. Верифікація через нев’язка баланси

Для транспортної задачі корисно обчислювати два нев’язка-вектори.

Рядковий нев’язка:

\[ r^{supply}_i= \sum_jx_{ij}-a_i \]

Стовпчиковий нев’язка:

\[ r^{demand}_j= \sum_ix_{ij}-b_j \]

План вважаємо збалансованим, якщо:

\[ \max_i|r^{supply}_i|\le\varepsilon \]

і:

\[ \max_j|r^{demand}_j|\le\varepsilon \]

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

25.9. Коли транспортна модель потребує обмежень пропускної здатності

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

У реальній логістиці маршрут може мати власну пропускна здатність:

\[ x_{ij}\le u_{ij} \]

Наприклад, одна дорога може пропускати не більше 8 машин за зміну.

Таке обмеження залишається лінійним, тому модель все ще може розв’язуватися як LP. Спеціальна класична транспортна структура стає складнішою, але загальний чисельний розв’язувач легко враховує додаткову нерівність.

25.10. Фіксована вартість відкриття маршруту

Припустимо, використання маршруту має фіксовану плату \(F_{ij}\), яка сплачується один раз, якщо потік додатний.

Тоді одного неперервного \(x_{ij}\) недостатньо. Потрібна бінарна змінна:

\[ y_{ij}\in\{0,1\} \]

і зв’язок:

\[ x_{ij}\le M_{ij}y_{ij} \]

Ціль міститиме:

\[ c_{ij}x_{ij}+F_{ij}y_{ij} \]

Така модель уже належить до MILP. Цей приклад показує, як предметна деталь змінює математичний клас задачі.

25.11. Транспортна задача як підготовка до мережевих потоків

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

У наступній мережевій моделі з’являться проміжні вузли. Потік зможе проходити через кілька дуг.

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

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

25.12. Як порівняти два допустимі транспортні плани

Нехай маємо два плани \(X^{(1)}\) і \(X^{(2)}\). Спочатку кожний з них окремо проходить балансову перевірку. Після цього порівнюються їхні вартості.

Для першого допустимого плану з північно-західного кута:

\[ C^{NW}=250 \]

Для оптимального плану:

\[ C^*=230 \]

Економія:

\[ 250-230=20 \]

Відносно початкової вартості це:

\[ \frac{20}{250}=0.08 \]

тобто 8%. Така інтерпретація показує практичну цінність оптимізації, а не тільки зміну таблиці.

25.13. Чому нульове перевезення теж має зміст

Клітина з \(x_{ij}=0\) означає, що відповідний маршрут не використовується у поточному плані. Нуль не означає, що маршрут відсутній фізично.

Маршрут може залишатися доступним і мати певну знижена вартість. Якщо параметри зміняться, він може увійти до оптимального базису.

Тому транспортна таблиця описує рішення для конкретних запасів, потреб і вартостей.

25.14. Чутливість транспортного плану

Якщо одна транспортна вартість \(c_{ij}\) трохи змінюється, поточний оптимальний план може зберегтися. Знижена вартість показує запас до зміни привабливості небазисної клітини.

Для клітини \((1,2)\) маємо:

\[ \Delta_{12}=2 \]

Тому зменшення її вартості на невелику величину меншу за 2 ще не робить маршрут вигіднішим за поточний базисний режим.

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

25.15. Що студент повинен уміти перевірити вручну

Мінімальний ручний аудит транспортної задачі складається з чотирьох дій. Спочатку перевіряється глобальний баланс. Далі — суми всіх рядків і стовпців. Потім повторно обчислюється вартість. На завершення для невеликої задачі перевіряються потенціали та знижені вартості.

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

25.16. Ручний контроль вартості за матрицею

Транспортну вартість зручно перевіряти через покомпонентний добуток двох матриць. Для кожної клітини множимо \(c_{ij}\) на \(x_{ij}\), а потім додаємо всі результати. Якщо маршрут не використовується, його внесок дорівнює нулю. Такий спосіб добре переноситься в NumPy через plan * cost_matrix і подальшу суму.

25.17. Що змінюється при забороненому маршруті

Якщо певне перевезення фізично неможливе, відповідну змінну потрібно виключити або зафіксувати:

\[ x_{ij}=0 \]

Не варто задавати «дуже велику» вартість без пояснення. Вона може спотворити чисельний масштаб і залишає маршрут формально доступним. Явна заборона точніше передає предметне правило.

25.18. Порівняння чисельний розв’язувач-плану з ручним оптимумом

Для маленького прикладу ручний план і результат чисельного розв’язувача повинні збігатися за вартістю. Самі матриці можуть відрізнятися, якщо задача має кілька оптимумів. Тому головна перевірка — баланси, невід’ємність і мінімальна ціль.

25.19. Чому порядок індексів важливий у коді

У транспортній моделі \(x_{12}\) і \(x_{21}\) описують різні маршрути. Перший індекс позначає постачальника, другий — споживача. Тому перестановка індексів змінює предметний зміст змінної.

У Python це правило потрібно зберігати в reshape, у векторі цільових коефіцієнтів і в матриці балансів. Наприклад, порядок за рядками:

\[ (x_{11},x_{12},x_{13},x_{21},x_{22},x_{23}) \]

повинен використовуватися всюди однаково.

25.20. Як перевірити план без чисельного розв’язувача

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

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

25.21. Предметна інтерпретація потенціалів

Потенціали \(u_i\) та \(v_j\) можна читати як внутрішні оцінки вузлів транспортної системи. Їхні абсолютні значення залежать від вибору нульового потенціалу, але суми \(u_i+v_j\) та знижені вартості мають стабільний зміст.

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

25.22. Міні-чекліст транспортної моделі

Перед завершенням задачі перевірте, що сумарний запас узгоджений із попитом, усі \(x_{ij}\) невід’ємні, кожний рядок має правильну суму, кожний стовпець має правильну суму, а вартість повторно обчислена з початкової матриці \(c_{ij}\). Якщо використовується метод потенціалів, окремо перевірте рівності на базисних клітинах і знижені вартості небазисних клітин.

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

Перевірка залишається однаковою і для ручного плану, і для бібліотечного результату. Різниця полягає тільки у способі пошуку. Баланси, невід’ємність та значення цілі мають бути підтверджені незалежно від алгоритму.

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

Інтерактивна самоперевірка лекції

Пройдіть 10 коротких питань. Після кожної відповіді ви побачите пояснення, а за потреби — підказку й повний розбір.

26. Підсумок

Транспортна задача є структурованою лінійною моделлю, де змінна \(x_{ij}\) описує обсяг перевезення від постачальника \(i\) до споживача \(j\). Ціль складається з вартостей перевезень, а обмеження балансу контролюють пропозицію та попит. Таблична форма допомагає перевірити порядок індексів і відповідність коефіцієнтів конкретним маршрутам.

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

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