Сетевое издание
Международный студенческий научный вестник
ISSN 2409-529X

ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКОГО АППАРАТА ТЕОРИИ ГРАФОВ ПРИ РЕШЕНИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ

Гурова Д.Г. 1
1 Ставропольский государственный аграрный университет
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): Сборник научных трудов VI международной научно-технической конференции, 2014. – С. 157-162.
10. Карнаухова А.А., Долгополова А.Ф. Использование теории графов при решении задач в экономике // Международный студенческий научный вестник. – 2015. – № 3-4. – С. 468-469.

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

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

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

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

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

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

Для графа, которыйизображен на рис. 1:

– кружочки A, B, C, D, E – вершины графа;

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

mat3.tif

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

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

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

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

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

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

mat4.tif

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

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

prakt310.wmf, (1)

где D(v) – длина кратчайшего пути от начальной вершины к конечной вершине; величины u, v – неотрицательный вес ребра.

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

Пусть вершина С будет являться начальной вершиной. Для этой вершины назначим постоянный ярлык prakt312.wmf. За конечную вершину примем Б.

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

Для этого назначаем им временные ярлыки:

Y(К)=26, Y(П)=19, Y(Р)=86.

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

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

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

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

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

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

При повторении этого процесса рассматривают вершины, смежные с вершиной Л. Это К, А и Ж. Для них временными ярлыками будут: Y(К)=66, Y(А)=13, Y(Ж)=43. Находим наименьший временный ярлык. Таким является ярлык: Y(А)=13.

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

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

prakt313.wmf км. (2)

mat5.tif

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

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


Библиографическая ссылка

Гурова Д.Г. ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКОГО АППАРАТА ТЕОРИИ ГРАФОВ ПРИ РЕШЕНИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ // Международный студенческий научный вестник. – 2016. – № 3-3. ;
URL: https://eduherald.ru/ru/article/view?id=15016 (дата обращения: 07.12.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674