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

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

9


0


21


12


19


Замечание. После определения дуги маршрута, в матрице стоимостей вычеркивается строка и столбец, которые образовали эту дугу. Однако нумерация городов после вычеркивания не меняется.


Ветвление матрицы. Множество всех маршрутов разбивается на два подмножества: содержащее и не содержащее выбранную дугу (i; j).


Разбиение на подмножества или ветвление всегда происходит от концевой вершины с минимальной оценкой. Начало ветвления — множество всех маршрутов — это вершина, оценка которой есть константа приведения h0 начальной матрицы.


При ветвлении оценка вершины по правой ветке увеличивается на константу приведения h, по левой увеличивается на 0j (рис. 3.1,а). На этапе ветвления одновременно формируется и маршрут (рис. 3.1,6).


а)



б)



Маршрут



UjJ



GZD


Рис. 3.1



В рассматриваемом примере начальная вершина имеет оценку h0 = h1 + h2= 71, первая дуга маршрута (1;6) (рис. 3.2).


Получив дугу маршрута, необходимо запретить путь, предотвращающий образование «преждевременного цикла». В данном случае следует запретить движение из города 6 в город 1. Поэтому в матрице 5*5 запрещаем (6;1). Запрет можно обозначить символом бесконечности да :


1


2


3


4


5


2


0


x


24


0


0


3


24


6


x


26


0


4


0


26


0


x


31


5


44


0


7


24


x


6


да


0


21


12


19

Итерация 2. Осуществим приведение матрицы по строкам:

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