Методические указания по изучению дисциплины и выполнению контрольной работы Для студентов заочного факультета всех специализаций (стр. 3 из 6)

1. Приступим к решению. Определим верхнюю границу маршрута Z_B(T) (вообще-то, ее вычисление не обязательно, но в некоторых случаях позволяет сократить расчеты). Верхняя граница – это стоимость взятого наугад маршрута. Пусть он будет состоять из звеньев (1,4)(4,5)(5,3)(3,6)(6,2)(2,1). Тогда в соответствии с табл.2 Z_В(T) = 16+18+27+0+5+7=73. Отсюда заключаем, что стоимость оптимального маршрута

.

2. Найдем нижнюю границу всего маршрута Н . Для этого проводится так называемая редукция строк и столбцов матрицы (см. табл.2). Редукция строк заключается в вычитании из каждой строки матрицы числа, равного минимальному значению элемента этой строки. В первой строке – это число С₁=16. Результат редукции представлен в табл.3.

Таблица 3

Пункты	1	2	3	4	5	6	Сi
1		11	27	0	14	10	16
2	6		15	0	29	29	1
3	20	13		35	5	0	0
4	5	0	9		2	2	16
5	7	41	22	43		0	5
6	18	0	0	4	0		5

Бесконечные стоимости C₁₁ =C₂₂ =…=C₆₆ =

– это математический прием, запрещающий перелет к самому себе.

В результате редукции в каждой строке будет не меньше одного нулевого элемента.

Аналогичным образом проводится редукция столбцов, в результате которой в каждом столбце будет, по крайней мере, по одному нулевому элементу (табл.4).

Таблица 4

Пункты	1	2	3	4	5	6	Сi
1		11	27	0	14	10	16
2	1		15	0	29	29	1
3	15	13		35	5	0	0
4	0	0	9		2	2	16
5	2	41	22	43		0	5
6	13	0	0	4	0		5
Qi	5	0	0	0	0	0	H=48

После редукции в каждой строке и столбце будет не меньше, чем по одному нулю. Если бы вдруг оказалось в каждой строке и столбце ровно по одному нулю, то они образовали бы тогда замкнутый маршрут с очевидно нулевой редуцированной стоимостью. А чтобы вернуться к настоящей стоимости, нужно к этой нулевой стоимости прибавить то, что мы уже вычли при редукции, т.е. нижняя граница вычисляется по формуле:

.

Это легко понять, если учесть, что в каждой строке и в каждом столбце есть только один элемент любого маршрута Т.

3. В табл.4 в строках и столбцах есть по несколько элементов с C_ij=0, поэтому необходимо рассмотреть варианты и сделать выбор, какое первое звено включить в маршрут. Выбирается то звено, которое имеет минимальную стоимость и максимальное значение штрафа Ф_ij . Штраф определяет ту цену, которую мы заплатим, если не включим звено (i, j) в маршрут Т. Поэтому если мы включим звено (i, j), которое назовем опорным, а не включим какое-то другое, то за это другое заплатим меньший штраф.

Штраф вычисляется по формуле

Ф_ij =A_i+B_j ,

где А_i=min

, j-кроме опорного; В_j= min , i-кроме опорного.

На каждом шаге мы выбираем звено с максимальным выигрышем (min{C_ij} и max{Ф_ij}). Поскольку min{C_ij} – это обязательно ноль, полученный в результате редукции, то A_i и B_j – это следующие минимальные после нуля числа. Если в строке несколько нулей, то А_i = 0. Аналогично обстоит дело и с В_j . Покажем это для нашего примера. Рассчитаем штраф для всех звеньев, претендующих на то, чтобы быть включенными в маршрут Т . Это все звенья с нулевой стоимостью (табл.5).

Таблица 5

Пункты	1	2	3	4	5	6	Сi	Аi
1		11	27	0	14	10	16	10
2	1		15	0	29	29	1	1
3	15	13		35	5	0	0	5
4	0	0	9		2	2	16	0
5	2	41	22	43		0	5	2
6	13	0	0	4	0		5	0
Qj	5	0	0	0	0	0	H=48
Bj	1	0	9	0	2	0

По найденным A_i и B_j рассчитываем штрафы Ф_ij для звеньев с нулевой стоимостью, т.е. для (1,4), (2,4), (3,6) и т.д. Эти звенья с полученными штрафами сведем в табл. 6.