Оптимізація рішення транспортної задачі (оптимізація розподілу постачань).

При переміщенні по циклу k одиниць ресурсу зміна вартості складе Δ W=k ´ b_ij. При цьому значення ресурсу в клітках зі знаком «+» збільшиться на k, а в клітках зі знаком «-» - зменшиться на k.

Значення k вибирається серед кліток циклу, що мають знак «-». Крім того, воно має мінімальне значення серед цих кліток, отже k = min{2, 4} = 2, тобто це буде клітка B2. Для обнулення постачання в цій клітці по циклу слід передати 2 одиниці ресурсу. Постачання, передане по циклу, визначається як мінімум серед постачань у клітках циклу зі знаком «-». Після цього клітка В3 вважається заповненою, а клітка В2 - вільною. Одержали новий базисний розподіл постачань:

А	3т	7 - 2т	6 +	5т
В			3т	3т
С		7 + 2т	10 - 2т	4т
n				Qj
q	3т	4т	5т

Зміна витрат на новому розподілі складе Δ W⁽¹⁾ = -7 ´ 2 = -14. Загальний обсяг витрат при новому базисному розподілі складе: W⁽¹⁾ = W⁽⁰⁾ + Δ W⁽¹⁾ = 107-14 = 93.

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

A3: b_A3 = 6-10+7-7 = - 4 по циклу A3à C3à C2à А2 à A3.

B1: b_B1 = 12-4+7-7+10-11 = 7 пo циклу B1à A1à A2à C2à C3à В3à В1.

В2: b_B2 = 15-7+10-11 = 7 по циклу B2à C2à C3à B3à B2.

C1: b_C1 = 13-4+7-7 = 9 по циклу C1à A1à A2à C2à C1.

Оскільки є вільні клітки з від’ємною оцінкою (b₃ = - 4), то оптимальне рішення ще не знайдене. Для одержання чергового базисного розподілу використовуємо цикл перерахунку по A3. При цьому k = min{2, 2} = 2; Δ W⁽²⁾ = b₃ x k⁽²⁾ = - 4 x 2 = - 8; W⁽²⁾= W⁽¹⁾ + Δ W⁽²⁾ = 93 - 8 = 85.

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

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

Загальний алгоритм рішення транспортної задачі може бути сформульований у такому вигляді:

1. Для даного базисного розподілу постачань підбираються потенціали рядків і стовпців таблиці постачань так, щоб коефіцієнти витрат заповнених кліток стали рівні 0. Складається матриця оцінок.

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

3. Для обраної вільної клітки будується зазначений цикл перерахунку. Постачання k, передане по циклу, визначається як мінімум серед постачань у клітках зі знаком «-». Знайдене постачання пересувається по циклу. При цьому постачання в клітках зі знаком «+» збільшується на k, а в клітках зі знаком «-» зменшується на k. Клітка, постачання в який при цьому стане рівним 0, буде вважатися вільною, інші клітки циклу – заповненими. Таким чином, отримано базисний розподіл постачань.

4. Переходимо до п. 1 алгоритму.

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

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