1 Гурова Д.Г. 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 - дуги.
Мал. 1. Складові частини графа
Алгоритми, які призначені для виконання завдання оптимізації, як правило, представляють собою послідовність кроків, і на кожному з них є безліч виборів. Так званий «жадібний» алгорітмпозволяет зробити вибір, який здається наілучшімв даний час. Тобто проводиться локально оптимальний вибір, вважаючи, що це призведе до оптимального вирішення глобальних завдань. Жадібний алгоритм в багатьох задачах призводить до потрібного результату, хоча і не завжди приводять до оптимального рішення. Жадібні алгоритми володіють необхідною потужністю, і підходять для вирішення досить-таки великого кола завдань.
До жадібних методів відносять алгоритм, побудований на графах, винайдений нідерландським вченим Едсгер Дейкстрой в 1959 році . Алгоритм Дейкстри - це алгоритм, який використовується для поіскасамого найкоротшого шляху від одних вершин графа до інших. Алгоритм можна використовувати тільки для тих графів, чиї ребра не мають негативного ваги.
Фірмі, яка здійснює перевезення швидкопсувного товару, дано завдання на доставку товару з Ставрополя в Будьонівськ, при цьому існує кілька шляхів, за якими можна представити товар. Відстань між містом Ставрополь і селом К. - 26 кілометрів, між м Ставрополем і селом П. - 19 кілометрів, междуг. Ставрополем і селом Р. - 86 кілометрів. Між селами К. і Д. - 16 кілометрів, між селами К. і Л. - 66 кілометрів. Між селом П. і містом Н. складає 4 кілометри, між селами П. і В. - 51 кілометр. Між селами Д. і В. - 21 кілометр. Між містом Н. і селом М. - 21 кілометр. Між селами. і Л. - 24 кілометри, між селами М. і В. - 34 кілометри. Між селами. і А. - 13 кілометрів, між селами Л. і Ж. - 43 кілометри. Між селами А. і Б. - 25 кілометрів. Між селами Ж. і Р. - 31 кілометр, між селами Ж. і Б. - 44 кілометри. Між сёламіБ. і Р. - 22 кілометри. Між селами В. ІЖ. - 9 кілометрів. Необхідно знайти найкоротший шлях із Ставрополя в Буденновск.
Побудуємо граф G, де місто Ставрополь позначимо літерою C, Буденновск - Б. Решта пункти маршруту позначимо відповідно буквами Л, П, Р, Д, Л, Н, М, В, А, Ж, Б. Кожному ребру графа зіставимо числа, які будуть дорівнюють відстані між пунктами. Необхідно знайти наікратчайшійпуть.
Метод Дейкстри дозволяє знайти найкоротший маршрут між необхідними вершинами в графі. Значить, можна використовувати даний алгоритм, для вирішення даної економічної завдання.
Мал. 2. Графічне зображення задачі
Застосуємо формулу методу Дейкстри для вирішення даної економічної завдання:
, (1)
де D (v) - довжина найкоротшого шляху від початкової вершини до кінцевої вершини; величини u, v - невід'ємні вага ребра.
За допомогою алгоритму Дейкстри можна знайти єдиний оптимальний маршрут, який з'єднує вершини С і Б графа (див. Рис.1).
Нехай вершина С буде початковою вершиною. Для цієї вершини призначимо постійний ярлик 
. За кінцеву вершину приймемо Б.
Розглянемо вершини, які є суміжними з вершиною Б.
Для цього призначаємо їм тимчасові ярлики:
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)).
км. (2)
Мал. 3. Знаходження рішення економічної задачі
Таким чином, маршрут з міста Ставрополь в місто Будьонівськ, з найменшим часом доставки товару, включає село П, місто Н, село М, село Л і село А. Загальна протяжність маршруту складає 104 кілометри.
бібліографічна посилання
Гурова Д.Г. ЗАСТОСУВАННЯ МАТЕМАТИЧНОГО АПАРАТУ ТЕОРІЇ ГРАФІВ ПРИ ВИРІШЕННІ ЕКОНОМІЧНИХ ЗАДАЧ // Міжнародний студентський науковий вісник. - 2016. - № 3-3 .;
URL: http://www.eduherald.ru/ru/article/view?id=15016 (дата звернення: 02.08.2019).
Пропонуємо вашій увазі журнали, що видаються у видавництві «Академія природознавства»
(Високий імпакт-фактор РИНЦ, тематика журналів охоплює всі наукові напрямки)
Ru/ru/article/view?
