3. Метод потенціалів

Припустимо, ми знайшли вихідне опорне рішення і базис цього рішення A_i1, A_i2, … A_im. Поставимо у відповідність кожному обмеженню транспортної задачі деяку змінну, яку назвемо потенціалом пункту відправлення чи пункту споживання.

А₁ (перше обмеження по запасах)  U₁,

А₂ (друге обмеження по запасах)  U₂,

………………………………………..

А_m (m- е обмеження по запасах)  U_m,

B₁ (перше обмеження по потребах)  V₁,

B₂ (друге обмеження по потребах)  V₂,

………………………………………..

B_n (n- е обмеження по потребах)  V_n.

Для кожної базисної клітинки справедливе співвідношення: U_i+V_j=C_ij.

Для кожної базисної клітинки складаємо таке рівняння й одержуємо систему з m+n-1 векторів з m+n змінними. Щоб вирішити таку систему необхідно прийняти одну змінну (будь–яку) як нульову. Для небазисних клітинок знаходимо оцінки ∆_ij у такий спосіб: ∆_ij = U_i+V_j-C_ij (для базисних клітинок : ∆_ij = 0).

Якщо всі оцінки ∆_ij 0, то знайдене рішення оптимальне. Якщо ні, то для однієї з клітинок, де max(∆_ij>0) будуємо цикл перерахування. Ставимо у клітинку ”+”. У цьому стовпці та цьому рядку треба поставити ”-” у заповнених клітинках. Потім, якщо у якійсь клітинці ”-”, то у цьому стовпці та цьому рядку треба поставити ”+” у заповнених клітинках. Так отримується цикл. Для кожної порожньої клітинки можна побудувати єдиний цикл перерахування. Далі з тих клітинок, у яких стоїть " - " вибираємо ту, у якої найменша величина постачання. Це число треба додати у всі клітинки з ”+” та відняти в усіх клітинках з " - ". У наступному розподілі одна клітинка буде порожньою, інші переписуємо без змін.

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

А₁  U₁,

А₂  U₂,

А₃  U₃,

B₁  V₁,

B₂  V₂,

B₃  V_3,

B₄  V₄,

B₅  V₅.

Виходячи з того, що для кожної базисної клітинки справедливе співвідношення: U_i+V_j=C_ij, складаємо 7 рівнянь з 8 невідомими.

Таблиця 3.6

Пункт відправлення		Пункт споживання										Запас
		B1	V1	B2	V2	B3	V3	B4	V4	B5	V5
A1	U1	4		1 45		3		4		4 15		60
A2	U2	2 22		3		2 13		2		3		35
A3	U3	3		5		2 7		4 18		4 15		40
Потреба		22		45		20		18		30		135

U₁+V₂=1;

U₁+V₅=4;

U₂+V₁=2;

U₂+V₃=2;

U₃+V₃=2;

U₃+V₄=4;

U₃+V₅=4.

Покладемо U₁=0, тоді з системи знайдемо інші невідомі:

U1=0; U2=0; U3=0;

V1=2; V2=1; V3=2; V4=4; V5=4.

Для небазисних клітинок знаходимо оцінки ∆_ij = U_i+V_j-C_ij.

∆₁₁ = U₁+V₁-C₁₁=0+2-4= -2; ∆₁₃ = U₁+V₃-C₁₃=0+2-3= -1;

∆₁₄ = U₁+V₄-C₁₄=0+4-4=0; ∆₂₂ = U₂+V₂-C₂₂=0+1-3= -2;

∆₂₄ = U₂+V₄-C₂₄=0+4-2=2; ∆₂₅ = U₂+V₅-C₂₅=0+4-3=1;

∆₃₁ = U₃+V₁-C₃₁=0+2-3= -1; ∆₃₂ = U₃+V₂-C₃₂=0+1-5= -4.

Оскільки не всі ∆_ij≤0, то план не оптимальний. Треба будувати цикл переходу. Шукаємо max(∆_ij>0)=2=∆₂₄. В А₂В₄ ставимо ”+”, в А₃В₄ ставимо ”-”, в А₃В₃ ставимо ”+”, в А₂В₃ ставимо ”-”.

Таблиця 3.7

Пункт відправлення		Пункт споживання										Запас
		B1	V1	B2	V2	B3	V3	B4	V4	B5	V5
A1	U1	4		1 45		3		4		4 15		60
A2	U2	2 22		3		2 13 ”-”		2 ”+”		3		35
A3	U3	3		5		2 7 ”+”		4 18 ”-”		4 15		40
Потреба		22		45		20		18		30		135

Далі з тих клітинок, у яких стоїть " - " вибираємо найменшу величину постачання min(13;18)=13 та додаємо у всі клітинки з ”+” та віднімаємо в усіх клітинках з " - ". Отримуємо табл. 3.8.

Таблиця 3.8

Пункт відправлення		Пункт споживання										Запас
		B1	V1	B2	V2	B3	V3	B4	V4	B5	V5
A1	U1	4		1 45		3		4		4 15		60
A2	U2	2 22		3		2		2 13		3		35
A3	U3	3		5		2 20		4 5		4 15		40
Потреба		22		45		20		18		30		135

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

U₁+V₂=1;

U₁+V₅=4;

U₂+V₁=2;

U₂+V₄=2;

U₃+V₃=2;

U₃+V₄=4;

U₃+V₅=4.

Знаходимо невідомі:

U1=0; U2= -2; U3=0;

V1=4; V2=1; V3=2; V4=4; V5=4.

Для небазисних клітинок знаходимо оцінки ∆_ij = U_i+V_j-C_ij.

∆₁₁ = U₁+V₁-C₁₁=0+4-4=0; ∆₁₃ = U₁+V₃-C₁₃=0+2-3= -1;

∆₁₄ = U₁+V₄-C₁₄=0+4-4=0; ∆₂₂ = U₂+V₂-C₂₂= -2+1-3= -4;

∆₂₃ = U₂+V₃-C₂₃= -2+2-2= -2; ∆₂₅ = U₂+V₅-C₂₅= -2+4-3= -1;

∆₃₁ = U₃+V₁-C₃₁=0+4-3=1; ∆₃₂ = U₃+V₂-C₃₂=0+1-5= -4.

Оскільки не всі ∆_ij≤0, то план не оптимальний. Будуємо цикл переходу. В А₃В₁ ставимо ”+”, в А₂В₁ ставимо ”-”, в А₂В₄ ставимо ”+”, в А₃В₄ ставимо ”-”.

Таблиця 3.9

Пункт відправлення		Пункт споживання										Запас
		B1	V1	B2	V2	B3	V3	B4	V4	B5	V5
A1	U1	4		1 45		3		4		4 15		60
A2	U2	2 22 ”-”		3		2		2 13 ”+”		3		35
A3	U3	3 ”+”		5		2 20		4 5 ”-”		4 15		40
Потреба		22		45		20		18		30		135

Таблиця 3.10

Пункт відправлення		Пункт споживання										Запас
		B1	V1	B2	V2	B3	V3	B4	V4	B5	V5
A1	U1	4		1 45		3		4		4 15		60
A2	U2	2 17		3		2		2 18		3		35
A3	U3	3 5		5		2 20		4		4 15		40
Потреба		22		45		20		18		30		135

U₁+V₂=1; U₁+V₅=4; U₂+V₁=2; U₂+V₄=2;

U₃+V₁=3; U₃+V₃=2; U₃+V₅=4.

Знаходимо невідомі:

U1=0; U2= -1; U3=0;

V1=3; V2=1; V3=2; V4=3; V5=4.

∆₁₁ = U₁+V₁-C₁₁=0+3-4=0; ∆₁₃ = U₁+V₃-C₁₃=0+2-3= -1;

∆₁₄ = U₁+V₄-C₁₄=0+3-4= -1; ∆₂₂ = U₂+V₂-C₂₂= -1+1-3= -3;

∆₂₃ = U₂+V₃-C₂₃= -1+2-2= -1; ∆₂₅ = U₂+V₅-C₂₅= -1+4-3=0;

∆₃₄ = U₃+V₄-C₃₄=0+3-4= -1; ∆₃₂ = U₃+V₂-C₃₂=0+1-5= -4.

План оптимальний, оскільки всі ∆_ij≤0.

;

z_min=45*1+15*4+17*2+18*2+5*3+20*2+15*4=290.