Приведення транспортних таблиць до машинного виду

Приведення транспортних таблиць до машинного виду полягає в тому, щоб

привести у відповідність позначення, прийняті в реальній мережі й у програмі,

для пунктів відправлень і призначень, для невідомих потоків навантаження, а також для обмежень і коефіцієнтів витрат на оброблення. У програмі прийняті такі позначення для підзадачі 1 табл. 9:

1. Пункти відправлення нумеруються послідовно, тобто (1, 2, 3, 4, 5), що

відповідає пунктам відправлення по табл. 9 (1, 5, 4, 7, 9). Пункти призначення нумеруються також послідовно, тобто (1, 2, 3, 4, 5, 6, 7, 8, 9), що відповідає пунктам призначення в табл. 9 (2, 3, 4, 5, 6, 7, 9, 11, Ф).

2. Коефіцієнти при невідомих C_ij у програмі вказуються на пересіченні i рядка і j стовпця:

C(1,1) = C₁ = 2, C(1,2) = M = 900, C(1,3) = M = 900,…., C(1,2) = C₁ = 2 і т.д.

3. Обмеження за рядками (число рядків М = 5):

A(1) = W’₁ = 289, A(2) = W’₅ = 239, A(3) = W’₄ = 259, A(4) = W’₇ = 271,

A(5) = W’₉ = 248.

4. Обмеження за стовпцями (число рядків N = 9):

B(1) = Q₂ = 6, B(2) = Q₃ = 3, B(4) = Q₅ = 3, B(5) = Q₆ = 6, B(6) = Q₇ = 4,

B(7) = Q₉ = 4, B(8) = Q₁₀ = 7, B(9) = Q_ф = 1263.

5. Невідомі потоки Х_ij:

X(1,1) = X₁₂, X(1,2) = X₁₃,….., X(1,9) = X_1ф,…., X(2,9) = X₅_ф і т.д.

Транспортна табл. 9, приведена до машинного виду, набуває вид табл. 11.

Таблиця 11

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

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

1. Пункти відправлення нумеруються послідовно (1, 2, 3), що відповідає пунктам відправлення в табл. 10 (2, 3, 8). Пункти призначення нумеруються (1, 2, 3, 4, 5), що відповідає пунктам призначення в табл. 10 (1, 8, 11, 12, Ф).

2. Коефіцієнти при невідомих:

С(1,1) =С₂= 3, С(1,2) = М = 900, С(1,3) = М = 900, С(1,3) = С₂ = 3

С(1,4) = М = 900, С(1,5) = 0 і т.д.

3. Обмеження за рядками (число рядків М 3):

А(1) = W₂' = 252, А(2) = W₃' = 252, А(3) = W₈' = 280.

4. Обмеження за стовпцями (число стовпців N — 5):

В(1)=Q₁=3,В(2) =Q8 =4,В(3) =Q₁₁=5,В(4) =Q₁₂=6,В(5)=Q_ф= 766.

5. Невідомі потоки:

X(1,1)=X₂₁,X(1,2) =X₂, X(1,3) =X_2,11, X(1,4) =X_2,12, X(1,5) =X_2ф і т.д.

Транспортна табл. 10 приводиться до машинного виду і подана табл. 12.

Таблиця 12

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



B_j

При цьому змінюється індексація для потоків. Нова індексація для

потоків до і після приведення до машиного виду наведена в табл. 13

Таблиця 13

Індексація до приведення до машиного виду	X₁₂	X₁₉	X₇₃	X₇₄	X₇₅	X₇₆	X₇₇	X_7,10	X₈₁
Індексація після приведення до машиного виду	X(1,1)	X(1,7)	X(4,2)	X(4,3)	X(4,4)	X(4,5)	X(4,6)	X(4,8)	X(3,1)

X₈₈	X_8,11	X_8,12
X(3,2)	X(3,3)	X(3,4)

3.3. Аналіз отриманих результатів

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

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

А_i

B_j

Таблиця 14

У результаті виконання підзадачі 1 на ЕОМ одержане остаточне рішення, що мінімізує витрати на оброблення транзитних ПВ. Остаточне рішення подане в табл. 14. Цільова функція зменшується з Z_поч = 29720, до Z_кінц = 86.

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



^В_j

Таблиця 15

Перейдемо від отриманих машинних змінних до фізичних змінних, прийнятих у даній мережі, для чого скористуємося данніми в табл. 5 і 13. Такий перехід дозволить проаналізувати найбільш економні (рекомендовані) транзитні вузли, через які варто відправляти ПВ.

Розраховані потоки і витрати у вузлах для підзадачі 1:

X(1,1) = X₁₂= X¹₂₈ = 6, Z¹₂₈=C₁ X¹₂₈ =12,

X(1,7) = X₁₂= X¹₈₂ = 4, Z¹₈₂=C₁ X¹₈₂ =12,

X(1,9) = X_1ф = 279,

X(2,9) = X_5ф = 239,

X(3,9) = X_4ф = 259,

X(4,2) = X₇₃= X⁷₃₅ = 3, Z⁷₃₅=C₇ X⁷₃₅ =6,

X(4,3) = X₇₄= X⁷₃₈ = 10, Z⁷₃₈=C₇ X⁷₃₈ =20,

X(4,4) = X₇₅= X⁷₄₆ = 3, Z⁷₄₆=C₇ X⁷₄₆ =6,

X(4,5) = X₇₆= X⁷₅₃ = 6, Z⁷₅₃=C₇ X⁷₅₃=12,

X(4,6) = X₇₇= X⁷₆₄ = 4, Z⁷₆₄=C₇ X⁷₆₄ =8,

X(4,8) = X_7,10= X⁷₈₃ = 7, Z⁷₈₃=C₇ X⁷₈₃ =14,

X(4,9) = X_7ф = 238,

X(5,9) = X_9ф = 248.

Загальні трудові витрати Z₁ = 86 (люд·хв).

Розраховані потоки і витрати у вузлах для підзадачі 2:

X(1,5) = X₂_ф = 252,

X(2,5) = X_3ф = 252,

X(3,1) = X₈₁= X⁸₁₉ = 3, Z⁸₁₉=C₈ X⁸₁₉ =6,

X(3,2) = X₈₈= X⁸₇₉ = 4, Z⁸₇₉=C₈ X⁸₇₉ =8,

X(3,3) = X_8,11= X⁸₉₁ = 5, Z⁸₉₁=C₈ X⁸₉₁ =10,

X(3,4) = X_8,12= X⁸₉₇ = 6, Z⁸₉₇=C₈ X⁸₉₇=12,

X(3,5) = X_8ф = 262.

Загальні трудові витрати Z₂ = 36 (люд·хв).

Трудові витрати перевезень транзитних ПВ для всієї задачі:

Z= Z₁+ Z₂= 86 + 36 = 122 (люд • хв).

З усіх можливих варіантів пересилання ПВ (табл.4) одержимо значення витрат при відправленні через рекомендовані і не рекомендовані транзитні вузли.

Кінцеві вузли маршрутів	Транзитні вузли
відправлення	призначення	Рекомендовані	Не рекомендовані
вузол	витрати	вузол	витрати

Таблиця 16

Одержані значення витрат можуть бути зведені в табл. 16.

Таким чином, пересилання й оброблення ПВ через рекомендовані вузли забезпечує значну економію трудових витрат. Якщо витрати через рекомендовані вузли складають 122 людхв, то витрати через не рекомендовані вузли дорівнюють 251 людхв.

4. ОПТИМІЗАЦІЯ ПЕРЕВЕЗЕННЯ ПОШТОВИХ ВІДПРАВЛЕНЬ ДЛЯ МЕРЕЖІ З ВИКОРИСТАННЯМ ГОЛОВНОГО ВУЗЛА

Міжобластна мережа перевезення поштових відправлень для цього варіанта побудови мережі показана на рис. 2. Використовувана мережа відрізняється наявністю головного вузла (ГВ), позначеного номером 10. Головний вузол мережі відповідає Києву і пов'язаний магістральним маршрутом із Харковом. Тому що ГВ має значну пропускну спроможність, то витрати на оброблення ПВ будуть мінімальними. З цієї причини може виявитися більш вигідним організовувати перевезення поштових відправлень між вузлами мережі через ГВ, що використовується в цьому випадку як транзитний. У транзитному вузлі

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

Для виконання розрахунків повинні бути задані вихідні дані, це: пропускна спроможність вузлів, витрати на оброблення ПВ у вузлах і добові потоки навантажень між вузлами мережі. Ці дані були отримані шляхом статистичного аналізу і наведені в табл. 17 і 18.

Таблиця 17

Номер вузла (i)
Пропускна спроможність вузла W_i (шт. ПВ)
Витрати на оброблення ПВ C_i (люд.хв. / шт.)

Таблиця 18

Вузли відправлення	Вузли призначення

	-
		-
			-
				-
					-
						-
							-
								-
									-
										-

Пропускна спроможність вузлів мережі по обробленню транзитних ПВ розраховується, як і раніше, за формулою:

для значень і = 1,2,3,...,10, де 0_Ц, , - добові потоки навантаження для

вихідних і вхідних вузлів (табл. 18). Розрахована пропускна спроможність вузлів мережі за транзитом наведена в табл. 19.

Таблиця 19

Номер вузла, і

Рисунок 2

Для виконання оптимізації перевезень ПВ за критерієм мінімуму витрат на оброблення транзиту, як і раніше, будемо враховувати тільки доцільні маршрути через один транзитний вузол. Запишемо рівняння-обмеження щодо невідомих, це: кількість ПВ, що направляються можливими маршрутами з і у j вузол мережі й назад.

Обмеження за навантаженням будуть мати вид:

X₁₂₉ + X₁₈₉ + X_1,10,9 = Q₁₉,

X₉₂₁ + X₉₈₁ + X_9,10,1 = Q₉₁,

X₂₉₈ + X₂₁₈ + X_2,10,8 = Q₂₈,

X₈₉₂ + X₈₁₂ + X_8,10,2 = Q₈₂,

X₃₉₈ + X₃₇₈ + X_3,10,8 = Q₃₈,

X₈₉₃ + X₈₇₃ + X_8,10,3 = Q₈₃,

X₇₈₉ + X₇₃₉ + X_7,10,9 = Q₇₉,

X₉₈₇ + X₉₃₇ + X_9,10,7 = Q₉₇,

X₃₇₅ + X₃₄₅ + X_3,10,5 = Q₃₅,

X₅₇₃ + X₅₄₃ + X_5,10,3 = Q₅₃,

X₄₇₆ + X₄₅₆ + X_4,10,6 = Q₄₆,

X₆₇₄ + X₆₅₄ + X_6,10,4 = Q₆₄.

Обмеження за пропускною спроможністю вузлів при обробленні транзитних

ПВ:

X₂₁₈ + X ₈₁₂ ≤ ,

X₁₂₉ + X₉₂₁ ≤ ,

X₂₃₇ + X₇₃₂ + X₇₃₉ + X₉₃₇ ≤ ,

X₃₄₅ + X₅₄₃ ≤ ,

X₆₅₄ + X₄₅₆ ≤ ,

X₃₇₅ + X₅₇₃+ X₃₇₆ + X₆₇₃ + X₄₇₆ + X₆₇₄ + X₃₇₈ + X₈₇₃ ≤ ,

X₁₈₉ + X₉₈₁ + X₇₈₉ + X₉₈₇ ≤ ,

X₂₉₈ + X₈₉₂ + X₃₉₈ + X₈₉₃ ≤ ,

X_2,10,8 + X_8,10,2+ X_1,10,9 + X_9,10,1 + X_7,10,9 + X_9,10,7+ X_3,10,5 + X_5,10,3 + X_3,10,8 + X_8,10,3+ X_4,10,6 + X_6,10,4 + X_2,10,8 + X_8,10,2+ X_1,10,9 + X_9,10,1 + X_7,10,9 + X_9,10,7+ X_3,10,5 + X_5,10,3 + X_3,10,8 + X_8,10,3+ X_4,10,6 + X_6,10,4 ≤ .

Цільова функція, що відтворює витрати на оброблення транзитних ПВ, буде мати вид:

Z = C₁(X₂₁₈ + X₈₁₂) + C₂(X₁₂₉ + X₉₂₁) + C₃(X₇₃₉ + X₉₃₇) + C₄ (X₃₄₅ + X₅₄₃) + C₅ (X₄₅₆+ X₆₅₄) + C₇(X₃₇₅ + X₅₇₃ + X₄₇₆+ X₆₇₄ + X₃₇₈ + X₈₇₃) + C₈ (X₁₈₉ + X₉₈₁ + X₇₈₉ + X₉₈₇) + C₉ (X₂₉₈+ X₈₉₂ + X₃₉₈ + X₈₉₃) + C₁₀(X_2,10,8 + X_8,10,2+ X_1,10,9 + X_9,10,1 + X_7,10,9 + X_9,10,7+ X_3,10,5 + X_5,10,3 + X_3,10,8 + X_8,10,3+ X_4,10,6 + X_6,10,4 + X_2,10,8 + X_8,10,2+ X_1,10,9 + X_9,10,1 + X_7,10,9 + X_9,10,7+ X_3,10,5 + X_5,10,3 + X_3,10,8 + X_8,10,3+ X_4,10,6 + X_6,10,4).

Можливі варіанти напрямку ПВ з одним транзитом можна звести в табл. 20, яка може бути використана для упорядкування транспортної таблиці.

Таблиця 20

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

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

Для складання транспортної таблиці введемо нову індексацію для навантажень і потоків. Стара і нова індексації для навантажень наведена в табл. 21.

Таблиця 21

Стара індексація

Q₁₉

Q₂₈

Q₃₅

Q₃₈

Q₄₆

Q₅₃

Q₆₄

Q₇₉

Q₈₂

Q₈₃

Q₉₁

Q₉₇

Нова індексація

Q₁

Q₂

Q₃

Q₄

Q₅

Q₆

Q₇

Q₈

Q₉

Q₁₀

Q₁₁

Q₁₂

Стара і нова індексації для потоків наведена в табл. 22.

Таблиця 22

Стара індексація

X²₁₉

X⁸₁₉

X¹⁰₁₉

X⁹₂₈

X¹₂₈

X¹⁰₂₈

X⁷₃₅

X⁴₃₅

X¹⁰₃₅

X⁹₃₈

X⁷₃₈

X¹⁰₃₈

Нова індексація

X₂₁

X₈₁

X_10,1

X₉₂

X₁₂

X_10,2

X₇₃

X₄₃

X_10,3

X₉₄

X₇₄

X_10,4

Стара індексація

X⁷₄₆

X⁵₄₆

X¹⁰₄₆

X⁷₅₃

X⁴₅₃

X¹⁰₅₃

X⁷₆₄

X⁵₆₄

X¹⁰₆₄

X⁸₇₉

X³₇₉

X¹⁰₇₉

Нова індексація

X₇₅

X₅₅

X_10,5

X₇₆

X₄₆

X_10,6

X₇₇

X₅₇

X_10,7

X₈₈

X₃₈

X_10,8

Стара індексація

X⁹₈₂

X¹₈₂

X¹⁰₈₂

X⁹₈₃

X⁷₈₃

X¹⁰₈₃

X²₉₁

X⁸₉₁

X¹⁰₉₁

X⁸₉₇

X³₉₇

X¹⁰₉₇

Нова індексація

X₉₉

X₁₉

X_10,9

X_9,10

X_7,10

X_10,10

X_2,11

X_8,11

X_10,11

X_8,12

X_3,12

X_10,12

З урахуванням нової індексації складено транспортну таблицю (табл. 23). В цій таблиці під транспортними вузлами потрібно розуміти склади 1, 2, 3,..., 10,

тобто відправлення з величинами запасів W’₁, W’₂,..., W’₁₀, а під потоками пункти споживання однорідного вантажу 1, 2, …, 12 з потребами Q₁, Q₂,…,Q₁₂. Для винятку, з розгляду потоків між пунктами, за якими перевезення не

допускається, уводяться чисельно великі витрати M = 900. Щоб призвести

транспортну модель до збалансованого виду, уводиться фіктивний пункт

споживання з величиною навантаження:

Транспортна табл. 23 являє собою матрицю 10 на 13 із 32 невідомими

обсягами перевезених вантажів, що повинні бути записані в клітках із

проставленими значеннями витрат у транзитних вузлах.

Таблиця 23

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

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

С₁

С₂

С₃

С4

С₅

С₇

С₈

С₉

Для спрощення рішення отриману транспортну таблицю можна поділити на

дві більш прості табл. 24 і 25, таким чином, щоб вхідні до них змінні були б незалежними, тобто знаходилися в різних рядках і стовпцях. У табл. 24 увійдуть рядки 1, 4, 5, 6, 7, 9, 10 і стовпці 2, 3, 4, 5, 6, 7, 9, 10. Відповідно в табл. 25 увійдуть рядки 2, 3, 8, 10 і стовпці 1, 8, 11, 12.

Таблиця 24

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

Таблиця 25

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

Для рішення отриманих підзадач 1 і 2, що відповідають табл. 24 і 25 слід привести ці таблиці до машинного виду. Таке приведення полягає в тому, що змінюється нумерація рядків і стовпців. Так, наприклад, для табл. 24 нумерація рядків 1, 4, 5, 7, 9, 10 змінюється на 1, 2, 3, 4, 5, 6, а нумерація стовпців 2, 3, 4, 5, 6, 7, 9, 10, Ф змінюється на нумерацію 1, 2, 3, 4, 5, 6, 7, 8, 9. Для підзадачі 1 одержимо транспортну таблицю (табл. 26).

Таблиця 26

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

		м	М	М	М	М		М
	М		М	М		М	М	М
	М	М	М		М		М	М
	М						М
		М		М	М	М

Для підзадачі 2 (табл. 25) нумерація рядків 2, 3, 8, 10 зміниться на нумерацію

1, 2, 3, 4, а нумерація стовпців 1, 8, 11, 12, Ф зміниться на нумерацію 1, 2, 3, 4,

5. Остаточно для рішення підзадачі 2 на ЕОМ одержимо транспортну таблицю

(табл.27).

Таблиця 27

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

Змінюється індексація для потоків. Нова індексація для потоків до і після

приведення до машиного виду наведена в табл. 28.

Таблиця 28

Індексація до приведення до машиного виду	X_10,2	X_10,3	X_10,4	X_10,5	X_10,6	X_10,7	X_10,9	X_10,10	X_10,1
Індексація після приведення до машиного виду	X(6,1)	X(6,2)	X(6,3)	X(6,4)	X(6,5)	X(6,6)	X(6,7)	X(6,8)	X(4,1)

X_10,8	X_10.11	X_10,12
X(4,2)	X(4,3)	X(4,4)

В результаті рішення підзадачі 1 на ЕОМ одержимо остаточне рішення для невідомих потоків навантаження у виді табл.29. Цільова функція зменшується з Z _поч= 29720 до Z_кінц = 43.

Таблиця 29

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

Результати остаточного рішення підзадачі 2 зведені в табл. 30. Цільова

функція зменшується з Z_поч = 9024 до Z_кінц = 18.

Таблиця 30

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

Перейдемо від отриманих машинних змінних до фізичних змінних, прийнятих у даній мережі, для чого скористуємося данніми в табл.22 і 28. Такий перехід дозволить проаналізувати найбільш економні (рекомендовані) транзитні вузли, через які варто відправляти ПВ. Розраховані потоки і витрати для підзадачі 1:

X(6,1) = X₁_0,₂= X¹⁰₂₈ = 6, Z¹⁰₂₈= 6,

X(6,2) = X_10,3= X¹⁰₃₅ = 4, Z¹⁰₃₅= 3,

X(1,9) = X_1ф = 99,

X(2,9) = X_5ф = 149,

X(3,9) = X_4ф = 119,

X(6,3) = X_10,4= X¹⁰₃₈ = 10, Z¹⁰₃₈ = 10,

X(6,4) = X_10,5= X¹⁰₄₆ = 3, Z¹⁰₄₆= 3,

X(6,5) = X_10,₆= X¹⁰₅₃ = 6, Z¹⁰₅₃ = 6,

X(6,6) = X_10,₇= X¹⁰₆₄ = 4, Z¹⁰₆₄ = 4,

X(6,7) = X_10,9= X¹⁰₈₂ = 4, Z¹⁰₈₂= 7,

X(6,8) = X₁₀_,10= X¹⁰₈₃ = 7, Z¹⁰₈₃ = 7,

X(4,9) = X_7ф = 101,

X(5,9) = X_9ф = 108,

X(6,9) = X₁₀_ф = 307.

Загальні трудові витрати Z₁ = 43(люд·хв).

Розраховані потоки і витрати у вузлах для підзадачі 2:

X(1,5) = X₂_ф = 102,

X(2,5) = X₃_ф = 112,

X(4,1) = X_10,1= X¹⁰₁₉ = 3, Z¹⁰₁₉= 3,

X(4,2) = X_10,8= X¹⁰₇₉ = 4, Z¹⁰₇₉= 4,

X(4,3) = X_10,11= X¹⁰₉₁ = 5, Z¹⁰₉₁= 5,

X(4,4) = X₁₀_,1₂= X¹⁰₉₇ = 6, Z¹⁰₉₇= 6,

X(3,5) = X₈_ф = 120,

X(4,5) = X₁₀_ф = 157.

Загальні трудові витрати Z₂ = 18(люд·хв).

Трудові витрати перевезень транзитних ПВ для всієї задачі:

Z = Z₁ + Z₂ = 43 + 18 = 61(люд · хв).

З усіх можливих варіантів перевезення ПВ (табл.20) одержимо значення

витрат через рекомендовані і не рекомендовані транзитні вузли. Одержані

значення витрат в цих вузлах зведені в табл.31.

Таблиця 31

Кінцеві вузли маршрутів	Транзитні вузли
відправлення	призначення	Рекомендовані	Не рекомендовані
вузол	витрати	вузол/вузол	витрати/витрати
				2/8	9/6
				2/8	15/10
				1/9	12/30
				1/9	8/20
				7/4	6/9
				7/4	12/18
				9/7	50/20
				9/7	35/14
				7/5	6/15
				7/5	8/20
				8/3	8/12
				8/3	12/18

Таким чином, пересилання й оброблення ПВ через рекомендовані вузли

забезпечує значну економію трудових витрат. Якщо витрати через рекомендовані вузли складають 61 люд·хв, то витрати через не рекомендовані вузли дорівнюють 181 / 192 люд·хв. Зрівнювання двох варіантів пересилання ПВ через рекомендовані вузли показує, що витрати у першому варіанті значно більше ніж у другому. Якщо витрати у першому варіанті складають значення 122 люд.хв,то у другому - тільки 61 люд.хв. Таким чином, можна зробити висновок про те, що у випадку використання ГВ, що має велику пропускну спроможність, більш доцільно виконувати перевезення через ГВ, де виконується перевантаження і сортування поштових відправлень.

СПИСОК ЛІТЕРАТУРИ

1. Барсук В.А., Губин Н.М., Математические методы планирования и управления в хозяйстве связи: Учебн. для вузов.- 2-е изд., доп. и перер. -М.:Связь, 1974.- 264 с.,ил.

2. Боровик В.Г. Розв’язання задач поштового зв’язку методами лінійного програмування на ЕОМ (транспортні задачі): мет.керівн.- Одеса: ОНАЗ ім. О.С. Попова, 2002.- 36 с.