Дискретные задачи размещения ballred.gif (861 bytes) Библиотека тестовых задач
line.jpg (1129 bytes)

ballred.gif (861 bytes) Библиотека тестовых задач ballred.gif (861 bytes) Задача о p-медиане ballred.gif (861 bytes)

Примеры на конечных проективных плоскостях

Рассмотрим конечную проективную плоскость размерности k, заданную n точками  x1, ..., xn  и  прямыми  L1,..., Ln, где  n = k2+k+1. Матрица  инциденций A размерности n× n определяется следующим образом aij=1, если xj Î Li, и aij = 0 в противном случае. Эта матрица обладает свойствами:

1. Каждый столбец содержит ровно k +1 единицу.
2. Каждая строка содержит ровно k +1 единицу.
3. Скалярное произведение любых двух строк равно 1.
4. Скалярное произведение любых двух столбцов равно 1.

Такие матрицы существуют если k есть степень простого числа. Множество прямых Bj = {Li | xj Î Li} называется пучком, проходящим через точку xj. Определим класс FPPk  тестовых примеров для задачи о  p-медиане следующим образом. Положим I = J ={1,…, n}  и 

где x ij случайные числа из множества {0,1,2,3,4} с равномерным распределением. Оптимальное решение соответствует пучку и может быть найдено за полиномиальное время. Каждый пучок определяет строгий локальный оптимум для задачи о p-медиане с окрестностью Flip+Swap. Расстояние Хэмминга для произвольной пары строгих локальных оптимумов равно 2k. Следовательно диаметр области скопления локальных оптимумов достаточно велик. Тем не менее не существует ни одного локального оптимума на расстоянии меньше либо равным k от пучка Bj.

Класс FPPk  сложен для методов локального поиска при достаточно больших k. 

 

Примеры для k = 11,  p = 12,  n = m = 133 приведены в таблице:

(Все примеры на проективных плоскостях для k = 11 mp_fp_11.zip 172 Kb)

Код Оптимум Разрыв 
двойственности (%)		 Оптимальное решение
1 230  12.20 9, 25, 38, 40, 68, 74, 75, 78, 86, 95, 100, 119
2 220  11.59 16, 39, 55, 68, 70, 98, 104, 105, 108, 116, 125, 130
3 233  11.33 13, 15, 43, 49, 50, 53, 61, 70, 75, 94, 117, 133
4 221  14.62 2, 3, 6, 14, 23, 28, 47, 70, 86, 99, 101, 129
5 226  10.68 3, 26, 42, 55, 57, 85, 91, 92, 95, 103, 112, 117
6 236  11.42 6, 15, 20, 39, 62, 78, 91, 93, 121, 127, 128, 131
7 211  7.02 4, 9, 28, 51, 67, 80, 82, 110, 116, 117, 120, 128
8 220  10.47 14, 27, 29, 57, 63, 64, 67, 75, 84, 89, 108, 131
9 225  10.00 4, 5, 8, 16, 25, 30, 49, 72, 88, 101, 103, 131
10 228  5.40 2, 15, 17, 45, 51, 52, 55, 63, 72, 77, 96, 119
11 219  12.86 2, 10, 19, 24, 43, 66, 82, 95, 97, 125, 131, 132
12 239  10.66 17, 33, 46, 48, 76, 82, 83, 86, 94, 103, 108, 127
13 226  11.90 12, 25, 27, 55, 61, 62, 65, 73, 82, 87, 106, 129
14 224  6.24 9, 25, 38, 40, 68, 74, 75, 78, 86, 95, 100, 119
15 236  12.23 4, 10, 11, 14, 22, 31, 36, 55, 78, 94, 107, 109
16 219  7.69 2, 30, 36, 37, 40, 48, 57, 62, 81, 104, 120, 133
17 234  7.76 1, 7, 8, 11, 19, 28, 33, 52, 75, 91, 104, 106
18 224  11.02 20, 36, 49, 51, 79, 85, 86, 89, 97, 106, 111, 130
19 234  5.16 2, 4, 32, 38, 39, 42, 50, 59, 64, 83, 106, 122
20 228  9.12 5, 24, 47, 63, 76, 78, 106, 112, 113, 116, 124, 133
21 221  9.48 9, 25, 38, 40, 68, 74, 75, 78, 86, 95, 100, 119
22 223  14.47 10, 26, 39, 41, 69, 75, 76, 79, 87, 96, 101, 120
23 223  6.79 6, 19, 21, 49, 55, 56, 59, 67, 76, 81, 100, 123
24 216  13.04 20, 26, 27, 30, 38, 47, 52, 71, 94, 110, 123, 125
25 216  10.48 17, 33, 46, 48, 76, 82, 83, 86, 94, 103, 108, 127
26 232  9.30 11, 17, 18, 21, 29, 38, 43, 62, 85, 101, 114, 116
27 222  6.76 15, 31, 44, 46, 74, 80, 81, 84, 92, 101, 106, 125
28 227  10.42 13, 36, 52, 65, 67, 95, 101, 102, 105, 113, 122, 127
29 213  6.59 10, 33, 49, 62, 64, 92, 98, 99, 102, 110, 119, 124
30 231  8.50 16, 22, 23, 26, 34, 43, 48, 67, 90, 106, 119, 121

В следующей таблице приведены примеры для  k = 17,  p = 18,  n = m = 307.

(Все примеры на проективных плоскостях для k = 17 mp_fp_17.zip  588 Kb)

Код Оптимум Разрыв двойствен-
ности (%)		 Оптимальное решение
1 548   29, 45, 49, 58, 109, 111, 130, 135, 158, 170, 176, 203, 206, 213, 214, 228, 245, 302
2 531   1, 24, 36, 42, 69, 72, 79, 80, 94, 111, 168, 202, 218, 222, 231, 282, 284, 303
3 554   7, 12, 35, 47, 53, 80, 83, 90, 91, 105, 122, 179, 213, 229, 233, 242, 293, 295
4 544   11, 27, 31, 40, 91, 93, 112, 117, 140, 152, 158, 185, 188 195, 196, 210, 227, 284
5 541   24, 27, 34, 35, 49, 66, 123, 157, 173, 177, 186, 237, 239, 258, 263, 286, 298, 304
6 552   1, 13, 19, 46, 49, 56, 57, 71, 88, 145, 179, 195, 199, 208, 259, 261, 280, 285
7 526   7, 24, 81, 115, 131, 135, 144, 195, 197, 216, 221, 244, 256, 262, 289, 292, 299, 300
8 546   5, 21, 25, 34, 85, 87, 106, 111, 134, 146, 152, 179, 182, 189, 190, 204, 221, 278
9 541   15, 17, 36, 41, 64, 76, 82, 109, 112, 119, 120, 134, 151, 208, 242, 258, 262, 271
10 549   46, 48, 67, 72, 95, 107, 113, 140, 143, 150, 151, 165, 182, 239, 273, 289, 293, 302
11 528   33, 67, 83, 87, 96, 147, 149, 168, 173, 196, 208, 214, 241, 244, 251, 252, 266, 283
12 551   6, 11, 34, 46, 52, 79, 82, 89, 90, 104, 121, 178, 212, 228, 232, 241, 292, 294
13 548   4, 27, 39, 45, 72, 75, 82, 83, 97, 114, 171, 205, 221, 225, 234, 285, 287, 306
14 548   42, 76, 92, 96, 105, 156, 158, 177, 182, 205, 217, 223, 250 253, 260, 261, 275, 292
15 555   5, 10, 33, 45, 51, 78, 81, 88, 89, 103, 120, 177, 211, 227, 231, 240, 291, 293
16 549   51, 85, 101, 105, 114, 165, 167, 186, 191, 214, 226, 232, 259, 262, 269, 270, 284, 301
17 556   40, 74, 90, 94, 103, 154, 156, 175, 180, 203, 215, 221, 248, 251, 258, 259, 273, 290
18 540   9, 14 37, 49 55, 82, 85, 92, 93 107, 124, 181, 215, 231, 235, 244, 295, 297
19 544   10, 12, 31, 36, 59, 71, 77, 104, 107, 114, 115, 129, 146, 203, 237, 253, 257, 266
20 538   14, 71, 105, 121, 125, 134, 185, 187, 206, 211, 234, 246, 252, 279, 282, 289, 290, 304
21 557   25, 28, 35, 36, 50, 67, 124, 158, 174, 178, 187, 238, 240, 259, 264, 287, 299, 305
22 551   4, 9, 32, 44, 50, 77, 80, 87, 88, 102, 119, 176, 210, 226, 230, 239, 290, 292
23 557   7, 9, 28, 33, 56, 68, 74, 101, 104, 111, 112, 126, 143, 200, 234, 250, 254, 263
24 531   9, 13, 22, 73, 75, 94, 99, 122, 134, 140, 167, 170, 177, 178, 192, 209, 266, 300
25 536   13, 18, 41, 53, 59, 86, 89, 96, 97, 111, 128, 185, 219, 235, 239, 248, 299, 301
26 552   28, 44, 48, 57, 108, 110, 129, 134, 157, 169, 175, 202, 205, 212, 213, 227, 244, 301
27 543   39, 41, 60, 65, 88, 100, 106, 133, 136, 143, 144, 158, 175, 232, 266, 282, 286, 295
28 552   32, 34, 53, 58, 81, 93, 99, 126, 129, 136, 137, 151, 168, 225, 259, 275, 279, 288
29 547   4, 5, 19, 36, 93, 127, 143, 147, 156, 207, 209, 228, 233, 256, 268, 274, 301, 304
30 541   36, 70, 86, 90, 99, 150, 152, 171, 176, 199, 211, 217, 244, 247, 254, 255, 269, 286

        
ballred.gif (861 bytes) Библиотека тестовых задач ballred.gif (861 bytes) Задача о p-медиане ballred.gif (861 bytes)