Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


Итерация 10. В матрице 4^4 удаляем строку и столбец, соответствующие дуге (4;3), и запрещаем движение (3;1), переходим к матрице на размерность меньше. Новую матрицу 3х3 приводим по строкам и столбцам:


В этой матрице также в каждой строке и каждом столбце есть хотя бы один ноль, поэтому ее константа приведения равна нулю.


Это означает, что концевая вершина будет иметь оценку 83, она наименьшая, значит, ветвить следует эту вершину (рис. 3.15).

Рис. 3.15


Рассчитаем    оценку    каждого    нуля    в    приведенной    матрице:


max 0у = 052 = 50.


1


2


5


ва


2


0


x


0


0+44=44


0+0=0


3


6


0


6+0=6


5


44


0


x


44+6=50

Следующее ветвление — ветвление конечной вершины с оценкой 83, следующая дуга маршрута — дуга (5;2) (рис. 3.16).

Рис. 3.16



1


5


2


0


да


3


да


0


Итерация 11. Перейдем к матрице 2^2, вычеркнув строку и столбец, соответствующие дуге (5;2). В новой матрице запретим движение (2;5) и определим константу приведения h.


Очевидно, что константа приведения h этой матрицы равна нулю. Значит, оценка концевой вершины будет равна 83. Наименьшая из оценок концевых вершин — 83 (рис. 3.17).

Рис. 3.17


Очевидно, что для замыкания маршрута необходимы дуги (3;5) и (2;1). Действительно, в приведенной матрице 2×2 на соответствующих позициях стоят нули. Это позволяет судить о том, что маршрут замкнется.


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

Скачать в pdf «Экстремальные модели менеджмента и экономики»