Файл: И.А. Кузнецов Сетевые модели. Методические указания к практическим занятиям.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 10.06.2024
Просмотров: 40
Скачиваний: 0
|
22 |
|
|
|
|
6 - 7 |
|
60 |
7 - 8 |
|
70 |
7 - 10 |
|
85 |
8 - 9 |
|
50 |
8 - 10 |
|
50 |
9 - 10 |
|
70 |
2-й шаг. По тому же принципу отыскиваем следующую цепь. Это цепь 11 - 1 - 2 - 5 - 8 - 10 - 9 (пропускная способность - 30 единиц, стоимость пересылки одной единицы - 22). Дуга (2 - 5) переходит во множество N. Остается переслать 20 единиц потока.
3-й шаг. Ищем вторую увеличивающую цепь. Ею оказывается цепь 11 - 1 - 2 - 3 - 4 - 9. По ней возможно переслать оставшиеся 20 единиц потока. Стоимость пересылки одной единицы по этой цепи - 23.
Общая стоимость пересылки потока по сети составляет Р=17• 50+30• 22+20• 23=1970 (стоимостных единиц).
Поток минимальной стоимости изображен на рис. 11. Величины потока (суммарные) в каждой дуге указаны курсивом. Цифры в скобках - резервы пропускных способностей дуг.
Следует заметить, что применение данного алгоритма невозможно, когда на потоки в дугах накладываются ограничения снизу, или когда стоимости, приписанные дугам, отрицательны.
23
СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
1. Вагнер Г. Основы исследования операций. - М.: Мир, 1972. - Т.
1. - 336 с.
2.Кристофидес Н. Теория графов. Алгоритмический подход. - M.:
Мир, 1978. - 432 с.
3.Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981.
4.Оре О. Теория графов. - М.: Мир, 1975.
5.Таха Х. Введение в исследование операций. В 2-х кн. - М.: Мир,
1985. - Кн. 1. - 479 с.; Кн. 2. - 496 с.
6.Форд Л.Р. Потоки в сетях/ Л.Р. Форд, Д.Р. Фалкерсон - М.: Мир,
1966. - 276 с.
7.Ху Т. Целочисленное программирование и потоки в сетях. -М.:
Мир, 1974. - 419 с.
24
СОДЕРЖАНИЕ
Введение .......……………………………………………………....... 1 1. Практическое занятие № 1. Редукция графа
транспортной сети …………………………...…………..…....... 2
2.Практическое занятие № 2. Минимизация сети .………........... 6
3.Практическое занятие № 3. Задача о нахождении
наиболее надежного маршрута ………………………............. 10 4. Практическое занятие № 4. Задача о максимальном
потоке ..…….……………………………………………........... 13 5. Практическое занятие № 5. Задача о потоке
минимальной стоимости ...……………………………............ 18
Список рекомендуемой литературы ........…..………………......... 24
25
Составители Игорь Алексеевич Кузнецов
Андрей Валентинович Косолапов Алексей Юрьевич Тюрин
СЕТЕВЫЕ МОДЕЛИ
Методические указания к практическим занятиям по курсу “Теоретические основы организации и функционирования транспортных систем” для студентов направления 552100 “Эксплуатация транспортных средств”
Редактор Е. Л. Наркевич
ЛР № 020313 от 23.12.96
Подписано в печать 05.06.2000. Формат 60×84/16. Уч.-изд. л. 1,5. Бумага офсетная.
Отпечатано на ризографе. Тираж 100 экз. Заказ
Кузбасский государственный технический университет. 650026, Кемерово, ул. Весенняя, 28.
Типография Кузбасского государственного технического университета. 650099, Кемерово, ул. Д. Бедного, 4а.