Графы
Вы
узнаете:
Þ
что такое граф, вершина, ребро, дуга;
Þ
что такое сеть, структура, параметры дуг;
Þ
как решаются такие задачи.
Геометрия,
занимающаяся графическим представлением объектов, благодаря своей наглядности,
получила широкое распространение еще в древности. Наглядность геометрии
используется при анализе сложных технических и организационных систем. Граф -
совокупность вершин и ребер. Каждую вершину обозначают порядковым номером. Если
ребро графа имеет направление, то его называют дугой. Сеть – это граф, в
котором вершины соединены дугами. Сеть характеризуется структурой и параметрами
дуг.
1 2 1 2
i Д
i,j j
граф дуга сеть
4 3
4 3
Структура
сети (топология) показывает, какие вершины связаны между собой и каково
направление связывающих дуг. Дугу обозначают двойной индексацией:
Þ
i - номер вершины, из которой выходит
дуга.
Þ
j - номер вершины, в которую входит дуга.
Каждая
дуга может иметь свою характеристику.
Например.
Tij – продолжительность
движения по дуге i-j.
Например.
Cij - стоимость перемещения
по дуге i-j.
Например.
Dij - пропускная способность
по дуге i-j.
Зная
структуру сети и характеристики её дуг, можно решать различные задачи оптимизации,
достаточно часто встречающиеся на практике.
Задача о
коммивояжере.
Есть
4 пункта соединенных дорогами между собой каждый с каждым, т.е. из любого
пункта можно проехать в любой другой пункт. Время, необходимое для переезда из
одного пункта в другой см. в таблице.
Требуется
найти такой маршрут, начинающийся в данном пункте, проходящий через все пункты
и заканчивающийся в точке выезда, чтобы его продолжительность была наименьшей.
Таблица
Из пункта i
|
В пункт j
|
Введем
обозначения:
|
1
|
2
|
3
|
4
|
i и j –
пункты выезда и въезда
|
1
|
0
|
10
|
25
|
25
|
Тij – время
переезда из пункта i в пункт
j.
|
2
|
1
|
0
|
10
|
15
|
Тij может
быть не равно Тji.
|
3
|
8
|
9
|
0
|
20
|
Один пункт
находится на вершине горы,
|
4
|
14
|
10
|
24
|
0
|
а другой у ее
подножия
|
Экономико-математическая
модель задачи:
Из
пункта 1 можно выехать в любой пункт 2-3-4 х14 1 х12
x12+x13+x14=1 Условие
выезда из пункта 1
x21+x23+x24=1 Условие
выезда из пункта 2
x31+x32+x34=1 Условие
выезда из пункта 3 х13
x41+x42+x43=1 Условие
выезда из пункта 4
В
пункт 1 можно въехать в любой пункт 2-3-4 х41 1 х21
x21+x31+x41=1
Условие въезда в пункт 1
x12+x32+x42=1
Условие въезда в пункт 2
x13+x23+x43=1
Условие въезда в пункт 3 х31
x14+x24+x34=1
Условие въезда в пункт 4
хij
>=0; Условие не отрицательности решения i=1…4;
j=1…4
Требование
минимальной продолжительности маршрута запишем в виде ЦФ, где коэффициенты при
переменных – это время в пути между пунктами.
F=10x12+25x13+25x14+x21+10x23+15x24+8x31+9x32+20x34+14x41+10x42+24x43
Результаты решения
на компьютере:
х1 х4 х2 х3 х1 маршрут
движения
25 10 10 8 время
в пути = 53
Максимальной
продолжительности путь.
х1 х3 х2 х4 х1 маршрут
движения
25 9 15 14 время
в пути = 63
К
задачам коммивояжера можно свести значительное число различных практических
задач:
Þ
выбор маршрута при развозке грузов;
Þ
последовательность обработки различных
деталей на одном станке;
Þ
проектирование технологических процессов и
т.д.
Вы узнали:
Þ
что такое
сеть, структура сети и параметры дуг;
Þ
как
решать такого класса задачи
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.