Цикл перерахунку.

На другому етапі перевіряється - чи є базисне рішення оптимальним.

Для цього спочатку потрібно виразити цільову функцію W (3.1) задачі через неосновні (вільні) змінні. Мінімум цільової функції, тобто рішення транспортної задачі, отримується тоді, коли всі коефіцієнти при вільних (неосновних) змінних у виразі для цільової функції W (3.1) через вільні перемінні невід’ємні.

У транспортній задачі змінна х_ij ототожнюється з вмістом відповідної клітки (i, j) таблиці постачань. Позначимо b_ij коефіцієнт біля вільної змінної х_ij у виразі для лінійної функції цілі W (3.1) через вільні змінні; b_ij називається оцінкою вільної клітки (i, j).

При даному базисному розподілі постачань клітка (i, j) - вільна (змінна х_ij - вільна), b_ij - оцінка клітки (i, j) чи коефіцієнт у виразі лінійної функції W (3.1) через вільні змінні:

W = W₀ + b_ij х_ij + … (3.4)

де трикрапкою позначені доданки, що відповідають вільним змінним, відмінним від х_ij, W₀ – сумарні витрати на даний розподіл постачань.

Тоді з (3.4) випливає, що оцінка b_ij вільної (i, j) клітки дорівнює зміні сумарних витрат Δ W на постачання при переведенні в клітку (i, j) одиничного постачання (збільшення змінної х_ij від 0 до 1), тобто: b_ij = Δ W = W_п – W_н, де W_н - первинні витрати на постачання;
W_п - витрати на постачання після перерозподілу. Передбачається, що у всіх вільних клітках відмінних від клітки (i, j), постачання залишиться нульовим. Очевидно, що Δ W > 0 якщо
b_ij > 0; Δ W < 0 якщо b_ij < 0. Останнє непряме визначення оцінки вільної клітки називають економічним змістом оцінки вільної клітки.

Знайдемо оцінку вільної клітки А3. Для цього дамо в клітку А3 одиничне постачання. При цьому буде потрібно змінити постачання в заповнених клітках так, щоб зберігся баланс по рядках і стовпцям (передбачається, що у всіх вільних клітках відмінних від клітки А3, постачання залишиться нульовим). Так, щоб 3-й район як і раніше одержав 5 тис. номерів, постачання в клітці В3 варто зменшити на 1тис. Для того, щоб АТС В як і раніше поставила 3тис. номерів, постачання в клітці В2 збільшуємо на 1тис. 2-му району необхідно тільки 4тис. номерів, тому постачання в клітці А2 варто зменшити на 1тис. З'єднавши один по одному зазначені клітки A3 à B3 à B2 à A2 à A3 одержимо замкнутий контур (цикл).

Циклом перерахунку базисної транспортної таблиці називається група кліток цієї таблиці, з'єднаних замкнутою ламаною лінією, що проходить через клітки зі змінюваним постачанням і в кожній клітці робить поворот на + 90⁰. Одна з вершин лежить у вільній клітці, інші - у заповнених. Кожен цикл має парне число вершин.

Позначимо знаком «+» ті вершини, у яких постачання (перевезення) збільшуються, а знаком «-» ті, у яких вони зменшуються.

Позначеним циклом перерахунку називається цикл, у вершинах якого розставлені знаки «+» і «-», так, що у вільній клітці стоїть знак «+», а сусідні вершини мають протилежні знаки.

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

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

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

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

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

В отриманій базовій транспортній таблиці необхідно побудувати зазначені цикли перерахунку для усіх вільних кліток. У вихідній вільній клітці розміщаємо одну з вершин і приписуємо «+». Всі інші вершини перерахунку повинні спиратися на зайняті клітки.

А	4 3т	7 2т		5т
В		2т	1т	3т
С			4т	4т
n				Qj
q	3т	4т	5т

А3: A3 à B3 à B2 à A2 à A3 b_A3 = 6-11+15-7 = 3

B1: В1 à А1 à А2 à В2 à В1 b_В1 = 12-4+7-15 = 0

C1: С1 à С3 à В3 à В2 à А2 à A1 à C1 b_С1 = 13-10+11-15+7-4 = 2

C2: С2 à В2 à В3 à C3 à C2 b_С2 = 7-15+11-10 = -7

Для поліпшення рішення в розглянутій задачі можна виконати єдиний цикл перерахунку з від’ємною ціною b_С2:

А	3т	2т		5т
В		15- 2т	11 + 1т	3т
С		7 +	10 - 4т	4т
n				Qj
q	3т	4т	5т