4.2.3. Модели сетевой оптимизации
В математически формализованной системе анализа, планирования и управления особое место занимают сетевые графики. Они позволяют выделить из всего комплекса работ наиболее важные, лежащие на критическом пути, и сосредоточить на них основные ресурсы предприятий, устанавливать взаимосвязь между различными специализированными организациями и координировать их работу. Коммуникационная сеть минимальной длины, или дерево кратчайших расстояний, — это совокупность дуг сети, имеющая минимальную суммарную длину и обеспечивающая достижение всех узлов сети.
Пример 5.
Рассмотрим задачу регионального вычислительного центра, который должен установить специальные линии связи между пятью локальными потребителями и новым центральным компьютером. Телефонная компания берется проложить новую сеть связи. Однако организация связи — дело дорогостоящее. Чтобы сократить затраты, руководство центра решило, что общая протяженность линий связи в сети должна быть минимальной. Хотя центральный компьютер может быть связан с каждым потребителем в отдельности, более экономичным было бы установить прямую связь с частью потребителей остальных связать с центральным компьютером через потребителей, которые уже получили эту связь. Определение такой системы связи минимальной длины представляет собой пример дерева кратчайших расстояний. Сеть применительно к этой задаче с различными возможными альтернативами связи и расстояний показана на рис. 4.2.
Р
40
5
2
30
50
3
40
20
40
10
30
4
30
20
1
6
40
ис.4.2.
Метод, который может быть использован для решения задачи нахождения дерева кратчайших расстояний, очень прост.
Шаг 1. Начните произвольно с любого узла и соедините его ближайшим узлом. Эти два узла теперь рассматриваются как связанные узлы, а остальные — как несвязанные узлы.
Шаг 2. Определите несвязанный узел, который наиболее близок к одному из связанных узлов. Если два или более узлов можно рассматривать как ближайшие, то выберите любой из них. Добавьте этот новый узел к связанным узлам. Повторяйте этот шаг до тех пор, пока все узлы не станут связанными.
Этот сетевой алгоритм легко реализуется, если выбирать связи непосредственно на графе сети. Обращаясь к сети связи для регионального вычислительного центра и начиная с узла 1, мы находим, что ближайшим является узел 2 с расстоянием 20. Используя жирные линии для пометки дуги, обеспечивающей соединение узлов 1 и 2, мы приходим у следующему результату, характеризующему шаг 1.( рис.4.3.)
Р
40
5
2
30
50
3
40
20
40
10
30
4
30
20
1
6
40
ис.
4.3.
На втором шаге метода находим, что несвязанный узел, ближайший к одному из связанных узлов, есть узел 4 с расстоянием 30 км от узла 1. Добавляя узел 4 к множеству связанных узлов, мы получаем следующий результат (рис. 4.4.).
Повторение шага, заключающегося в добавлении ближайшего несвязанного узла к связанному сегменту сети, дает нам решение задачи о дереве кратчайших расстояний, показанное на рис. 4.5. Повторяйте шаги метода и посмотрите, получите ли вы решение. Минимальная длина дерева представлена суммой расстояний на дугах, образующих дерево.
Р
40
5
2
30
50
3
40
20
40
10
30
4
30
20
1
6
40
ис.
4.4.
Р
40
5
2
30
50
3
40
20
40
10
30
4
30
20
1
6
40
ис.
4.5.
В данном случае сумма расстояний в сети регионального вычислительного центра составляет 110 км. Заметим, что хотя дуги сети вычислительного центра измерялись в километрах, другие сетевые модели могут характеризоваться совсем другими показателями — затратами, временем и т.д. В таких случаях алгоритм дерева кратчайших расстояний будет приводить к оптимальному решению (минимальные затраты, минимальное время и т.д.) применительно к рассматриваемому критерию.