Тестовые
примеры 
Простейшая
задача размещения
Тестовые
примеры
Главная страница
библиотеки
Простейшая задача размещения
Примеры на совершенных кодах
Примеры из данного класса построены с помощью бинарных совершенных кодов с расстоянием 3. Для кодов размерности k = 2l – 1, l = 2, 3, ... генерируется простейшая задача размещения с n = 2k предприятиями и m = n потребителями. Предприятие i может обслуживать потребителя j, если расстояние между соответствующими точками в гиперкубе E k не превосходит единицы. Стоимость открытия любого предприятия равна 3000. Матрица gij имеет k+1 незапрещенных (небесконечных) элементов из множества {0, 1, 2, 3, 4} в каждой строке и каждом столбце. Оптимальное решение содержит n / (k + 1) открытых предприятий и соответствует одному из совершенных кодов, число которых растет экспоненциально с ростом k. В таблицах приводятся тестовые примеры для k = 3, n = m = 128. Исходные данные в виде текстовых файлов доступны в первой колонке таблицы. Расположение локальных оптимумов для первого примера можно увидеть на диаграмме.
(Архив со всеми примерами на совершенных кодах ufpl-pc.zip 109 Kb)
| Код | Оптимум | Разрыв
двойствен- ности (%) |
Оптимальное решение |
|
48232.00 |
0.01 |
5
12 24
25 35
46 50
63 66
79 83
94 104
105 117
124 |
|
|
48217.00 |
0.01 |
2
11 23
30 40
45 49
60 69
80 84
89 99
106 118
127 |
|
|
48227.00 |
0.00 |
3
13 18
32 40
42 53
59 70
76 87
89 97
111 116
126 |
|
|
48219.00 |
0.01 |
1
12 23
30 38
47 52
57 72
77 82
91 99
106 117
128 |
|
|
48223.00 |
0.01 |
3
13 18
32 40
42 53
59 70
76 87
89 97
111 116
126 |
|
|
48215.00 |
0.01 |
3
16 22
25 37
42 52
63 66
77 87
92 104
107 113
126 |
|
|
48221.00 |
0.01 |
4
14 23
25 37
43 50
64 65
79 86
92 104
106 115
125 |
|
|
48217.00 |
0.01 |
2
7 27
30 44
45 49
56 73
80 84
85 99
102 122
127 |
|
|
48220.00 |
0.01 |
4
9 22
31 37
48 51
58 71
78 81
92 98
107 120
125 |
|
|
48223.00 |
0.01 |
4
13 23
26 38
43 49
64 65
80 86
91 103
106 116
125 |
|
|
48211.00 |
0.00 |
6
12 17
31 35
45 56
58 71
73 84
94 98
112 117
123 |
|
|
48226.00 |
0.01 |
3
13 24
26 34
48 53
59 70
76 81
95 103
105 116
126 |
|
|
48209.00 |
0.00 |
8
11 21
26 34
45 51
64 65
78 84
95 103
108 118
121 |
|
|
48226.00 |
0.01 |
7
10 22
27 36
45 49
64 65
80 84
93 102
107 119
122 |
|
|
48221.00 |
0.01 |
12
13 18
23 33
40 59
62 67
70 89
96 106
111 116
117 |
|
|
48225.00 |
0.00 |
1
8 27
30 42
47 52
53 76
77 82
87 99
102 121
128 |
|
|
48222.00 |
0.01 |
4
15 21
26 38
41 51
64 65
78 88
91 103
108 114
125 |
|
|
48205.00 |
0.00 |
8
11 21
26 33
46 52
63 66
77 83
96 103
108 118
121 |
|
|
48226.00 |
0.00 |
4
13 23
26 33
48 54
59 70
75 81
96 103
106 116
125 |
|
|
48229.00 |
0.00 |
6
11 17
32 39
42 52
61 68
77 87
90 97
112 118
123 |
|
|
48215.00 |
0.01 |
3
14 21
28 34
47 56
57 72 73
82 95
101 108
115 126 |
|
|
48212.00 |
0.01 |
2
11 21
32 40
45 51
58 71
78 84
89 97
108 118
127 |
|
|
48209.00 |
0.01 |
7
9 22
28 34
48 51
61 68
78 81
95 101
107 120
122 |
|
|
48207.00 |
0.00 |
7
14 18
27 33
44 56
61 68
73 85
96 102
111 115
122 |
|
|
48220.00 |
0.01 |
8
11 18
29 33
46 55
60 69
74 83
96 100
111 118
121 |
|
|
48220.00 |
0.01 |
12
13 19
22 33
40 58
63 66
71 89
96 107
110 116
117 |
|
|
48207.00 |
0.00 |
2
15 24
25 35
46 53
60 69
76 83
94 104
105 114
127 |
|
|
48222.00 |
0.00 |
2
13 23
28 35
48 54
57 72
75 81
94 101
106 116
127 |
|
|
48223.00 |
0.01 |
6
11 23
26 33
48 52
61 68
77 81
96 103
106 118
123 |
|
|
48204.00 |
0.01 |
8
13 17
28 34
43 55
62 67
74 86
95 101
112 116
121 |