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

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

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

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

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

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

A(1) = W’1 = 289, A(2) = W’5 = 239, A(3) = W’4 = 259, A(4) = W’7 = 271,

A(5) = W’9 = 248.

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

B(1) = Q2 = 6, B(2) = Q3 = 3, B(4) = Q5 = 3, B(5) = Q6 = 6, B(6) = Q7 = 4,

B(7) = Q9 = 4, B(8) = Q10 = 7, B(9) = Qф = 1263.

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

X(1,1) = X12 , X(1,2) = X13 ,….., X(1,9) = X,…., X(2,9) = X5ф і т.д.

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

Таблиця 11

Пункти відправлення Пункти призначення
Приведення транспортних таблиць до машинного виду - student2.ru
Приведення транспортних таблиць до машинного виду - student2.ru

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

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

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

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

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

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

А(1) = W2' = 252, А(2) = W3' = 252, А(3) = W8' = 280.

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

В(1)=Q1=3,В(2) =Q8 =4,В(3) =Q11=5,В(4) =Q12=6,В(5)=Qф= 766 .

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

X(1,1)=X21,X(1,2) =X2, X(1,3) =X2,11, X(1,4) =X2,12, X(1,5) =X і т.д.

Транспортна табл. 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) = X12= X128 = 6, Z128=C1 X128 =12,

X(1,7) = X12= X182 = 4, Z182=C1 X182 =12,

X(1,9) = X = 279,

X(2,9) = X = 239,

X(3,9) = X = 259,

X(4,2) = X73= X735 = 3, Z735=C7 X735 =6,

X(4,3) = X74= X738 = 10, Z738=C7 X738 =20,

X(4,4) = X75= X746 = 3, Z746=C7 X746 =6,

X(4,5) = X76= X753 = 6, Z753=C7 X753 =12,

X(4,6) = X77= X764 = 4, Z764=C7 X764 =8,

X(4,8) = X7,10= X783 = 7, Z783=C7 X783 =14,

X(4,9) = X = 238,

X(5,9) = X = 248.

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

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

X(1,5) = X2ф = 252,

X(2,5) = X = 252,

X(3,1) = X81= X819 = 3, Z819=C8 X819 =6,

X(3,2) = X88= X879 = 4, Z879=C8 X879 =8,

X(3,3) = X8,11= X891 = 5, Z891=C8 X891 =10,

X(3,4) = X8,12= X897 = 6, Z897=C8 X897 =12,

X(3,5) = X = 262.

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

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

Z= Z1+ Z2= 86 + 36 = 122 (люд • хв).

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

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

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

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

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

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

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

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

Таблиця 17

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

Таблиця 18

Вузли відправлення Вузли призначення Приведення транспортних таблиць до машинного виду - student2.ru
-
-
-
-
-
-
-
-
-  
-  
Приведення транспортних таблиць до машинного виду - student2.ru                      

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

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

для значень і = 1,2,3,...,10, де 0Ц, Приведення транспортних таблиць до машинного виду - student2.ru , Приведення транспортних таблиць до машинного виду - student2.ru - добові потоки навантаження для

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

Таблиця 19

Номер вузла, і
Приведення транспортних таблиць до машинного виду - student2.ru

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

Рисунок 2

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

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

X129 + X189 + X1,10,9 = Q19,

X921 + X981 + X9,10,1 = Q91,

X298 + X218 + X2,10,8 = Q28,

X892 + X812 + X8,10,2 = Q82,

X398 + X378 + X3,10,8 = Q38,

X893 + X873 + X8,10,3 = Q83,

X789 + X739 + X7,10,9 = Q79,

X987 + X937 + X9,10,7 = Q97,

X375 + X345 + X3,10,5 = Q35,

X573 + X543 + X5,10,3 = Q53,

X476 + X456 + X4,10,6 = Q46,

X674 + X654 + X6,10,4 = Q64.

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

ПВ:

X218 + X 812Приведення транспортних таблиць до машинного виду - student2.ru ,

X129 + X921Приведення транспортних таблиць до машинного виду - student2.ru ,

X237 + X732 + X739 + X937Приведення транспортних таблиць до машинного виду - student2.ru ,

X345 + X543Приведення транспортних таблиць до машинного виду - student2.ru ,

X654 + X456Приведення транспортних таблиць до машинного виду - student2.ru ,

X375 + X573 + X376 + X673 + X476 + X674 + X378 + X873Приведення транспортних таблиць до машинного виду - student2.ru ,

X189 + X981 + X789 + X987Приведення транспортних таблиць до машинного виду - student2.ru ,

X298 + X892 + X398 + X893Приведення транспортних таблиць до машинного виду - student2.ru ,

X2,10,8 + X8,10,2 + X1,10,9 + X9,10,1 + X7,10,9 + X9,10,7 + X3,10,5 + X5,10,3 + X3,10,8 + X8,10,3 + X4,10,6 + X6,10,4 + X2,10,8 + X8,10,2 + X1,10,9 + X9,10,1 + X7,10,9 + X9,10,7 + X3,10,5 + X5,10,3 + X3,10,8 + X8,10,3 + X4,10,6 + X6,10,4Приведення транспортних таблиць до машинного виду - student2.ru .

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

Z = C1(X218 + X812) + C2(X129 + X921) + C3(X739 + X937) + C4 (X345 + X543) + C5 (X456 + X654) + C7 (X375 + X573 + X476 + X674 + X378 + X873) + C8 (X189 + X981 + X789 + X987) + C9 (X298 + X892 + X398 + X893) + C10 (X2,10,8 + X8,10,2 + X1,10,9 + X9,10,1 + X7,10,9 + X9,10,7 + X3,10,5 + X5,10,3 + X3,10,8 + X8,10,3 + X4,10,6 + X6,10,4 + X2,10,8 + X8,10,2 + X1,10,9 + X9,10,1 + X7,10,9 + X9,10,7 + X3,10,5 + X5,10,3 + X3,10,8 + X8,10,3 + X4,10,6 + X6,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’1, W’2, ... , W’10 , а під потоками пункти споживання однорідного вантажу 1, 2, … , 12 з потребами Q1, Q2,…,Q12. Для винятку, з розгляду потоків між пунктами, за якими перевезення не

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

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

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

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

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

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

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

Таблиця 23

Пункти відправлення Пункти призначення
ф Приведення транспортних таблиць до машинного виду - student2.ru
М С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
Приведення транспортних таблиць до машинного виду - student2.ru  

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

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

Пункти відправлення Пункти призначення
ф Приведення транспортних таблиць до машинного виду - student2.ru
м М М М М М
М М М М М М
М М М М М М
М М
М М М М
Приведення транспортних таблиць до машинного виду - student2.ru

Таблиця 25

Пункти відправлення Пункти призначення
ф Приведення транспортних таблиць до машинного виду - student2.ru
   
   
Приведення транспортних таблиць до машинного виду - student2.ru

Для рішення отриманих підзадач 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

Пункти відправлення Пункти призначення
Приведення транспортних таблиць до машинного виду - student2.ru
м М М М М М
М М М М М М
М М М М М М
М М
М М М М
Приведення транспортних таблиць до машинного виду - student2.ru
                       

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

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

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

(табл.27).

Таблиця 27

Пункти відправлення Пункти призначення
Приведення транспортних таблиць до машинного виду - student2.ru
   
   
Приведення транспортних таблиць до машинного виду - student2.ru

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

приведення до машиного виду наведена в табл. 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

Пункти відправлення Пункти призначення
Приведення транспортних таблиць до машинного виду - student2.ru
           
           
           
   
       
Приведення транспортних таблиць до машинного виду - student2.ru    
                       

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

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

Таблиця 30

Пункти відправлення Пункти призначення
Приведення транспортних таблиць до машинного виду - student2.ru
   
   
Приведення транспортних таблиць до машинного виду - student2.ru  

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

X(6,1) = X10,2= X1028 = 6, Z1028 = 6,

X(6,2) = X10,3= X1035 = 4, Z1035 = 3,

X(1,9) = X = 99,

X(2,9) = X = 149,

X(3,9) = X = 119,

X(6,3) = X10,4= X1038 = 10, Z1038 = 10,

X(6,4) = X10,5= X1046 = 3, Z1046 = 3,

X(6,5) = X10,6= X1053 = 6, Z1053 = 6,

X(6,6) = X10,7= X1064 = 4, Z1064 = 4,

X(6,7) = X10,9= X1082 = 4, Z1082 = 7,

X(6,8) = X10,10= X1083 = 7, Z1083 = 7,

X(4,9) = X = 101,

X(5,9) = X = 108,

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

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

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

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

X(2,5) = X3ф = 112,

X(4,1) = X10,1= X1019 = 3, Z1019 = 3,

X(4,2) = X10,8= X1079 = 4, Z1079 = 4,

X(4,3) = X10,11= X1091 = 5, Z1091 = 5,

X(4,4) = X10,12= X1097 = 6, Z1097 = 6,

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

X(4,5) = X10ф = 157.

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

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

Z = Z1 + Z2 = 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 с.


Наши рекомендации