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

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

Примеры на евклидовой плоскости

Примеры из данного класса имеют размерность  n = m = 100. Стоимость открытия любого предприятия равна 3000. Элементы матрицы gij генерируются следующим образом. На квадрате со стороной 7000 выбрасываются случайным образом 100 точек. Элемент gij равен евклидовому расстоянию между точками i и j. Построенная таким способом матрица удовлетворяет неравенству треугольника.

Исходные данные в виде текстовых файлов доступны в первой колонке таблицы.  Расположение локальных оптимумов для первого примера можно увидеть на диаграмме.

Все примеры на евклидовой плоскости euclid.zip 1,6 Mb

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

111

96116

 0.00

2  4  6  10  19  26  27  31  53  62  74  98 
211 98091  0.00 5  6  8  10  22  47  49  61  65  80  94  95  97
311 96212  0.00 4  17  18  22  32  33  42  44  49  52  60  65  71  74  76  84
411 102157 0.02 9  24  29  39  41  47  52  53  54  56  62  64  78  82  90
511 98527  0.00 2  5  6  7  27  30  35  38  40  42  58  81  89  100
611 98374  0.00 2  9  25  43  59  61  64  68  78  80  82  88  90  93
711 99331  0.00 2  4  7  16  19  24  34  37  42  46  50  95
811 100277  0.00 2  13  17  20  27  34  40  44  50  53  54  69  72  84  85  100
911 100335  0.00 9  11  15  53  55  63  65  76  81  83  87  89
1011 95868  0.00 18  20  23  24  30  44  45  46  58  60  64  70  76
1111 97181  0.00 6  21  22  24  32  35  39  46  53  61  65  74  86  97
1211 98528  0.00 12  14  15  35  44  48  56  59  60  62  72  87  88  93
1311 99880  0.00 5  24  45  50  55  58  61  64  68  75  79  84  97  100
1411 96460  0.00 7  11  13  17  18  29  42  51  69  84  95  96  98
1511 99239  0.03 4  5  6  12  15  17  25  26  28  29  62  94  98
1611 98486  0.00 2  4  5  12  17  42  67  72  73  78  90  92  96  97
1711 97578  0.00 11  12  14  19  27  29  31  44  45  48  68  74  87  91  97
1811 100189  0.00 2  7  22  29  41  46  54  56  71  82  84  91  96  97
1911 98617  0.00 6  8  15  16  34  36  51  57  70  79  88  98  100
2011 96938  0.00 7  15  26  39  41  43  46  48  63  65  66  75  79  95
2111 94611  0.00 5  10  15  23  31  37  41  49  54  88  89  93
2211 98238  0.00 1  11  13  23  35  51  55  56  62  68  72  82  87  92  95 
2311 97419  0.00 2  22  36  42  43  47  50  64  69  75  80  82  89 
2411 96715  0.00 7  14  16  17  24  36  38  40  58  63  78  81  91  99
2511 99195  0.00 3  6  7  9  11  13  22  27  38  58  67  68  80  81  84  98 
2611 96088  0.00 15  16  20  32  45  49  61  81  83  85  92  100
2711 93845  0.00 22  25  28  31  32  41  48  63  70  79  83  96  98
2811 100651  0.00 8  14  35  41  44  50  57  65  71  74  83  84  94  96
2911 98699  0.00 1  2  12  17  27  28  29  53  67  83  85  86  97  100
3011 98846  0.00 5  6  9  19  31  35  40  55  71  72  80  88  94

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