Мета заняття - набути практичних навичок щодо визначення найкоротших відстаней між вершинами транспортної мережі.,
Завдання. Скласти матрицю найкоротших відстаней між вершинами транспортної мережі.
Задача. Надана транспортна мережа. Відстані між вершинами наведені на рис. 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.