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

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

Так как осуществлен переход к другой ветви, то придется формировать новый маршрут. Новое ветвление — это ветвление концевой вершины с оценкой 83 — разбиение множества всех маршрутов, содержащих дугу (1;6) и не содержащих дугу (2;4) (рис. 3.12).

Рис. 3.12


Итерация 9. В матрице 5×5 вычеркнем строку и столбец, образовавшие дугу ветвления (6;4), запретим движение по дуге (4;1) для предотвращения преждевременного цикла и приведем новую матрицу 4х4, рассчитав константу приведения h :


1


2


3


5


2


0


x


24


0


3


24


6


x


0


4


да


26


0


31


5


44


0


7


x


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


На рис. 3.13 показано ветвление с учетом этой константы. Очевидно, что наименьшая оценка концевых вершин равна 83, поэтому продолжаем ее ветвление.

Рассчитаем оценку 0j каждого нуля в приведенной матрице: max 0j = 043 = 33.


1


2


3


5


Oij


2


0


x


24


0


0+24=24


0+0=0


3


24


6


x


0


6+0=6


4


26


0


31


26+7=33


5


44


0


7


x


7+6=13

На рис. 3.14 показано ветвление, соответствующее найденной оценке, и маршрут.

Рис. 3.14

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