Библиотека тестовых задач
Дискретные
задачи размещения
Библиотека тестовых задач
Библиотека тестовых задач
Задача о p-медиане
Примеры
на шахматной доске
Склеим края шахматной доски размером 3k ×3k так, чтобы она образовала тор. Пусть r = 3k. Каждая клетка доски имеет 8 соседних клеток. Например клетка (1,1) имеет следующих соседей: (1, 2), (1, r), (2, 1), (2, 2), (2, r), (r, 1), (r, 2), (r, r). Положим n = 9k2, p = k2, I = J = {1,…, n} и
где xij – случайное число из множества {0,1,2,3,4} с равномерным распределением. Разделим тор на k2 квадратов по 9 клеток в каждом. Каждому квадрату соответствует допустимое решение задачи о p-медиане. Общее число допустимых решений 2 · 3k+1 – 9. Минимальное расстояние между ними – 2k. Обозначим этот класс тестовых примеров CBk. Примеры для k = 4, p = 16, n = m = 144 приведены в таблице.
Все примеры на шахматной доске pm_chess.zip 129 Kb
| Код | Оптимум | Разрыв двойственности (%) |
Оптимальное решение |
|
258 |
7.17 | 3, 6, 21, 36, 39, 42, 57, 72, 75, 78, 93, 108, 111, 114, 129, 144 | |
|
247 |
4.82 | 2, 5, 8, 11, 38, 41, 44, 47, 73, 76, 79, 82, 109, 112, 115, 118 | |
|
246 |
1.89 | 1, 4, 7, 10, 38, 41, 44, 47, 75, 78, 81, 84, 111, 114, 117, 120 | |
|
235 |
26.38 | 26, 29, 32, 35, 63, 66, 69, 72, 99, 102, 105, 108, 134, 137, 140, 143 | |
|
257 |
9.96 | 15, 18, 21, 24, 51, 54, 57, 60, 85, 88, 91, 94, 121, 124, 127, 130 | |
|
236 |
3.76 | 2, 5, 8, 11, 38, 41, 44, 47, 74, 77, 80, 83, 110, 113, 116, 119 | |
|
249 |
6.21 | 2, 5, 11, 32, 38, 41, 47, 68, 74, 77, 83, 104, 110, 113, 119, 140 | |
|
239 |
23.01 | 3, 6, 9, 12, 39, 42, 45, 48, 74, 77, 80, 83, 109, 112, 115, 118 | |
|
232 |
28.88 | 10, 13, 16, 19, 46, 49, 52, 55, 82, 85, 88, 91, 118, 121, 124, 127 | |
|
244 |
6.23 | 26, 29, 32, 35, 63, 66, 69, 72, 97, 100, 103, 106, 135, 138, 141, 144 | |
|
249 |
6.44 | 16, 25, 31, 34, 52, 61, 67, 70, 88, 97, 103, 106, 124, 133, 139, 142 | |
|
247 |
6.43 | 25, 28, 31, 34, 62, 65, 68, 71, 97, 100, 103, 106, 133, 136, 139, 142 | |
|
247 |
3.01 | 6, 9, 27, 36, 42, 45, 63, 72, 78, 81, 99, 108, 114, 117, 135, 144 | |
|
250 |
23.20 | 13, 16, 19, 22, 51, 54, 57, 60, 85, 88, 91, 94, 121, 124, 127, 130 | |
|
247 |
8.79 | 25, 28, 31, 34, 62, 65, 68, 71, 97, 100, 103, 106, 135, 138, 141, 144 | |
|
253 |
27.67 | 8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107, 116, 125, 134, 143 | |
|
251 |
34.66 | 26, 29, 32, 35, 61, 64, 67, 70, 97, 100, 103, 106, 134, 137, 140, 143 | |
|
243 |
29.22 | 8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107, 116, 125, 134, 143 | |
|
242 |
8.48 | 25, 28, 31, 34, 62, 65, 68, 71, 98, 101, 104, 107, 134, 137, 140, 143 | |
|
249 |
8.01 | 1, 4, 7, 10, 38, 41, 44, 47, 75, 78, 81, 84, 111, 114, 117, 120 | |
|
250 |
28.00 | 9, 12, 18, 27, 45, 48, 54, 63, 81, 84, 90, 99, 117, 120, 126, 135 | |
|
249 |
30.12 | 27, 30, 33, 36, 63, 66, 69, 72, 97, 100, 103, 106, 134, 137, 140, 143 | |
|
256 |
9.58 | 3, 6, 9, 12, 38, 41, 44, 47, 75, 78, 81, 84, 110, 113, 116, 119 | |
|
239 |
7.74 | 7, 10, 16, 25, 43, 46, 52, 61, 79, 82, 88, 97, 115, 118, 124, 133 | |
|
248 |
5.07 | 7, 13, 28, 34, 43, 49, 64, 70, 79, 85, 100, 106, 115, 121, 136, 142 | |
|
232 |
26.72 | 27, 30, 33, 36, 61, 64, 67, 70, 99, 102, 105, 108, 134, 137, 140, 143 | |
|
239 |
28.45 | 13, 16, 19, 34, 49, 52, 55, 70, 85, 88, 91, 106, 121, 124, 127, 142 | |
|
247 |
31.17 | 3, 6, 9, 12, 38, 41, 44, 47, 74, 77, 80, 83, 110, 113, 116, 119 | |
|
239 |
2.73 | 26, 29, 32, 35, 61, 64, 67, 70, 97, 100, 103, 106, 133, 136, 139, 142 | |
|
226 |
3.32 | 5, 11, 14, 20, 41, 47, 50, 56, 77, 83, 86, 92, 113, 119, 122, 128 |