Оптимизация сетевых моделей презентация
Содержание
- 2. Сети: Сети: Транспортные, электрические, коммуникационные Сетевое представление:
- 3. Пример: Пример: Парк Кирова предназначен для экскурсий и пикников.
- 5. Администрация парка сталкивается с тремя проблемами: Администрация парка сталкивается с тремя
- 6. Сеть = точки, соединенные линиями. Сеть = точки, соединенные линиями.
- 7. Ориентированный путь= Ориентированный путь= Последовательность дуг из узла i
- 8. (A B C E)= ориентированный путь (поток к E допустим). (B
- 9. Два узла = связаны, если сеть содержит по крайней мере один
- 10. Пропускная способность дуги = максимальное значение потока на ориентированной дуге.
- 11. Пример связующего дерева Пример связующего дерева
- 12. ЗАДАЧА НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ В неориентированной и связанной сети с двумя
- 13. Алгоритм нахождения кратчайшего пути: Алгоритм нахождения кратчайшего пути: Цель n-ной итерации:
- 14. Кандидаты для n-го ближайшего узла: Каждый решенный узел непосредственно соединенный звеном
- 15. Решение задачи кратчайшего пути на примере о парке Кирова: Администрации парка
- 16. Tретья колонка (кандидаты на n-й узел) (нерешенные узлы с кратчайшим связующим
- 18. Ввод для n-ной итерации: даны 5-й и 6-й столбцы для предыдущих
- 19. ЗАДАЧА МИНИМАЛЬНОГО СВЯЗУЮЩЕГО ДЕРЕВА Задача минимального связующего дерева имеет некоторое сходство
- 20. Минимальное связующее дерево: Минимальное связующее дерево: 1. Даны узлы
- 21. Для сети с n узлами требуется только (n - 1) звено
- 22. Звенья в (b) охватывают сеть (т.е., сеть связана), но это не
- 23. Применение: Применение: 1. Проектирование телекоммуникационных сетей (волоконно-оптические сети, компьютерные сети, выделенные
- 24. Связующее дерево для парка Кирова – только (с) – связующее дерево
- 25. Первый этап: выбор самого короткого звена к другому узлу, не думая
- 26. Алгоритм минимального связующего дерева : 1. Произвольно выбираем любой узел, соединяем
- 27. Применение минимального связующего дерева на примере парка Кирова: Руководство должно определить,
- 28. Все узлы теперь связаны, так что это решение является оптимальным. Общая
- 36. ЗАДАЧА МАКСИМАЛЬНОГО ПОТОКА Третьей задачей, стоящей перед администрацией парка в пик
- 37. С учетом ограничений, одним из допустимых решений является отправка 7 трамваев
- 38. 1. Поток через ориентированные и связанные сети начинается в исходном узле
- 40. Применение: 1. Увеличить поток дистрибьюторской сети компании от своих заводов до
- 41. Для некоторых приложений, потоки сети начинаются в нескольких узлах и заканчиваются
- 42. Фиктивный источник = в узле начинается поток, который на самом деле
- 43. Алгоритм: Задача о максимальном потоке = задача линейного программирования, решается симплекс-методом.
- 44. Число дуг рядом с узлом дает остаточную пропускную способность для потока
- 45. Минимальная остаточная пропускная способность = остаточная пропускная способность добавляемого пути(она представляет
- 46. Алгоритм нахождения увеличивающего пути для задачи максимального потока: Алгоритм нахождения увеличивающего
- 47. При выполнении шага 1 часто будет присутствовать число альтернативных увеличивающих путей,
- 48. Применение алгоритма для задачи максимального потока парка Применение алгоритма для задачи
- 51. Итерация 2: Назначим поток 3 для увеличивающего пути O A D
- 53. Итерация 5: Назначим поток 1 для увеличивающего пути O C E
- 56. Текущая модель потоков: определяется Текущая модель потоков: определяется - Накопленными заданными
- 57. Нахождение увеличивающего пути: Нахождение увеличивающего пути: Определяем узлы, которые могут быть
- 58. Величина разреза = сумма пропускных способностей разрезанных ребер (в заданном направлении).
- 61. Скачать презентацию
Слайды и текст этой презентации