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

Аналізуйчи моделі наведених транспортних задач приходимо до висновку, що ТЗ є ЗЛП і для неї справедлива вся розглянута теорія лінійного програмування і її можна розв’язати СМ. Враховуючи специфіку моделі ТЗ, а особливо те що коефіцієнти при змінних в головній системі обмежень є 0 або 1, розроблені більш простіші методи розв’язування ТЗ. Ця специфіка моделі надає дещо скорегувати відповідну теорію, а саме: можна довести , що серед (m+n) головних обмежень ТЗ лінійно незалежних (m+n-1), тому опорний план ТЗ має небільше (m+n-1) додатніх компонент.Якщо (m+n-1), то він називається невиродженим, якщо меньше (m+n-1), то – виродженим.

Будь-яка закрита ТЗ має оптимальний план.

Всі методи розв’язання ТЗ називаються розподільчими методами і складаються з тих же основних етапів, що і СМ, тобто:

1. побудова початкового опорного плану

2. оцінка оптимальності опорного плану

3. перехід від одного опорного плану до інщого

І етап. Побудова початкового опорного плану.

Існує декілька простих схем побудови опорного початкового плану , серед них метод північно-західного кута, метод найменьшого елемента в рядку (логічний метод), метод найменьшого елемента в таблиці (метод подвійної переваги)

• метод північно-західного кута. Наприклад:

а₁=250 b₁=180

а₂=150 b₂=120

а₃=200 b₃=200

b₄=100

8 4 3 5

IIc_ijII= 4 7 5 2

3 8 9 10

Математична модель задачі: Z=8x₁₁+4x₁₂+3x₁₃+5x₁₄+4x₂₁+7x₂₂+5x₂₃+2x₂₄+3x₃₁+8x₃₂+4x₃₃+10x₃₄ (min)

x₁₁+x₁₂+x₁₃+x₁₄=250

x₂₁+x₂₂+x₂₃+x₂₄=150

x₃₁+x₃₂+x₃₃+x₃₄=200

x₁₁+ x₂₁+ x₃₁=180

x₁₂+ x₂₂+ x₃₂=120

x₁₃+ x₂₃+ x₃₃=200

x₁₄+ x₂₄+ x₃₄=100

x_ij  0 .

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

		В1		В2		В3			В4
		180		120		200			100
А1	250	8		4		3			5
		180		70
А2	150	4		7		5			2
				50		100
А3	200	3		8		9			10
						100			100

Домовлемось про термінологію:

1. клітину на перетині постачальника і споживача будемо називати маршрутом, кожну з них ділимо на дві (три) частини, в верхній частині будемо писати тарифи

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

Метод північно-західного кута полягає в слідуючому: розподіл поставок проводимо по першому рядку від першого постачальника, починаючи з першого споживача, порівнюючи відповідну потужність і попит, і записуємо поставку рівну меньшому із двох чисел. Можливі 2 випадки: 1) потужність більша попиту (наш випадок 250>180) за поставку беремо 180 і йдемо до другого споживача порівнюючи надлишкову потужність з його попитом, за поставку беремо меньше з двох чисел і так далі. 2) потужність меньша попиту – за поставку беремо попит і переходимо до другого постачальника. Розподіл від другого постачальника ведемо по другому рядку, але з врахуванням поставок від попереднього постачальника і так далі.

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

x₁₁=180

x₁₂=70

x₂₂=50

x₂₃=100

x₃₃=100

x₃₄=100

Z=180*8+70*4+50*7+100*5+100*9+100*10=4470

• Метод найменьшого елемента в рядку

		В1				В2				В3				В4
		180				120				200				100
А1	250	8				4				3				5
						50				200
А2	150	4				7				5				2
		50												100
А3	200	3				8				9				10
		130				70

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

x₁₂=50

x₁₃=200

x₂₁=50

x₂₄=100

x₃₁=130

x₃₂=70

План невироджений, так як m+n-1 = 3+4-1=6 і заповнених клітин 6.

• Метод найменьшого елемента в таблиці полягає в тому , що розподіл поставок починається з найменьшого елемента таблиці (в нашому випадку –А₂В₄), потім найменьший із залишившихся, але так щоб виконувався баланс по стовпцям і по рядкам.

ІІ етап Оцінка оптимальності опроного плану. Проводиться на основі достатньої ознаки оптимальності : якщо набір х_ij^* є оптимальним планом ТЗ, то знайдуться такі n+m чисел U_i^* - потенціали постачальників і V_j^* - потенціали споживачів, які задовольняють слідуючим умовам:

1. U_i^*+ V_j^* = C_ij для х_ij^* >0

2. U_i^*+ V_j^*= <C_ij для х_ij^* = 0

Ця ознака примінюється слідуючим образом: за допомогою першої умови, тобто по заповненим клітинам знаходиться система потенціалів, іншими словами – сума потенціалів для кожної заповненної клітини дорівнює тарифу цієї клітини. За допомогою другої умови, яку можна записати U_i^*+ V_j^*- C_ij = _ij ( де _ij – оцінка ), беспосередньо перевіряється оптимальність плана. План буде оптимальним, якщо для кожної незаповненної клітини оцінка _ij – невід’ємне, в протилежному випадку – план неоптимальний.

Задача. Розв’язати транспортну задачу (ТЗ).

Розглянемо приклад

1. ТЗ є відкритою, оскільки менше ніж . Введемо фіктивного постачальника з потужністю . Тарифи від якого до всіх споживачів дорівнюють нулю, зафіксуємо це в таблиці планування перевезень

		100		200		300
	50	8	-5	4		6	-3	-3
				50
	250	6		7		8	-2	0
		100 (”+”)		150 (”-”)
	150	10	1	8	4	11	1	5
				(“+”)		150 (”-”)
	150	0		0		0		-6
		0 (”-”)				150 (”+”)
		6		7		6

2. Побудуємо початковий опорний план методом найменьшого елементу в рядку.

Означення 2.14.Планом ТЗ називається невід’ємний набір значень змінних записаний у таблицю планування перевезень, такий, що сума елементів кожного рядка дорівнює потужності відповідного постачальника, сума елементів кожного стовпця – попиту відповідного споживача.

Числа називатимемо поставками. Клітки, в яких , називатимемо заповненими, решту – незаповненими.

У першому рядку вибираємо маршрут з мінімальним тарифом . За цим маршрутом можна відправити 50 одиниць вантажу, менше з двох чисел. Так як у першого постачальника забрали весь вантаж, то переходимо до другого рядку. Найменший тариф у цьому рядку по маршруту , тому відправляємо 100 одиниць вантажу (менше з двох чисел). Остачу 150 одиниць відправляємо за маршрутом , оскільки тут тариф найменший серед тих, що залишилося та йому потрібно ще 150 одиниць вантажу. Аналогічно розподіляється вантаж від решти постачальників. Тарифи заповнених клітин виділяємо.

Зауваження.

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

3. Перевіримо невиродженість опорного плану. Побудований опорний план вироджений, оскільки число заповнених клітин дорівнює 5 меньше від . Такий план становить труднощі при знаходженні системи потенціалів. У цьому випадку потрібна одна нуль-поставка, тобто записати в одну з незаповнених клітин нуль і вважати її заповненою. В загальному випадку їх вводять в тій кількості, щоб загальне число заповнених клітин дорівнювало . Краще це робити при виконанні слідуючого етапу.

4. По заповнених клітинах знаходимо систему потенціалів. Згідно з першою умовою достатньої ознаки оптимальності опорного плану ТЗ, сума потенціалів має дорівнювати тарифам у заповнених клітинах. Тому маємо систему із лінійних рівнянь з невідомими, у якій число рівнянь на одне менше числа невідомих (для невиродженого опорного плану, тобто враховуючи нуль-поставку). Така система має незлічиму множину розв‘язків. Щоб знайти окремий розв‘язок, одне з невідомих можна задати довільно, тоді решта визначаються при розв‘язанні системи. Враховуючи, що кожне рівняння має тільки дві невідомі, то систему потенціалів дуже просто розв‘язати за допомогою таблиці планування перевезень. У другому рядку маємо дві заповнені клітини ( ) та ( ). Покладемо потенціал , тоді і . Далі скористаємось знайденим потенціалом і знайдемо . Оскільки наш план вироджений, то цепочка далі не можлива. Потрібно ввести нуль-поставку. ЇЇ можна ввести в декілька клітин ( ), або ( ), або ( ), або ( ), або ( ), або ( ) і цепочка завершиться. Введемо в ( ) в якій найменший тариф, тоді: , і .

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

; ; ;

; ; ;

Наявність додатніх оцінок свідчить про те, що план неоптимальний.

6. Перехід до кращого опорного плану. Вибираємо клітину з найбільшої додатньою оцінкою ( ) і будуємо цикл перерахунку поставок.

Означення 2.15. Циклом перерахунку поставок називається цикл, одна з вершин якого міститься в незаповнений клітині з додатньою оцінкою, а решта – в заповнених, і вершини по черзі помічені знаками “+” і “-” починаючи з незаповненої клітини.

З означенння випливає просте правило побудови циклу – рухаючись від клітини початку циклу тільки по рядку чи стовпцю, робити поворот можна тільки в заповненій клітині, не обов’язково в кожній, потрібно повернутись в початкову клітину. В клітинах повороту знаки розставляти по черзі. В клітинах із знаком “-” вибираємо найменшу поставку . Цю поставку додаємо в клітини зі знаком “+” і віднімаємо в клітинах зі знаком “-”. Клітини, які не увійшли в цикл залишаються без зміни. В нашому випадку нуль-поставка переноситься в іншу клітину. Одержуємо новий опорний план, тобто нову таблицю перевезень:

		100		200		300
	50	8	-5	4		6	1	-4
				50
	250	6		7		8	2	-1
		100		150 (”-”)		(”+”)
	150	10	-3	8		11		0
				0 (“+”)		150 (”-”)
	150	0	-4	0	-3	0		-11
						150
		7		8		11

Для другої та наступних таблиць перевезень пункти 3-6 послідовно виконуються до одержання оптимального плану.

; ; ;

; ;

План неоптимальний, складаємо третю таблицю перевезень:

		100		200		300
	50	8	-4	4		6		-2
				50		0
	250	6		7	-1	8		0
		100				150
	150	10	-2	8		11	-1	2
				150
	150	0	-2	0	-2	0		-8
						150
		6		6		8

План вироджений.

; ; ;

; ;

Одержали оптимальний план. Випишемо його: третій споживач не одержав 150 одиниць ( ). Всі інші змінні дорівнюють нулю

.

Оскільки нульових оцінок для незаповнених клітин немає, то оптимальний план перевезень один.