5.7. Задача о кратчайшем пути

Частным случаем задачи об оптимальном потоке является задача по­строения кратчайшего пути между двумя вершинами пути. Пусть дан граф G=[N, A] , каждой дуге которого поставлено в соответствие чис­ло С(х, у), называемое длиной дуги (х, у). Выделяются две вершины гра­фа - s и t . Требуется найти путь наименьшей длины, ведущий из вершины s в вершину t. При этом длина произвольного пути определяется следующим образом:

.

Данная задача может быть сформулирована как задача об оптимальном пото­ке. Ставится задача определения потока, минимизирующего функционал

, где .

Рассмотрим теперь сеть, вершина s которой является источником еди­ничной интенсивности, t - стоком единичной интенсивности, остальные вершины - нейтральные. Дугам приписываются неограниченные пропускные способности, а стоимость перевозок по дуге полагается равной длине дуги. Для потока в рассматриваемой сети

Пусть имеется некоторый конечный граф G = [N ={1,2,…,n}, а], каж­дой вершине i которого поставлено в соответствие некоторое число , назы­ваемое интенсивностью потока. Вершины назовем источниками, нейтраль­ными вершинами и стоками, если , и соответственно. По­током в полученной сети назовем совокупность величин , удов­летворяющих соотношениям

,

.

5.8. Задача коммивояжера

Пример. Пусть имеются пять пунктов, соединенных между собой дорогами так, что из любого пункта можно проехать в любой другой пункт (рис. 11). Известно время перевозки из пункта i в пункт j (табл. 17).

Таблица 17

Из пункта 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

Рис. 11

Требуется найти такой маршрут, начинающийся в дан­ном пункте, проходящий через все пункты и заканчиваю­щийся в пункте выезда, чтобы его продолжительность была наименьшей.

Решение. Для решения этой задачи необходимо соста­вить математическую модель. Введем обозначения: i и j; - номера пунктов выезда и въезда; tij - время переезда из пункта i в пункт j. Из табл. 17 видно, что tij в общем случае может быть не равно времени переезда в обратном направлении (например, когда один пункт на вершине горы, а другой - у ее подножия). Введем булевы переменные:

Составим модель (рис. 12).

Рис. 12

Из п. 1 можно выехать в любой из п. 2 или 5, или 3, или 4, или остаться в п. 1. Но при этом можно выехать только в одном единственном на­правлении. Это условие можно записать так:

или

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

Условие въезда в п. 1 аналогично условию выезда из п. 1 (рис. 12). Требование минимальной продолжительно­сти маршрута запишется в виде целевой функции:

где t_ij берутся из исходной таблицы, а δ_ij - искомые пере­менные.

Тогда всю задачу можно сформулировать:

В результате решения системы (*) получим (рис. 13) следующие значения остальные

Переходя от частной к общей постановке, задачу комми­вояжера можно сформулировать как:

Рис. 13