Численный пример, реализующий работу алгоритма
Строим остаточную сеть, как показано на рис. 2. Так как остаточная сеть на первом шаге совпадает с исходным «растянутым во времени» графом, находим в ней путь минимальной стоимости от к по алгоритму Форда в. Получаем путь стоимости условных единиц и передаем по нему общей стоимости единиц потока, что показано на рис. 3. Рассмотрим пример, иллюстрирующий реализацию описанного алгоритма. Пусть… Читать ещё >
Численный пример, реализующий работу алгоритма (реферат, курсовая, диплом, контрольная)
Рассмотрим пример, иллюстрирующий реализацию описанного алгоритма. Пусть транспортная сеть, являющаяся частью железнодорожной карты, представлена в форме нечеткой транспортной сети, полученной из ГИС «Object Land» [9], как показано на рис. 1. Понятие «ГИС» представлено в [10].
Вершина представляет собой источник, вершина — сток. Нечеткие пропускные способности и стоимости, а также параметры времени прохождения потока по дугам, зависящие от момента отправления потока представлены в виде таблиц № 1, 2 и 3. Необходимо найти минимальную стоимость перевозки максимального количества единиц потока. Правила оперирования с нечеткими треугольными числами представлены в [6].
Рис. 1. — Исходный динамический граф
Строим остаточную сеть, как показано на рис. 2. Так как остаточная сеть на первом шаге совпадает с исходным «растянутым во времени» графом, находим в ней путь минимальной стоимости от к по алгоритму Форда в. Получаем путь стоимости условных единиц и передаем по нему общей стоимости единиц потока, что показано на рис. 3.
Таблица № 1.
Нечеткие пропускные способности, зависящие от момента отправления потока.
Момент времени. | Нечеткие пропускные способности по дугам графа, ед. | ||||||
Таблица № 2.
Нечеткие стоимости, зависящие от момента отправления потока.
Момент времени. | Нечеткие стоимости по дугам граф, условные ед. | ||||||
Переходим к построению «растянутого во времени графа», как на рис. 2. Строим остаточную сеть исходя из нового значения потока по дугам графа, как показано на рис. 4. Находим путь минимальной стоимости в построенной остаточной сети от к по алгоритму Форда. Получаем путь стоимости условных единиц и передаем по нему единиц потока общей стоимости, тогда поток переходит в (рис.5).
Таблица № 3.
Параметры времени прохождения потока по дугам.
Момент времени. | Время прохождения потока по дугам графа, ед. времени. | ||||||
Рис. 2. — - «растянутый во времени» вариант графа
Рис. 3. — Граф с потоком единиц
Рис. 4. — Остаточная сеть после нахождения потока
Рис. 5. — Граф с новым значением потока
Строим остаточную сеть исходя из нового значения потока по дугам графа, как показано на рис. 6. Так как в данной сети не существует увеличивающего пути, найден максимальный поток минимальной стоимости.
Рис. 6. — Остаточная сеть после нахождения потока
Отбрасывая искусственные вершины и дуги с потоком, соединяющие их с другими вершинами, получаем максимальный поток единиц минимальной стоимости условных единиц. Переходя к динамическому графу от «растянутого во времени» статического графа, можно сделать вывод, что максимальный поток за 3 интервала времени равен потоку, выходящему из пар «вершина-время» и и входящему в пару «вершина-время», т. е. единиц, которые определяются путем, который отправляется в момент времени и прибывает в сток в момент времени и путем, который отправляется в момент времени и прибывает в сток в момент времени .