Скачать 0.66 Mb.
|
^ Шаг 1. Источник s получает метку (s+). Шаг 2. Для всех дуг (s,j) выходящих из вершины s, соответствующие вершины j получают метку s+, если xsj dsj. Для дуг (i,s), входящих в вершину s, соответствующие вершины i получают метку (s-), если xis 0. Шаг k. Просматриваем все вершины, помеченные на (k-1)- ом шаге. Для каждой такой вершины k, соответствующие им вершины j, для которых xki dkj, получают метку (k+), для всех дуг (i,k), входящих в вершину k, соответствующих им вершины i , для которых xik 0, получают метку (k -). Алгоритм заканчивает работу одним из двух состояний: а) после некоторого шага мы не можем пометить ни одной вершины, и сток t остался непомеченным. Это означает, что имеющийся поток является максимальным, а (R, ![]() ![]() Алгоритм Форда – построения максимального потока в сети. Начальный. Выбираем некоторый поток ![]() Общая итерация 1. Применяем алгоритм нахождения увеличивающего пути из источника s в сток t. Если такого пути нет, то построенный поток является максимальным. Алгоритм заканчивает работу. Если увеличивающий путь найден, то переходим к 2. 2. В найденном увеличивающем пути обозначим через P+ множество прямых, а P - - множество обратных дуг пути и вычисляем величину ![]() ![]() ![]() ![]() ![]() ![]() ![]() xij’ = xij+ ![]() xij’ = xij – ![]() xij’ = xij для остальных дуг пути. Переходим к 1. Рассмотрим пример. На рис.1. изображена сеть. Первое число в скобках указывает пропускную способность дуги, второе – дуговой поток. ![]() Рис.1. Найдем увеличивающий путь. Общая итерация: Шаг 1. Источник s получает пометку (s+). Шаг 2. Так как ![]() ![]() ![]() Шаг 3. Соседними вершинами с вновь помеченными являются вершины 3 и 4. Вершина 3 помечена не может быть, так как x13 = d13..Вершина 4 получает пометку (2-), т.к. х42 = 1 0. Шаг 4. Соседними с помеченной вершиной 4 являются вершины t и 5. Вершина t помечена не может быть, т.к. хt4 = 0. Вершина 5 получает пометку (4-), т.к. x54=10. Шаг 5. Помечаем вершину t с меткой (5+), x51=1 < d51=3. Увеличивающий путь: s – 2 – 4 – 5 - t , причем на этом пути дуга (5, t) является прямой, а дуги (2, s); (4, 2); (5, 4) обратными. Увеличим поток вдоль этого пути по формулам (23). Находим 1 ![]() 2 = ![]() т.е. = min( 1, 2) = 1. Полагаем ![]() ![]() ![]() ![]() Величина суммарного потока в сети равна 3. Общая итерация 1. Для нового потока ищем увеличивающий путь методом расстановки пометок. Пометить удается только вершины s и 1. Следовательно, увеличивающего пути нет, и построенный поток является максимальным. Минимальный разрез (R,, ![]() ![]() ![]() C (R, ![]() На рис.2 минимальный разрез показан пунктирной линией ![]() Рис. 2 ^ Задание 6. Сеть задана матрицей ![]()
^ . Сетевое планирование. Основой методов сетевого планирования является сетевая модель (сетевой график), отражающая логическую взаимосвязь работ, входящий в некоторый комплекс, что позволяет осуществлять управление ходом выполнения этих работ. Для построения сетевой модели необходимо, прежде всего, разбить весь комплекс на отдельные работы или операции и составить очередность выполнения этих работ. Для этого составляется список работ, которые непосредственно предшествуют каждой работе, а так же планируется время, необходимое для их выполнения. Полученные данные удобно заносить в таблицу. В таблице 1 приведены данные для проекта, состоящего из девяти работ. |
![]() | Методические указания предназначены для студентов 1 курса заочного отделения экономических специальностей бнту. Они могут быть также... | ![]() | Методические указания предназначены для студентов 1 курса заочного отделения экономических специальностей бнту. Они могут быть также... |
![]() | Немецкий язык : методические указания и контрольные задания для студентов 2 курса железнодорожных специальностей заочной формы обучения... | ![]() | Производственные технологии : программа, методические указания и контрольные задания для студентов специальностей 1-25 01 07 – Экономика... |
![]() | Методические указания и контрольные задания по дисциплине Стандартизация норм точности для студентов специальности: 1- 38. 02. 01... | ![]() | Методические указания к изучению дисциплины “Логистика” составлены на основе требований Государственного общеобразовательного стандарта... |
![]() | Статистика: методические указания и контрольные задания для студентов специальностей 1-26 02 02 «Менеджмент» и 1-26 02 03 «Маркетинг»... | ![]() | Методические указания и контрольные задания по дисциплине "Электротехника и электроника" для студентов спец. 37 01 06 "Техническая... |
![]() | ... | ![]() | Методические указания предназначены для студентов экономических специальностей заочной формы обучения. Они составлены в соответствии... |