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

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

Карнаухова А.А. 1 Долгополова А.Ф. 1
1 Ставропольский государственный аграрный университет
1. Зыков А.А. Основы теории графо: учебник. – М.: Вузовская книга, 2004. – 664 с.
2. Горбатов В.А. Дискретная математика. Теория, задачи, приложения: учебное пособие. – М.: Физмалит, 2000. – 544 с.
3. Долгополова А.Ф., Гулай Т.А., Литвин Д.Б. Перспективы применения математических методов в экономических исследованиях // Аграрная наука, творчество, рост. – 2013. – С. 255-257.
4. Долгополова А. Особенности применения методов математического моделирования в экономических исследованиях / А.Ф. Долгополова, Т.А. Гулай, Д.Б. Литвин // Кант: экономика и управление. – 2013. – №1. – С. 62-66.
5. Гулай Т.А., Долгополова А.Ф., Литвин Д.Б., Донец З.Г. Экономико-математическое моделирование факторов экономического анализа посредством метода линейного программирования: сборник «Аграрная наука, творчество, рост». – Ставрополь, 2014. – С. 329-332.
6. Мамаев И.И., Родина Е.В. Основные особенности применения экономико-математических моделей в управлении: сб. науч. тр. «Учетно-аналитические и финансово-экономические проблемы развития региона», 2012.
7. Невидомская И.А., Якубова А.М. Применение факторного анализа при исследовании экономических процессов // Современные наукоемкие технологии. – 2013. – № 6. – С. 81-83.
8. Коннова Д.А., Леликова Е.И., Мелешко С.В. Взаимодействие математики с экономикой // Современные наукоемкие технологии. – 2014. – № 5-2. – С. 159-161.
9. Бондаренко В.А., Цыплакова О.Н. Некоторые аспекты интегрированного подхода изучения математического анализа // Учетно-аналитические и финансово-экономические проблемы развития региона: матер. 76-й научно-практической конференции. – Ставрополь: Альфа-Принт, 2012. – С. 280-283.

Теория графов один из наиболее интересных разделов математики. Родоначальником теории графов считается швейцарский математик Леонард Эйлер, который в 1736 году сформулировал решение задачи о семи кёнигсбергских мостах, ставшей впоследствии классической задачей теории графов. Развитие этой теории долгое время не происходило, а лишь в середине 20 века интерес к проблемам теории графов вновь появился, главным образом в Англии. Наиболее известной задачей-проблемой того периода является задача четырех красок, которая была составлена математиком Огастесом де Морганом в 1850 году. В настоящее время теория графов неуклонно развивается и получил широкое распространение в экономических исследованиях. В последнее время все чаще наблюдается проникновение математики в разные сферы и отрасли многих наук. Этот процесс затронул и экономическую сферу. Для нахождения кратчайшего или объездного пути, рационального маршрута передвижения, для оптимизации производственного цикла применяется теория графов.

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

Классическим примером таких задач является практическое применение жадного алгоритма в решении экономических проблем.

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

Пусть на территории некоторого города N размещены заводы, которые поставляют свою продукцию в магазины. В результате разработки были определены возможные трассы для прокладки коммуникаций и оценена стоимость их создания для каждой трассы (табл. 1).

Таблица 1

Стоимость создания трассы между объектами

Первый объект

Второй объект

Стоимость проведения коммуникаций, у.е.

заводом №1

зоомагазином

20

магазином №1

заводом №3

90

заводом №1

пекарней

25

хозяйственным магазином

заводом№2

30

хозяйственным магазином

текстильной фабрикой

70

пекарней

магазином канцтоваров

10

пекарней

кафе

55

заводом №2

кафе

25

магазином канцтоваров

продуктовым магазином

25

продуктовым магазином

текстильной фабрикой

30

текстильной фабрикой

магазином №3

20

продуктовым магазином

кафе

40

текстильной фабрикой

аптекой

45

кафе

аптекой

15

магазином №3

торговым комплексом

25

аптекой

заводом №3

35

аптекой

торговым комплексом

50

заводом №3

торговым комплексом

30

Необходимо, чтобы коммуникации связали все объекты, но затраты на прокладку данных коммуникаций должны быть минимальными (табл. 2).

Таблица 2

Обозначения объектов

V1 – завод №1

V5 – магазин

канцтоваров

V9 – магазин №3

V2 – хозяйственный магазин

V6 – продуктовый магазин

V10 – аптека

V3 – пекарня

V7 – текстильная фабрика

V11 – завод №3

V4 – завод №2

V8 – кафе

V12 – торговый комплекс

Данная задача решается с помощью одной из разновидностей жадного алгоритма – алгоритма Краскала. Пусть имеется конечное множество E, при E = 18, весовая функция missing image file и семейство missing image file. Необходимо найти missing image file, такое что: E – конечное множество, missing image file – функция, ставящая в соответствие каждому элементу е этого множества неотрицательное действительное число missing image file – вес элемента missing image file. Для missing image file вес missing image fileопределим как сумму всех элементов множества Х:

missing image file

missing image file

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

missing image file.

missing image file

missing image file

missing image file

missing image file

missing image file

missing image file

missing image file

missing image file

Найдено минимальное дерево покрытия взвешенного графа, а следовательно, найдена и оптимальная структура сети, где общая стоимость затраченная на прокладку коммуникаций составит:

missing image file10 + 15 + 2 × 20 + 4 × 25 + 3 × 30 = 255

Это минимальная сумма затрат из всех возможных исходов. При прокладке коммуникационной сети, которая соединяет все пункты, затрачивается 255 у.е.

Коммуникации необходимо проложить между следующими пунктами: аптека – кафе – завод №2 – хозяйственный магазин – завод №1 – пекарня – магазин канцтоваров – продуктовый магазин – текстильная фабрика – магазин №3 – торговый комплекс.

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


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

Карнаухова А.А., Долгополова А.Ф. ИСПОЛЬЗОВАНИЕ ТЕОРИИ ГРАФОВ ПРИ РЕШЕНИИ ЗАДАЧ В ЭКОНОМИКЕ // Международный студенческий научный вестник. – 2015. – № 3-4. ;
URL: https://eduherald.ru/ru/article/view?id=14128 (дата обращения: 07.12.2021).

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

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