Теория графов – применение в логистике (история, основы теории, линейная транспортная задача)

Цель работы:

Общая: воспитание у обучающихся устойчивых стремлений к знаниям при изучении общеобразовательных дисциплин и математики в частности.

Прикладная:

• показать курсантам НКРУ им. С.И. Дежнева значение прикладной математики для их будущей профессиональной деятельности;
• продемонстрировать курсантам высокую экономическую эффективность речных перевозок, и тем самым закрепить у них уважение к своим будущим специальностям.

Указанная цель достигается:

1. Кратким описанием теории графов и истории её возникновения.
2. Перечислением различных областей эффективного применения теории графов в прикладных задачах.
3. Описанием линейной транспортной задачи.
3. Представлением примеров применения теории графов в логистике. В частности при выборе наиболее оптимальной схемы и способов перевозки грузов.
4. Представлением реального примера расчета стоимости различных типов перевозок грузов, в котором показана высокая экономическая эффективность речных перевозок.

Состав работы:

I. Лекция  (продолжительность: 1 академический час)
II. Презентация.
III. Комплект контрольно-проверочных средств.

Содержание:

1. Введение: Логистика
2. История возникновения теории графов.
3. Области эффективного применения теории графов.
4. Основные понятия и теоремы теории графов.
5. Наиболее известные и яркие задачи теории графов.
6. Применение теории графов в логистике. Типовая задача речного флота.
7. Контрольные вопросы для проверки усвоения материала.
8. Литература

1. Введение

Если рассматривать логистику как задачу нахождения оптимального перемещения, то с этой точки зрения – каждый человек в течении дня на уровне подсознания неоднократно решает такую задачу, перемещаясь:
–  из дома на работу и обратно;
– с работы в театр, в кино, в кафе и т.п.;
– в столовую во время обеда, по помещениям и учреждениям во время работы, и т.д.
– даже первобытный человек во время охоты, решал данную задачу в процессе погони за добычей!
В своей общественно-практической деятельности человек также каждодневно решает задачи логистики оптимального перемещения:
– грузов;
– войск;
– готовой продукции и комплектующих в процессе её производства;
– пассажиров и многого другого.

Логистика – как наука известна со времен Римской империи, где: “Логист” – снабженец в армии.

В настоящее время – основная задача логистики, это:

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

К началу 20-го века Логистика, как наука, получила в арсенал своих научных средств новый математический аппарат – теорию графов

* Данное определение логистики не охватывает все её задачи и выбрано как наиболее простое, поскольку к настоящему времени дано более 200 определений, многие из которых противоречивы к другим.

2. История возникновения теории графов

Датой рождения теории графов принято считать 1736 год, когда Леонард Эйлер сформулировал первые теоремы новой теории, решая задачу "О кенигсбергских мостах", и написал об этом в письме итальянскому математику и инженеру Мариони 13 марта 1736 г., чем и закрепил за собой приоритет автора новой теории.
Однако: Термин «граф» впервые ввел в математику венгерский математик Денеш Кениг в 1936 году.

В настоящее время:

– в некоторых отраслях прикладной деятельности вместо понятия "граф" используется термин "сеть": сетевой график; сеть железных дорог и т.п.;
– вместо термина "вершина графа" при использовании "сетевой" терминологии используется термин "сетевой узел" или просто – "узел".

"Задача о кенигсбергских мостах".

В 1736 г. город Калининград назывался Кёнигсбергом. Он был расположен на берегах р. Прегель, и на двух островах между ними. Четыре образовавшихся участка суши (правый и левый берег, и два острова) соединяло семь мостов так (рис.1). В задаче предлагалось составить маршрут для почтальона, полицейского или туриста, чтобы они побывали во всех районах города, и при этом прошли по каждому мосту только один раз – в настоящее время такой путь называется "Эйлеровым путём".

В числе сформулированных Эйлером теорем была теорема о том, что: Граф с более чем двумя нечётными степенями вершин невозможно начертить или обойти все его вершины так, чтобы пройти по каждому ребру графа только один раз.

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

На рис. 2 показано изображение графа, для "Задачи о кенигсбергских мостах".

Вершины графа соответствуют определённому району города, а ребра – мостам через реку.
Из рисунка видно, что все четыре вершины графа – имеют нечетные степени: вершины А, В, Г – имеют степень 3, вершина Б – степень 5, т.е. "Эйлерового пути" у данного графа не существует!

На рис. 3 приведены примеры изображений графов, для которых существуют "Эйлеровы пути".

Далее, вплоть до начала 20-го века теория графов развивалась в основном в виде формулирования новых теорем, сформированных по результатам решения различных "головоломных задач".
   Серьезное развитие теория графов получила в связи с возникновением массового крупносерийного производства, общим всплеском науки и технологий в первой половине 20-го века.

3. Области применения графов.

В настоящее время теория графов нашла очень широкое применение в:

1. В микроэлектронике – при разработке топологии микросхем.
2. При разработке сложных электрических схем и схем их монтажа в электротехнических шкафах, в электрощитах.
3. В химии – при разработке новых сложных молекулярных соединений и т.п.
4. Физике – при описании и анализе схем развития квантовых процессов.
5. При разработке коммуникационных систем различного назначения.
6. В транспортных системах – как для изучения самих систем, так и при составлении оптимальных маршрутов доставки грузов – логистика.
7. В информатике и программирование – при разработке алгоритмов расчетов, программ.
8. В экономике и планировании – в виде сетевых графиков.
и т.д.

4. Основные понятия теории графов.

Графом, или точнее: "Изображением графа" – называется конечное множество точек, соединенных, как правило, друг с другом любыми линиями. Данные точки называются вершинами графа или узлами сети, а соединяющие их линии – рёбрами.
Если, точка не соединена ни с одной другой точкой – она называется "висячей".
Степень вершины графа равна количеству линий или ребер, связанных с данной точкой, вершиной, узлом. p(N)
С точки зрения решения задачи, связанной с конкретным изображением графа:
Граф непосредственнл – это решение поставленной задачи в виде конкретной схемы пути по вершинам и ребрам изображения графа. Каждая задача может иметь одно и более решений, либо не иметь решения.
Эйлеров граф – это такой граф, в котором существует путь по всем его ребрам такой, чтобы каждое ребро было пройдено только один раз.
Гамильтонов путь – путь через все вершины графа наиболее коротким путем.
Пути могут быть замкнутыми, т.е. начинаться и заканчиваться в одной точке, либо разомкнутыми.
Ориентированные графы – граф, имеющий ребра по которым можно перемещаться только в одном направлении.
Неориентированные графы – в котором по всем ребрам можно перемещаться в любую сторону.

Элементарные теоремы:

Теорема 1.

Сумма степеней вершин графа – четное и равна удвоенному числу ребер графа.
Доказательство: Каждое ребро соединяет две вершины (например A и B), и будет дважды учтено при определении степеней узлов, поскольку: p(А) = p(B) =1 и  p(А) + p(B) = 2.

Теорема 2.

Число узлов с нечетной степенью любого графа – четное.

Доказательство:  Из Теоремы 1 мы знаем, что сумма четных и нечетных степеней вершин – четная:  ∑ p_ч + ∑ p_н = 2R, а сумма четных чисел ∑ p_ч – всегда четная. Значит и ∑ p_н – четная.

Теорема 3.

У Графа с количеством вершин нечетной степени больше 2-х Эйлерова пути нет.

Доказательство: выполнено Эйлером в 1736 г.

5. Наиболее известные и "яркие" задачи теории графов:

1. Теорема о четырёх красках утверждает, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. Теорема была сформулирована в 1852 году, однако доказать ее долгое время не удавалось. В течение этого времени было предпринято множество попыток как доказательства, так и опровержения, и эта задача носила название проблемы четырёх красок. Для простых карт достаточно и трёх цветов, а четвёртый цвет начинает требоваться, например, тогда, когда имеется одна область, окруженная нечетным числом других, которые соприкасаются друг с другом, образуя цикл. Теорема о пяти красках, утверждающая, что достаточно пяти цветов, имела короткое несложное доказательство и была доказана в конце XIX века, но доказательство теоремы для случая четырёх цветов столкнулось со значительными трудностями и была доказана лишь в 1976 году. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Доказательство этого факта заняло сотни страниц и не все математики признали его. В 1997 году, и в 2005 году были найдены более простые доказательства, также проделанные с помощью компьютера.

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

3.  Задача о ходе коня – задача о нахождении маршрута шахматного коня, проходящего через все поля стандартной шахматной доски по одному разу. Как оказалось: Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно:
13 267 364 410 532.Количество всех незамкнутых маршрутов (с учётом направления обхода) равно: 19 591 828 170 979 904.
Наиболее красивое решение (рис. 4) получено при помощи "Шахматного компьютера". Однако с точки зрения логистики наиболее интересным кажется маршрут, найденный К. Я. Янишем, в котором конь сначала обходит одну половину доски, а затем вторую.

Рис. 4.

6. Применение Теории Графов в логистике.

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

Типичная задача речного флота (рис. 5): У Базы в точке Б имеется в распоряжении транспортные средства грузоподъемностью:1000, 600, 200,10 тонн.
В точки А, С, Д требуется доставить 1200, 85 и 20 тонн груза соответственно.
Стоимость перевозок сухогрузами:
1000 тонн – 60 000 рублей/сутки; 600 тонн – 35 000 рублей/сутки и 200 тонн – 24 000 рублей/сутки.

Рис. 5.

Задание.

Необходимо составить графы возможный решений и найти наиболее выгодные варианты с экономической точки зрения для Изображения Графа на Рис. 5.

Данная задача предлагается курсантам для самостоятельного практического задания на 2-ой час занятий по теме: "Графы".

7. Контрольные вопросы для проверки усвоения материала.

1. Что называется степенью вершины Графа?
2. Альтернативное название Графа?
3. Что такое "полный" Граф?
4. Что такое "неполный" Граф?
5. Какие пути существуют в Графе?
6. Чему равна сумма степеней Графа?
7. Какую ещё теорему о Графах знают учащиеся?
8. Нарисовать изображение графа для простой перевозки одним из транспортных средств (рис. 5).
9. Составить Граф решений для одного из транспортных средств по Рис. 5.

8. Литература.

[1]. Интернет ресурсы по темам Теория Графов, Логистика.