asyan.org
добавить свой файл
1 2 ... 6 7
Візьмемо як довільного маршруту:

X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,7);(7,8);(8,9);(9,10);(10,1)

Тоді F(X0) = 1 + 1 + 0 + 5 + 0 + 0 + 0 + 0 + 0 + 1 = 8

Для визначення нижньої межі більшості скористаємося операцією редукції або приведення матриці по рядках, для чого необхідно в кожному рядку матриці D знайти мінімальний елемент.

di = min(j) dij

i j


1


2


3


4


5


6


7


8


9


10


di


1


M


1


2


3


4


5


6


7


8


9


1


2


9


M


1


2


3


4


5


6


7


8


1


3


8


8


M


0


1


2


3


4


5


6


0


4


7


7


6


M


5


4


3


2


1


0


0


5


6


6


5


0


M


0


1


2


3


4


0


6


5


5


4


1


0


M


0


0


0


0


0


7


4


4


3


2


1


0


M


0


0


0


0


8


3


3


2


3


2


0


0


M


0


0


0


9


2


2


1


4


3


0


0


0


M


0


0


10


1


1


0


5


4


0


0


0


0


M


0


Потім відняти його з елементів розглянутої рядка. У зв'язку з цим у знову отриманої матриці в кожному рядку буде як мінімум один нуль.

i j


1


2


3


4


5


6


7


8


9


10


1


M


0


1


2


3


4


5


6


7


8


2


8


M


0


1


2


3


4


5


6


7


3


8


8


M


0


1


2


3


4


5


6


4


7


7


6


M


5


4


3


2


1


0


5


6


6


5


0


M


0


1


2


3


4


6


5


5


4


1


0


M


0


0


0


0


7


4


4


3


2


1


0


M


0


0


0


8


3


3


2


3


2


0


0


M


0


0


9


2


2


1


4


3


0


0


0


M


0


10


1


1


0


5


4


0


0


0


0


M


Потім таку ж операцію редукції проводимо по стовпцях, для чого в кожному стовпці знаходимо мінімальний елемент:

dj = min(i) dij

i j


1


2


3


4


5


6


7


8


9


10


1


M


0


1


2


3


4


5


6


7


8


2


8


M


0


1


2


3


4


5


6


7


3


8


8


M


0


1


2


3


4


5


6


4


7


7


6


M


5


4


3


2


1


0


5


6


6


5


0


M


0


1


2


3


4


6


5


5


4


1


0


M


0


0


0


0


7


4


4


3


2


1


0


M


0


0


0


8


3


3


2


3


2


0


0


M


0


0


9


2


2


1


4


3


0


0


0


M


0


10


1


1


0


5


4


0


0


0


0


M


dj


1


0


0


0


0


0


0


0


0


0


Після вирахування мінімальних елементів отримуємо повністю скороченої матрицю, де величини di и dj називаються константами приведення.

i j


1


2


3


4


5


6


7


8


9


10


1


M


0


1


2


3


4


5


6


7


8


2


7


M


0


1


2


3


4


5


6


7


3


7


8


M


0


1


2


3


4


5


6


4


6


7


6


M


5


4


3


2


1


0


5


5


6


5


0


M


0


1


2


3


4


6


4


5


4


1


0


M


0


0


0


0


7


3


4


3


2


1


0


M


0


0


0


8


2


3


2


3


2


0


0


M


0


0


9


1


2


1


4


3


0


0


0


M


0


10


0


1


0


5


4


0


0


0


0


M


Сума констант приведення визначає нижню межу H:
H = 1+1+0+0+0+0+0+0+0+0+1+0+0+0+0+0+0+0+0+0 = 3

Елементи матриці dij відповідають відстані від пункту i до пункту j.

Оскільки в матриці n міст, то D є матрицею nxn з невід'ємними елементами dij >=0

Кожен допустимий маршрут являє собою цикл, за яким комівояжер відвідує місто тільки один раз і повертається у вихідний місто.

Довжина маршруту визначається виразом:
Причому кожен рядок і стовпець входять в маршрут тільки один раз з елементом dij .



следующая страница >>