Складання транспортних таблиць

⇐ Назад

Для розгляду можливих варіантів напрямку ПВ з одним транзитом

складається допоміжна табл. 4. В основу складання таблиці беруться

обмеження за навантаженням для транзитних вузлів.

Таблиця 4

Пункти відправлення	Пункти призначення

									2,8
								9,1
					7,4			9,7
						7,5
			7,4
				7,5
									8,3
		9,1	9,7
	2,8						8,3

У клітці 19 записані пункти призначення 2,8, що показує можливість

напрямку ПВ із вузла 1 у вузол 9 через вузли 2 або 8 з одним транзитом. Потік

ПВ, що направляється з пункту відправлення i в пункт призначення j через транзитний вузол k можна записати X_ikj . Така форма запису невідомих полегшує перехід до моделі транспортної задачі. Користуючись табл. 4, побудуємо математичну модель, в яку включимо всі потоки з одним транзитом. Попередньо необхідно ввести нову індексацію невідомих і потоків. Перелік старих і нових індексів зведено в табл. 5. Номер чергового індексу визначається черговою заповненою кліткою табл. 4 при перегляді рядків у напрямку зліва направо й вниз. Наприклад, навантаження з вузла 1 у вузол 9 позначається по старому Q₁₉ , а по новому Q₁ . Навантаження з 2 у 8 по старому позначається Q₂₈ , а по новому Q₂ і т.д. Потік ПВ з 1 у 9 через вузол 2 по старому позначався X²₁₉ , а по новому буде X₂₁ , тобто номер транзитного вузла 2 стає першою цифрою індексу, а 19 замінюється 1, тому що Q₁₉ було замінено на Q₁ і записується другою цифрою індексу X₂₁. Потрібно читати X₂₁ - потік із пункту відправлення 2 у пункт призначення 1.

Таблиця 5

Стара індексація	Нова індексація	Стара індексація	Нова індексація	Стара індексація	Нова індексація
Q₁₉	Q₁	X²₁₉	X₂₁	X⁷₆₄	X₇₇
Q₂₈	Q₂	X⁸₁₉	X₈₁	X⁵₆₄	X₅₇
Q₃₅	Q₃	X²₁₉	X₉₂	X⁸₇₉	X₈₈
Q₃₈	Q₄	X⁹₂₈	X₁₂	X³₇₉	X₃₈
Q₄₆	Q₅	X¹₂₈	X₇₃	X⁹₈₂	X₉₉
Q₅₃	Q₆	X⁷₃₅	X₄₃	X¹₈₂	X₁₉
Q₆₄	Q₇	X⁴₃₅	X₉₄	X⁹₈₃	X_9,10
Q₇₉	Q₈	X⁹₃₈	X₇₄	X⁷₈₃	X_7,10
Q₈₂	Q₉	X⁷₃₈	X₇₅	X²₉₁	X_2,11
Q₈₃	Q₁₀	X⁷₄₆	X₅₅	X⁸₉₁	X_8,11
Q₉₁	Q₁₁	X⁷₅₃	X₇₆	X⁸₉₇	X_8,12
Q₉₇	Q₁₂	X⁴₅₃	X₄₆	X³₉₇	X_3,12

Далі з урахуванням нової індексації складається транспортна табл. 6. За цією таблицею під транспортними вузлами потрібно розуміти склади 1, 2, 3, 4, 5, 6, 7, 8, 9, тобто пункти відправлення з розміром запасів W¹₁ , W¹₂ , W¹₃ , W¹₄ , W¹₅ , W¹₆ , W¹₇ , W¹₈ , W¹₉ , а під потоками - пункти споживання однорідного вантажу 1,2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 із потребами Q₁ , Q₂ , Q₃ , Q₄ , Q₅ , Q₆ , Q₇ , Q₈ , Q₉ , Q₁₀ , Q₁₁ , Q₁₂. На відміну від транспортної задачі в її звичайній постановці, тут перевезення однорідного вантажу з певного вузла допускається тільки в певний пункт споживання. Тому за тими напрямками, де перевезення не допускається, витрати на перевезення одиниці вантажу приймаються рівними M . Під M розуміється велике значення розміру витрат, що фактично виключає з розгляду цю змінну. Перевезення ПВ у заданих кількостях може бути реалізовано тільки в тому випадку, якщо сумарна пропускна спроможність вузлів буде не менше сумарного розміру потоків, тобто :

Розглянута задача відповідає відкритій моделі транспортної задачі. Потреба введення фіктивного пункту споживання визначається як різниця:

Пункти відправлення

Пункти призначення

С₁

С₂

С₃

С4

С₅

С₇

С₈

С₉

Транспортна таблиця являє собою матрицю 9 на 13, в якій є 24 невідомих, що представляють собою обсяги перевезених ПВ з пунктів відправлення в пункти призначення. Ці невідомі X_ij повинні бути записані в тих клітинах таблиці, в яких проставлені значення витрат у транзитних вузлах C_і . Рішення задачі можна спростити, якщо поділити загальне число невідомих на дві групи (підзадачі), в яких змінні будуть незалежними, тобто будуть знаходитися в різних рядках і стовпцях табл. 6. Так, наприклад, змінні X₁₂, X₁₉, X₅₅, X₅₇, X₄₃, X₇₂, X₇₄, X₇₅, X₇₆, X₇₇, X_7,10, X₉₂, X₉₄, X₉₉, X_9,10 можна віднести до першої групи, а змінні X₂₁, X_2,11, X₃₈, X_3,12, X₈₁, X₈₈, X_8,11, X_8,12 - до другої. У цьому випадку одержимо начебто дві самостійні підзадачі. Перша з них включає 5 пунктів відправлення 1, 5, 4, 7, 9 і 8 пунктів призначення 2, 3, 4, 5, 6, 7, 9, 10, а друга - 3 пункти відправлення 2, 3, 8 і 4 пункти призначення 1, 8, 11, 12. Незаповнені матриці цих двох спрощених підзадач наведені в табл. 7 і 8.

Таблиця 7

Пункти відправлення	Пункти призначення
								ф
	С₁	М	М	М	М	М	С₁	М	О
	М	С4	М	М	С4	М	М	М	О
	М	М	М	С₅	М	С₅	М	М	О
	М	С₇	С₇	С₇	С₇	С₇	М	С₇	О
	С₉	М	С₉	М	М	М	С₉	С₉	О

Таблиця 8

Пункти відправлення	Пункти призначення
				ф
	С₂	М	С₂	М	О
	М	С₃	М	С₃	О
	С₈	С₈	С₈	С₈	О

⇐ Назад

Далее ⇒