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

Таблица 6

Звено (i,j)	1,4	2,4	3,6	4,1	4,2	5,6	6,2	6,3	6,5
Фij =Ai+Bj	10	1	5	1	0	2	0	9	2

Из табл. 6 замечаем, что {Ф_ij}=Ф₁₄=10. Следовательно, в качестве опорного звена выбираем (1,4).

Если максимальное значение Ф_ij имеет несколько звеньев, то в маршрут можно включать любое из них.

4. Пересчет нижней границы стоимости. Мы выяснили, что на данном (первом) шаге выгоднее всего взять звено (1,4). Но мы можем его и не брать, предполагая, что в дальнейшем это даст большой выигрыш. Если в маршруты мы не включаем звено (1,4), что записывается Т:

– с чертой сверху, то нижней границей будет

Z(T:

)= 48+10 = 58 .

Действительно, поскольку штраф рассчитывается по минимальным значениям элементов матрицы, то меньше, чем Ф₁₄ мы не заплатим, если возьмем какое-либо другое звено в Т. А какой-то элемент из строки 1 и столбца 4 обязательно должен войти в маршрут: мы обязательно должны куда-то улететь из пункта 1 и откуда-то прилететь в пункт 4.

5. Для определения нижней границы стоимости маршрутов, включающих звено (1,4), надо преобразовать матрицу стоимости. Раз звено (1,4) включено в маршрут, то из дальнейшего рассмотрения надо исключить строку 1 и столбец 4 (кроме как в пункт 4 из пункта 1 мы никуда не полетим), а также обратный перелет - звено (4,1), поэтому принимается С₄₁=

. Вычеркиваем в табл.5 строку 1 и столбец 4 и получаем табл.7.

Таблица 7

Пункты	1	2	3	5	6
2	1		15	29	29
3	15	13		5	0
4		0	9	2	2
5	2	41	22		0
6	13	0	0	0

Проведем редукцию табл.7, как в п.2, и укажем А_i, В_j. Получаем табл.8.

Таблица 8

Пункты	1	2	3	5	6	Сi	Аi
2	0		14	28	28	1	14
3	15	13		5	0	0	5
4		0	9	2	2	0	2
5	2	41	22		0	0	2
6	13	0	0	0		0	0
Qj	0	0	0	0	0	Н1=1
Bj	2	0	9	2	0

Новая нижняя граница для Т , включающего (1,4) равна:

Z(T:1,4) = 48 + 1 = 49 .

Теперь можно приступить к изображению дерева решений (пока содержащего две короткие ветви) (рис.1).

Рис.1

В узлах дерева указаны звенья, включенные или нет в маршруты, и рядом – нижние границы этих маршрутов.

6. Проводится вторая итерация решения во второй матрице (табл.8). Как в п.3 рассчитываются штрафы Ф_ij, (табл.9).

Таблица 9

( i, j)	2,1	3,6	4,2	5,6	6,2	6,3	6,5
Фij	16	5	2	2	0	9	2

Максимальный штраф у звена (2,1): Ф₂₁=16.

Следовательно, после (1,4) выбирается (2,1).

Новая нижняя граница для Т:

равна:

Z(T :

) = 49 + 16 = 65 .

Новая нижняя граница для (T:

) находится, как в п.5: в табл.8 вычеркивается строка 2 и столбец 1, кроме того, С₁₂= (но в таблице его не будет).

Теперь необходимо указать на появление новой процедуры – проверки оставшихся звеньев на возможность подмаршрутов, т.е. маршрутов, включающих не все узлы (пункты). В нашем случае подмаршрутом может быть следующий: (1,4), (4,2), (2,1) для уже выбранных звеньев (1,4) и (2,1). Чтобы его исключить, надо сделать звено (4,2) запрещенным, а для этого положить С₄₂=

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

В результате указанных действий приходим к третьей матрице решений (табл.10).

Таблица 10

Пункты	2	3	5	6
3	13		5	0
4		9	2	2
5	41	22		0
6	0	0	0

Далее нужно провести ее редукцию, которая дает для маршрутов, включающих звено (2,1), нижнюю границу Н+Н₁=49+2=51 и т.д.