Тестовые
примеры
Простейшая
задача размещения
Тестовые
примеры
Головная страница
библиотеки
Простейшая задача размещения
Примеры на шахматной доске
Примеры из данного класса сформированы с помощью шахматной доски размера 3k
3k, k = 1,2,... Края доски склеены так, чтобы образовывать тор. Простейшая задача размещения имеет n = 9k2 предприятий и m = n потребителей. Предприятие i может обслуживать потребителя j, если соответсвующие клетки шахматной доски имеют хотя бы одну общую точку. На языке шахмат предприятие подобно королю, который бьет все соседние клетки. Стоимость открытия любого предприятия равна 3000. Матрица gij имеет ровно 9 незапрещенных (небесконечных) элементов из множества {0, 1, 2, 3, 4} в каждой строке и каждом столбце. Оптимальное решение содержит k2 открытых предприятий и соответствует минимальному числу шахматных королей, расставив которые можно побить все клетки. Число наборов из k2 предприятий, покрывающих всю доску, равно 2·3k+1 – 9, то есть растет экспоненциально с ростом k. В таблицах приводятся тестовые примеры для k = 4, n = m = 144. Исходные данные в виде текстовых файлов доступны в первой колонке таблицы. Расположение локальных оптимумов для первого примера можно увидеть на диаграмме.
Все примеры на шахматной доске chess_board.zip 129 Kb
|
Код |
Оптимум |
Разрыв
двойствен- |
Оптимальное
решение |
|
8258.00 |
0.01 |
3,
6, 21,
36, 39, 42,
57, 72, 75, 78,
93, 108,
111, 114,
129, 144
|
|
|
48247.00 |
0.00 |
2,
5, 8,
11, 38, 41,
44, 47,
73, 76, 79, 82, 109, 112, 115, 118 |
|
|
48246.00 |
0.00 |
1, 4, 7, 10, 38, 41, 44, 47, 75, 78, 81, 84,
111, 114, 117, 120 |
|
|
48235.00 |
0.01 |
26, 29, 32, 35, 63, 66, 69, 72, 99, 102, 105,
108, 134, 137, 140, 143 |
|
|
48257.00 |
0.01 |
15, 18, 21, 24, 51, 54, 57, 60, 85, 88, 91, 94,
121, 124, 127, 130 |
|
|
48236.00 |
0.00 |
2, 5, 8, 11, 38, 41, 44, 47, 74, 77, 80, 83,
110, 113, 116, 119 |
|
|
48249.00 |
0.00 |
2, 5, 11, 32, 38, 41, 47, 68, 74, 77, 83, 104,
110, 113, 119, 140 |
|
|
48239.00 |
0.01 |
3, 6, 9, 12, 39, 42, 45, 48, 74, 77, 80, 83,
109, 112, 115, 118 |
|
|
48232.00 |
0.00 |
10, 13, 16, 19, 46, 49, 52, 55, 82, 85, 88, 91,
118, 121, 124, 127 |
|
|
48244.00 |
0.01 |
26, 29, 32, 35, 63, 66, 69, 72, 97, 100, 103,
106, 135, 138, 141, 144 |
|
|
48249.00 |
0.01 |
16, 25, 31, 34, 52, 61, 67, 70, 88, 97, 103,
106, 124, 133, 139, 142 |
|
|
48247.00 |
0.00 |
25, 28, 31, 34, 62, 65, 68, 71, 97, 100, 103,
106, 133, 136, 139, 142 |
|
|
48247.00 |
0.00 |
6, 9, 27, 36, 42, 45, 63, 72, 78, 81, 99, 108,
114, 117, 135, 144 |
|
|
48250.00 |
0.00 |
13, 16, 19, 22, 51, 54, 57, 60, 85, 88, 91, 94,
121, 124, 127, 130 |
|
|
48247.00 |
0.01 |
25, 28, 31, 34, 62, 65, 68, 71, 97, 100, 103,
106, 135, 138, 141, 144 |
|
|
48253.00 |
0.00 |
8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107,
116, 125, 134, 143 |
|
|
48251.00 |
0.00 |
26, 29, 32, 35, 61, 64, 67, 70, 97, 100, 103,
106, 134, 137, 140, 143 |
|
|
48243.00 |
0.01 |
8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107,
116, 125, 134, 143 |
|
|
48242.00 |
0.01 |
25, 28, 31, 34, 62, 65, 68, 71, 98, 101, 104,
107, 134, 137, 140, 143 |
|
|
48249.00 |
0.01 |
1, 4, 7, 10, 38, 41, 44, 47, 75, 78, 81, 84,
111, 114, 117, 120 |
|
|
48250.00 |
0.01 |
9, 12, 18, 27, 45, 48, 54, 63, 81, 84, 90, 99,
117, 120, 126, 135 |
|
|
48249.00 |
0.01 |
27, 30, 33, 36, 63, 66, 69, 72, 97, 100, 103,
106, 134, 137, 140, 143 |
|
|
48256.00 |
0.01 |
3, 6, 9, 12, 38, 41, 44, 47, 75, 78, 81, 84,
110, 113, 116, 119 |
|
|
48239.00 |
0.01 |
7, 10, 16, 25, 43, 46, 52, 61, 79, 82, 88, 97,
115, 118, 124, 133 |
|
|
48248.00 |
0.01 |
7, 13, 28, 34, 43, 49, 64, 70, 79, 85, 100, 106,
115, 121, 136, 142 |
|
|
48232.00 |
0.00 |
27, 30, 33, 36, 61, 64, 67, 70, 99, 102, 105,
108, 134, 137, 140, 143 |
|
|
48239.00 |
0.01 |
13, 16, 19, 34, 49, 52, 55, 70, 85, 88, 91, 106,
121, 124, 127, 142 |
|
|
48247.00 |
0.01 |
3, 6, 9, 12, 38, 41, 44, 47, 74, 77, 80, 83,
110, 113, 116, 119 |
|
|
48239.00 |
0.00 |
26, 29, 32, 35, 61, 64, 67, 70, 97, 100, 103,
106, 133, 136, 139, 142 |
|
|
48226.00 |
0.00 |
5, 11, 14, 20, 41, 47, 50, 56, 77, 83, 86, 92,
113, 119, 122, 128 |