2015-01-30
1345
Задачи анализа относятся к случаям, когда задана структура и характеристики элементов сети, а требуется определить характеристики обслуживаемых потоков. Или, наоборот, заданы характеристики потоков, а необходимо определить потребности в каналах.
Задачи синтеза связаны с построением сети, с поиском лучших структур, алгоритмов обмена информацией. Все эти задачи относятся к классу оптимизационных, когда осуществляется поиск лучшего решения.
Процесс решения оптимизационных задач складывается из ряда этапов:
1. Изучение объекта. Надо понять исследуемый объект, разобраться в происходящих в нем процессах, выделить необходимые характеристики, взаимосвязи.
2. Описательное моделирование. Осуществляется словесная формулировка (фиксация) основных связей и зависимостей между характеристиками процесса с точки зрения оптимизационного критерия.
3. Математическое моделирование. Перевод описательной модели на формальный математический язык. Все условия записываются в виде уравнений, неравенств (системы ограничений). Любое решение этой системы называется допустимым решением. Критерий записывается в виде функции, называемой целевой. Процесс оптимизации состоит в отыскании на множестве допустимых решений максимального или минимального значения целевой функции.
4. Выбор (или создание) метода решения задачи. После того как задача записана в математической форме, ее прикладная специфика уже не интересует. Главное внимание обращается на математическую структуру.
5. Выбор или написание программы для решения задачи на ЭВМ. Подавляющая часть сетевых задач из-за большого числа переменных и зависимостей между ними могут быть решены в разумные сроки только с помощью ЭВМ. Для решения их следует составить программу, реализующую выбранный метод решения, или использовать уже готовую, «стандартную» программу из библиотеки программ, если таковые есть.
6. Решение задачи на ЭВМ. Вся необходимая информация для решения задачи вводится в память машины вместе с программой. ЭВМ производит необходимую обработку в соответствии с программой и исходными данными. Результат выдается человеку в удобной для него форме.
7. Анализ полученного решения. Анализ двух видов: 1) формальный (математический), когда проверяется соответствие полученного решения построенной математической модели, и 2) содержательный (технологический, экономический и т.п.), когда проверяется соответствие полученного решения тому объекту (процессу), который моделировался. В результате такого анализа в модель могут быть внесены изменения или уточнения.
Решение многих задач анализа сетей начинается с определения путей между узлами сети. Одним из наиболее удобных и легко поддающихся машинизации способов определения путей является построение дерева путей. Оно (дерево путей) позволяет определить все пути от одного наперед заданного узла ко всем остальным узлам сети. Перечень путей удобно записывать в виде таблицы путей.
Существуют три стандартных алгоритма решения задач отыскания кратчайшего пути: алгоритм Беллмана-Форда, алгоритм Дийкстра и алгоритм Флойда-Уоршела. Первые два алгоритма находят кратчайшие пути от данного узла-источника ко всем другим узлам (или, эквивалентно, от всех узлов к данному узлу адресату),а третий алгоритм находит кратчайшие пути от всех узлов ко всем другим узлам.
