Библиотека тестовых задач
Дискретные
задачи размещения
Библиотека тестовых задач
Библиотека тестовых задач
Задача о (r|p)-центроиде
Примеры на евклидовой плоскости
В данных примерах множество клиентов и множество возможных мест размещения предприятий совпадают: I = J, n = m = 100.
Элементы матрицы (gij) генерируются следующим образом. На квадрате со стороной 7000 случайным образом с равномерным распределением выбрасываются m точек.
Элемент gij равен евклидовому расстоянию между точками i и j.
В первом столбце каждой таблицы содержатся коды примеров и ссылки на текстовые файлы с координатами точек на евклидовой плоскости.
Все примеры с равнми весами: COMP(100).zip 14 Kb Все примеры с различнми весами: COMP100(W).zip 15 Kb
В Таблицах приводятся точные или наилучшие найденные решения задач при различных значениях p и r с равными весами клиентов wj = 1 или различными wj ∈ [1, 200], выбранными случайно. В последнем случае также приводится значение целевой функции в процентах от суммарного дохода (доля рынка)
Размерность задачи: n=m=100 p =r =5
Таблица 1. wj = 1
Код
примераОптимальное
значениеОптимальное решение 47 Лидер: 11 13 38 68 91
Конкурент: 3 7 15 40 8848 Лидер: 2 6 10 13 51
Конкурент: 1 21 24 28 5645 Лидер: 15 32 54 55 85
Конкурент: 7 12 33 70 8447 Лидер: 40 44 49 82 90
Конкурент: 6 15 26 42 7747 Лидер: 22 23 62 84 93
Конкурент: 36 39 41 64 6747 Лидер: 30 53 85 91 98
Конкурент: 1 12 43 48 9047 Лидер: 43 62 65 77 86
Конкурент: 4 59 70 75 9548 Лидер: 79 11 18 37 30
Конкурент: 1 46 51 84 8747 Лидер: 15 73 36 81 92
Конкурент: 25 33 35 50 8547 Лидер: 3 67 48 35 10
Конкурент: 14 15 38 49 91
Таблица 2 1 ≤ wj ≤ 200
Код
примераОптимальное
значение
абс.знач, (в %)Оптимальное решение 4139 (47,63%) Лидер: 11 13 38 68 94
Конкурент: 40 42 78 88 98211 4822 (45,84%) Лидер: 1 49 60 82 93
Конкурент: 11 15 51 57 81311 4215 (45,08%) Лидер: 15 33 54 58 78
Конкурент: 7 19 38 47 63411 4678 (47,12%) Лидер: 6 7 40 42 82
Конкурент: 54 56 90 91 95511 4599 (44,89%) Лидер: 22 61 84 91 93
Конкурент: 35 60 62 65 74611 4483 (47,10%) Лидер: 17 19 30 47 73
Конкурент: 32 53 58 70 85711 5153 (46,01%) Лидер: 18 62 65 79 90
Конкурент: 28 33 40 52 99811 4404 (46,08%) Лидер: 11 45 51 55 84
Конкурент: 10 32 54 69 77911 4700 (45,21%) Лидер: 7 46 87 95 99
Конкурент: 12 17 55 81 831011 4923 (48,14%) Лидер: 3 11 14 15 89
Конкурент: 42 49 68 72 93
Размерность задачи: n=m=100 p =r =10
Таблица 3 wj = 1
Код
примераОптимальное
значениеОптимальное решение 50
Лидер: 2 3 15 18 27 31 40 44 64 91
Конкурент: 4 7 11 24 48 50 53 62 74 85
49
Лидер: 5 6 19 28 29 31 32 41 49 97
Конкурент: 11 25 33 35 45 47 59 61 64 93
48
Лидер: 16 31 54 59 60 70 71 72 81 82
Конкурент: 1 7 21 29 35 41 48 84 86 88
49
Лидер: 8 15 28 34 40 41 64 79 90 92
Конкурент: 16 23 24 26 44 60 75 80 84 93
48
Лидер: 6 19 21 35 36 40 42 58 61 89
Конкурент: 5 15 25 30 49 52 53 55 74 76
47
Лидер: 11 17 45 47 61 72 76 80 82 90
Конкурент: 10 19 30 68 75 79 81 86 87 98
51
Лидер: 1 40 42 53 58 66 77 85 86 95
Конкурент: 15 18 25 28 46 50 51 54 72 83
48
Лидер: 3 20 22 44 54 58 59 75 77 88
Конкурент: 10 11 15 38 47 53 56 76 98 99
49
Лидер: 7 25 27 50 52 63 81 85 89 99
Конкурент: 6 9 12 14 26 40 53 55 58 83
49
Лидер: 18 29 44 46 52 58 64 78 82 90
Конкурент: 13 21 35 45 56 70 73 74 85 100
Таблица 4 1 ≤ wj ≤ 200
Код
примераОптимальное
значение
абс.знач, (в %)Оптимальное решение 4361 (50%)
Лидер: 2 4 15 18 32 44 64 74 85 91
Конкурент: 6 9 29 38 43 50 53 55 67 82211 5310 (50%) Лидер: 5 8 10 14 28 51 54 67 75 93
Конкурент: 7 34 40 47 52 57 65 86 92 94311 4483 (48%) Лидер: 4 18 29 33 35 38 51 67 70 94
Конкурент: 16 34 36 50 58 61 63 84 86 89411 4994 (50%) Лидер: 8 11 12 15 28 46 56 62 79 92
Конкурент: 24 26 29 38 49 50 70 75 85 100511 4906 (48%) Лидер: 5 9 12 27 35 38 40 42 89 99
Конкурент: 7 24 30 31 48 53 58 61 74 82611 4595 (48%) Лидер: 6 7 19 22 45 47 60 72 76 85
Конкурент: 25 27 28 35 55 65 91 92 97 98711 5586 (50%) Лидер: 4 39 40 46 53 66 77 79 86 95
Конкурент: 2 18 22 28 57 67 70 72 87 100811 4609 (48%) Лидер: 3 11 43 58 65 79 82 84 85 98
Конкурент: 1 4 23 27 29 34 38 40 44 60911 5302 (51%) Лидер: 7 14 19 24 25 32 33 64 81 89
Конкурент: 9 13 26 44 46 55 85 87 90 921011 5005 (49%) Лидер: 3 11 45 60 64 68 74 78 90 96
Конкурент: 12 21 30 35 53 55 56 76 85 87
Размерность задачи: n=m=100 p =r =15
Таблица 5 1 ≤ wj ≤ 200
Код
примераНижняя оценка
Рекордное решение
(номера предприятий открытых Лидером и Конкурентом)4596 (52,9%) Лидер: 6 13 14 18 26 32 37 38 42 74 79 85 90 91 100
Конкурент: 3 7 8 19 23 27 28 49 50 52 53 56 83 87 96211 5373 (51,1%) Лидер: 5 10 18 28 32 33 38 41 54 67 75 79 86 93 95
Конкурент: 7 25 30 40 51 53 56 62 76 77 81 82 92 94 99311 4800 (51,3%) Лидер: 4 17 18 21 24 29 33 35 44 51 67 68 70 94 95
Конкурент: 23 26 28 36 39 41 46 47 49 63 81 86 88 96 99411 5064 (51,0%) Лидер: 8 12 15 19 21 28 29 56 62 64 65 87 89 92 100
Конкурент: 2 7 26 46 49 51 52 68 74 82 84 85 91 95 97511 5131 (50,1%) Лидер: 2 5 6 30 35 40 42 61 63 66 71 75 76 89 99
Конкурент: 7 8 9 12 17 21 24 33 38 45 53 54 70 82 93611 4881 (51,3%) Лидер: 5 17 19 22 25 45 60 64 68 73 78 82 85 92 97
Конкурент: 1 8 10 11 13 16 21 34 39 58 61 63 76 77 98711 5827 (52,0%) Лидер: 4 9 22 24 31 42 46 50 66 77 79 86 87 94 97
Конкурент: 1 8 11 13 25 37 39 53 64 69 74 78 89 95 100811 4675 (48,9%) Лидер: 2 11 15 23 29 43 67 68 69 72 78 79 84 85 100
Конкурент: 3 6 19 24 26 34 44 50 52 60 71 75 82 95 98911 5158 (49,6%) Лидер: 13 19 25 34 44 55 76 77 78 85 86 87 89 90 95
Конкурент: 4 9 14 21 29 33 35 37 43 45 46 49 53 63 981011 5195 (50,8%) Лидер: 3 6 10 12 23 35 45 58 60 64 70 71 87 90 100
Конкурент: 11 13 15 18 24 32 33 42 44 52 53 55 76 78 85
Размерность задачи: n=m=100 p =r =20
Таблицаe 6 1 ≤ wj ≤ 200
Код
примераНижняя оценка
Рекордное решение
(номера предприятий открытых Лидером и Конкурентом)4512 (51,93%) Leader: 7 13 14 18 26 28 32 37 42 52 56 60 64 67 74 79 90 91 96 100
Follower: 2 5 8 11 15 23 29 40 45 50 51 54 55 68 76 77 84 87
211 5432 (51,63%) Leader: 5 10 23 25 32 33 35 40 41 44 53 54 55 61 79 82 86 88 89 95
Follower: 1 4 7 11 22 31 34 36 42 47 48 50 59 70 72 75 81 96 99 100
311 4893 (52,33%) Leader: 4 17 21 22 35 39 41 49 51 58 63 68 76 81 83 84 86 90 94 95
Follower: 7 9 14 18 20 23 28 29 33 36 40 44 46 69 79 82 89 93 96 100
411 5209 (52,47%) Leader: 4 7 12 15 21 24 42 50 51 54 56 62 64 65 80 85 89 91 93 96
Follower: 8 10 17 19 20 23 26 28 29 44 46 55 67 76 78 79 84 92 97 100
511 5334 (52,07%) Leader: 2 7 9 13 21 33 34 35 40 45 51 53 63 66 71 75 76 82 94 99
Follower: 4 5 6 12 14 26 30 39 43 47 49 50 61 73 74 85 88 89 93 100
611 4952 (52,03%) Leader: 5 16 17 19 23 25 45 46 49 60 64 65 68 69 73 78 85 88 92 97
Follower: 4 7 8 11 13 14 18 20 27 34 35 36 39 61 74 77 82 86 91 98
711 5893 (52,62%) Leader: 2 9 13 19 22 24 31 37 39 42 46 50 64 66 72 77 79 86 87 97
Follower: 4 5 6 8 11 17 18 25 35 40 53 57 60 63 65 71 74 78 89 94
811 4858 (50,83%) Leader: 2 3 6 15 23 24 29 31 35 38 43 47 48 68 72 74 75 78 82 94
Follower: 11 34 40 44 45 49 50 52 56 57 58 60 67 69 85 87 88 91 93 97
911 5459 (52,51%) Leader: 7 13 16 19 21 27 43 45 46 49 55 58 62 65 77 84 85 87 92 96
Follower: 3 5 14 15 22 23 24 32 35 38 41 53 63 76 82 83 86 89 95 98
1011 5399 (52,8%) Leader: 5 6 12 18 23 30 34 45 49 58 60 64 70 71 80 87 90 92 96 100
Follower: 3 4 11 14 15 19 24 31 33 35 42 52 59 63 67 72 76 78 81 94
ЛИТЕРАТУРА
1. Ю.А. Кочетов, А.В.Кононов, А.В. Плясунов. Конкурентные модели размещения производства // Журн. вычисл. матем. и матем. физики. 2009. Том 49, № 6. С. 1-17. pdf-file 338 Kb
2. Е.В. Алексеева, Н.А. Кочетова. Верхние и нижние оценки для конкурентной задачи о р-медиане // Труды 14 Байкальской международной школы-семинара "Методы оптимизации и их приложения. Том 1. Северобайкальск. 2008. стр. 563-569. pdf-file 208 Kb
3. Е.В. Алексеева, А.В. Орлов. Генетический алгоритм для конкурентной задачи о р-медиане // Труды 14 Байкальской международной школы-семинара "Методы оптимизации и их приложения". Том 1. Северобайкальск. 2008. стр. 570-585. pdf-file 469 Kb
4. E. Alekseeva, N. Kochetova, Yu. Kochetov, A. Plyasunov. A Hybrid Memetic Algorithm for the Competitive p-Median Problem. Proc. of 13 IFAC Symposium on Information Control Problems in Manufacturing (INCOM '09). Moscow. 2009. pdf.file 143 Kb
5. J. Bhadury, H.A. Eiselt, J.H. Jaramillo. An alternating heuristic for medianoid and centroid problems in the plane. Computers and Oper. Res. 2003. V. 30. P. 553-565.