Многостадийная
задача размещения
Главная страница библиотеки
Многостадийная задача
размещения
Примеры с четверками Штейнера
и матрицей транспортных
расходов типа Gap-C
(St4-GapC)
Один из наиболее трудных классов исходных данных для многостадийной задачи размещения может быть построен по аналогии с классом Gap-C для простейшей задачи размещения. Специфика этого класса состоит в том, что каждый потребитель может обслуживаться одной из 10 технологических цепочек. Каждая цепочка может удовлетворить спрос не более 10 потребителей. В состав каждой цепочки входит ровно 4 предприятия, выбранные аналогично системам Штейнера. Другими словами, каждая пара предприятий может встретиться не более одного раза. Начальные затраты на открытие каждого предприятия равны 3000. Размерность тестовых примеров: 50 предприятий, 100 технологических цепочек, 100 потребителей.
В нижеследующей таблице приведены исходные данные и результаты расчетов для 30 тестовых примеров. В первом столбце таблицы даны стартовые числа (коды) для датчика псевдослучайных чисел, позволяющие формировать данные примеры. Для удобства здесь же содержатся ссылки на файлы исходных данных в текстовом формате. Второй столбец содержит оптимальные значения целевой функции, полученные методом ветвей и границ. В третьем столбце приведены оценки разрыва двойственности, и в последнем столбце содержатся оптимальные решения (номера открываемых предприятий).
Все примеры класса St4-GapC.zip 118 Kb
|
Код |
Оптимум |
Разрыв
двойственности |
Номера открываемых предприятий |
|
78174 |
61,9 |
1, 2, 4, 5, 8, 11, 12, 16, 18, 20, 23, 24, 27, 28, 29, 30, 33, 34, 36, 39, 41, 42, 44, 45, 47, 50 |
|
|
81127 |
62,5 |
3, 6, 9, 10, 11, 12, 19, 20, 23, 24, 26, 28, 30, 31, 32, 33, 35, 38, 40, 41, 43, 44, 45, 46, 47, 49, 50 |
|
|
81119 |
62,2 |
1, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 18, 19, 20, 22, 25, 26, 29, 30, 33, 35, 36, 44, 45, 47, 48, 49 |
|
|
78130 |
61,4 |
3, 5, 6, 7, 9, 11, 12, 22, 26, 27, 28, 30, 32, 33, 35, 36, 37, 38, 40, 41, 42, 43, 44, 46, 47, 50 |
|
|
78141 |
61,2 |
2, 5, 7, 9, 11, 12, 14, 16, 18, 19, 22, 23, 24, 25, 27, 28, 30, 32, 34, 35, 36, 37, 38, 39, 41, 44 |
|
|
81123 |
61,5 |
2, 4, 5, 7, 8, 9, 12, 14, 15, 16, 18, 20, 21, 22, 24, 27, 29, 30, 31, 36, 40, 41, 42, 43, 45, 47, 49 |
|
|
81113 |
63,2 |
1, 2, 3, 4, 5, 9, 10, 11, 13, 16, 17, 18, 21, 23, 26, 30, 31, 34, 35, 36, 41, 43, 44, 46, 47, 49, 50 |
|
|
81128 |
63,2 |
1, 3, 4, 6, 7, 8, 9, 11, 14, 15, 17, 20, 24, 30, 31, 32, 33, 34, 37, 38, 39, 42, 43, 44, 47, 49, 50 |
|
|
81130 |
62,3 |
2, 6, 8, 15, 16, 18, 19, 21, 23, 24, 25, 26, 30, 32, 33, 34, 35, 36, 37, 38, 39, 41, 43, 44, 46, 48, 50 |
|
|
81106 |
62,8 |
1, 2, 7, 8, 9, 10, 12, 14, 16, 22, 25, 26, 27, 29, 30, 32, 36, 37, 40, 42, 43, 44, 46, 47, 48, 49, 50 |
|
|
81130 |
63,8 |
1, 2, 3, 6, 12, 18, 19, 22, 23, 24, 25, 28, 31, 33, 34, 37, 39, 40, 42, 43, 44, 45, 46, 47, 48, 49, 50 |
|
|
81131 |
63,0 |
2, 3, 6, 7, 10, 11, 13, 16, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 34, 36, 40, 41, 42, 43, 44, 48 |
|
|
78147 |
61,2 |
2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 16, 18, 19, 20, 22, 23, 26, 33, 35, 36, 38, 40, 43, 44, 49, 50 |
|
|
75162 |
60,1 |
1, 2, 4, 7, 8, 9, 10, 13, 14, 17, 18, 19, 21, 22, 23, 24, 29, 33, 35, 37, 39, 41, 45, 47, 49 |
|
|
81119 |
63,8 |
1, 2, 4, 5, 9, 10, 11, 12, 13, 15, 16, 17, 19, 22, 23, 26, 30, 36, 37, 40, 42, 43, 45, 46, 48, 49, 50 |
|
|
78141 |
61,1 |
1, 2, 3, 4, 6, 7, 8, 9, 12, 15, 18, 19, 21, 23, 27, 29, 35, 36, 37, 42, 43, 45, 47, 48, 49, 50 |
|
|
81130 |
61,0 |
1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 15, 16, 19, 20, 21, 28, 30, 32, 33, 34, 36, 42, 43, 45, 49, 50 |
|
|
81111 |
62,3 |
2, 3, 4, 5, 6, 7, 10, 14, 15, 16, 17, 18, 19, 24, 26, 28, 29, 31, 32, 33, 35, 36, 38, 39, 43, 46, 48 |
|
|
78150 |
60,4 |
2, 3, 4, 5, 6, 7, 9, 10, 11, 15, 16, 19, 20, 21, 24, 25, 28, 31, 32, 34, 41, 42, 45, 46, 48, 50 |
|
|
81105 |
62,7 |
2, 3, 6, 9, 10, 11, 13, 14, 15, 16, 18, 19, 21, 22, 23, 26, 27, 33, 35, 36, 37, 39, 41, 42, 46, 48, 50 |
|
|
75143 |
60,2 |
2, 3, 5, 6, 7, 8, 9, 10, 12, 13, 18, 20, 21, 22, 26, 28, 31, 33, 35, 38, 44, 45, 47, 49, 50 |
|
|
78119 |
62,2 |
2, 3, 5, 14, 17, 19, 20, 21, 22, 24, 25, 27, 28, 29, 30, 31, 33, 38, 39, 42, 43, 44, 46, 47, 48, 49 |
|
|
81133 |
62,7 |
1, 2, 3, 4, 5, 9, 13, 16, 18, 19, 22, 27, 28, 30, 31, 33, 34, 35, 37, 38, 39, 40, 41, 42, 44, 45, 46 |
|
|
81119 |
63,0 |
1, 3, 4, 5, 7, 9, 14, 16, 19, 21, 22, 23, 24, 25, 27, 31, 32, 33, 34, 35, 37, 38, 40, 41, 43, 47, 50 |
|
|
78149 |
61,2 |
1, 3, 4, 5, 8, 9, 11, 13, 17, 18, 20, 22, 23, 27, 29, 30, 32, 35, 37, 38, 39, 41, 42, 45, 48, 50 |
|
|
81130 |
62,0 |
1, 2, 3, 5, 8, 12, 13, 15, 17, 21, 22, 23, 25, 26, 28, 29, 30, 33, 35, 36, 39, 40, 42, 44, 48, 49, 50 |
|
|
78144 |
60,5 |
1, 2, 7, 9, 12, 13, 14, 15, 21, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 41, 44, 48, 49, 50 |
|
|
81130 |
62,9 |
1, 4, 6, 9, 10, 15, 17, 19, 21, 22, 25, 28, 29, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 47, 48, 49, 50 |
|
|
78142 |
61,1 |
1, 2, 3, 5, 6, 7, 8, 9, 11, 12, 13, 15, 19, 23, 25, 26, 30, 33, 35, 37, 38, 40, 41, 47, 49, 50 |
|
|
78136 |
61,2 |
1, 3, 4, 9, 13, 16, 19, 20, 21, 23, 24, 28, 29, 30, 31, 32, 33, 36, 37, 39, 40, 42, 43, 45, 46, 50 |