- •230105 «Программное обеспечение вычислительной техники и
- •Зам. Директора по ур
- •Содержание
- •Введение
- •1 Общие положения
- •2. Тематика заданий на курсовую работу
- •3. Выполнение курсовой работы
- •4 Содержание разделов курсовой работы
- •6 Список рекомендуемой литературы, при выполнении задания курсовой работы
- •Приложение а Методика решения злп симплекс-методом
- •5 Общие требования к оформлению пояснительной записки
- •Проверяем выполнение критерия оптимальности при решении задачи на максимум. Наличие в последней стороне отрицательных коэффициентов говорит о том, что решение не оптимально.
- •Приложение б Методика решения транспортной задачи методом потенциалов
- •Алгоритм метода потенциалов.
- •Приложение в Методика решения задачи методом искусственного базиса
- •Первая итерация
- •Вторая итерация
- •Приложение г Методика нахождения максимального потока в графе по алгоритму Форда-Фалкерсона
- •Заключительный шаг
- •Приложение д Методика решения задачи о коммивояжере
- •Приложение а
- •Краткое описание разделов примера курсовой работы
- •Результаты тестирования программы
Приложение г Методика нахождения максимального потока в графе по алгоритму Форда-Фалкерсона
Предварительный шаг.
Записываем пропускные способности дуг сети в таблицу размерности (n+1)x(n+1), где n+1 – количество вершин сети G(E,e). Если пропускная способность дуги (Ei, Ej) больше нуля, а симметричной ей дуги (Ej, Ei) равна нулю, то в клетку (i,j) заносим bij , а в клетку (j,i) – нуль; если bij=bji=0, то клетки (i,j) (j,i) не заполняем
-
Находим по таблице путь из E0 в En с пропускной способностью больше нуля. Для этого столбец, соответствующий вершине E0 помечаем знаком *. Отыскиваем в E0 –й строке элементы b0j>0 и столбцы, в которых они находятся, помечаем сверху номером просматриваемой строки (цифрой 0). В результате окажутся выделенными все дуги (E0, Ej) с положительной пропускной способностью. Эти дуги могут служить первыми дугами пути из E0 в En.
Далее просматриваем те строки, номера которых совпадают с номерами помеченных столбцов. В каждой такой строе, например Ei-й отыскиваем элементы bij больше нуля находящиеся в непомеченных столбцах, и помечаем эти столбцы номером просматриваемой сроки. Таким образом, окажутся выделенными дуги, которые могут служить вторыми дугами путей из E0 в En
Продолжаем аналогичный просмотр строк, номера которых совпадают с номерами помеченных столбцов, до тех пор, пока:
-
либо не будет помечен столбец En (сток). Это означает, что удалось выделить путь с пропускной способностью больше нуля из E0 в En. В этом случае искомый путь находим, используя пометки столбцов. Пусть последняя вершина пути En помечена номером k. По этой метке находим предшествующую вершину Ek (при просмотре Ek был помечен столбец En, и дуга (Ek, En) – последняя в искомом пути). Элемент bkn>0, стоящий на пересечении Ek-й строки и En-го столбца, отмечаем знаком минус (получим b-kn ), а симметричный ему элемент bnk , находящийся на пересечении En –й строки и – Ek го столбца ,- знаком плюс (получим b+nk ). Так как просматривалась Ek- я строка, то перед этим был помечен, например, номером r , Ek- й столбец. Поэтому двигаясь от элемента b+nk по Ek-му столбцу до r-й строки (дуга (Er, Ek) предшествует дуге (Ek, En)) и отмечаем brk знаком минус, bkr – знаком плюс. Продолжаем этот процесс до тех пор, пока не придем к E0-й строке и не отметим знаком минус элемент этой строки и знаком плюс – симметричный ему элемент. Переходим к п. 2.
-
Либо нельзя будет пометить новые столбцы ( в просматриваемых строках не окажется положительных элементов, расположенных в непомеченных столбцах). В этом случае отсутствует путь из E0 в En, проходящий по дугам с положительной пропускной способностью и общий повторяющийся шаг законен
-
Находим пропускную способность найденного пути , т.е. максимальное количество вещества, которое можно переместить из E0 в En по пути в единицу времени. Пропускная способность пути равна наименьшей из пропускных способностей дуг, входящих в этот путь, т.е.
.
-
Определяем остаточные пропускные способности дуг найденного пути и симметричных к ним. Для этого из элементов таблицы b-il вычитаем , а к элементам b+il прибавляем . В результате выполнения этого действия получим новую таблицу, аналогичную исходной, но с измененными пропускными способностями. Перейти к п.1, который применяем до тех пор, пока не получим окончательную таблицу, в которой нет ни одного пути из E0 в En с пропускной способностью больше нуля
