Простейшая задача размещения  ballred.gif (861 bytes)  Тестовые примеры
line.jpg (1129 bytes)

ballred.gif (861 bytes) Головная страница библиотеки ballred.gif (861 bytes) Простейшая задача размещения ballred.gif (861 bytes)

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

Примеры из данного класса сформированы с помощью матрицы инциденций для конечных проективных плоскостей. Для плоскости размерности k генерируется простейшая задача размещения с n = k2 + k + 1 предприятиями и m = n потребителями. Предприятие i может обслуживать потребителя j, если прямая i проходит через точку j. Стоимость открытия любого предприятия равна 3000. Матрица gij имеет k+1 незапрещенных (небесконечных) элементов из множества {0, 1, 2, 3, 4} в каждой строке  и каждом столбце. Оптимальное решение содержит (k + 1) открытых предприятий, может быть найдено за полиномиальное время и соответствует пучку прямых, проходящих через некоторую точку плоскости.  В таблицах приводятся тестовые примеры для k = 11, k = 17.  Исходные данные в виде текстовых файлов доступны в первой колонке таблицы.  Расположение локальных оптимумов для первого примера и k = 11 можно увидеть на диаграмме.

 

Размерность конечной проективной плоскости  k = 11

Все примеры на конечных проективных плоскостях k = 11 fpp_11.zip  102 Kb

Код Оптимум Разрыв двойственности (%) Оптимальное решение
1 36230

7,50

 9  25  38  40  68  74  75  78  86  95  100  119
2 36220 7,48 16  39  55  68  70  98  104  105  108  116  125  130
3 36233 7,49 13  15  43  49  50  53  61  70  75  94  117  133
4 36221 7,48 2  3  6  14  23  28  47  70  86  99  101  129
5 36226 7,49 3  26  42  55  57  85  91  92  95  103  112  117
6 36236 7,50 6  15  20  39  62  78  91  93  121  127  128  131
7 36211 7,46 4  9  28  51  67  80  82  110  116  117  120  128
8 36220 7,47 14  27  29  57  63  64  67  75  84  89  108  131
9 36225 7,49 4  5  8  16  25  30  49  72  88  101  103  131
10 36228 7,47 2  15  17  45  51  52  55  63  72  77  96  119
11 36219 7,49 2  10  19  24  43  66  82  95  97  125  131  132
12 36239 7,49 17  33  46  48  76  82  83  86  94  103  108  127
13 36226 7,50 12  25  27  55  61  62  65  73  82  87  106  129
14 36224 7,49 9  25  38  40  68  74  75  78  86  95  100  119
15 36236 7,51 4  10  11  14  22  31  36  55  78  94  107  109
16 36219 7,45 2  30  36  37  40  48  57  62  81  104  120  133
17 36234 7,50 1  7  8  11  19  28  33  52  75  91  104  106
18 36224 7,51 20  36  49  51  79  85  86  89  97  106  111  130
19 36234 7,49 2  4  32  38  39  42  50  59  64  83  106  122
20 36228 7,49 5  24  47  63  76  78  106  112  113  116  124  133
21 36221 7,47 9  25  38  40  68  74  75  78  86  95  100  119
22 36223 7,48 10  26  39  41  69  75  76  79  87  96  101  120
23 36223 7,45 6  19  21  49  55  56  59  67  76  81  100  123
24 36216 7,48 20  26  27  30  38  47  52  71  94  110  123  125
25 36216 7,48 17  33  46  48  76  82  83  86  94  103  108  127
26 36232 7,47 11  17  18  21  29  38  43  62  85  101  114  116
27 36222 7,48 15  31  44  46  74  80  81  84  92  101  106  125
28 36227 7,48 13  36  52  65  67  95  101  102  105  113  122  127
29 36213 7,79 10  33  49  62  64  92  98  99  102  110  119  124
30 36231 7,48 16  22  23  26  34  43  48  67  90  106  119  121

 

Размерность конечной проективной плоскости  k = 17

Все примеры на конечных проективных плоскостях k = 17  fpp_17.zip  558 Kb

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