Белорусский  государственный  университет

↑

Стр 1 из 11Следующая ⇒

БЕЛОРУССКИЙ  ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

ФАКУЛЬТЕТ  ПРИКЛАДНОЙ  МАТЕМАТИКИ И ИНФОРМАТИКИ

Кафедра информационных систем управления

ИССЛЕДОВАНИЕ  ОПЕРАЦИЙ В  ЗАДАЧАХ

Учебно-методическое пособие для студентов

факультета прикладной математики и информатики

В трёх частях

Часть II

СЕТЕВЫЕ ЗАДАЧИ

МИНСК

УДК 519.8 (075)

ББК 22.18

    И85

А в т о р ы  -  с о с т а в и т е л и:

А. Н. Исаченко, Л. Ф. Дробушевич

Рекомендовано ученым советом

факультета прикладной математики и информатики

6 декабря 2011 г., протокол № 3

Исследование операций в задачах: учеб.-метод. пособие для И85 студентов факультета прикладной математики и информатики.

В 3 ч. Ч. II: Сетевые задачи /  авт.-сост.: А. Н. Исаченко, Л. Ф. Дробушевич. – Минск: БГУ, 2011. – 63 с.

Излагаются основные понятия, методика, алгоритмы и методы исследования операций,  касающиеся построения сетевых моделей и решения задач на сетях.  Даются задачи для самостоятельной работы студентов.

Предназначено для студентов факультета прикладной математики и информатики.

                                                                   УДК 519.8(075)

                                                                   ББК 22.18

© БГУ, 2011

ВВЕДЕНИЕ

Сеть – это ориентированный или неориентированный граф, дугам, ребрам, вершинам которого приписаны некоторые параметры, называемые весами.

Сеть как математическая модель возникает при рассмотрении объектов или явлений, которые можно представить в виде элементов, между которыми существует связь или взаимодействие, причем наличие связи или взаимодействия является определяющим.

Примером объектов, моделируемых сетью, являются транспортные сети (наземные, водные, воздушные), коммуникационные сети, электрические схемы, проекты работ с четкой иерархией предшествования, управляющие системы, информационные системы, компьютерные вычислительные сети и так далее. При этом веса, приписываемые элементам сети, имеют физическую интерпретацию, связанную с предметной областью в которой рассматривается объект (явление).

Так при моделировании транспортных систем вес дуги может интерпретироваться как длина участка дороги, соединяющего соответствующие пункты, или его пропускная способность. Аналогично, при моделировании нефте, газо, водопроводов, вес может интерпретироваться как длина или пропускная способность участка проводящей системы. При рассмотрении систем связи веса могут указывать количество каналов между абонентами. При моделировании управления назначениями – время или эффективность выполнения исполнителем работ. При моделировании проекта выполняемых работ веса имеют значения длительностей выполнения работ.

Сетевые задачи часто встречаются в приложениях и отличаются постановкой и методами решения. Моделируемый сетью объект может допускать математические модели, содержащие целевую функцию, систему ограничений в виде равенств и неравенств. Наличие таких моделей только расширяет совокупность математических методов, привлекаемых для решения рассматриваемой задачи.

К классическим сетевым задачам можно отнести задачу об остовных деревьях, задачу о кратчайших путях, задачу о максимальном потоке в сети, задачу коммивояжера, задача о максимальном паросочетании двудольного графа, задачи сетевого планирования и управления.

Существует ряд задач, в которых сетевые модели используются как вспомогательные. Например, в задаче о назначениях алгоритм поиска максимального потока  используется в качестве одного из этапов получения решения.

 1. ЗАДАЧА О МИНИМАЛЬНОМ ОСТОВНОМ ДЕРЕВЕ НЕОРИЕНТИРОВАННОГО ГРАФА

Напомним, что дерево это ациклический связный граф. Подграф графа называется остовным, если он содержит все вершины исходного графа. Пусть дан связный неориентированный граф G(V, E), с числом вершин | V | = n, числом ребер | E | = m, и каждому его ребру e Î E приписан некоторый вес w(e). Вес подграфа G^’(V ^‘, E^’) графа G(V, E) определим как сумму весов его ребер, то есть

.

Задача о минимальном остовном дереве состоит в поиске остовного дерева исходного графа с минимальным весом.

Приведем базовые алгоритмы решения задачи. Обозначим через I_j совокупность ребер, включенное в искомое дерево на j-ой итерации алгоритма.

Алгоритм Краскала. Начальный шаг: j = 0, I₀ = Æ.

Шаг 1. Упорядочиваем ребра множества E в порядке неубывания их весов. Пусть w(e₁) ≤ w(e₂) ≤…≤w(e_m).

Шаг 2.

Шаг 3. Если | I_j+1 | = n-1, стоп. I_j+1 – совокупность ребер искомого дерева. В противном случае j := j+1, идем к шагу 2.

Алгоритм Краскала выполняет не более чем m итераций, сложность алгоритма O(m log m).

Обозначим через O_e ( I_j ) множество ребер из E \ I_j, в котором каждое ребро инцидентно с некоторым ребром из I_j . Полагаем O_e ( Æ ) = E.

Алгоритм Прима. Начальный шаг: j = 0, I₀ = Æ.

Шаг 1. Строим множество O_e ( I_j ) и упорядочиваем его ребра по неубыванию весов. Пусть O_e ( I_j ) = { } и .

Шаг 2.1. k = 1.

Шаг 2.2.

Шаг 2.3. Если I_j+1 ≠ I_j , то идем к шагу 3. В противном случае k := k + 1  и возвращаемся к шагу 2.2.

Шаг 3. Если | I_j+1 | = n-1, стоп. I_j+1 – совокупность ребер искомого дерева. В противном случае j := j+1, идем к шагу 1.

Cложность алгоритма Прима составляет O(m + n log n).

Для подграфа G^’(V ^‘, E^’) графа G( V, E ) обозначим через O_v (G^’ ) множество ребер из E \ E^’ инцидентных ровно с одной вершиной множества V ^‘. Через V( I_j ) обозначим множество вершин графа G( V, E ) инцидентных ребрам из I_j . При этом положим V( Æ ) = V.

Алгоритм Борувки. Начальный шаг: j = 0, I₀ = Æ.

Шаг 1. Упорядочиваем ребра множества E в порядке неубывания их весов.

Шаг 2. Выделяем компоненты связности  подграфа G^’(V( I_j ), I_j ), образованного ребрами I_j .

Шаг 3. Для каждого , находим первое в упорядочении, полученном на шаге 1, ребро  из . Очевидно, .

Шаг 4. Полагаем I_j+1 = I_j È { , }.

Шаг 5. Если | I_j+1 | = n-1, стоп. I_j+1 – совокупность ребер искомого дерева. В противном случае j := j+1, идем к шагу 2.

Cложность алгоритма Борувки составляет O(m log n).

Пример. Найти минимальное остовное дерево для графа, представленного на рисунке 1. Числа указывают вес ребра, в скобках указано обозначение ребра с номером соответствующим упорядочению по неубыванию.

Рис. 1.

Схема алгоритма Крускала представлена на рисунках 2.1. – 2.4.

Рис. 2.1. Первые две итерации алгоритма Краскала

Рис. 2.2. Третья и четвертая итерации алгоритма Краскала

Рис. 2.3. Пятая и шестая итерации алгоритма Краскала

Рис. 2.4. Завершающая итерация алгоритма Крускала.

Схема алгоритма Прима представлена на рисунках 3.1 – 3.7.

1(e₂)

Рис. 3.1. Первые две итерации алгоритма Прима

7(e₆)

12(e₁₀)

1(e₂)

Рис. 3.2. Третья и четвертая итерации алгоритма Прима

Рис. 3.3. Пятая и шестая итерации алгоритма Прима

Рис. 3.4. Завершающая итерация алгоритма Прима

Схема алгоритма Борувки представлена на рисунке 4.

Рис. 4. Первая и завершающая итерации алгоритма Борувки

Указанные алгоритмы Краскала, Прима и Борувки можно применять и для поиска максимального остовного дерева. Для этого необходимо заменить упорядочение по неубыванию на упорядочение по невозрастанию в соответствующих шагах алгоритмов.

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология