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

^ Алгоритм расстановки пометок нахождения увеличивающего пути Шаг 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 = (dij – xij)  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=10. Шаг 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 приведены данные для проекта, состоящего из девяти работ.

Похожие:

	Задания и методические указания к контрольной работе №2 по высшей... Методические указания предназначены для студентов 1 курса заочного отделения экономических специальностей бнту. Они могут быть также...		Задания и методические указания к контрольной работе №2 по высшей... Методические указания предназначены для студентов 1 курса заочного отделения экономических специальностей бнту. Они могут быть также...
	Немецкий язык методические указания и контрольные задания для студентов... Немецкий язык : методические указания и контрольные задания для студентов 2 курса железнодорожных специальностей заочной формы обучения...		Методические указания по выполнению контрольной работы 31 Общие указания 31 Производственные технологии : программа, методические указания и контрольные задания для студентов специальностей 1-25 01 07 – Экономика...
	Методические указания и контрольные задания для студентов специальности,... Методические указания и контрольные задания по дисциплине Стандартизация норм точности для студентов специальности: 1- 38. 02. 01...		Методические указания для самостоятельной работы студентов экономических... Методические указания к изучению дисциплины “Логистика” составлены на основе требований Государственного общеобразовательного стандарта...
	Методические указания и контрольные задания для студентов специальностей... Статистика: методические указания и контрольные задания для студентов специальностей 1-26 02 02 «Менеджмент» и 1-26 02 03 «Маркетинг»...		Методические указания и контрольные задания по дисциплине Методические указания и контрольные задания по дисциплине "Электротехника и электроника" для студентов спец. 37 01 06 "Техническая...
	- ...		Методические указания и тематика контрольных работ для студентов экономических специальностей Методические указания предназначены для студентов экономических специальностей заочной формы обучения. Они составлены в соответствии...