Простейшая задача размещения ballred.gif (861 bytes) Тестовые примеры
line.jpg (1129 bytes)

ballred.gif (861 bytes) Головная страница библиотеки ballred.gif (861 bytes) Простейшая задача размещения ballred.gif (861 bytes) 

Примеры с большим разрывом двойственности

Примеры с большим разрывом двойственности являются трудными для точных методов, основанных на линейной релаксации. Ниже приводятся три класса таких примеров  Gap-A, Gap-B, Gap-C, заметно отличающиеся по трудоемкости для метода ветвей и границ и алгоритмов локального поиска.
             
 Класс Gap – A 

Примеры из класса Gap-A являются наиболее легкими в серии Gap-A, Gap-B, Gap-C.  Разрыв двойственности для них в среднем составляет около 26 %.  Размерность: 100 предприятий, 100 потребителей. Стоимость открытия любого предприятия  равна 3000. Матрица транспортных расходов gij имеет ровно 10 незапрещенных (небесконечных) элементов из множества {0, 1, 2, 3, 4} в каждом столбце. Другими словами, каждый потребитель имеет ровно десять потенциальных поставщиков-предприятий, которые выбираются случайным образом с равномерным распределением из всего множества предприятий. Оптимальное решение содержит 12 или 13 открытых предприятий. Исходные данные в виде текстовых файлов доступны в первой колонке таблицы.  Расположение локальных оптимумов для первого примера можно увидеть на диаграмме.

Все примеры класса Gap – A  gap-a.zip 107 Kb

Код Оптимум Разрыв двойственности (%) Оптимальное решение
332 36154 25.43 10  14  17  33  34  40  44  50  59  63  64  78
432 36155 24.71 12  21  35  44  47  57  58  61  65  75  80  91
532 36150 27.68 2  4  31  32  40  42  52  56  73  77  80  89
632 36162 24.40 10  13  38  52  63  64  67  75  82  85  87  93
732 33157 21.73 3  5  11  17  25  31  37  51  53  59  95
832 36136 26.22 13  19  21  22  32  34  40  56  60  62  87  98
932 36133 26.55 16  30  37  41  46  55  56  58  63  67  72  87
1032 36127 26.16 12  20  21  23  33  36  38  41  48  64  67  75
1132 36163 25.66 10  16  23  58  68  69  74  75  82  88  94  100
1232 39123 29.69 3  10  18  21  22  31  35  57  69  71  87  92  99
1332 36164 24.50 4  9  17  28  59  66  71  76  79  82  91  97
1432 36150 27.19 5  11  22  25  41  55  61  62  65  75  84  89
1532 36158 23.56 7  10  22  23  31  32  40  45  52  54  55  59
1632 36141 26.33 9  10  21  35  37  39  41  45  48  67  80  86
1732 36157 24.27 4  13  33  38  41  65  73  75  85  90  91  96
1832 36135 25.79 7  11  13  27  28  30  34  46  47  48  77  78
1932 36146 24.34 9  32  39  40  45  56  61  62  70  72  90  98
2032 36150 25.62 22  26  28  41  49  61  64  67  80  84  93  97
2132 36140 23.70 2  13  23  36  43  48  50  64  76  77  85  91
2232 36145 23.51 4  5 10 31 34 42 47 70 81 92 94  100
2332 36172 24.37 12 13 32 36 38 44 51 57 67 71 87 88
2432 36137 27.37 3 7 11 14 21 23 28 31 68 74 87 90
2532 36153 25.09 11 25 28 33 43 47 52 64 79 95 98 99
2632 36164 23.48 5 9 16 25 26 28 44 66 79 91 95 99
2732 39123 28.58 2 6 11 12 13 21 41 48 49 63 64 90 91
2832 36145 25.21 9 11 21 26 33 34 65 67 76 83 84 90
2932 36155 24.50 2 16 19 52 55 62 71 76 77 81 84 91
3032 36113 27.02 9 27 35 39 43 53 66 67 72 73 89 93
3132 39130 30.48 1 24 26 30 31 54 60 62 63 83 85 96 99
3232 36157 25.82 5 17 30 33 38 41 50 55 64 71 89 95

 

Класс Gap – В 

Класс Gap-B является более трудным чем, класс Gap-A, но уступает классу Gap-C. Разрыв двойственности для примеров из данного класса  в среднем составляет около 21 %.  Размерность: 100 предприятий, 100 потребителей. Стоимость открытия любого предприятия  равна 3000. Матрица транспортных расходов gij имеет ровно 10 незапрещенных (небесконечных) элементов из множества {0, 1, 2, 3, 4} в каждой строке. Другими словами, каждое предприятие имеет ровно десять потенциальных потребителей, которые выбираются случайным образом с равномерным распределением из всего множества потребителей. Оптимальное решение содержит 14 или 15 открытых предприятий. Исходные данные в виде текстовых файлов доступны в первой колонке таблицы.  Расположение локальных оптимумов для первого примера можно увидеть на  диаграмме.

Все примеры класса Gap – B  gap-b.zip 107 Kb

Код Оптимум Разрыв двойственности (%) Оптимальное решение
331 45123 24.26 4 16 21 23 24 25 28 29 51 58 69 79 85 91 92
431 45132 22.52 20 22 32 37 49 55 60 62 69 74 80 84 87 88 92
531 45135 19.25 11 13 19 23 30 32 33 34 35 42 59 73 74 79 90
631 45140 19.22 1  7  17 20 24 33 77 80 83 84 85 92 95 99 100
731 45130 24.01 6 12 33 34 37 38 45 50 60 69 71 74 76  77  91
831 45138 22.86 4 17 25 27 46 47 54 56 63 82 84 89 91 95 100
931 42172 20.69 6 12 18 19 24 28 35 37 51 53 55 61 94 100
1031 42165 16.91 4 16 17 19 21 30 36 70 74 82 84 85 86 100
1131 42162 17.74 3  7  9  22 33 35 44 72 84 86 91 96 97 99
1231 45136 19.72 1  2  4  10 11 26 31 37 41 59 61 73 75  86  87
1331 42169 18.05 5  6  7  11 13 17 26 47 64 67 79 83 86 92
1431 42157 18.65 10 20 32 34 41 42 54 64 65 72 73 81 91 100
1531 42160 17.72 7  14 19 26 44 45 48 63 65 72 78 95 96 97
1631 45140 21.89 4  5  11 12 15 29 37 41 60 63 73 77 79 98 99
1731 42174 19.22 12 16 19 24 28 42 45 50 57 59 87 94 96 98
1831 45134 22.72 5  9  13 17 23 26 32 42 54 58 89 90 94 95 97
1931 45136 22.80 17 20 30 32 34 38 39 59 63 65 78 81 84 92 98
2031 45131 22.55 7  8  9  22 32 42 58 62 67 69 71 77 83 84 100
2131 45126 24.14 4  5  10 11 12 14 17 25 54 55 60 74 92 94 97
2231 42179 19.75 7  8  15 28 49 55 58 62 67 71 72 89 90 92
2331 45134 21.82 4  7  8  15 21 23 50 52 64 73 74 84 85 90 93
2431 45137 24.28 18 25 29 30 42 48 52 54 55 68 71 72 73 78 97
2531 45124 26.26 2 3 9 10 23 44 48 60 69 74 76 85 91 93 98
2631 45131 23.83 10 17  20 35 40 44 48 59 63 77 82 83 93 95 96
2731 42159 16.96 3 10 12 20 23 25 35 38 43 45 56 57 69 94
2831 42151 17.56 7  10 17 19 26 28 29 31 34 36 48 51 67 72
2931 45132 24.55 13 27 33 36 39 43 45 50 51 52 56 64 71 79 96
3031 45144 20.88 1  15 24 25 26 27 33 39 44 49 54 65 72 76  89
3131 42158 21.68 1  12 15 18 25 34 36 39 78 82 95 96 98 100
3231 45125 23.58 5 10 18 20 28 42 52 64 67 76 79 89 91 92 96

 

Класс Gap – С 

Примеры из класса Gap-C являются наиболее трудными в серии Gap-A, Gap-B, Gap-C.  Разрыв двойственности для них в среднем составляет около 28 %.  Размерность: 100 предприятий, 100 потребителей. Стоимость открытия любого предприятия  равна 3000. Матрица транспортных расходов gij имеет ровно 10 незапрещенных (небесконечных) элементов из множества {0, 1, 2, 3, 4} в каждом столбце и каждой строке. Другими словами, каждый потребитель имеет ровно десять потенциальных поставщиков-предприятий, а каждое предприятие имеет ровно десять потенциальных потребителей, те и другие выбираются случайным образом с равномерным распределением из соответствующих множеств. Оптимальное решение содержит 14 открытых предприятий. Исходные данные в виде текстовых файлов доступны в первой колонке таблицы. Расположение локальных оптимумов для первого примера можно увидеть на диаграмме.

Все примеры класса Gap – C  gap-c.zip 106 Kb

Код Оптимум Разрыв двойственности (%) Оптимальное решение
333 42147 28.39 7  18 24 26 28 29 34 50 53 57 66 75 80 92
433 42145 28.42 29 34 40 42 47 50 51 58 59 68 74 76 88 90
533 39177 22.99  9 30 33 35 40 54 60 68 71 72 84 91 92
633 42144 28.42 6  15 21 29 32 33 38 42 54 65 70 71 73 88
733 42137 28.42 3  33 36 38 42 49 54 55 56 65 76 91 94 96
833 42144 28.41 11  17 25 39 45 46 51 55 60 74 83 85 86 96
933 42130 28.39 5 12 20 22 25 33 47 57 67 80 84 93 97 98
1033 42138 28.41 1  7  8  12 14 17 28 32 44 49 52 63 74 100
1133 42147 28.41 3  13 14 18 23 28 34 37 38 59 72 83 89 91
1233 42142 28.41 1  3  9  14 25 45 48 52 72 73 82 88 90 94
1333 42140 28.41 1  2  4  23 26 42 49 55 66 70 71 86 91 97
1433 42152 28.42 17  22  25 39 49 53 55 65 69 72 74 79 80 83
1533 42133 28.40 2  5  19 22 33 35 38 51 52 65 66 67 73 91
1633 42141 28.42 23 24 35 37 42 51 52 71 82 88 90 96 97 100
1733 42134 28.41 8  32 44 52 53 55 57 65 71 79 82 89 95 99
1833 42139 28.42 5  8  12 18 31 34 41 51 54 57 74 76 83 90
1933 42137 28.41 6  13 16 22 28 58 64 65 69 76 77 87 91 92
2033 42140 28.40 5  11 24 27 28 33 57 61 68 73 75 84 94 98
2133 42138 28.38 3  10 12 15 26 28 52 57 81 91 95 97 98  100

2233

 42121 28.39 6  8  14 17 25 31 32 33 55 63 67 75 85 89
2333 42133 28.40 7  8  13 21 22 25 27 42 61 69 80 88 92 95
2433 42139 28.41 3  12  21 29 38 62 67 74 75 77 78 85 88 90
2533 42131 28.41 5  8  11 27 32 45 56 62 66 68 69 71 82 85
2633 42132 28.40 9  10  24 27 28 39 51 55 66 67 69 71 95 99
2733 42139 28.39 2  4  19 31 32 35 38 39 40 50 57 71 91 92
2833 42137 28.42 18  21  31 42 50 54 56 57 58 59 62 73 81 99
2933 42124 28.40 5  6  13 23 24 31 45 53 56 57 59 61 70 85
3033 42137 28.42 17  18  20 35 41 58 64 65 68 75 79 90 92 96
3133 42141 28.42 9  22  39 45 66 70 73 75 77 84 85 90 91 97
3233 42129 28.42 3 6 22 25 33 60 62 68 72 80 84 86 93 95

 ballred.gif (861 bytes) Главная страница библиотеки ballred.gif (861 bytes) Простейшая задача размещения ballred.gif (861 bytes)