Оліскевич М.С. (укладач) Технологічні процеси вантажних автомобільних перевезень - файл n1.doc

Оліскевич М.С. (укладач) Технологічні процеси вантажних автомобільних перевезень
скачать (5798 kb.)
Доступные файлы (1):
n1.doc5798kb.03.11.2012 04:35скачать

n1.doc

  1   2   3


МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”

ТЕХНОЛОГІЧНІ ПРОЦЕСИ

ВАНТАЖНИХ АВТОМОБІЛЬНИХ

ПЕРЕВЕЗЕНЬ



Методичні рекомендації

до розв’язання практичних вправ та самостійних завдань

до першого змістовного модулю

з курсу “Організація автомобільних перевезень”

для студентів фахового спрямування

8.090258 “Автомобілі і автомобільне господарство”
Затверджено на засіданні

кафедри „Експлуатація та

ремонт автомобільної техніки”

Протокол № 13/09-10 від 24.09.2009 р.



Львів-2009

Технологічні процеси вантажних перевезень: Методичні рекомендації до розв’язання практичних вправ та самостійних завдань до першого змістовного модулю з курсу “Організація автомобільних перевезень” для студентів фахового спрямування 8.090258 “Автомобілі і автомобільне господарство”/ Укл.: М.С. Оліскевич – Львів, 2009. – 36 с.


Укладач Оліскевич М.С., канд. техн. наук, доц.


Відповідальний за випуск: Гащук П.М., д-р техн. наук, проф.

Рецензенти: Глобчак М.В., канд. техн. наук, доц.

Качмар Р.Я., канд. техн. наук, доц.

передмова

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

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

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

Розрахунково-графічна робота складається з чотирьох задач, які не є взаємопов’язаними. До них відносяться задачі 1.2.3, 2.1.3, 2.3.3, 3.3.3. Вони виконуються за індивідуальними варіантами. Методика розв’язання цих задач є аналогічною до тих, що пропонуються на практичних заняттях. Це дає змогу студентам зрозуміти суть комплексного планування перевезень, а також підвищує відповідальність за точність і правильність розв’язків. Всі варіанти задач даної розрахунково-графічної роботи мають однозначний розв’язок. Задачі для розрахунково-графічної роботи, що відносяться до цього змістовного модулю займають 6-7 год. самостійної роботи. Допустимим у цьому випадку є використання ПЕОМ і ліцензійного програмного забезпечення з обов’язковим роздруковуванням початкових даних, результатів і посиланням на повну назву програмного забезпечення. Оформлення розрахунково-графічної роботи повинно цілком відповідати вимогам, що описані в розділі 4.
1. засади вантажознавства

1.1. Оптимізація розміщення вантажу в АТЗ

1.1.1. Зміст та формулювання задач.

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

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

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

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

Як приклад розглянемо завдання про завантаження двадцятифутового контейнера штучними вантажами відомої номенклатури (п видів). Допустимо, що відома маса одиниці кожного вантажного місця і об’єм, який він займає, максимальна допустима маса , яка може бути перевезена в контейнері, і об’єм контейнера V. Відомі також тарифи на перевезення одного вантажного місця кожного виду вантажу в контейнері. Завдання полягає у визначенні кількості одиниць вантажу кожного виду, який потрібно завантажити в контейнер, щоб прибуток від перевезення вантажів в контейнері був максимальним. При цьому передбачається, що всі вантажі сумісні між собою, тобто можуть укладатися в контейнер у будь-якому порядку.

Для математичного формулювання розглянутого завдання введемо змінні , які можуть набувати таких значень: 1 ? якщо вантаж виду підлягає завантаженню в контейнер; 0 ? в іншому випадку. Позначимо ? об’єм, що займає одиниця вантажу -го виду, bjвага однієї одиниці вантажу виду . Тоді математична модель, що відображає закономірність завантаження контейнера вантажами видів, виглядатиме таким чином:

; (1.1)

; (1.2)

Дані умови забезпечують, відповідно, не перевищення об'єму контейнера (1.1) і максимально допустимої маси (1.2) завантажених в нього вантажів. Функція мети в даному завданні ? грошові надходження від перевезення вантажів в контейнері:

(1.3)

де cj ? тариф на перевезення одиниці вантажу j-го виду у контейнері, який підлягає максимізації.

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

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

На автомобілі КамАЗ-5320 (розмір кузова 2,3Ч5,2 м) необхідно перевезти вантажі на піддонах А, В і С таких розмірів: А — 0,8Ч1,2 м; В ? 0,8Ч1,6 м; С ? 1,0Ч1,2 м ? у співвідношенні 74:12:65 відповідно, всього 151 шт. Визначити оптимальні способи завантаження АТЗ за умови максимального використання площі підлоги кузова. Визначити найбільш раціональні варіанти розміщення піддонів в кузові автомобіля КамАЗ-5320.

Розв’язок. На рис. 1.1 наведені різні варіанти завантаження кузова автомобіля.



Рис. 1.1. Схема розміщення піддонів А, В,С в кузові АТЗ різними варіантами (а - г)
Дані про кількість піддонів і втрати площі при різних способах навантаження подано в табл.1.1.

Таблиця 1.1

Варіанти завантаження піддонів

Параметр

Варіант

а

б

в

г

Кількість піддонів типу:













А

6

?

4

6

В

?

3

?

3

С

4

5

5

?

Незайнята площа, м2

1,4

2,12

2,12

2,36

Кількість завантажень (поїздок) для кожного варіанту









Виходячи з умов завдання отримуємо таку функцію мети:

(1.4)

Запишемо систему обмежень:

, (1.5)

Перше обмеження означає, що загальна кількість піддонів типу А, які перевозять 1-м, 3-м і 4-м способами повинна становити 74. Друге ? стосується піддонів типу В, які перевозять 2-м і 4-м способами завантаження і має їх бути 12 разом. Третє ? піддонів типу С, яких при завантаженні 1?3-м способами має бути 65.

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

Оптимальний розв’язок цієї задачі: =10; =3; =2; =1, при якому функція мети (1.4) набуває значення

F = 1,4·10 + 2,12·3 + 2,12·2 + 2,36·1 = 26,96 м2. Обмеження (1.5) також при цьому дотримані.
1.1.3. Практичні вправи.

На вантажному автомобілі потрібно перевезти пакети А штук, В штук, С штук. Враховуючи показники вантажомісткості, автомобіль можна завантажити двома різними способами: 1) пакетів А + пакетів В + пакетів С; 2) пакетів А + пакетів В + пакетів С. Прибуток після перевезення пакетів, завантажених різними способами може становити, відповідно, П1; і П2 тис. грн. Записати формулу мети та обмеження, а також знайти оптимальну кількість завантажень АТЗ двома різними способами з метою отримати максимальний прибуток і умовою, що інші способи завантаження, крім вказаних двох не використовуються. Використати початкові дані згідно з варіантом (табл.1.2).

Таблиця 1.2

Початкові дані для самостійної роботи

Величина

Варіант (остання цифра номеру залікової книжки)

0

1

2

3

4

5

6

7

8

9



150

112

65

48

92

33

102

64

50

75



25

40

60

102

25

11

88

64

55

62



24

15

80

60

45

125

170

32

42

27



4

6

3

12

3

6

4

3

2

3



8

4

6

8

8

2

6

3

3

4




Варіант (передостання цифра номеру залікової книжки)

0

1

2

3

4

5

6

7

8

9



7

8

9

10

11

4

7

8

9

10



10

2

4

6

8

15

11

7

4

5



1

2

3

3

2

1

2

3

4

1



1

5

6

3

6

7

3

5

6

7

П1

1,4

1,5

1,9

2,2

1,8

1,7

2,5

0,8

1,6

1,1

П2

2,5

2,1

2,0

1,8

1,7

0,5

1,7

0,2

2,5

1,6

1.2. Обчислення навантаження на АТЗ при різних схемах розміщення вантажів

1.2.1. Зміст та формулювання задачі.

При плануванні автомобільних перевезень важливо правильно, з урахуванням експлуатаційних обмежень розрахувати масу вантажу в кузові автомобіля, або автопоїзда, що перевозиться, яка не повинна перевищувати встановлені нормативні обмеження. При здійсненні міжнародних перевезень діють експлуатаційні обмеження, засновані на директивах ЄЕК ООН, або відповідні національні обмеження. Вагові обмеження ЄС подані в табл. 1.3.

Подібні обмеження діють і в сусідній Російській Федерації.

Таблиця 1.3

Вагові обмеження для АТЗ в Європейському Союзі

Показник

Числове обмеження, кг

Допустиме навантаження на одну вісь

10000

Допустиме навантаження на одинарну провідну вісь

11500

Допустиме навантаження на здвоєну вісь з відстанню між осями: до 1,0 м

11500

від 1,0 до 1,3 м

16000

від 1,3 до 1,8 м

18000

понад 1,8 м

2000

Допустиме навантаження на потроєну вісь причепа, або напівпричепа з відстанню між осями:

до 1,3 м

21000

від 1,3 до 1,4 м

24000

Допустима повна маса АТЗ:




автомобіля двохвісного

18000

автомобіля з трьома і більше осей

24000

причепа двовісного

18000

причепа з трьома і більше осями

24000

тягача з напівпричепом з трьома осями

28000

тягача з напівпричепом з чотирма осями і відстанню між осями напівпричепа не меншою, ніж 1,3 м

36000

тягача з напівпричепом з чотирма осями і пневматичною підвіскою

38000

тягача з напівпричепом з п’ятьма (2+3), шістьма (3+3) осями і відстанню між осями не більшою, ніж 1,8 м

40000


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



Рис.1.2. Загальний ескіз автопотяга: Q ? маса вантажу, т; Р1, Р2, Р3, ? осьові навантаження; Рс ? навантаження на сідло, т; т1, т2 ? маса порожнього автомобіля, що доводиться на передню і задню осі, відповідно; т3 — маса напівпричепа, що доводиться на задній візок; тсмаса напівпричепа, що доводиться на сідло, кг.
Для того, щоб знайти невідомі Р1, Р2, Р3 при заданих т1, т2, т3, Q, потрібно розглянути дві системи сил, що діють, відповідно, на тягач і на напівпричіп (рис.1.3).



а б

Рис. 1.3. Ескіз для розрахунку допустимої маси вантажів в кузові автопоїзда: а ? відстань між осями коліс візка тягача; h — відстань від передньої осі до сідельного пристрою; L — база автомобіля; S ? відстань від сідла до осі візка напівпричепа; Z ? відстань від сідла до центру ваги вантажу; .

В системі сил і реакцій тягача (рис.1.3 а) і напівпричепа (рис .13.б) потрібно скласти три рівняння моментів усіх сил і реакцій відносно:

а) уявної точки опори передніх коліс ? А (рис.1.4):

; (1.6)

б) осі візка тягача ? точки Б (рис.1.5):

, (1.7)

в) осі візка напівпричепа

, (1.8)





В результаті розв’язування системи рівнянь (1.6-1.8) знаходять числові значення відповідних реакцій Р1, Р2, Р3 при заданих т1, т2, т3, Q.

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

В типових виробничих задачах, як правило, потрібно визначити допустиму масу вантажу, що перевозиться на піддонах в кузові сідельного автопотяга у складі тягача і напівпричепа по дорогах країни, де встановлено відповідні вагові обмеження.
1.2.2. Приклад типової задачі.

Згідно з ескізом на рис. 1.2 та початковими даними:

а = 1350 мм; h = 3443 мм; L=3825 мм; т1=4774 кг; т2=4805 кг; т3=3721 кг; тс = 6279 кг; S =10600 мм; Z = 6415 мм обчислити допустимі навантаження на осі та повної маси автопотяга для перевезення вантажів у пакетах дорогами Російської Федерації.

Розв’язування. Вважаємо, що вантаж рівномірно розподілений по довжині кузова напівпричепа. Вагові обмеження для даного автопоїзда є такі:

•навантаження на передню вісь тягача Р1 = 7000 кг;

•навантаження на вбудований візок напівпричепа Р2 = 13000 кг;

•загальна маса автопоїзда з урахуванням його бази Y = S + h + a = 3825 + +10600 + 1350 = 15775 мм < 18000 мм повинна складати не більше, Gап = 44000 кг.

Допустима маса вантажу, виходячи з обмежень загальної маси автопотяга:

Q1 = Ga-пт1 ? т2т3 ? тc = 44000 ? 4774 ? 4805  3721 ? 6279 = 24421 кг.

Допустима маса вантажу, виходячи з обмеження навантаження на візок напівпричепа, визначена за формулою:

, кг, (1.9)

Q3 = (24421 ? 3721) 10600 /6415 = 34204 кг.

Допустима маса вантажу, виходячи з обмеження навантаження на сідло тягача, за формулою:

, кг, (1.10)

Q2 = [(13000 ? 4805)·3825/(3443  1350)] 10600/(10600 ? 6415) = 37933 кг.

Остаточно одержуємо, що допустима маса вантажу в кузові напівпричепа складає:

Q = min (Q1, Q2, Q3) = min (24421; 34204; 37933) = 24421 кг.

При цьому максимальне навантаження на візок напівпричепа 

= 24421∙6415/10600 + 3721 = 11058 кг.

Навантаження на сідло тягача:

= 24421 + 6279 + 3721  11058 = 23363 т.

Навантаження на задній візок тягача визначаємо за формулою:

, кг, (1.11)

P2 = 233633443/3825 + 4805 = 23836 кг.

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

Коефіцієнт використання вантажності автопоїзда:

, (1.12)

де qф ? фактична маса вантажу, розрахована по допустимим ваговим параметрам автопоїзда, кг; qн ? номінальна вантажність напівпричепа, кг;

?с = 24421/33000 = 0,74.

Отже, максимальне завантаження автопоїзда допустиме на 74%.
1.2.3. Завдання для самостійної роботи

Визначити допустиме максимальне завантаження автопотяга у складі двохвісного автомобіля-тягача (рис.1.7) та трьохвісного напівпричепа дорогами ЄС, використовуючи задані параметри АТЗ за варіантом (табл. 1.4). Визначити допустимий коефіцієнт використання вантажності автопоїзда.



Рис.1.7. Розрахункова схема для визначення навантаження на осі двохвісного тягача
Таблиця 1.4

Початкові дані для самостійної роботи

Величина

Варіант (остання цифра номеру залікової книжки)

0

1

2

3

4

5

6

7

8

9

, т

4,71

4,73

5,22

4,57

4,85

5,08

4,68

4,68

4,61

3,35

, т

2,17

2,19

1,985

1,63

1,975

2,51

2,37

2,45

4,5

3,3

, т

5,52

5,72

3,99

5,25

6,3

5,13

7,11

6,62

4,85

5,4

, т

1,42

1,3

0,9

1,3

1,6

1,97

2,29

1,88

1,15

2,1

, т

19

18

20,5

19,7

18,5

20,2

16,2

16,5

18

18




Варіант (передостання цифра номеру залікової книжки)

0

1

2

3

4

5

6

7

8

9

, м

3,05

3,2

3,13

3,15

3,64

3,04

3,18

3,1

4

3,97

, м

3,3

3,6

3,2

3,8

3,7

3,48

3,3

3,55

3,55

4,1

, м

5,1

5,12

5,16

4,88

5,16

4,4

4,52

4,64

4,48

5,1

, м

7,69

7,66

7,62

7,69

7,5

7,4

7,77

7,74

7,65

7,1

, т

34

33,8

34

34

32

31

32,7

34

32

33,2



2. автомобільні транспортні мережі

2.1. Визначення максимальної пропускної спроможності транспортної мережі

2.1.1. Зміст та формулювання задачі. Дано транспортну мережу, яка складається з n пунктів і деякої множини шляхів сполучень. Пропускна спроможність кожної транспортної ділянки між пунктами Рi, Pj задана у вигляді невід’ємного числа aij. Якщо aij=0, то це означає, що між пунктами Рi, Pj не існує шляху. В окремих пунктах Рh, h{1,n} зберігаються запаси однорідного вантажу, який потрібно перевезти в інші пункти Рm m{1,n}, де вони споживаються. В задачах такого виду потрібно визначити потенціал транспортної мережі, тобто її максимальну пропускну спроможність, яка в принципі не залежить від пунктів зародження і поглинання вантажопотоків. Пункти Рh у даному випадку використовуються формально, а обсяги запасів та потреб встановлюються як безмежно великі числа. Якщо ж задаються конкретні їх значення, то така задача набуває змісту перевірочного розрахунку.

Умови пошуку розв’язку ? замкнутість транспортної мережі, її зв’язаність і збалансованість. Будь-яку зв’язану транспортну мережу можна розглянути як замкнену систему, якщо ввести два додаткові фіктивні транспортні пункти: Р0 і Рn+1. Фіктивний пункт Р0 пов’язаний з кожним пунктом, де є запаси вантажу. Відповідним зв’язкам а0і цього фіктивного пункту потрібно надати значення, що дорівнюють кількості запасів вантажу. Аналогічно фіктивний пункт Рn+1 пов’язаний з кожним транспортним пунктом, куди однорідні вантажі потрібно доставити. Зв’язкам аj,n+1 надають числові значення, які дорівнюють відповідній потребі споживання вантажу. Згідно з такими введеннями потрібно використовувати початкову матрицю пропускної спроможності = .

З умов задачі сформулюємо такі обмеження:

(2.1)

(2.2)

де ? вантажопотік вздовж транспортної ділянки Рi - Рj;

Обмеження (2.1) означає, що вантажопотік по кожній ділянці Рi – Рj є невід’ємним і не перевищує її пропускної спроможності. Обмеження (2.2) означає, що кількість вантажу, який надходить в кожен транспортний пункт Рi, дорівнює кількості вантажу, який з нього вивозиться (і=1,2,…,n). З обмеження (2.2) випливає:

(2.3)

Величина називається вантажопотоком в транспортній мережі. Умова задачі полягає у пошуку максимального числового значення Qmax. Така задача розв’язується методом повного перебору всіх можливих вантажопотоків від пункту до пункту за алгоритмом Форда-Фалкерсона. Для її розв’язання введемо такі означення. Якщо розбити множину всіх даних транспортних пунктів на дві підмножини U, V, які не перетинаються, з обов’язковими умовами , то множину всіх транспортних сполучень, які виходять з підмножини U і входять в підмножину V назвемо перерізом транспортної мережі. Переріз з найменшою пропускною спроможністю назвемо мінімальним. Згідно із засадами лінійного програмування, для будь-якої величини потоку Q в кінцевий фіктивний транспортний пункт Рn+1 надійде вантажопотік, який не більший, ніж Q. Отже, зміст задачі полягає в пошуку мінімального перерізу.

Для пошуку максимального потоку в мережі потрібно, очевидно, знайти всі різні шляхи від пункту Р0 до пункту Рn+1 і максимально використати їх пропускні спроможності. Якщо якась транспортна ділянка вже використана в одному з шляхів, то її можна використати і в інших шляхах, але з меншою пропускною спроможністю. Алгоритм складається з циклічного повторення кроків 1 і 2, а також завершального кроку 3.

Крок 1. Помітити в початковій матриці А0 Р0-й стовпець і Р0-й рядок. Знайти в Р0 рядку клітинки, в яких є аij>0 і помітити відповідні j-ті стовпці, іншими словами ? знайти всі транспортні пункти, які можуть бути першими ланками різних шляхів. Помітити також всі j-ті рядки. У будь-якому з помічених рядків знайти клітинку, яка містить значення аij>0 і знаходиться в непоміченому стовпці. Знову помітити j-й стовпець. Процес продовжити доти, поки не буде з’ясовано один з фактів: (а) поміченим є Рn+1-й стовпець; (б) неможливо знайти будь-якого шляху до вершини Рn+1. У випадку (а) пропускна спроможність шляху S1 від пункту Р0 до пункту Pn+1 обчислиться за формулою:

(2.4)

У випадку (б) потрібно сформувати множину усіх знайдених шляхів , і якщо , то перейти до кроку 3. В іншому випадку ? до кроку 2.

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

Крок 3. Матрицю , отриману на попередньому -у циклі алгоритму вважати остаточною ? . Для визначення всіх отриманих вантажопотоків потрібно від усіх елементів початкової матриці відняти відповідні елементи матриці , отриманої на завершальному циклі. Якщо перший цикл виявився завершальним, то значить умови розв’язання задачі є недотриманими і потрібно перевірити матрицю . Якщо ж виконано хоча б один цикл, тобто , то усі додатні числові значення знайдених різниць визначають числові значення вантажопотоків xij на відповідних транспортних шляхах, а числове значення потоку в транспортній мережі визначиться за формулою (2.3).
2.1.2. Приклад типової задачі. Обчислити максимальну пропускну спроможність мережі, яка задана пропускними спроможностями її доріг (табл.2.1).

Таблиця 2.1

Матриця пропускної спроможності доріг транспортної мережі, т/год.

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

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

1

2

3

4

5

6

7

1

0

5

0

7

0

12

0

2

6

0

4

8

8

0

0

3

0

6

0

0

6

0

15

4

8

9

0

0

0

4

0

5

0

6

5

0

0

10

12

6

14

0

0

4

11

0

10

7

0

0

15

0

10

11

0


Створюємо початкову матрицю (табл. 2.2), яка містить два фіктивні пункти: , де міститься незліченна кількість однорідного вантажу і , де є така ж необмежена потреба у цьому вантажі. Формально для відображення цих попиту і пропозиції використаємо досить велике число, наприклад, 300 т. Також вибираємо довільну множину пунктів, де зберігаються такі вантажі і довільну множину пунктів, де ці вантажі мають споживатися. Єдиною умовою вибору є те, що ці множини не повинні перетинатися. Загальний обсяг потрібно перерозподілити довільним чином між пунктами-відправниками вантажу, тобто встановити числові значення , де - вибрана кількість відправників. У матриці це зроблено пропорційно між трьома відправниками: , , . Пунктами споживання вантажу довільно вибрано 6-й і 7-й, а відповідні значення , .

Таблиця 2.2

Початкова матриця пропускної спроможності ділянок мережі, т/год.

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

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

0

1

2

3

4

5

6

7

8

0

0

100

100

100

0

0

0

0

0

1

0

0

5

0

7

0

12

0

0

2

0

6

0

4

8

8

0

0

0

3

0

0

6

0

0

6

0

15

0

4

0

8

9

0

0

0

4

0

0

5

0

0

6

5

0

0

10

12

0

6

0

14

0

0

4

11

0

10

150

7

0

0

0

15

0

10

11

0

150

8

0

0

0

0

0

0

0

0

0


Перший і другий кроки алгоритму Форда-Фалкерсона на першому циклі дали змінену матрицю . перший шлях для якої - (табл. 2.3)
Таблиця 2.3

Змінена матриця пропускної спроможності ділянок мережі, т/год.

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

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

0

1

2

3

4

5

6

7

8

0

0

96

100

100

0

0

0

0

0

1

4

0

5

0

3

0

12

0

0

2

0

6

0

4

8

8

0

0

0

3

0

0

6

0

0

6

0

15

0

4

0

12

9

0

0

0

0

0

0

5

0

0

6

5

0

0

10

12

0

6

0

14

0

0

8

11

0

10

146

7

0

0

0

15

0

10

11

0

150

8

0

0

0

0

0

0

6

0

0


Разом до третього кроку було виконано дев’ять циклів і знайдено такі шляхи:



Остаточна матриця пропускної спроможності має вигляд як у табл.2.4. Її різниця з початковою матрицею подано в табл.2.5.

Таблиця 2.4

Остаточна матриця пропускної спроможності ділянок мережі, т/год.

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

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

0

1

2

3

4

5

6

7

8

0

0

75

96

83

0

0

0

0

0

1

26

0

0

0

0

0

0

0

0

2

4

10

0

0

11

0

0

0

0

3

17

0

10

0

0

0

0

0

0

4

0

15

6

0

0

0

0

0

0

5

0

4

10

11

0

0

8

0

0

6

0

27

0

0

8

13

0

10

131

7

0

0

0

30

0

22

11

0

123

8

0

0

0

0

0

0

21

27

0
  1   2   3


Учебный материал
© bib.convdocs.org
При копировании укажите ссылку.
обратиться к администрации