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

Припустимо, що оплату перевезень здійснюють спільно виробник і споживач. Вони вносять так звані платежі: виробник платежі , споживач платежі .

Суму цих платежів назвемо псевдовартістю:

.

(2.3)

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

,

(2.4)

де – множина базисних клітин.

Технологія призначення платежів проста завдяки такому факту. Всього платежів , а рівнянь типу (2.4) – стільки, скільки базисних клітин, тобто , значить, один платіж можна брати довільно, наприклад, . Знайдемо платежі в таблиці 2.3 з лекції 1 і отримаємо табл. 2.4.

Таблиця 2.4

	10 –	2 10	15 +	2 7
	12 7			5 4
	14 4	7 6	10 –

Якщо , то , . Але тоді , щоб . Далі: , щоб , ; . Знайдемо псевдовартості для вільних клітин і запишемо їх у верхніх лівих кутах клітин.

Бачимо, що у клітині (3, 1) ціна циклу

.

Для цієї клітини доцільно побудувати цикл (позначений у табл. 2.4). Цей цикл має деяку особливість: величина одночасно наявна у двох від’ємних клітинах. Згідно з приміткою до теореми 2 лише одну клітину робимо вільною. Здійснимо перенесення по циклу і знайдемо нове значення цільової функції:

	0 -		25 +
			20 -	15 4 +
	10 +			30 -	-5

.

Отримаємо табл. 2.5 і знову призначимо платежі.

Таблиця 2.5

Як видно з табл. 2.5, платежі можуть бути і від’ємними (). Розглянемо цикл для клітини (2; 4). Ціна циклу , але . Отже, цикл доцільний, хоча величина не зміниться. Його сенс у тому, що структура базису буде іншою, і це приведе до поліпшення плану у майбутньому. У таблиці 2.6 клітина (1; 1) стала вільною, а в нову базисну клітину (2; 4) записуємо 0.

Таблиця 2.6

		15 -		0 +
		6+		30 -
	-2

Здійснимо цикл для клітини (3, 2).

Наведемо табл. 2.7

Таблиця 2.7

			20 -	15 +
			12 11 +	15 -
	-2

Тепер залишається лише одна клітина (3; 3) з від’ємною ціною:

.

Маємо: , і таблицю 2.8

Таблиця 2.8

	–11 9	1 10		1 7
	2 7	4 5
				6 7
	–1

У табл. 2.8 всі псевдовартості менші за вартості, тому план оптимальний:

всі інші ; .

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

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

1. Складаємо транспортну таблицю.

2. Будуємо допустимий і одночасно базисний план за методом північно-західного кута або за іншим методом. Знаходимо початкове значення цільової функції.

3. Призначаємо платежі.

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

5. Фіксуємо оптимальні значення перевезень. Кінець.

Крім методу потенціалів, існують інші ефективні методи розв’язування ТЗ, зокрема так званий угорський метод. Його досить складний алгоритм застосовний для розв’язування частинного випадку ТЗ – задачі про призначення.