УДК 519.17
У. Медетбекова, ,
Казахский национальный технический университет имени
Казахстан, г. Алматы
РАЗРАБОТКА ПРОГРАММНОГО КОМПЛЕКСА «ПОИСК МАКСИМАЛЬНОГО ПОТОКА МЕТОДОМ ФОРДА-ФАЛКЕРСОНА»
Аннотация. Программное решение одной из задач оптимизации – задачи о максимальном потоке в сети. Задача занимает центральное место в теории сетей применительно к организации работы транспорта, компьютерных сетей, систем нефтепроводов. В данной статье рассматривается нахождение максимального потока с помощью алгоритма Форда-Фалкерсона, разработан программный комплекс.
Ключевые слова. Алгоритм Форда-Фалкерсона, максимальный поток, сеть.
Преимущества цепей поставок в логистических системах определяются потенциалом возможности приращения ценности реализуемого продукта для конечного потребителя. В этой связи стратегические приоритеты развития сети распределения играют чрезвычайно большое значение. Популярный пропорциональный метод распределения товара в сети, зачастую, не имеет возможности привести в соответствие располагаемые мощности поставщика, транспортной организации, центра распределения и ценностные стратегические приоритеты развития сети. Предлагаемый алгоритм может быть использован как инструмент интеграции усилия звеньев сети распределения, учитывающий названные современные особенности процесса управления логистическими системами [1].
Алгоритм Форда – Фалкерсона нахождения максимального потока в сети
Теорема Форда-Фалкерсона 1 (о максимальном потоке и минимальном разрезе).
В любой сети существует максимальный поток. Величина максимального потока равна пропускной способности минимального разреза [2].
Теорема Форда-Фалкерсона 2.
Поток, вычисленный с помощью алгоритма Форда-Фалкерсона имеет максимальную величину, а разрез (X, X), где X-множество вершин, помеченных при последнем помечивании, имеет минимальную пропускную способность.
Описание алгоритма
Пусть изначально в сети имеется поток f (допустим с нулевыми значениями на всех дугах).
Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети состоит из двух процедур:
1) Процедура помечивания вершин
2) Процедура изменения потока
1) Процедура помечивания вершин.
Обработка i-й вершины с пометкой (x, e) заключается в том, что из вершины i помечаются смежные непомеченные вершины по следующему правилу:
- если дуга направлена из i в j и поток по этой дуге (fij) меньше пропускной способности дуги (cij), то вершине j присваивается метка (i+,min(e, cij-fij))
- если дуга направлена из j в i и поток по этой дуге (fji) больше нуля, то вершине j присваивается метка (i-,min(e, fji))
Эта процедура всегда начинается с помечивания и обработки истока. Он помечается особой меткой (-,). Затем обрабатываются другие помеченные вершины (после обработки истока пометятся вершины, смежные с ним) и т. д.
Процесс помечивания заканчивается в двух случаях:
1) Ни одну вершину больше нельзя пометить, но сток не помечен. Это значит, что найденный поток - максимальный и алгоритм останавливается.
2) Помечается сток. В этом случае производится изменение потока.
2) Процедура изменения потока.
Если сток получил метку (k+,d), то потоки будут изменяться на величину d следующим образом:
- если мы находимся в вершине j с меткой (i+,x), то прибавляем d к fij и переходим в вершину i.
- если мы находимся в вершине j с меткой (i-,x), то вычитаем d из fij и переходим в вершину i.
Изменение потока начинается от стока и продолжается до достижения истока. После этого все метки стираются и заново выполняется процедура помечивания вершин.
Этот процесс продолжается до тех пор, пока не будет найден максимальный поток (ни одну вершину больше нельзя пометить, но сток не помечен) [3].
Разработанный программный комплекс на основе алгоритма Форда – Фалкерсона нахождения максимального потока в сети состоит из разделов «Визуальный редактор», «Решение», «Граф». При запуске программы открывается окно «Поиск максимального потока методом Форда - Фалкерсона» (рисунок 1).
Рисунок 1. Вид главного окна «Поиск максимального потока методом Форда-Фалкерсона»
В верхней части окна созданы меню «Файл» и «Справка». Меню «Файл» состоит из разделов «Новый граф», «Открыть», «Сохранить» и «Выход», они используются для создания нового графа, открытия уже существующего графа, сохранения построенного графа и выхода из программы.
Раздел «Визуальный редактор» включает кнопки «Разместить вершину», «Добавить ребро», «Удалить вершину». С помощью этих кнопок можно осуществить следующие действия: разместить вершину, добавить ребро, удалить вершину.
Вид раздела «Визуальный редактор» показан на рисунке 2.
Рисунок 2. Вид раздела «Визуальный редактор»
В разделе «Решение» существует кнопка «Найти максимальный поток». Эта кнопка позволяет вычислить максимальный поток. Перед нажатием кнопку «Найти максимальный поток» нужно задать число вершин и заполнить матрицу смежности вершин. А также в этом разделе можно задать значения течение потока, то есть из какой точки в какую точку течет поток (рисунок 3).
Рисунок 3. Общий вид раздела «Решение»
В левой стороне раздела «Решение» находится кнопка, которая позволяет задать чило вершин. Внизу этой кнопки есть кнопки «Загрузить граф из файла» и «Сохранить граф в файл» (рисунок 4).
Рисунок 4. Вид окна, которая позволяет задать число вершин
В середине находится окно, в которое строится графы. Здесь можно построить, удалить вершины и ребра графа (рисунок 5).
Рисунок 5. Вид окна, в которое строится графы
Раздел «Граф» состоит из вкладок «Матрица смежности вершин», «Дополнительно». В вкладка «Дополнительно» есть кнопки «Удалить все ребра», «Обновить изображение», «Распределить равномерно», «Распределить без наложений» (рисунок 6).
Рисунок 6. Вид раздела «Граф»
ЛИТЕРАТУРА
1 Тулембаева . Учебное пособие. Издатмаркет 6 2004 Логистика: Учебник / Под ред. . 2-е изд., перераб. и доп. - М.: Инфра • М, 2000.
2 Неруш : Учебник для вузов. 2-е изд., перераб. и доп.- М.: ЮНИТИ: ДАНА, 1998.
3 Логистика: Учебное пособие/Под ред. . — М.: ИНФРА-М, 1997.
REFERENCES
1 Тulembayeva А. N. Logistic. Train aid. 2004 Logistic: Textbook / Under red. B. А. Аnikina. 2th publ., - М.: Infra is M, 2000.
2 Nerush U. М. Logistic: Textbook for institutions of higher learning. 2th publ., - М.: Uniti: Dana, 1998.
3 Logistic: train/aid Under red. B. А. Anikina. - М.: Infra-m, 1997.
Ұ. Медетбекова, А. І. Наурызбаева, Б. А. Төлегенова
«Форд-Фалкерсон әдісімен ең үлкен ағынды табу» бағдарламалық кешенін құру
Түйіндеме. Мақалада берілген есепті Форд-Фалкерсон әдісімен ең үлкен ағынды табудың бағдарламалық кешенін құру қарастырылады. Сонымен қатар құрылған программа графтармен орындалатын кез келген есептеулер жүргізуге мүмкіндік береді.
Түйін сөздер: Форд-Фалкерсон алгоритмі, ең үлкен ағын, желі.
U. Мedetbekova, А. І. Nauryzbayeva, B. А. Тulegenova
Development of programmatic complex "search of maximal stream method of Ford-Falkerson"
Abstract. A programmatic decision of one of tasks of optimization is tasks about a maximal stream in a network. A task occupies a central place in the theory of networks as it applies to organization of work of transport, computer networks, systems of oil pipelines. In this article, being of maximal stream is examined by means of algorithm of Ford-Falkerson, a programmatic complex is worked out.
Keywords. Algorithm of Ford-Falkerson, maximal stream, network.
Сведения об авторах:
1) У. Медетбекова студентка 4-курса специальности 5В070300 - Информационные системы, Казахский национальный технический университет имени , *****@***ru,
2) , старший преподаватель кафедры ИТ, Казахский национальный технический университет имени .
3) , старший преподаватель кафедры ИТ, Казахский национальный технический университет имени .
