Главная Коллекция "Revolution" Транспорт Раціональна організація вантажних перевезень на транспортних мережах

Раціональна організація вантажних перевезень на транспортних мережах

Метод мінімального вузла відправлення вантажу. Аналіз оптимізації транспортних перевезень. Угорський метод розв’язання транспортної задачі про призначення. Принципи пошуку найкоротшого шляху між заданими вершинами. Матрично-мережева модель управління.

Рубрика Транспорт
Вид курсовая работа
Язык украинский
Дата добавления 07.09.2016
Размер файла 232,7 K
рефераты на заказ со скидкой

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Курсовий проект

Раціональна організація вантажних перевезень на транспортних мережах

1. Метод мінімального вузла відправлення вантажу ТТ

вантаж мережевий транспортний перевезення

Метод мінімального вузла відправлення вантажу побудови опорного плану перевезень, який поєднує кращі якості перерахованих вище методів також розглянемо на конкретному прикладі (див. табл. 1).

Таблиця 1

B1

B2

B3

B4

Запаси

ai

A1

3

x11

5

x12

4

x13

5

x14

12

A2

3

x21

6

x22

1

x23

2

x24

8

A3

2

x31

6

x32

2

x33

2

x34

10

Заявки

bj

7

8

9

6

30

Спочатку знайдемо суми вартостей перевезення одиниці вантажу окремо по рядках (Сі, i = 1, m) ТТ і відсортуємо отримані величини у порядку їх зростання (табл. 2). Порядкові номери зростання сум проставлені у вигляді нижніх індексів відповідних величин.

Таблиця 2. Вихідна ТТ

B1

B2

B3

B4

Запаси

ai

Ci

A1

3

5

4

5

12

171

A2

3

_

6

_

1

8(1)

x23

2

_

8

122

8-8=0

A3

2

6

2

2

10

123

Заявки

bj

7

8

9

6

30

9-8=1

Заносити обсяги перевезень починаємо з вузла, який має найменшу суму вартостей одиниці перевезень вантажу по окремому рядку - вузлу відправлення вантажу (звідси і назва методу). Подальший процес формування опорного плану буде відбуватися у відповідності з порядковими номерами зростання сум вартостей перевезень одиниці вантажу вузлів відправлення, що залишилися і т.д., до одержання (m + n - 1) перевезень. Принцип заповнення клітинок ТТ у самому рядку буде наступним: максимально задовольнити весь обсяг замовлення вантажу в першу чергу за рахунок найменших вартостей перевезень одиниці вантажу.

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

Таблиця 3

B1

B2

B3

B4

Запаси

ai

A1

3

5

4

5

12

A2

3

_

6

_

1

8(1)

x23

2

_

0

A3

2

7(2)

6

2

2

10

10-7=3

Заявки

bj

7

8

1

6

22

7-7=0

Таблиця 4

B1

B2

B3

B4

Запаси

ai

A1

3

_

5

4

1(3)

5

12

12-1=11

A2

3

_

6

_

1

8(1)

x23

2

_

0

A3

2

7(2)

6

2

_

2

3

Заявки

bj

0

8

1

6

15

1-1=0

Таблиця 5

B1

B2

B3

B4

Запаси

ai

A1

3

_

5

4

1(3)

5

11

A2

3

_

6

_

1

8(1)

x23

2

_

0

A3

2

7(2)

6

_

2

_

2

3(4)

3

3-3=0

Заявки

bj

0

8

0

6

14

6-3=3

Таблиця 6

B1

B2

B3

B4

Запаси

ai

A1

3

_

5

8(5)

4

1(3)

5

11

11-8=3

A2

3

_

6

_

1

8(1)

x23

2

_

0

A3

2

7(2)

6

_

2

_

2

3(4)

0

Заявки

bj

0

8

0

3

11

8-8=0

Таблиця 7. Опорний план за методом мінімального вузла відправлення вантажу ТТ

B1

B2

B3

B4

Запаси

ai

A1

3

_

5

8(5)

4

1(3)

5

3(6)

3

3-3=0

A2

3

_

6

_

1

8(1)

x23

2

_

0

A3

2

7(2)

6

_

2

_

2

3(4)

0

Заявки

bj

0

0

0

3

3

3-3=0

Одержали (m + n - 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

у.г.о.

2. Метод потенціалів оптимізації транспортних перевезень

Більш простим методом оптимізації плану перевезень є метод потенціалів, суть якого полягає у наступному.

1. Приймаємо будь-яке значення початкового потенціалу для i-го ряду транспортної таблиці; шукаємо заповнену клітку (ij), для якої і визначаємо відповідний потенціал по наступній формулі: Робимо аналогічні розрахунки для решти рядів і колонок таблиці, спираючись на вже розраховані транспортні потенціали.

2. Після визначення всіх i (;) перевіряємо нерівність для всіх (ij) незайнятих клітинок таблиці (тобто для ). Якщо ця нерівність має місце для усіх без виключення незайнятих кліток, план перевезень є оптимальним.

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

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

Наприклад, є певний опорний план перевезень (табл. 7). Відмітимо, що для отриманого плану маємо у.г.о.

Розрахуємо потенціали і , використовуючи саме зайняті клітинки, і занесемо їх в додаткові стовпчик і рядок.

Приймаємо , тоді ; . Використовуючи вже отримані потенціали, визначаємо решту потенціалів:

; ;

; .

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

; ; ;

; ; .

Таблиця 8

B1

B2

B3

B4

ui

Запаси

ai

A1

3

_

5

8(5)

4

1(3)

5

3(6)

0

12

A2

3

_

6

_

1

8(1)

x23

2

_

-3

8

A3

2

7(2)

6

_

2

_

2

3(4)

1

10

vj

6

5

4

1

Заявки

bj

7

8

9

6

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

Для цього шукаємо контур, що містить у решті кутів зайняті клітинки. Це контур: (див. табл. 8). Оскільки ми завантажуємо , присвоюємо їй знак «+», потім, пересуваючись по контуру, послідовно міняємо знаки. Мінімальне абсолютне значення від'ємного обсягу знаходиться в клітинці і дорівнює xп = 1 в.о. Пересуваємо цей обсяг по контуру з урахуванням знаків і отримуємо новий план перевезень (див. табл. 9), при цьому вартість його реалізації буде дорівнювати:

L2 = 8Ч5 + 4Ч5 + 8Ч1 + 7Ч2 + 1Ч2 + 2Ч2 = 88 у.г.о.

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

.

Перевіряємо побудований план на оптимальність, використовуючи отримані потенціали, а саме:

; ; ;

; ; .

Таблиця 9. ТТ після розподілу вантажу у клітинку

B1

B2

B3

B4

ui

Запаси

ai

A1

3

_

5

8

4

0

5

4

0

12

A2

3

_

6

_

1

8

x23

2

_

0

8

A3

2

7

6

_

2

1

2

2

1

10

vj

3

5

1

2

Заявки

bj

7

8

9

6

План оптимальний, тому що для всіх незайнятих клітинок виконується умова .

3. Угорський метод розв'язання транспортної задачі про призначення

Угорський метод є одним з найцікавіших і найпоширеніших методів рішення транспортних завдань. Основна ідея цього методу була вперше висловлена угорським математиком Е. Егерварі (звідси й назва методу) задовго до виникнення теорії лінійного програмування.

Розглянемо спочатку основні ідеї угорського методу на прикладі рішення завдання вибору (завдання про призначення), що є окремим випадком транспортної задачі, а потім узагальнимо цей метод для довільної транспортної задачі.

Постановка завдання

Припустимо, що є різні транспортні засоби (ТЗ), кожний з яких може виконувати будь-яку транспортну роботу, але з неоднаковою ефективністю. Продуктивність кожного i-го ТЗ при виконанні j-тої транспортної роботи позначимо Cij, і = 1, …, n; j = 1, …, n. Потрібно так розподілити ТЗ по роботах, щоб сумарний ефект від їхнього використання був максимальний. Таке завдання називається завданням вибору або завданням про призначення.

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

щоб сума була максимальна й при цьому з кожного рядка й стовпця був обраний тільки один елемент.

Розв'язання завдання

Введемо наступні поняття:

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

Еквівалентні матриці С і D (C ~ D), якщо сij = dij + ai + bj для всіх i, j.

Попередній етап. Розшукують максимальний елемент в j-му стовпці й всі елементи цього стовпця послідовно віднімають із максимального. Цю операцію проробляють над всіма стовпцями матриці С. У результаті утвориться матриця з ненегативними елементами, у кожному стовпці якої є, принаймні, один нуль.

Далі розглядають i-ий рядок отриманої матриці, розшукують її мінімальний елемент і з кожного елемента цього рядка віднімають мінімальний. Цю процедуру повторюють із усіма рядками. У результаті одержимо матрицю С0 (С0 ~ C), у кожному рядку й стовпці якої є, принаймні, один нуль. Описаний процес перетворення С у С0 називається приведенням матриці.

Знаходимо довільний нуль у першому стовпці й відзначаємо його зірочкою. Потім переглядаємо другий стовпець, і якщо в ньому є нуль, розташований у рядку, де немає нуля із зірочкою, то відзначаємо його зірочкою. Аналогічно переглядаємо один за іншим всі стовпці матриці С0 і відзначаємо, якщо можливо, що випливають нулі знаком '*'. Очевидно, що нулі матриці С0, відзначені зірочкою, є незалежними. На цьому попередній етап закінчується.

(k+1) - а ітерація. Припустимо, що k-та ітерація вже проведена й у результаті отримана матриця Сk. Якщо в ній є рівно n нулів із зірочкою, то процес рішення закінчується. У противному випадку переходимо до (k+1) - ої ітерації.

Кожна ітерація починається першим і закінчується другим етапом. Між ними може кілька разів проводитися пари етапів: третій - перший. Перед початком ітерації знаком '+' виділяють стовпці матриці Сk, які містять нулі із зірочками.

Перший етап. Переглядають невиділені стовпці Сk. Якщо серед них не виявиться нульових елементів, то переходять до третього етапу. Якщо ж невиділений нуль матриці Сk виявлений, то можливо один із двох випадків:

1) рядок, що містить невиділений нуль, містить також і нуль із зірочкою;

2) цей рядок не містить нуля із зірочкою.

У другому випадку переходимо відразу до другого етапу, відзначивши цей нуль штрихом.

У першому випадку цей невиділений нуль відзначають штрихом і виділяють рядок, у якій він утримується (знаком '+' праворуч від рядка). Переглядають цей рядок, знаходять нуль із зірочкою й знищують знак '+' виділення стовпця, у якому втримується даний нуль.

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

Цей процес за кінцеве число кроків закінчується одним з наступних результатів:

1) всі нулі матриці Сk виділені, тобто перебувають у виділених рядках або стовпцях. При цьому переходять до третього етапу;

2) є такий невиділений нуль у рядку, де немає нуля із зірочкою. Тоді переходять до другого етапу, відзначивши цей нуль штрихом.

Другий етап. На цьому етапі будують наступний ланцюжок з нулів матриці Сk: вихідний нуль зі штрихом, нуль із зірочкою, розташований в одному стовпці з першим нулем зі штрихом в одному рядку з попереднім нулем із зірочкою й т.д. Отже, ланцюжок утвориться пересуванням від 0' до 0* по стовпці, від 0* до 0' по рядку й т.д.

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

Далі над елементами ланцюжка, що знаходяться на непарних місцях (0') ставимо зірочки, знищуючи їх над парними елементами (0*). Потім знищуємо всі штрихи над елементами Сk і знаки виділення '+'. Кількість незалежних нулів буде збільшено на одиницю. На цьому (k+1) - а ітерація закінчена.

Третій етап. До цього етапу переходять після першого, якщо всі нулі матриці Сk виділені. У такому випадку серед невиділених елементів Сk вибирають мінімальний і позначають його h (h>0). Далі віднімають h із всіх елементів матриці Сk, розташованих у невиділених рядках і додають до всіх елементів, розташованим у виділених стовпцях. У результаті одержують нову матрицю Сk', еквівалентну Сk. Помітимо, що при такому перетворенні, всі нулі із зірочкою матриці Сk залишаються нулями й у Сk', крім того, у ній з'являються нові невиділені нулі. Тому переходять знову до першого етапу. Завершивши перший етап, залежно від його результату або переходять до другого етапу, або знову повертаються до третього етапу.

Після кінцевого числа повторень черговий перший етап обов'язково закінчиться переходом на другий етап. Після його виконання кількість незалежних нулів збільшиться на одиницю й (k+1) - а ітерація буде закінчена.

Розв'язання задачі за допомогою угорського методу

Нехай в результаті вирішення основної транспортної задачі ми отримали оптимальні обсяги перевезень xij>=0 у кількості (m+n-1). З урахуванням матриці відстаней можна отримати відповідну матрицю обсягів транспортної роботи (ТР) , причому кількість її ненульових елементів також дорівнює (m+n-1).

Перенумеруємо всі ненегативні обсяги ATPij від 1 до (m+n-1), рухаючись послідовно по кожному рядку матриці обсягів ТР зверху до низу. В результаті отримуємо матрицю-строку А = {Aj}, (), де N = (m+n - 1) - кількість необхідних ТР.

Припустимо, що для виконання спланованих обсягів перевезень передбачено також N транспортних засобів (ТЗ), кожний з котрих характеризується деякою продуктивністю виконання одиниці тієї чи іншої ТР (Пij - продуктивність виконання i - м ТЗ j - ї ТР, де , ). Очевидно, що термін виконання j - ї ТР i - им ТЗ дорівнює

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

- знайдемо у матриці T максимальне значення - саму довгу за терміном виконання транспортну роботу;

- потім порахуємо за який робочий час tроб буде вона виконана, причому час виконання буде кратним 8 (кількості робочих годин у зміну);

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

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

,

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

Розглянемо вищеописану методику на конкретному прикладі - оптимальному плану перевезень вантажу з табл. 10, який був отриманий за допомогою метода мінімального вузла відправлення вантажу ТТ.

Таблиця 10. ТТ з оптимальним планом перевезень вантажу

B1

B2

B3

B4

Запаси

ai

A1

3

_

5

8(5)

4

1(3)

5

3(6)

3

A2

3

_

6

_

1

8(1)

x23

2

_

0

A3

2

7(2)

6

_

2

_

2

3(4)

0

Заявки

bj

0

0

0

3

3

З табл. 10 формуємо матрицю-строку А = {Aj}, (), де N = (m+n - 1) - кількість необхідних ТР: 8Ч5 = 40; 4Ч1 = 4; 3Ч5 = 15; 8Ч1 = 8; 7Ч2 = 14; 3Ч2 = 6. Задана матриця Пij-продуктивності виконання i-м ТЗ j-ї ТР:

Матриця Пij - продуктивності виконання i-м ТЗ j-ї ТР

2

3

4

5

2

3

4

5

2

3

4

5

П =

5

4

3

2

5

4

3

2

5

4

3

2

3

1

2

4

1

3

2

4

1

3

2

4

Розрахуємо по формулі (з приведенням до цілого числа) матрицю Tрч - матрицю робочого часу виконання ТЗ відповідних транспортних робіт:

20

1

4

2

7

2

10

1

8

3

4

1

Трч=

8

1

5

4

3

2

13

2

3

2

5

3

13

4

8

2

14

2

20

1

15

3

7

2

Побудуємо нову матрицю Tвч, елементи якої із розрахунку tроб = 8 (8 годин у зміну)Ч4 (зміни) = 32 години:

12

31

28

30

25

30

22

31

24

29

28

31

Твч=

24

31

27

28

29

30

19

30

29

30

27

29

19

28

24

30

18

30

12

31

17

29

25

30

При рішенні завдання використаємо наступні позначення: знак виділення '+', що підлягає знищенню, обводимо кружком.

Попередній етап. Відшукуємо максимальний елемент першого стовпця - 29. Віднімаємо з нього всі елементи цього стовпця. Аналогічно для одержання другого, третього, четвертого, п'ятого й шостого стовпців нової матриці віднімаємо всі елементи цих стовпців від 31, 30, 28, 30 і 26 відповідно. Одержимо матрицю С0(C0~Твч).

12

0

1

0

4

1

2

0

5

1

1

0

С0=

0

0

2

2

0

1

5

1

0

0

2

2

5

3

5

0

11

1

12

0

12

1

4

1

Тому що в кожному рядку С0 є хоча б один нуль, то на цьому процес приведення матриці закінчується. Далі шукаємо й відзначаємо знаком '*' незалежні нулі в С0, починаючи з першого рядка. Число незалежних нулів дорівнює 5 (5 ? n(6)), тому переходимо на першу ітерацію.

12

0

1

0

4

1

2

0*

5

1

1

0*

С0=

0*

0

2

2

0

1

5

1

0*

0*

2

2

5

3

5

0

11

1

12

0

12

1

4

1

Перша ітерація

Виділяємо знаком '+' перший, другий, третій, четвертий і шостий стовпці матриці C0, які містять 0*.

Перший етап. Переглядаємо невиділений п'ятий стовпець, знаходимо в ньому невиділений нуль C035 = 0, відзначаємо його штрихом і виділяємо знаком '+' третій рядок. Переглядаємо цей рядок, знаходимо в ньому елемент C031= 0* і знищуємо знак виділення першого стовпця, що містить 0*.

+

+

+

+

12

0

1

0

4

1

2

0*

5

1

1

0*

С0=

0*

0

2

2

0»

1

+

5

1

0*

0*

2

2

5

3

5

0

11

1

12

0

12

1

4

1

Далі переглядаємо цей перший стовпець (який уже став невиділеним) і відшукуємо у ньому невиділений нуль (або нулі). Таких нулів у цьому стовпці не має і також всі нулі матриці C0 виділені, тобто усі вони перебувають у виділених стовпцях або рядках, тому переходимо до третього етапу.

Третій етап. Вибираємо серед невиділених елементів C0 мінімальний і позначаємо його h (h > 0). У нашому випадку h = min {12, 2, 5, 5, 12, 4, 1, 2, 11, 4} = 1. Далі віднімаємо h із всіх цих невиділених елементів C0, і додаємо до всіх елементів, розташованих на пересічні виділених рядків і стовпців.

+

+

+

+

12

0

1

0

4

1

2

0*

5

1

1

0*

С0=

0*

0

2

2

0»

1

+

5

1

0*

0*

2

2

5

3

5

0

11

1

12

0

12

1

4

1

Отримуємо наступну модифікацію таблиці C'0 і переходимо до першого етапу.

+

+

+

+

11

0

1

0

3

1

1

0*

5

1

0'

0*

С'0=

0*

1

3

3

0»

2

+

4

1

0*

0*

1

2

4

3

5

0

10

1

11

0

12

1

3

1

Перший етап. Переглядаємо невиділений пятий стовпець, знаходимо в ньому невиділений нуль C'025 = 0, відзначаємо його штрихом і виділяємо знаком '+' другий рядок. Переглядаємо цей рядок, знаходимо в ньому елемент C'022= 0* і знищуємо знак виділення другого стовпця, що містить 0*. Далі переглядаємо цей другий стовпець (який уже став невиділеним) і шукаємо у ньому невиділений нуль (або нулі). Знаходимо в ньому невиділений нуль C'012 = 0, відзначаємо його штрихом і виділяємо знаком '+' перший рядок.

Переглядаємо цей рядок, не знаходимо в ньому елемент 0* і не знищуємо знак виділення другого стовпця. Далі переглядаємо цей другий стовпець (не виділений) і шукаємо у ньому невиділений нуль (або нулі). Знаходимо в ньому невиділений нуль C'062 = 0, відзначаємо його штрихом і виділяємо знаком '+' шостий ряд. Переглядаємо цей рядок, і не знаходимо в ньому елемент 0*

Таких нулів у цьому стовпці не має і також всі нулі матриці C0 виділені, тобто усі вони перебувають у виділених стовпцях або рядках, тому переходимо до третього етапу.

+

+

11

0'

1

0

3

1

+

1

0*

5

1

0'

0*

С'0=

0*

1

3

3

0»

2

+

4

1

0*

0*

1

2

4

3

5

0

10

1

11

0'

12

1

3

1

+

Третій етап. Вибираємо серед невиділених елементів C'0 мінімальний і позначаємо його h (h > 0). У нашому випадку h = min {1, 4, 4, 1, 3, 0, 1, 10,} = 1. Далі віднімаємо h із всіх цих невиділених елементів C'0, і додаємо до всіх елементів, розташованих на пересічні виділених рядків і стовпців.

+

+

11

0'

2

1

3

1

+

0

0*

5

1

0'

0*

С'0=

0*

1

4

4

0»

3

+

3

1

0*

0*

0

2

3

3

5

0

9

1

11

0'

13

2

3

2

+

Отримуємо наступну модифікацію таблиці C''0 і переходимо до першого етапу.

+

+

11

0'

2

1

3

1

+

0'

0*

5

1

0'

0*

+

С'0=

0*

1

4

4

0»

3

+

3

1

0*

0*

0

2

3

3

5

0

9

1

11

0'

13

2

3

2

+

Перший етап. Перший невиділений нуль C''021 = 0 (і його виділяємо штрихом) знаходиться у першому стовпці, який перетинається з другим рядком. Переглядаємо цей рядок, знаходимо в ньому елемент C'022= 0* і виділяємо + другий стовпець, що містить 0*.

Другий невиділений нуль C''045 = 0 знаходиться у п'ятому стовпці, який перетинається з четвертим рядком. Переглядаємо цей рядок, знаходимо в ньому елемент C'044= 0* і виділяємо + четвертий стовпець, що містить 0* і знищуємо знак виділення четвертого стовпця, що містить 0*. Далі переглядаємо цей четвертий стовпець (не виділений) і шукаємо у ньому невиділений нуль (або нулі). Знаходимо в ньому невиділений нуль C'054 = 0, відзначаємо його штрихом і виділяємо знаком '+' п'ятий ряд. Переглядаємо цей рядок, і не знаходимо в ньому елемент 0*

Тому відмічаємо його штрихом і переходимо до другого етапу.

+

+

11

0'

2

1

3

1

+

0'

0*

5

1

0'

0*

+

С'0=

0*

1

4

4

0»

3

+

3

1

0*

0*

0'

2

+

3

3

5

0'

9

1

11

0'

13

2

3

2

+

Другий етап. Починаючи з останнього відміченого нуля зі штрихом C''054 = 0', будуємо ланцюг, рухаючись від нього по стовпцю. Знаходимо нуль із зірочкою C»044= 0*, далі від нього рухаємося уздовж четвертого рядка й знаходимо нуль зі штрихом C»045 = 0'. Далі пересуваємося по п'ятому стовпцю і не знаходимо нуль із зіркою. На цьому ланцюг закінчується, тому що у п'ятому стовпці не має нулів із зірочкою.

Таким чином, ланцюг побудований: 0'54 > 0*44 > 0'45. Заміняємо у ланцюги штрих на зірочку й знищуємо зірочки над парними елементами ланцюга (0*54 > 044 > 0*45), а також всі знаки виділення стовпців і рядків. Після цієї ітерації кількість незалежних нулів у аналізованої матриці стало дорівнювати 6 (розмірності матриці С0) і тому алгоритм закінчує роботу. Шукані елементи призначення відповідають позиціям незалежних нулів матриці С1 (тобто 0*).

+

+

11

0'

2

1

3

1

+

0'

0*

5

1

0'

0*

+

С'0=

0*

1

4

4

0»

3

+

3

1

0*

0

0*

2

+

3

3

5

0*

9

1

11

0'

13

2

3

2

+

Таким чином, оптимальне закріплення рухомого складу (шість ТЗ) за шістю ТР, при якому сумарний час виконання усього комплексу є мінімальним, дорівнює:

F = Трч13 + Трч22 + Трч43 + Трч54 + Трч44 + Трч26 = 8 + 1 + 3 + 2 + 4 + 1 = 19 (умовних одиниць часу).

4. Задача пошуку найкоротшого шляху між двома заданими вершинами

Орграф з позначеними дугами

Нехай є орієнтований граф G = (V, Е), у якого всі дуги мають позитивні мітки (вартості дуг), а одна вершина визначена як джерело. Завдання полягає в пошуку вартості найкоротших шляхів від джерела до всіх інших вершин графа G. Ця задача часто називається задачею пошуку найкоротшого шляху з одним джерелом і може показатися, що більш природною задачею буде пошук найкоротшого шляху від джерела до визначеної вершини призначення. Але ця задача в загальному випадку має такий же рівень складності, що і задача пошуку найкоротшого шляху для усіх вершин графа (за винятком того «щасливого» випадку, коли шлях до вершини призначення буде знайдений раніше, чим переглянуті шляхи до усіх вершин графа).

Примітка: затемненими показані найкоротші відстані від 1-ої вершини до кожної з вершин, котрі вже знаходяться у множині S

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

Таблиця 11

Ітерація

S

D[A2]

D[A3]

D[B1]

D[B2]

D[B3]

D[B4]

Початок А1

1

5

7

14

8

Початок А1

2

5

7

9

8

15

16

Початок

А1

3

5

7

9

8

23

13

5. Матрично-мережева модель управління перевезеннями вантажів в ТС

Формування МММ управління перевезеннями вантажів у ТС включає д...


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены