Графы, сети и их применение в экономике.

 
Введение

Теория графов – это раздел дискретной математики, который изучает характеристики графов. Она имеет очень широкое практическое применение. Зачастую, задачи, которые возникают в экономике, химии, электротехнике, планировании транспортных перевозок, управлении предприятием, торговле и образовании, можно сформулировать как задачу теории графов.
Теория графов также находит свое приложение, к примеру, в геоинформационных системах (ГИС). Дома, которые уже существуют и те, что вновь проектируются, здания, улицы и тому подобное, рассматривают как вершины, а дороги, которые их соединяют, инженерные сети, провода электропередачи и тому подобное – как рёбра. Использование разнообразных расчетов, которые производят на таких графах, дает возможность поиска кратчайшего объездного пути или ближайшего продуктового магазина, составить план оптимального маршрута.
 
Теория графов и сетей

Граф (в широком смысле) – это множество узлов или вершин, которые соединены рёбрами. Граф состоит из двух компонентов: вершин и дуг, которые соединяют между собой данные вершины.
При представлении графов зачастую применяется такая совокупность обозначений:
– всякой вершине соотносится точка на плоскости,
– если между вершинами имеется ребро, то такие точки соединяют отрезком или стрелкой.
Для графа, который изображен на рис. 1:
– кружочки A, B, C, D, E – вершины графа;
– линии a, b, c, d, e, f, g – дуги.

Алгоритмы, которые предназначены для выполнения задачи оптимизации, как правило, представляют собой последовательность шагов, и на каждом из них имеется множество выборов. Так называемый «жадный» алгоритм позволяет сделать выбор, который кажется наилучшим в данное время. То есть проводится локально оптимальный выбор, считая, что это приведет к оптимальному решению глобальных задач. Жадный алгоритм во многих задачах приводит к нужному результату, хотя и не всегда приводят к оптимальному решению. Жадные алгоритмы обладают необходимой мощностью, и подходят для решения довольно-таки большого круга задач.
К жадным методам относят алгоритм, построенный на графах, изобретенный нидерландским ученым Эдсгером Дейкстрой в1959 году. Алгоритм Дейкстры – это алгоритм, применяемый для поиска самого кратчайшего пути от одних вершин графа до других. Алгоритм можно использовать только для тех графов, чьи ребра не имеют отрицательного веса.
Фирме, осуществляющей перевозку скоропортящегося товара, дано задание на доставку товара из Ставрополя в Будённовск, при этом существует несколько путей, по которым возможно доставить товар. Расстояние между городом Ставрополь и селом К. – 26 километров, между г. Ставрополем и селом П. – 19 километров, меж дуг. Ставрополем и селом Р. – 86 километров. Между сёлами К. и Д. – 16 километров, между сёлами К. и Л. – 66 километров. Между селом П. и городом Н. составляет 4 километра, между сёлами П. и В. – 51 километр. Между сёлами Д. и В. – 21 километр. Между городом Н. и селом М. – 21 километр. Между сёлами М. и Л. – 24 километра, между сёлами М. и В. – 34 километра. Между сёлами Л. и А. – 13 километров, между сёлами Л. и Ж. – 43 километра. Между сёлами А. и Б. – 25 километров. Между сёлами Ж. и Р. – 31 километр, между сёлами Ж. и Б. – 44 километра. Между сёламиБ. и Р. – 22 километра. Между сёлами В. иЖ. – 9 километров. Необходимо найти самый короткий путь из Ставрополя в Буденновск.
Построим граф G, где город Ставрополь обозначим буквой C, Буденновск – Б. Оставшиеся пункты маршрута обозначим соответственно буквами Л, П, Р, Д, Л, Н, М, В, А, Ж, Б. Каждому ребру графа сопоставим числа, которые будут равны расстоянию между пунктами. Необходимо найти наикратчайший путь.
Метод Дейкстры позволяет найти наикратчайший маршрут между необходимыми вершинами в графе. Значит, можно использовать данный алгоритм, для решения данной экономической задачи.

Применим формулу метода Дейкстры для решения данной экономической задачи:
, (1)
где D(v) – длина кратчайшего пути от начальной вершины к конечной вершине; величины u, v – неотрицательный вес ребра.
С помощью алгоритма Дейкстры можно найти единственный оптимальный маршрут, который соединяет вершины С и Б графа (см. рис.1).
Пусть вершина С будет являться начальной вершиной. Для этой вершины назначим постоянный ярлык . За конечную вершину примем Б.
Рассмотрим вершины, которые являются смежными с вершиной Б.
Для этого назначаем им временные ярлыки: