Методические указания и контрольные задания для студентов экономических специальностей бнту




НазваниеМетодические указания и контрольные задания для студентов экономических специальностей бнту
страница7/9
Дата публикации30.06.2013
Размер0.66 Mb.
ТипМетодические указания
zadocs.ru > Математика > Методические указания
1   2   3   4   5   6   7   8   9
^

Алгоритм расстановки пометок нахождения увеличивающего пути




Шаг 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, ), где Rмножество помеченных, - множество непомеченных вершин, образует минимальный разрез; б) сток t оказался помеченным. Двигаясь от стока t к вершине, номер которой указан в ее метке и т.д., мы придем к источнику.

Алгоритм Форда – построения максимального потока в сети.
Начальный. Выбираем некоторый поток в сети G (V,U) (например xi j= 0 для всех дуг (i,j) U).

Общая итерация 1. Применяем алгоритм нахождения увеличивающего пути из источника s в сток t. Если такого пути нет, то построенный поток яв­ляется максимальным. Алгоритм заканчивает работу. Если увеличивающий путь найден, то переходим к 2.

2. В найденном увеличивающем пути обозначим через P+ множество прямых, а P - - множество обратных дуг пути и вычисляем величину 1 = (dijxij) 0 и 2 = . Полагаем q = min (1, 2). Увеличиваем поток вдоль пути P на величину , полагая
xij = xij+ , если (i ,j) P+

xij = xij , если (i, j) P- (23)

xij = xij для остальных дуг пути.
Переходим к 1.

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


Рис.1.
Найдем увеличивающий путь.

Общая итерация: Шаг 1. Источник s получает пометку (s+).

Шаг 2. Так как = 1 = 2, то вершина 1 получает метку (s+). Вер­шина 2 получает метку (s-), т.к. x21 = 1 0. Вершина 5 не может быть помечена, т.к. (дуга (s, 5) – насыщенная).

Шаг 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.

Полагаем

2S = x2S – 1 = 0, 42 = x42 –1 =0, 54 = x54 – 1 = 0, 5t = x5 t+1 = 2.

Величина суммарного потока в сети равна 3.

Общая итерация 1. Для нового потока ищем увеличивающий путь мето­дом расстановки пометок. Пометить удается только вершины s и 1. Следова­тельно, увеличивающего пути нет, и построенный поток является максималь­ным. Минимальный разрез (R,, , где R = 1; 2, = 2; 3; 4; 5; t состоит из дуг (R, ) = (1, 3); (s, 5); (s,2); (1,2) и обладает пропускной способностью

C (R, ) = d13 + dS5 = 3.

На рис.2 минимальный разрез показан пунктирной линией

Рис. 2
^ КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Задание 6. Сеть задана матрицей пропускных способ­ностей дуг (dij = 0 означает, что в сети отсутствует дуга, ведущая из вершины 1 в вершину j). Требуется по матрице D построить сеть и найти в ней максимальный поток из вершины 1 в вершину 10, опреде­лив при этом минимальный разрез.


Вариант 1


Вариант 2








Вариант 3


Вариант 4












Вариант 5


Вариант 6









Вариант 7

Вариант 8





Вариант 9

Вариант 10







^ VII. Сетевое планирование.
Основой методов сетевого планирования является сетевая модель (сете­вой график), отражающая логическую взаимосвязь работ, входящий в некото­рый комплекс, что позволяет осуществлять управление ходом выполнения этих работ.

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

Полученные данные удобно заносить в таблицу. В таблице 1 приведены данные для проекта, состоящего из девяти работ.
1   2   3   4   5   6   7   8   9

Похожие:

Методические указания и контрольные задания для студентов экономических специальностей бнту iconЗадания и методические указания к контрольной работе №2 по высшей...
Методические указания предназначены для студентов 1 курса заочного отделения экономических специальностей бнту. Они могут быть также...

Методические указания и контрольные задания для студентов экономических специальностей бнту iconЗадания и методические указания к контрольной работе №2 по высшей...
Методические указания предназначены для студентов 1 курса заочного отделения экономических специальностей бнту. Они могут быть также...

Методические указания и контрольные задания для студентов экономических специальностей бнту iconНемецкий язык методические указания и контрольные задания для студентов...
Немецкий язык : методические указания и контрольные задания для студентов 2 курса железнодорожных специальностей заочной формы обучения...

Методические указания и контрольные задания для студентов экономических специальностей бнту iconМетодические указания по выполнению контрольной работы 31 Общие указания 31
Производственные технологии : программа, методические указания и контрольные задания для студентов специальностей 1-25 01 07 – Экономика...

Методические указания и контрольные задания для студентов экономических специальностей бнту iconМетодические указания и контрольные задания для студентов специальности,...
Методические указания и контрольные задания по дисциплине Стандартизация норм точности для студентов специальности: 1- 38. 02. 01...

Методические указания и контрольные задания для студентов экономических специальностей бнту iconМетодические указания для самостоятельной работы студентов экономических...
Методические указания к изучению дисциплины “Логистика” составлены на основе требований Государственного общеобразовательного стандарта...

Методические указания и контрольные задания для студентов экономических специальностей бнту iconМетодические указания и контрольные задания для студентов специальностей...
Статистика: методические указания и контрольные задания для студентов специальностей 1-26 02 02 «Менеджмент» и 1-26 02 03 «Маркетинг»...

Методические указания и контрольные задания для студентов экономических специальностей бнту iconМетодические указания и контрольные задания по дисциплине
Методические указания и контрольные задания по дисциплине "Электротехника и электроника" для студентов спец. 37 01 06 "Техническая...

Методические указания и контрольные задания для студентов экономических специальностей бнту icon-
...

Методические указания и контрольные задания для студентов экономических специальностей бнту iconМетодические указания и тематика контрольных работ для студентов экономических специальностей
Методические указания предназначены для студентов экономических специальностей заочной формы обучения. Они составлены в соответствии...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов