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

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


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


2


3


hi


5


0


да


0

6 да 21    21


hi = 21


Константа приведения матрицы h = 21+ 0 = 21, поэтому оценка концевой вершины по правой ветви будет равна 92 (рис. 3.9).


На каждой итерации осуществляется ветвление концевой вершины с наименьшей оценкой (так как определяется маршрут с наименьшей стоимостью). Среди концевых вершин (см. рис. 3.9) наименьшую оценку имеет вершина по левой ветке с оценкой 80: min {80; 83; 96; 115; 92} = 80, поэтому на следующей итерации следует ветвить именно эту вершину. Для этого вернемся к матрице, «породившей» ветвление на подмножества, содержащие дугу (1;6) и не содержащие эту дугу, и повторим все рассуждения. Матрица, «породившая» это ветвление, есть матрица размерности 6*6. Следует брать неприведенную матрицу и запретить в ней движение по дуге (1;6).


Итерация 6. Приведем матрицу 6*6 по строкам:


1


2


3


4


5


6


hi


1


x


31


40


25


47


да


25


2


22


x


44


26


20


22


20


3


37


17


x


43


11


55


11


4


11


35


9


x


40


26


9


5


50


4


11


34


x


36


4


6

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