Властивості ТЗО та основні теореми

1. Ранг складеної з векторів A _ij матриці A обмежень транспортної задачі дорівнює m+n 1, звідки випливає, що допустимий базисний розв’язок задачі (якщо він існує) має не більше m+n 1 перевезень x_ij, які задовольняють умову 0< x_ij < r_ij.

2. Розв’язок ТЗО є базисним, якщо з його основних комунікацій неможливо скласти замкнений маршрут (цикл).

3. Допустимий базисний розв’язок (ДБР) x = (x_ij, i= 1 ,...,m, j= 1 ,...,n) оптимальний тоді i тільки тоді, коли існують потенціали u_i, v_jтакі, що

v_j u_i = c_ij, якщо x_ij - базисне перевезення,

v_j u_i c_ij, якщо x_ij = 0, небазисне перевезення,

v_j u_i c_ij, якщо x_ij = r_ij, небазисне перевезення.

Метод пошуку вихідного ДБР. Вихiдний ДБР ТЗО (на відміну від ТЗ без обмежень), якщо він існує, знаходиться суттєво складніше. Його пошук здійснюється за два етапи.

Перший етап (попередній) нагадує метод мінімального елемента в ТЗ без обмежень i в загальному випадку не дає допустимого розв’язку.

Другий етап містить ряд iтерацiй методу потенціалів, який застосовується до деякої розширеної ТЗО, побудованої за результатами першого етапу.

Вихiдний ДБР ТЗО. I етап. На множині невикреслених клітинок транспортної таблиці знаходять клітинку (i₁, j₁) з мінімальними транспортними витратами .

Припускають .

Якщо , то викреслюють i1 -й рядок транспортної таблиці.

Якщо , то викреслюють j₁ -й стовпець Т-таблиці.

Якщо , то викреслюють тільки клітинку (i₁, j₁) транспортної таблиці.

Якщо , то у довільну, не викреслену на попередніх кроках клітинку, яка лежить або в i₁ – у рядку або в j₁ – у стовпчику, заносять нульове базисне перевезення.

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

Вихiдний ДБР ТЗО. II етап. Нехай X =|| x_ij ||, i= 1 ,...,m, j= 1 ,...,n, - матриця перевезень, що побудована на першому етапi. Покладемо

x_i,n+1 = a_i – (x_i1 +...+ x_in), i= 1 ,...,m,

x_m+1,j = b_j – (x_1j +...+ x_mj), j= 1 ,...,n.

Позначимо = x_1,n+1 +...+ x_m,n+1 = x_m+1,1 +...+ x_m+1,n.

Якщо =0, то x – вихідний ДБР.

Якщо >0, то вихідна ТЗ розширюється за рахунок фіктивних пунктів виробництва P_m+1 та споживання Q_n+1 з a_m+1 = b_n+1 =, де

c_i,n+1 = M, r_i,n+1 =, i= 1 ,...,m,

c_m+1,j = M, r_m+1,j =, j= 1 ,...,n,

c_m+1,n+1 = 0, r_m+1,n+1 =,

де M – досить велике додатне число, – нескінченність.

Нерозподiленi на першому етапі залишки продукту (як за об’ємами виробництва, так i за об’ємами споживання) розподіляються по фіктивних пунктах P_m+1 та Q_n+1. Відповідні заповнені клітинки вважаються базисними (оскільки пропускні здатності відповідних їм комунікацій необмежені) i приєднуються до сукупності базисних клітинок заповнених на першому етапі. Якщо після цього загальна кількість базисних клітинок не рівна (m+1) + (n+1)1, то множину базисних клітинок доповнюють до цього числа за рахунок незаповнених клітинок або заповнених до пропускної здатності, але так, щоб розширена множина базисних клітинок не містила циклів. Розширена ТЗ розв’язується методом потенціалів.

Якщо в оптимальному розв’язку x*_m+1,n+1 =, то, відкидаючи фіктивні пункти, отримаємо вихідний ДБР, інакше, ТЗО не має розв’язкiв.

Потенцiали. Потенцiали рядків ui, i=1,...,m, та колонок vj, j=1,...,n, визначаються як розв’язок системи vjui = cij, де i та j приймають такі значення, що клітинки (i,j) – базисні.

Вказана система містить m+n –1 рівнянь (за числом базисних клітинок) та m+n змінних. Тому одна із змінних задається довільно (u₁ = 0).

Оцiнки. Оцiнки ij змінних x_ij для всіх небазисних клітинок обчислю­ються за формулою _ij = c_ij – v_j + u_i (оцінки базисних змінних – ну­льо­ві). Поточний ДБР X =|| x_ij ||, i= 1 ,...,m, j= 1 ,...,n, оптимальний, коли

ij =0, якщо x_ij - базисне перевезення,

ij 0, якщо x_ij = 0, небазисне перевезення,

ij 0, якщо x_ij = r_ij, небазисне перевезення.

Цикл. Метод викреслювання. Під час побудови циклу застосовується метод викреслювання. На кожному кроцi методу в транспортній таблиці викреслюється або рядок, або стовпець, які в подальшому ігноруються. Викреслюванню підлягають рядки (стовпцi), що містять тільки одну базисну клітинку. Невикресленi клітинки транспортної таблиці утворюють цикл.

Новий ДБР. Серед всіх клітинок (i,j), для яких не виконується критерій оптимальності, обирають клітинку, що відповідає найбільшій за модулем оцінці ij. Позначимо таку клітинку через (i₀, j₀).

Нехай клітинка (i₀, j₀), для якої приєднується до сукупності базисних клітинок. Знаходиться цикл, що утворюється цими клітинками. Цикл розбивається на додатний (C+) та від’ємний (C) пiвцикли, клітинки яких чергуються одна з одною, причому клітинка (i₀, j₀) відноситься до додатного пiвциклу. Обчислюються величини

1 = min { x_ij } за C,

2 = min { r_ij – x_ij } за C+,

= min { ₁, ₂ }.

Далі збiльшують на значення перевезення x_ij в клітинках пiвциклу C+ i зменшують їх на те ж значення в клітинках C.

Для клітинки (i₀, j₀) такої, що різниця полягає у тому, що вона відноситься до від’ємного пiвциклу.

У результаті виконання вказаних процедур клітинка (i₀, j₀) вводиться до множини базисних, а клітинка, пов’язана з, стає небазисною. Якщо досягається на клітинці (i₀, j₀), то множина базисних клітинок не змінюється після перерозподілу перевезень вздовж циклу на сталу i новий ДБР матиме ту ж саму систему потенціалів i ті ж самі оцінки, що i попередній. Тому у цьому випадку після обчислення нового ДБР безпосередньо переходять до перевірки його на оптимальність.

Алгоритм методу потенціалів:

а) Будується вихідний ДБР.

б) Далі метод складається з однотипних кроків, на кожному з яких:

1) обчислюються потенціали ui, i= 1 ,...,m, та vj, j= 1 ,...,n;

2) обчислюються оцінки ij змінних x_ij, i= 1 ,...,m, j= 1 ,...,n;

3) аналiзуються знайдені оцінки ij. Якщо оцінка ij 0 для xi =0 та ij 0 для x_ij = r_ij, то поточний ДБР є оптимальним. Інакше, переходять до покращання поточного ДБР (п. п. 4 та 5).

4) будується цикл.

5) знаходиться новий ДБР.

Крок закінчено. Перехiд до пункту 1).

Задача про оптимальні призначення

Постановка задачі про призначення. Знайти вектор (матрицю) X= (x_ij, i,j=1,...,n), що мiнiмiзує цільову функцію:

L (X) = c₁₁x₁₁ +...+ c_1nx_1n +...+ c_n1x_n1 +...+ c_nnx_nn

i задовольняє систему обмежень:

x_i1 +... + x_in = 1, i=1,...,n,

x_1j +... + x_nj = 1, j=1,...,n,

x_ij = 0 або 1, i,j=1,...,n,

де c_ij – витрати, пов’язані з використанням i -го виконавця для виконання j -ї роботи (i,j=1,...,n). Елементи c_ij утворюють матрицю витрат C.

Наведена задача може бути розв’язана угорським методом, що грунтується на тому факті, що віднімання числа a_i, i=1,...,n, від кожного елемента i -го рядка та числа b_j, j=1,...,n, від кожного елемента j -го стовпця матриці витрат C не змінює множини оптимальних призначень, тобто вказані дії перетворюють матрицю витрат C в еквівалентну їй матрицю, яку також називають матрицею витрат.