3. Методы и модели теории графов и сетевого моделирования на транспортных объектах. Элементы теории графов
Наука, занимающаяся графическими представлениями, - геометрия из-за своей наглядности получила широкое распространение уже в древности. Так, задолго до жившего в VI в. до н.э. Пифагора была известна теорема, которая позже стало носить его имя. Наглядность геометрии широко используется в наше время, в том числе при анализе больших технических и организационных систем, в которых используют теорию графов.
Граф – совокупность вершин и ребер – универсальное средство наглядного представления достаточно разнообразных задач.
Разнообразные сочетания различных ребер и вершин представляют многообразие возможных графов и их применения. Граф, в котором вершины – прямоугольники и направления ребер не заданы, описывают блок-схему (или структуру) организационно-технической системы. Граф-дерево – многоуровневая иерархическая система, в которой все вершины распределены по нескольким уровням. Граф с дугами, изображающими связь между вершинами, - сеть.
Сетями представляют различные задачи, в которых исследуют перемещение или выполнение работ во времени. Сеть характеризуется структурой и параметрами дуг. Структура (топология) сети показывает, какие вершины связаны между собой, и направление связывающих их дуг.
Каждую вершину сети нумеруют порядковым номером. Начальную 1 вершину в описании движения потоков называют источником, конечную – стоком. В общем случае дугу обозначают i-j, где i – номер вершины, из которой исходит дуга; j – номер вершины, в которую входит дуга. Каждая дуга имеет свою характеристику: tij – продолжительность движения по дуге i-j; cij – стоимость перемещения; dij – пропускная способность дуги и т.д.
Зная топологию сети и ее параметры, можно решать самые разнообразные, часто встречающиеся задачи оптимизации.
Задача коммивояжера
П
ример.
Пусть имеются
5 пунктов, соединенных между собой
дорогами так, что из любого пункта можно
проехать в любой другой пункт (рис.1).
Известно время перевозки из пункта i
в пункт j
(табл.1).
Р
исунок
1.
Таблица 1.
Из пункта i |
В пункт j |
||||
1 |
2 |
3 |
4 |
5 |
|
1 |
0 |
10 |
25 |
25 |
10 |
2 |
1 |
0 |
10 |
15 |
2 |
3 |
8 |
9 |
0 |
20 |
10 |
4 |
14 |
10 |
24 |
0 |
15 |
5 |
10 |
8 |
25 |
27 |
0 |
Требуется найти такой маршрут, начинающийся в данном пункте, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы его продолжительность была минимальной.
Решение.
Для решения этой задачи необходимо
составить математическую модель. Введем
обозначения: i
и j
– номера пунктов выезда и въезда; tij
– время переезда из пункта i
в пункт j.
Из таблицы 1 видно, что tij
в общем случае может быть не равно
времени переезда в обратном направлении
tij
tji
(например, когда один пункт на вершине
горы, а другой – у ее подножия). Введем
булевые
переменные:
1,
если из пункта i
торговец переедет в пункт j
=
0, если не поедет.
Составим модель. Из пункта 1 можно выехать в любой из пунктов 2 или 5, или 3, или 4, или остаться в пункте 1. Но при этом можно выехать только в одном единственном направлении. Это условие можно записать так:
,
или
,
или
для произвольного i-ого пункта
Эти зависимости обеспечивают выполнение условия, что из каждого пункта выезд производится только один раз и только в одном направлении.
Условие въезда в пункт 1 аналогично условию выезда из пункта 1. Требование минимальной продолжительности маршрута запишется в виде целевой функции:
где tij берутся из исходной таблицы 1, а - искомые переменные.
Тогда всю задачу можно сформулировать:
,
,
,
(*)
=
[0;1]
.
В
результате решения системы (*) получим
(рис.2) следующие значения
,
остальные
;
min
L
= 10+8+10+20+14=62.
Рисунок 2.
Переходя от частной к общей постановке, задачу коммивояжера можно сформулировать как:
,
,
,
(*)
=
[0;1]
.