Сетевое издание

Международный студенческий научный вестник

ISSN 2409-529X

• Авторы
• Файлы
• Литература

Карнаухова А.А. 1 Долгополова А.Ф. 1

---

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

Статья в формате PDF

286 KB

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).

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

Таблица 2

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

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

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

.

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

10 + 15 + 2 × 20 + 4 × 25 + 3 × 30 = 255

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

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

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

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