VII Международная студенческая научная конференция Студенческий научный форум - 2015

Теория графов один из наиболее интересных разделов математики. Родоначальником теории графов считается швейцарский математик Леонард Эйлер, который в 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

V1– завод №1	V5– магазин канцтоваров	V9– магазин №3
V2–хозяйственный магазин	V6–продуктовый магазин	V10– аптека
V3– пекарня	V7– текстильная фабрика	V11–завод №3
V4–завод №2	V8–кафе	V12– торговый комплекс

Данная задача решается с помощью одной из разновидностей жадного алгоритма – алгоритма Краскала. Пусть имеется конечное множество E, при E=18, весовая функция ω:E∈R и семейство ε∈2E. Необходимо найти XE, такое что: E– конечное множество, ω:E∈R – функция, ставящая в соответствие каждому элементу е этого множества неотрицательное действительное число ω(ε) - вес элемента ε. ДляXEвесω (X)определим как сумму всех элементов множества X:

ωX=minYϵεω(Y)

ωZ= εϵZ⊂Eω(e)

Необходимо выбрать в данном семействе непустое подмножество наименьшего веса. Сопоставив каждому пункту сети вершину графаG, а каждому из ребер этого графа составить число, которое равно стоимости строительства соответствующей коммуникации. Согласно теореме, алгоритм Краскала всегда приводит к ребру, имеющему минимальный вес. То есть это ребро e1=3;5, тогда получается граф T1. Строиться граф T2=T2+e2, где e2 - ребро, имеющее минимальный вес среди ребер, не входящих в T1 и не составляющий циклов с ребрамиT1, e28;10.

T3=T2+e3, гдеe3=7;9.

T4=T3+e4, гдеe4=1;2.

T5=T4+e5, гдеe5=1;3.

T6=T5+e6, гдеe6=5;6.

T7=T6+e7,гдеe7=4;8.

T8=T7+e8, гдеe8=9;12.

T9=T8+e9, гдеe9=2;4.

T10=T9+e10, гдеe10=6;7.

T11=T10+e11, гдеe11=11;12.

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

ωEG= εϵEG10+15+2*20+4*25+3*30=255

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

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

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

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

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.

Код для цитирования: Скопировать