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

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


Требуется


j


i


1


2


3


4


5


6


маршрут/цикл,


1


x


31


40


25


47


12


печивает мини-


2


22


x


44


26


20


22


мость проезда. ны быть выпол-


3


37


17


x


43


11


55


щие условия:


4


11


35


9


x


40


26


1) маршрут


5


50


4


11


34


x


36


замкнутым, т.е.


6


18


7


28


25


26


x

читься в том же


найти    такой


который обес-мальную стои-При этом долж-нены следую-


должен    быть


должен законгороде, из кото-


рого было начато движение;


2) маршрут должен проходить через все города, но каждый город необходимо пройти один


раз.


Пример такого маршрута, удовлетворяющего этим условиям: 1 — 3 — 2 — 5 — 6 — 4 — 1 или, что то же самое,


(1;3) — (3;2) — (2;5) — (5;6) — (6;4) — (4;1).


Стоимость такого маршрута будет равна:


L = 40 + 17 + 20 + 36 + 25 + 11 = 149 у.е.


Метод ветвей и границ может быть алгоритмизирован, так как состоит из конечного числа итераций. На каждой итерации осуществляется две процедуры: приведение матрицы и ветвление матрицы. При этом на каждой итерации определяются нижняя и верхняя границы, в пределах которых содержится оптимальное значение целевой функции.

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