Алгоритмы топологической оптимизации транспортных сетей.

Презентация:



Advertisements
Похожие презентации
y = f(x) -5,3 9 1) D(f) = [-5,3; 9] 4 -2,7 2) E(f) = [-2,7; 4] ) f(x) = 0, x 1 = -5, x 2 = -1, x 3 = 7. 1,8 3) f(0) = 1,8. нули функции.
Advertisements

Графы Граф состоит из вершин, связанных линиями - рёбрами. Вершины графа изображаются кругами, овалами, точками, прямоугольниками и т. д. Объекты представляются.
Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.
«ДОБАВЛЕНИЕ И УДАЛЕНИЕ УЧРЕЖДЕНИЙ» УМИПЦ Омутнинского РУО 2009 г.
Найди ошибку. Рисунок (а) Область определения функции Область значения функции Точка пересечения с осью ох Наименьшее значение функции Функция возрастает.
Исследование функций Применение производной к исследованию функций.
1 Исследование алгоритмов решения задачи k коммивояжеров Научный руководитель, проф., д.т.н. Исполнитель, аспирант Ю.Л. Костюк М.С. Пожидаев Томский государственный.
Санкт-Петербургский колледж Информационных технологий Студенческое научное общество «Шаг в будущее» 7-я итоговая студенческая научно-практическая конференция.
Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда.
Графы Граф – совокупность точек и линий, в которой каждая линия соединяет две точки. Точки – вершины графа Линии – рёбра графа Вершины, соединенные ребром,
День знакомства. Идеальная пара.
x y y x Если функция возрастает, то производная положительна Если функция убывает, то производная отрицательна.
1. Функция обратимая – каждое своё значение принимает в единственной точке области определения. 2. Обратная функция – её значения равны значению аргумента.
Задача коммивояжера. Задача коммивояжера: имеется n городов, задана матрица расстояний между городами. Коммивояжер должен побывать в каждом городе только.
Функция y=cosx. Свойства функции y=cosx x0 y10,90,70,50-0,5-0,7-0,9 Область определения – все действительные числа Область значений – [-1; 1] Функция.
ИССЛЕДОВАНИЕ ФУНКЦИЙ НА МОНОТОННОСТЬ.. Функцию y = f(x) называют возрастающей на множестве X D(f), если для любых двух точек x 1 и x 2 множества X, таких,
Дерево это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами.
Урок алгебры в 9 классе. Тема: «Графический способ решения систем уравнений».
Преобразование графиков функций. Задачи урока Повторить правила преобразований:
Возрастание и убываниефункций Слушаю – забываю. Смотрю – запоминаю. Делаю – понимаю. Конфуций.
Транксрипт:

Алгоритмы топологической оптимизации транспортных сетей

Критерии: F - сумма длин кратчайших путей между всеми парами узлов S - стоимость сети m - количество ребер Методы решения: Многокритериальная оптимизация - решение по Нэшу - евклидово расстояние - свертка критериев Алгоритмы добавления A, B, C, D, R, Q

Решение по Нэшу Минимизация функции E=(F-F*)(S-S*) F* - значение критерия F на полном графе S* - стоимость минимального связывающего дерева Удаляем ребро, при удалении которого максимально уменьшается значение критерия E

Решение по Нэшу n=10 m=35

Метод идеальной точки Минимизация функции (F*, S*) – «идеальная точка» (F, S) – точка-текущие значения критериев Удаляем ребро, при удалении которого максимально уменьшается расстояние до идеальной точки

Метод идеальной точки F возрастает на 1-5% S убывает на 60-70% m

Свертка критериев Минимизация функции Удаляем ребро, при удалении которого максимально уменьшается значение критерия Q Изменение изменяет положение минимума Q

Свертка критериев

F возрастает на 10% S уменьшается на 90% «хорошая топология»

Алгоритмы добавления А. Добавляем самое короткое ребро. В. Добавляем ребро, при добавлении которого приращение F будет максимально. C. Добавляем ребро, при добавлении которого отношение будет максимально. D. Добавляем ребро, которое максимально уменьшается значение критерия E. R. Добавляем ребро, которое максимально уменьшает расстояния до (F*, S*). Q. Добавляем ребро, которое максимально уменьшается значение критерия Q.

Алгоритмы добавления