Визначення найкоротших відстаней

 

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

Завдання. Скласти матрицю найкоротших відстаней між вершинами транспортної мережі.

Задача. Надана транспортна мережа. Відстані між вершинами наведені на рис. 9.1 за варіантами (і — остання, а j – предостання цифра номеру залікової книжки). Визначити найкоротші відстані між усіма вершинами транспортної мережі методом потенціалів.

 

Вказівки до виконання

 

Завдання виконується у такій послідовності:

1. Розрахувати довжину ланок транспортної мережі за своїм варіантом.

2. Розв’язати задачу методом потенціалів.

Початковій вершині, від якої знаходять найкоротші відстані, надають потенціал, який дорівнюється нулю  Визначають ланки, де обрана вершина (і -я) є початковою, і розраховують потенціали кінцевих вершин цих ланків за формулою:

                                                                                  (9.1)

де  – довжина ланки  тобто відстань між вершинами і та j.

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

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

 

Контрольні запитання

 

1. Що означає задати транспортну мережу?

2. Як скласти граф-модель транспортної мережі?

3. Методи рішення задачі оптимізації транспортної мережі.

4. Сутність метода потенціалів

5. Алгоритм метода “Метли”.

6. Оптимізація транспортної мережі методом динамічного програмування.

 

ЛІТЕРАТУРА [1, 3]

 

ЗАНЯТТЯ 10

 

Мережне планування і управління

Мета заняття - придбати практичні навички розрахунку мережного графіку.

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

Задача. Надан мережний графік (рис. 10.1). Тривалість робіт вказана на його ланках за варіантами. Знайти часові характеристики подій і робіт.

 

 

Рис. 10.1. Мережний графік

 

Вказівки до виконання

 

Розрахувати тривалість робіт за своїм варіантом, використовуючи
рис. 10.1, де і – остання цифра залікової книжки, а j –предостання.

Розв'язання задачі виконати у такій послідовності.

Визначити ранні досягнуті строки настання подій; пізні припустимі строки звершення подій; резерви часу настання подій; ранні досягнуті строки початку та закінчення робіт; повний незалежний, приватний за ранніми строками і приватний за пізніми строками настання подій аналітично.

Аналогічні розрахунки звести до таблиці.

Встановити критичний та підкритичні шляхи в мережному графіку

Контрольні запитання

 

1. Що таке мережний графік і його елементи?

2. Що таке критичний і підкритичний шляхи?

3. Як визначаються часові характеристики подій і робот?

4. Як визначаються резерви настання подій?

5. Які бувають резерви виконання робіт? Як їх знаходять?

 

ЛІТЕРАТУРА [1, 3, 4]

 

ЗАНЯТТЯ 11

 

Рішення транспортної задачі лінійного програмування
в мережній постановці

 

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

Завдання. Скласти оптимальний план перевезень вантажів.

Задача. Надана мережа автомобільних шляхів (рис. 11.1). Довжина ланків мережі надана на рис. 11.1 по варіантам (і – остання, а j – предостання цифра номеру залікової книжки). У вершинах мережі розташовані пункти відправлення вантажу  пункти призначення  і вільні (транзитні) пункти  Наявність вантажу у відправників і потреба у вантажі споживачів надані за варіантами в табл. 11.1, 11.2. Значення визначаються за останньою цифрою номеру залікової книжки.

 

Таблиця 11.1 – Потреба у вантажі

Варіант	Споживачі							Всього
0	55	40	35	95	65	45	55	390
1	185	95	95	125	125	115	110	850
2	85	95	135	65	45	65	60	550
3	140	135	125	130	90	105	75	800
4	120	95	180	150	105	150	120	920
5	130	150	110	90	55	95	120	750
6	120	110	135	165	190	130	100	950
7	120	110	35	165	90	80	150	750
8	80	75	90	70	125	120	80	640
9	65	50	40	75	45	55	50	380

 

Таблиця 11.2 – Наявність вантажів у постачальників

Варіант	Постачальники					Всього
	А 1	А 2	А 3	А 4	А 5
0	110	70	100	50	60	390
1	190	200	160	60	240	850
2	130	150	100	80	90	550
3	50	300	200	150	100	800
4	120	100	400	200	100	920
5	100	200	150	100	200	750
6	250	110	90	300	200	950
7	180	120	150	150	150	750
8	160	130	150	110	90	640
9	90	90	80	70	50	380

 

Вказівки до виконання

 

Виконання завдання здійснюється у такій послідовності:

1. Скласти припустимий вихідний план на мережі шляхів.

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

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

 

Контрольні запитання

 

1. Алгоритм розв'язання транспортної задачі лінійного програмування на мережі.

2. Коли доцільно вирішувати транспортну задачу в мережній постановці?

3. Як визначаються допоміжні числа вершин мережі?

4. Ознака оптимальності плану перевезень при розв'язанні транспортної задачі в мережній постановці.

5. Правила знаходження контуру і перерозподіл завантажених ділянок мережі по контуру.

6. Переваги і недоліки розв'язання транспортної задачі в мережній постановці в порівнянні з матричною формою.

 

ЛІТЕРАТУРА [2]

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

 

1. Кожин А. Н. Математические методы в планировании и управлении грузовыми автомобильными перевозками. – М: Высшая школа, 1979.

2. Бобарыкин В.А., Тимошин Е.Ф. Математические методы на автотранспорте. – Л., 1969.

3. Громовой Э.П. Математические методы и модели в планировании и управлении на морском транспорте. – М.: Транспорт, 1979.

4. Пьяных С.М. Экономико-математические методы оптимального планирования работы речного транспорта. – М.: Транспорт, 1988.

5. Геронимус Б.Л. Экономико-математические методы в планировании на автомобильном транспорте. – М.: Транспорт, 1982

6. Воркут А.И. Грузовые автомобильные перевозки. – К.: Вища школа, 1986.