Задача по системному анализу

Автор работы: Пользователь скрыл имя, 03 Сентября 2013 в 18:18, контрольная работа

Краткое описание

Работа содержит условие и решение задачи коммивояжера с матрицей расстояний.

Прикрепленные файлы: 1 файл

системный анализ.doc

— 100.50 Кб (Скачать документ)

                             Системный анализ

Решить задачу коммивояжера с матрицей расстояний.

 

Решение

Возьмем в качестве произвольного  маршрута: 
X= (1,2);(2,3);(3,4);(4,5);(5,1) 
Тогда F(X0) = 23 + 16 + 5 + 1 + 5 = 50 
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент. 
d= min(j) dij 

i j

1

2

3

4

5

di

1

23

24

7

27

7

2

14

16

10

5

5

3

22

15

5

22

5

4

20

18

22

1

1

5

5

8

7

12

5


 

Вычтем  dиз элементов рассматриваемой строки.

Получим. 

i j

1

2

3

4

5

1

16

17

0

20

2

9

11

5

0

3

17

10

0

17

4

19

17

21

0

5

0

3

2

7


 

Операцию редукции проводим по столбцам, и находим минимальный  элемент: 
d= min(i) dij 

i j

1

2

3

4

5

1

16

17

0

20

2

9

11

5

0

3

17

10

0

17

4

19

17

21

0

5

0

3

2

7

dj

0

3

2

0

0


 

В итоге  получаем  редуцированную матрицу, где величины dи djназываются константами приведения.

 

i j

1

2

3

4

5

1

13

15

0

20

2

9

9

5

0

3

17

7

0

17

4

19

14

19

0

5

0

0

0

7


 

Сумма констант приведения определяет нижнюю границу H:

H = ∑d+ ∑dj

H = 7+5+5+1+5+0+3+2+0+0 = 28

Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.

D является матрицей nxn с неотрицательными элементами dij >=0

Длина маршрута определяется выражением:

F(Mk) = ∑dij

Причем каждая строка и столбец входят в маршрут  только один раз с элементом dij 

Шаг 1 - определим ребро ветвления.

i j

1

2

3

4

5

di

1

13

15

0(13)

20

13

2

9

9

5

0(5)

5

3

17

7

0(7)

17

7

4

19

14

19

0(14)

14

5

0(9)

0(7)

0(9)

7

0

dj

9

7

9

0

0

0




Разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). 
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках. 

 

 

 

 

 

 

 

 

 

 

d(1,4) = 13 + 0 = 13;

d(2,5) = 5 + 0 = 5;

d(3,4) = 7 + 0 = 7;

d(4,5) = 14 + 0 = 14;

d(5,1) = 0 + 9 = 9;

d(5,2) = 0 + 7 = 7;

d(5,3) = 0 + 9 = 9. 
Наибольшая сумма констант приведения равна (14 + 0) = 14 для ребра (4,5), следовательно, множество разбивается на два подмножества (4,5) и (4*,5*). 
Нижняя граница гамильтоновых циклов этого подмножества: 
H(4*,5*) = 28 + 14 = 42 
Исключение ребра (4,5) проводим путем замены элемента d45 = 0 на ∞, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,5*), в результате получим редуцированную матрицу. 

i j

1

2

3

4

5

di

1

13

15

0

20

0

2

9

9

5

0

0

3

17

7

0

17

0

4

19

14

19

14

5

0

0

0

7

0

dj

0

0

0

0

0

14


 

Включение ребра (4,5) проводится путем исключения всех элементов 4-ой строки и 5-го столбца, в которой элемент d54 заменяем на ∞, для исключения образования негамильтонова цикла.

В результате получим другую сокращенную матрицу (4 x 4), и применим операцию привидения.

Сумма констант приведения сокращенной матрицы: 
∑d+ ∑d= 5

После операции приведения сокращенная матрица будет иметь  вид: 

i j

1

2

3

4

di

1

13

15

0

0

2

9

9

5

5

3

17

7

0

0

5

0

0

0

0

dj

0

0

0

0

5


 

Нижняя граница подмножества (4,5) равна:

H(4,5) = 28 + 5 = 33 ≤ 42

Нижняя граница этого подмножества (4,5) меньше, чем подмножества (4*,5*), ребро (4,5) включаем в маршрут с новой границей H = 33

Шаг 2 - определим ребро ветвления.

Разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). 
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на ∞ (бесконечность) и определяем для них сумму образовавшихся констант приведения. 
d(1,4) = 13 + 0 = 13;

d(2,4) = 4 + 0 = 4;

d(3,4) = 7 + 0 = 7;

d(5,1) = 0 + 4 = 4;

d(5,2) = 0 + 7 = 7;

d(5,3) = 0 + 4 = 4. 
Наибольшая сумма констант приведения равна (13 + 0) = 13 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*). 
Нижняя граница гамильтоновых циклов этого подмножества: 
H(1*,4*) = 33 + 13 = 46 
Исключение ребра (1,4) проводим путем замены элемента d14 = 0 на ∞, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.

i j

1

2

3

4

di

1

M

13

15

M

13

2

4

M

4

0

0

3

17

7

M

0

0

5

0

0

0

M

0

dj

0

0

0

0

13


 

Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d41заменяем на ∞, для исключения образования негамильтонова цикла.

В результате получим  другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы: 
∑d+ ∑d= 11

i j

1

2

3

di

2

4

M

4

4

3

17

7

M

7

5

0

0

0

0

dj

0

0

0

11

Информация о работе Задача по системному анализу