Визначення!!! Приведення матриці С може бути здійснено наступним чином:

Приведення матриці С може бути здійснено наступним чином:

Крок1 -Приведення по строкам. По кожній строчці і знайдемо найменший елемент min Cij = ai. Тоді при переході до приведеної матриці . Ця операція потребує, на наш погляд, пояснень. Здавалось би логічним. виключати найбілішу відстань згідно з умовами постанови задачі, але у такому випадку всі останні елементи строчки будуть мати від’ємні значення, що порушує обмеження (4). Обрані значення ai відображаються у заключному стовбці приведеної матриці табл.2.

Крок 2. У кожному стовбці j, який не має нульових елементів знаходимо найменше значення Cij= bj, яке відображаємо у заключній строчці bj приведеної матриці,табл..3.

Тоді Результати першого кроку відображено в табл..2

Порти виходу	ИСХОДНАЯ ТАБЛИЦА
Одесса (1)	Афины(2)	Неаполь (3)	Барселона (4)	Валлетта (5)	Алек-я (6)	Хайфа (7)	Стамбул (8)
Одеса (1)								298
Афіни (2)							285
Неаполь (3)					325
Барселона (4)			558
Валлетта (5)
Александрія (6)
Хайфа (7)
Стамбул (8)

Табл.2

Матриця, приведена по рядках (строках)

									ai
			0
		50
	51
bj

Результати кроку 2 відображено в табл.3, яка представляє першу приведену матрицю G0.

Табл.3 Приведена матриця G0

									ai
								0 - 316
							0 - 69
				0 - 113	0-113
			0-113
			0-113
							0-234
		0 - 57				0-234
	0-316						0 - 0
bj

Згідно з теоремою Ейлера, яка стверджує, що коли ми відраховуємо любу константу із усіх елементів строки чи стовпця матриці Сij, ми залишаємо мінімальний тур мінімальним.

На пересечінні ітогової строки i та стовбця j знаходиться величина, яка має назву – «сума приводящих констант», яка дорівнює:

(4)

Дані, наведені у таблиці 3, визначимо як матрицю G0, що визначає нову задачу комівояжера, яка в якості оптимального варіанту має ту саму послідовність портів.

Між величинами L, існує наступне співвідношення.

L= + S (5)

Таким чином, L , що визначає S як нижню межу цільової функції задачі комівояжера.

Знаходимо ступені кожного з нулів повністю приведеної матриці.

Дата добавления: 2015-06-27