Построение экономической модели при помощи графов

Современную экономическую теорию невозможно представить без различных графовых алгоритмов. Различные применения графовых алгоритмов связано с тем, что графы являются простым объяснением сложных ситуаций. И это преимущество становится еще более ощутимо при правильной визуализации графа. Теория графов превращается в средство, которое необходимо для применения компьютеров во многих прикладных областях. Считается, что родоначальником теории графов был Леонард Эйлер. В 1736 году он предложил знаменитую задачу о семи Кенигсбергских мостах. Впоследствии эта задача стала классической в теории графов. Теория графов применяется в различных областях, таких как:

• 1.   Химия

• 2.   Экономика

• 3.   Информатика

• 4.   Программирование

• 5.   Социология

Теория графов много раз переоткрывалась разными учеными для различных задач. В том числе задача о трех мостах и трех колодцах, задача о Кенигсбергских мостах, задача о четырех красках и многие другие.

В экономике чаще всего используются два вида графов: дерево и сеть.

Дерево представляет собой связный граф без циклов, имеющий исходную вершину и крайние вершины(листья); пути от исходной вершины к крайним вершинам называются ветвями.

Сеть — это ориентированный конечный связный граф, имеющий начальную вершину t(источник) и конечную вершину s(сток). Таким образом, сетевая модель может представлять собой граф вида «сеть».

В экономических исследованиях сетевые модели возникают при моделировании экономических процессов методами сетевого планирования и управления (СПУ).

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

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

Задачу нахождения максимальной пропускной способности сети впервые сформулировал Джордж Данциг в 1951 году. Первый отчет «Максимальный поток в сети» датируется 19 ноября 1954 года. Авторы отчета – Форд и Фалкерсон, доказали теорему о максимальной пропускной способности потока и минимальном разрезе для неориентированных графов: значение максимального потока в сети равно минимальной пропускной способности разреза. В 1955 году в работе Робахера было упомянуто, что впервые теорему максимальной пропускной способности сети доказал Фалкерсон.

В таблице 1.1 представлена полная хронология создания алгоритмов нахождения максимальной пропускной способности сети, а так же трудоемкости этих алгоритмов.

Год создания	Ангоры	T рудоемкость
1956	Fad, Fulkei con
1969	Edmonds, Karp	(Цлт1)
1970	Dinic	O(n2m)
1974	Karzanov	Otf)
1977	Cherkasky	ал11)
1978	Malhotra, Prarnos Kumar
	Maheshwari	an')
1978	Galil	(V5™1^
1978	Galil, Naamad;	a^iogn)2)
	Shiloadt
1980	Sleator, Tarjan	O(nm log л)
1982	Shi loach, Vishkin	a*’)
1983	Gabow ■	O[nm log CT)
1984	Tarjan	a^)
1985	Goldberg	ал1)
1986	Goldberg, Tarjan	O(iim logfn^/nr))
1986	Ahuja, Orlin	O(nm logfwVm))
1988	Ahuja, Orlin, Tarjan	O(nrn log(>i(!og U + 2)'2 >»))

Таблица 1.1 Хронология создания алгоритмов нахождения максимального потока

Алгоритм Форда-Фалкерсона является ключевым в данной квалификационной работе. Задача этого алгоритма так же определяется поиском максимального пути или максимальной пропускной способности сети. Для этого сначала нужно найти любой путь увеличивающий пропускную способность. Далее нужно взять поток по всем его дугам на минимальную из оставшихся пропускных способностей. Повторять до тех пор, пока имеется увеличивающий путь. Алгоритм Форда-Фалкерсона работает только для целочисленных весов. В противном случае, он будет работать бесконечно, при этом не найдя правильного ответа. Сложность метода зависит от алгоритма нахождения увеличивающего пути.

Алгоритм Эдмонса-Карпа. Этот алгоритм довольно схож с алгоритмом Форда-Фалкерсона. Различие заключается в том, что выполняя алгоритм Форда-Фалкерсона, каждый раз выбираем кратчайший увеличивающий маршрут. Он находится поиском в ширину. Сложность определяется как O(VE²).

Алгоритм Диница. Хоть и этот алгоритм был найден раньше, считается, что он представляет собой улучшенный алгоритм Эдмонса-Карпа. На каждой итерации используется алгоритм поиска в ширину. После этого определяются все расстояния от начальной вершины до всех вершин в остаточном графе. Далее строится граф, который содержит только такие дуги остаточного графа, на которых расстояние от начальной вершины до всех остальных увеличивается на единицу. Убираем из исходной сети все тупиковые вершины с инцидентными дугами, пока все вершины данного графа не станут не тупиковыми. Сложность зависит от алгоритма.

Также можно описать алгоритм проталкивания предпотока. Этот алгоритм сильно отличается от остальных тем, что вместо потока он работает с предпотоком. Главное отличие заключается в том, что для любой вершины нашего графа, кроме начальной и конечной вершин, сумма входящих в неё потоков для потока строго должна быть равна нулю, а для предпотока — больше или равной нулю. Так же это условие называется условием сохранения потока. Эта сумма определяется как избыточный поток в вершину, а вершина с положительным избыточным потоком именуется переполненной. Кроме того, для каждой вершины алгоритм сохраняет важную дополнительную характеристику, высоту, которая является целым числом. Такой алгоритм осуществляет две операции. Первая это проталкивание, когда поток по дуге, проходящей из более высокой в более низкую вершину, увеличивается на максимально допустимую величину. И вторая это подъём, когда переполненная вершина, проталкивание из которой уже невозможно из-за недостаточной высоты, поднимается. Проталкивание возможно только тогда, когда дуга принадлежит остаточному графу, ведёт из более высокой вершины в более низкую, и исходная вершина переполнена. Подъём возможен только в том случае, если поднимаемая вершина переполнена, но другие вершины, в которые из неё ведут рёбра остаточной сети, не ниже самой поднимаемой вершины. Подъем совершается до высоты на единицу большей, чем самая минимальная из высот этих вершин. Изначально высота начальной вершины H, по всем дугам, исходящим из начальной вершины, протекает максимально допустимый поток, а все остальные высоты и потоки нулевые. Операции проталкивания и подъёма осуществляются до тех пор, пока это является возможным. Сложность этого алгоритма равна O(V²E).

Метод «поднять в начало». Этот алгоритм представляет собой алгоритм проталкивания предпотока. Отличие лишь в том, что он специальным образом определяет порядок операций проталкивания и подъёма. Сложность такого метода определяется как O(V³).

В данной курсовой работе используется метод Форда-Фалкерсона. Этот метод является классическим для решения данного рода задач. За долго время этот метод много раз улучшался, но до сих пор считается одним из лучших алгоритмов для нахождения максимальной пропускной способности сети. Он относительно прост в реализации, при этом показывает довольно неплохие результаты. Сложность алгоритма Форда-Фалкерсона сравнительно невысока.

Для нахождения максимальной пропускной способности сети требуется теорема Форда-Фалкерсона. Эта теорема звучит следующим образом: «величина максимального потока в графе путей равна величине пропускной способности его минимального разреза». Любой поток между источником и стоком не более величины любого сечения. Допустим, дан заданный поток и заданное сечение. Величина данного потока складывается из величин пакетов, перевозимых по всем возможным ребрам (дугам) из источника в сток. Каждый такой путь обязательно должен иметь общую дугу с данным сечением. Так как по каждой дуге сечения суммарно нельзя перевести пакет больше, чем его пропускная способность, поэтому сумма всех пакетов не более чем сумма всех пропускных способностей дуг данного сечения.

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

Работа алгоритма осуществляется до тех пор, пока есть возможность находить данные маршруты. Сразу отметим, что данный алгоритм относится к классу недетерминированных, то есть каждый последующий шаг алгоритма определен неоднозначно. И время работы (количество шагов) такого алгоритма зависит от того, как будут выбираться шаги.

Неформальное описание алгоритма Форда-Фалкерсона выглядит так:

Шаг 1. Обнуляем все потоки в графе. Остаточный граф изначально совпадает с исходным графом;

Шаг 2. В остаточном графе находим любой маршрут из начальной вершины в конечную. Если такого маршрута не находим, то останавливаемся;

Шаг 3. Пускаем через найденный маршрут максимально возможный поток;

Шаг 4. На найденном маршруте в остаточном графе находим дугу с минимальной пропускной способностью c min ;

Шаг 5. Для каждой дуги на найденном маршруте увеличиваем поток на c min , а в противоположном ему — уменьшаем на c min ;

Шаг 6. Модифицируем остаточный граф. Для всех дуг на найденном маршруте, а также для всех противоположных им дуг, вычисляем новую пропускную способность. Если после этого пропускная способность стала ненулевой, то добавляем дугу к остаточному графу, а если обнулилась, стираем;

Шаг 7. Возвращаемся на шаг 2.

Важно знать, что данный алгоритм не конкретизирует, какой именно маршрут мы пытаемся найти на шаге 2 или как мы это делаем. По этой причине алгоритм сходится только для целочисленных пропускных способностей. Но даже при очень больших значениях пропускных способностей алгоритм может вычислять очень долго. Если пропускные способности вещественны, алгоритм может работать бесконечно долго, не сходясь к оптимальному решению.

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

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