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

Транспортна задача – це задача про найекономніший план перевезень із т пунктів виробництва (зберігання) продукції в п пунктів споживання. Нехай, наприклад, А₁, А₂, …, А_т – це фабрики-постачальники, які виробляють однорідну продукцію в кількостях а₁, а₂,…, а_т. Ця продукція відправляється на фабрики В₁, В₂,…, В_п, що потребують відповідно в₁, в₂,…, в_п одиниць цієї продукції. Відомі витрати на перевезення одиниці продукції від кожного постачальника і до кожного споживача j – с_ij. Складемо таблицю затрат (матрицю транспортних затрат) і матрицю невідомих x_ij, де x_ij - кількість одиниць продукції, доставлених від постачальника A_i споживачеві B_{j .} Об’єднаємо ці дві таблиці в одну (таблиця 1). Це – матриця (або план) перевезень; x_ij називаються перевезеннями.

Таблиця 1

Матриця перевезень

Ai	Bj
B1	B2	…	Bn
A1	c11 x11	c12 x12	…	c1n x1n
A2	c21 x21	c22 x22	…	c2n x2n
…	…	…	…	…
Am	cm1 xm1	cm2 xm2	…	cmn xmn

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

Складемо математичну модель задачі: мінімізувати лінійну форму при умовах

Щоб задача мала розв’язок, необхідно і достатньо виконання умови (баланс виробництва і споживання).

Сформульована задача – це ЗЛП. Простіше розв’язувати її не симплекс-методом, а методом потенціалів, який ми розглянемо нижче.

Для зручності представлення усіх вихідних даних транспортної задачі формують таблицю 2.

Таблиця 2.

Дані для транспортної задачі

Ai	Bj	К-сть од. продукції в п. Аі
B1	B2	…	Bn
A1	c11 x11	c12 x12	…	c1n x1n	а1
A2	c21 x21	c22 x22	…	c2n x2n	а2
…	…	…	…	…	…
Am	cm1 xm1	cm2 xm2	…	cmn xmn	ат
К-сть од. продукції в п. Вj	в1	в2	…	вп	∑ ai ∑ bj

Спочатку побудуємо перший опорний план задачі (наприклад, методом північно-західного кута).

Щоб перевірити опорний план на оптимальність, користуються методом потенціалів. Виявляється, що для будь-якого опорного плану існують потенціали u_i, v_j такі, що v_j – u_i=c_ij (i m, j n). Ці потенціали розраховуються для всіх базисних змінних опорного плану діагональним методом (для першого, другого і т.д. рядка). Один із потенціалів (наприклад, и₁) можна вибрати довільно.

Далі проводимо розрахунки для кожної з пустих клітин: обчислюємо для них різниці виду v_j-u_i-c_ij. Якщо різниця недодатня ( 0), то відповідна клітинка має бути незаповненою (оскільки перевезення невигідне). Якщо ж ця різниця більша нуля (її називають нев’язкою), то план не оптимальний.

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

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

1)Вершини ламаної лежать у центрах клітинок матриці, причому тільки одна вершина розміщена у вільній клітинці, а всі інші – у базисних.

2)Ланки ламаної розміщені паралельно або рядкам, або стовпчикам матриці.

3)У кожній вершині перетинаються тільки дві ланки.

4)Ніякі три вершини не лежать на одній прямій.

5)Вершина, що лежить у вільній клітинці матриці, вважається додатною, і коло неї ставлять знак «+».

6)Всі інші вершини отримують по черзі знаки «–» і «+».

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

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

Виявляється, що доцільно вибирати х так: де - перевезення, розміщенні у від’ємних вершинах циклу перерахунку.

Сформулюємо принцип послідовного «покращення» матриці перевезень транспортної задачі.

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

Зсуваючи по циклу перерахунку на число х, утворюють нову матрицю з меншими нев’язками (або без них).

До транспортного алгоритму зводиться чимало інших задач – наприклад, задача про призначення: потрібно розподілити т робіт (або виконавців) по п верстатах (або участках). Робота і (і=1,2,…т), що виконується на верстаті j (j=1,2,…,n), пов’язана з витратами c_ij. Задача полягає у такому розподілі робіт по верстатах (одна робота виконується одним верстатом), якому відповідає мінімум сумарних витрат.