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

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

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

для пунктів відправлень і призначень, для невідомих потоків навантаження, а також для обмежень і коефіцієнтів витрат на оброблення. У програмі прийняті такі позначення для підзадачі 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_5ф і т.д.

Транспортна табл. 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
Bj

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

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

Таблиця 13

Індексація до приведення до машиного виду	X12	X19	X73	X74	X75	X76	X77	X7,10	X81
Індексація після приведення до машиного виду	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)

X88	X8,11	X8,12
X(3,2)	X(3,3)	X(3,4)

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

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

Таблиця 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_2ф = 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 )
Пропускна спроможність вузла Wi (шт. ПВ)
Витрати на оброблення ПВ Ci (люд.хв. / шт.)

Таблиця 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

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

Q19

Q28

Q35

Q38

Q46

Q53

Q64

Q79

Q82

Q83

Q91

Q97

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

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Q8

Q9

Q10

Q11

Q12

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

Таблиця 22

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

X219

X819

X1019

X928

X128

X1028

X735

X435

X1035

X938

X738

X1038

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

X21

X81

X10,1

X92

X12

X10,2

X73

X43

X10,3

X94

X74

X10,4

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

X746

X546

X1046

X753

X453

X1053

X764

X564

X1064

X879

X379

X1079

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

X75

X55

X10,5

X76

X46

X10,6

X77

X57

X10,7

X88

X38

X10,8

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

X982

X182

X1082

X983

X783

X1083

X291

X891

X1091

X897

X397

X1097

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

X99

X19

X10,9

X9,10

X7,10

X10,10

X2,11

X8,11

X10,11

X8,12

X3,12

X10,12

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

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

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

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

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

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

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

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

Таблиця 23

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

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

ф

М

С1

М

М

М

М

М

М

С1

М

М

М

О

С2

М

М

М

М

М

М

М

М

М

С2

М

О

М

М

М

М

М

М

М

С3

М

М

М

С3

О

М

М

С4

М

М

С4

М

М

М

М

М

М

О

М

М

М

М

С5

М

С5

М

М

М

М

М

О

М

М

М

М

М

М

М

М

М

М

М

М

O

М

М

С7

С7

С7

С7

С7

М

М

С7

М

М

О

С8

М

М

М

М

М

М

С8

М

М

С8

С8

О

М

С9

М

С9

М

М

М

М

С9

С9

М

М

О

O

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

дві більш прості табл. 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

Індексація до приведення до машиного виду	X10,2	X10,3	X10,4	X10,5	X10,6	X10,7	X10,9	X10,10	X10,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)

X10,8	X10.11	X10,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_10,2= 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,6= X¹⁰₅₃ = 6, Z¹⁰₅₃ = 6,

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

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

X(6,8) = X_10,10= X¹⁰₈₃ = 7, Z¹⁰₈₃ = 7,

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

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

X(6,9) = X_10ф = 307.

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

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

X(1,5) = X_2ф = 102,

X(2,5) = X_3ф = 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_10,12= X¹⁰₉₇ = 6, Z¹⁰₉₇ = 6,

X(3,5) = X_8ф = 120,

X(4,5) = X_10ф = 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 с.