3. Методические указания к выполнению лабораторной работы

Поясним процесс вычислений, определив кратчайшее расстояние от пункта А₁ до всех остальных по сети, представленной на рис. 6 [13]. Цифры обозначают расстояния между соседними пунктами. Используя данные сети, составляем табл. 3 и приступаем к определению индексов. Индекс u_i принимаем равным нулю. Далее в соответствии с правилом (6) находим клетки А₁ А_2, А₁ А₄ и А₁ А₆ индексы υ₂, υ₄ и υ₆, а затем индексы u₂, u ₄ и u ₆:

υ₂= u₁+ l₁₂= 0+12=12, u₂= υ₂=12,

υ₄= u₁+ l₁₄= 0+4=4, u₄= υ₄=4,

υ₆= u₁+ l₁₆= 0+8=8, u₆= υ₆=6.

Найденные индексы записываем в таблицу (см. табл. 3), после чего вычисляем индекс υ₃ через заполненную клетку А₂ А₃ с уже известным индексом u₂: υ₃= u₂+ l₂₃=12+6=18 и u₃= υ₃=18. Записав индексы υ₃ и u₃ в таблицу, находим индексы u₅ и υ₅:

υ₅=min (u₂+ l₂₅=12+8=20; u₃+ l₃₅=18+6=24;

u₄+ l₄₅=4+7=11; u₆+ l₆₅=8+8=16)=11,

u₅= υ₅=11.

Таблица 3

Пункт	Вспомо- гатель- ные	Пункт
		А1	А2	А3	А4	А5	А6	А7	А8
	строка столбец	0	12		4		8
А1	0		12		4		8
А2	12	12		6	7	8
А3			6			6		9
А4	4	4	7			7	6
А5			8	6	7		8	5	7
А6	8	8			6	8			7
А7				9		5			6
А8						7	7	6

Результаты вычислений на данной стадии представлены в табл. 4. Теперь можно определить индекс υ₇ (табл. 5), а затем и υ₈ (табл. 6):

υ₇=min (u₃+ l₃₇=18+9=27; u₅+ l₅₇=11+5=16) =16,

u₇= υ₇=16.

υ ₃=min (u₃+ l₅₈=11+7=18; u₆+ l₆₈=8+7=15) =15;

u₇+ l₇₈=16+6=22) = 15,

u ₈=15.

Таблица 4

Пункт	Вспомо- гатель- ные	Пункт
		А1	А2	А3	А4	А5	А6	А7	А8
	строка столбец	0	12	18	4	11	8
А1	0		12		4		8
А2	12	12		6	7	8
А3	13		6			6		9
А4	4	4	7			7	6
А5	11		8	6	7		8	5	7
А6	8	8			6	8			7
А7	16			9		5			6
А8						7	7	6

Поскольку все индексы найдены, проверяем каждую заполненную клетку таблицы, сравнивая её l_ij (υ_j- u_j). В нашей таблице (см. табл. 6)

l₄₂< υ₂- u₄, т.е. 7<12-4, следовательно, данное решение не является оптимальным.

Таблица 5

Пункт	Вспомо- гатель- ные	Пункт
		А1	А2	А3	А4	А5	А6	А7	А8
	строка столбец	0	12	18	4	11	8	16
А1	0		12		4		8
А2	12	12		6	7	8
А3	18		6			6		9
А4	4	4	7			7	6
А5	11		8	6	7		8	5	7
А6	8	8			6	8			7
А7	16			9		5			6
А8						7	7	6

Таблица 6

Пункт	Вспомо- гатель- ные	Пункт
		А1	А2	А3	А4	А5	А6	А7	А8
	строка столбец	0	12	18	4	11	8	16	15
А1	0		12		4		8
А2	12	12		6	7	8
А3	18		6			6		9
А4	4	4	7			7	6
А5	11		8	6	7		8	5	7
А6	8	8			6	8			7
А7	16			9		5			6
А8						7	7	6

Рассчитываем новый индекс υ ₂ по формуле (6): υ₂ = u₄+ l₄₂ = 4+7 = 11 и

u₂= υ₂=11 (табл. 7). Проверка показывает, что и это решение не является оптимальным, поскольку l₅₃< υ₃- u₅ (6<18-11). Определив новый индекс

u₃= υ₅₃=11+6=17 и индекс u₃= υ₃=17, получаем еще одно решение (табл. 8). Поскольку здесь соблюдается условие оптимальности (8), т.е. все расстояния меньше разности соответствующих им индексов, решение является оптимальным и, следовательно, кратчайшее расстояние от А₁ до всех остальных пунктов задано числами υ₂, υ₃, υ₄, υ₅, υ₆, υ₇ и υ₈,т.е. от А₁ до А₂ –

11 км, до А₃ – 17 км, до А₄ – 4 км, до А₅ – 11 км, до А₆ – 8 км, до А₇ – 16 км

и до А₈ – 15 км.

Таблица с оптимальным решением дает не только кратчайшие расстояния между А₁ и А_j пунктами, но и последовательность прохождения промежуточных пунктов, т.е. кратчайший маршрут. Пусть необходимо определить кратчайший маршрут из пункта А₁ в пункт А₇. Порядок работы следующий.

Таблица 7

Пункт	Вспомо- гатель- ные	Пункт
		А1	А2	А3	А4	А5	А6	А7	А8
	строка столбец	0	11	18	4	11	8	16	15
А1	0		12		4		8
А2	11	12		6	7	8
А3	18		6			6		9
А4	4	4	7			7	6
А5	11		8	6	7		8	5	7
А6	8	8			6	8			7
А7				9		5			6
А8						7	7	6

Таблица 8

Пункт	Вспомо- гатель- ные	Пункт
		А1	А2	А3	А4	А5	А6	А7	А8
	строка столбец	0	11	17	4	11	8	16	15
А1	0		12		4		8
А2	11	12		6	7	8
А3	17		6			6		9
А4	4	4	7			7	6
А5	11		8	6	7		8	5	7
А6	8	8			6	8			7
А7	16			9		5			6
А8	15					7	7	6

В столбце А₇, соответствующем конечному пункту маршрута, отыскиваем заполненную клетку, у которой расстояние равно разности индексов столбца и строки ( lij = Vj - Ui). Такая клетка в рассматриваемом столбце всегда имеется (если таких клеток в столбце несколько, можно принять любую из них), в нашем примере – это А₅ А₇. Она обозначает последнее звено искомого маршрута – звено А₅ А₇. Для определения предпоследнего звена эта операция повторяется для пункта А₅, который является конечным для предпоследнего звена. В столбце А₅ расстояние равно разности индексов υ и u в клетке А₄ А₅ (l₄₅ = υ₅ – u₄. т.е. 7 = 11-4). Таким образом, предпоследним звеном маршрута будет А₄ А₅. Повторив процесс для пункта А₄, находим звено А₁ А₄, предшествующее звену А₄ А₅. В результате кратчайший маршрут из пункта А₁ в пункт А₇ найден:

А_i→А₄→А₅→А₇.

Итак, мы определили кратчайшее расстояние от пункта А₁ до всех остальных пунктов А₂,А₃,…А₈. Проделав теперь показанные вычисления последовательно для каждого пункта А₂,А₃,…А₈, принимая последовательно u₂=0, затем u₃=0 и т.д., получим матрицу ║l_ij║ кратчайших расстояний по сети между пунктами А_i и А_j. В табл. 9 и 10 для примера приведены оптимальные решения соответственно для пункта А₂ и А₃. В соответствии с ними кратчайшее расстояние от А₂ до А₁ – 11 км, до А₃ – 6 км, до А₄ – 7 км, до А₅ – 8 км, до А₆ – 13 км, А₇ – 13 км и до А₈ – 15 км (см. клетки вспомогательной строки в табл. 10). Кратчайшее расстояние от А₃ до А_i 17 км, до А₂ – 6 км, до А₄ -13 км, до А₅-6 км, до А₆ – 14 км, до А₇ – 9 км, до А₈ – 13 км.

Таблица 9

Пункт	Вспомо- гатель- ные	Пункт
		А1	А2	А3	А4	А5	А6	А7	А8
	строка столбец	11	0	6	7	8	13	13	15
А1	11		12		4		8
А2	0	12		6	7	8
А3	6		6			6		9
А4	7	4	7			7	6
А5	8		8	6	7		8	5	7
А6	13	8			6	8			7
А7	13			9		5			6
А8	15					7	7	6

Таблица 10

Пункт	Вспомо- гатель- ные	Пункт
		А1	А2	А3	А4	А5	А6	А7	А8
	строка столбец	17	6	0	13	6	14	9	13
А1	17		12		4		8
А2	6	12		6	7	8
А3	0		6			6		9
А4	13	4	7			7	6
А5	6		8	6	7		8	5	7
А6	14	8			6	8			7
А7	9			9		5			6
А8	13					7	7	6