Применение математического аппарата теории графов при решении экономических задач

Размещено на http://www.allbest.ru/

Ставропольский государственный аграрный университет

Применение математического аппарата теории графов при решении экономических задач

Гурова Д.Г.

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

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

Граф (в широком смысле) - это множество узлов или вершин, которые соединены рёбрами. Граф состоит из двух компонентов: вершин и дуг, которые соединяют между собой данные вершины.

При представлении графов зачастую применяется такая совокупность обозначений:

- всякой вершине соотносится точка на плоскости,

- если между вершинами имеется ребро, то такие точки соединяют отрезком или стрелкой.

Для графа, который изображен на рисунке 1: - кружочки A, B, C, D, E -это вершины графа,

- линии a, b, c, d, e, f, g- дуги.

Рис. 1 - Составные части графа

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

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

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

Построим граф G, где город Ставрополь обозначим буквой С, Буденновск - Б. Оставшиеся пункты маршрута обозначим соответственно буквами К, П, Р, Д, Л, Н, М, В, А, Ж, Б . Каждому ребру графа сопоставим числа, которые будут равны расстоянию между пунктами. Необходимо найти наикратчайший путь.

Метод Дейкстры позволяет найти наикратчайший маршрут между необходимыми вершинами в графе. Значит, можно использовать данный алгоритм, для решения данной экономической задачи.

Рис.2 - Графическое изображение задачи

Применим формулу метода Дейкстры для решения данной экономической задачи:

D(v)= min D(u) (1)

x(u)=0

где D(v) - длина кратчайшего пути от начальной вершины к конечной вершине.

Величины u, v - неотрицательный вес ребра.

С помощью алгоритма Дейкстры можно найти единственный оптимальный маршрут, который соединяет вершины Си Б графа(см. рис.1).

Пусть вершина Сбудет являться начальной вершиной. Для этой вершины назначим постоянный ярлык Y(1)=0. За конечную вершину примем Б .

Рассмотрим вершины, которые являются смежными с вершиной Б.

Для этого назначаем им временные ярлыки: Y(K)=26, Y(П) =19, Y(P)=86.

Необходимо выбрать вершину с наименьшим ярлыком - это вершина П, и её ярлык считают постоянным, то есть Y(П) =19.

При повторении этого процесса для вершины П, вершинам присваивают временные ярлыки: Y(H)=4, Y(B)=51 .

Выбирая из всех временных ярлыков, минимальным будет являться Y(H)=4. Этот ярлык устанавливается постоянным.

С вершиной Н считается смежной только вершина М, тогда Y(M)=19.

При повторении этого процесса для вершины М, вершинам присваивают временные ярлыки: Y(Л) = 24, Y(B)=34.

Среди них минимальным будет величина Y(Л) = 24.Такой ярлык считают постоянным.

При повторении этого процесса, рассматривают вершины, смежные с вершиной Л.

Это К, Аи Ж . Для них временными ярлыками будут: Y(К) = 66, Y(A)=13,

Y(Ж) = 43. Находим наименьший временный ярлык. Таким является ярлык: Y(A)=13.

С вершиной А смежной является только вершина Б, тогда Y(Б) = 25.

В то время, когда дерево составлено, становится возможным найти наикратчайший путь от С до Б . Им будет являться путь дерева, который соединяет вершины С и Б . Выявлено, что это путь, проходящий через вершины К, Н, М, Л и А. Длина такого пути рассчитывается как сумма всех дуг данных вершин (формула 2).

Y(L)=19+4+19+24+13+25=104километра (2)

Рис.3-Нахождение решения экономической задачи

Таким образом, маршрут из города Ставрополь в город Буденновск, с наименьшим временем доставки товара, включает село П, город Н, село М, село Л и село А. Общая протяженность маршрута составляет 104 километра.

граф экономика алгоритм

Список литературы

1. Быкова, В. В. Теоретические основы анализа параметризированных алгоритмов [Электронный ресурс] : Монография / В. В. Быкова. - Красноярск: Сиб. федер. ун-т, 2011. -180 с.

2. Исследование операций (учебное пособие) / Крон Р.В., Попова С.В., Долгих Е.В., Смирнова Н.Б. // Международный журнал экспериментального образования. 2014. № 11-1. С. 118-119.

3. Математика (учебное пособие) / Крон Р.В., Попова С.В., Долгих Е.В., Смирнова Н.Б. // Международный журнал экспериментального образования. 2014. № 11-1. С. 114-115.

4. Смирнова Н.Б., Давтян А.Г. Математика как область научного познания современного информационного общества // Культура и общество: история и современность материалы II Всероссийской (с международным участием) научно-практической конференции под редакцией: Колосовой О.Ю., Гударенко Р.Ф., Ряснянской Н.А., Красиковой Е.А. / Ставрополь, 2013. С. 154-158.

5. Смирнова Н.Б., Попова С.В. Проблемы создания математических моделей эколого-экономических систем в процессе взаимодействия человека и окружающей среды // Культура и общество: история и современность материалы III Всероссийской (с международным участием) науч.-практ. конф. Филиал РГСУ в г. Ставрополь; под редакцией О. Ю. Колосовой, Т. В. Вергун, Р. Ф. Гударенко. / Ставрополь, 2014. С. 185-190.

6. Попова С.В., Смирнова Н.Б. Элементы алгоритмизации в процессе обучения математике в высшей школе // Современные проблемы развития экономики и социальной сферы: сборник материалов Международной научно-практической конференции, посвященной 75-летию Ставропольского государственного аграрного университета. Ответственный редактор: Н. В. Кулиш. 2005. с. 526-531.

7. Попова С.В., Колодяжная Т.А. Применение алгоритмов при обучении математике в вузе // Моделирование производственных процессов и развитие информационных систем / Даугавпилсский университет, Латвия, Европейский Союз Белорусский государственный университет, Беларусь Днепропетровский университет экономики и права, Украина Московский государственный университет им. М.В. Ломоносова, Россия Санкт-Петербургский государственный политехнический университет Северо-Кавказский государственный технический университет Ставропольский государственный университет Ставропольский государственный аграрный университет. Ставрополь, 2011. с. 278-281.

8. Смирнова Н.Б., Попова С.В. Модели, подходы к классификации моделей // Экономика регионов России: анализ современного состояния и перспективы развития: сборник научных трудов по материалам Ежегодной 69-й научно-практической конференции, посвященной 75летию СтГАУ. Ответственный редактор: Кулиш Н. В. 2005. С. 181-185.

9. Зайцева И.В., Попова М.В., Филимонов А.А. Алгоритм программной реализации математической модели динамической экономической системы // Инфокоммуникационные технологии в науке, производстве и образовании (Инфоком-6)Сборник научных трудов Шестой международной научно-технической конференции. 2014. С. 157-162.

10. Карнаухова А.А., Долгополова А.Ф. Использование теории графов при решении задач в экономике // Международный студенческий научный вестник. 2015.№ 3-4. С. 468-469.

Размещено на Allbest.ru