Простейшая
задача размещения
Тестовые
примеры
Головная страница
библиотеки
Простейшая задача размещения
Примеры на евклидовой плоскости
Примеры из данного класса имеют размерность n = m = 100. Стоимость открытия любого предприятия равна 3000. Элементы матрицы gij генерируются следующим образом. На квадрате со стороной 7000 выбрасываются случайным образом 100 точек. Элемент gij равен евклидовому расстоянию между точками i и j. Построенная таким способом матрица удовлетворяет неравенству треугольника.
Исходные данные в виде текстовых файлов доступны в первой колонке таблицы. Расположение локальных оптимумов для первого примера можно увидеть на диаграмме.
Все примеры на евклидовой плоскости euclid.zip 1,6 Mb
Код | Оптимум | Разрыв двойственности (%) | Оптимальное решение |
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 |