Дискретные задачи размещения ballred.gif (861 bytes) Библиотека тестовых задач
line.jpg (1129 bytes)

ballred.gif (861 bytes) Библиотека тестовых задач ballred.gif (861 bytes) Задача о p-медиане ballred.gif (861 bytes)

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

Примеры с большим разрывом двойственности являются трудными для точных методов, основанных на линейной релаксации. Ниже приводятся три класса таких примеров  Gap-A, Gap-B, Gap-C  для задачи о p-медиане. Разрыв двойственности в них колеблется от 30% до 60%. Для всех примеров n = m =100, а матрица транспортных затрат строится точно также как и  матрица (gij) для примеров Gap-A, Gap-B, Gap-C для простейшей задачи размещения (UFLP). Величина p полагается равной числу открываемых предприятий в оптимальном решении для соответствующего примера в UFPL.

Класс Gap-A 

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

Матрица транспортных затрат (gij) содержит в каждом столбце 10 небесконечных элементов. Эти элементы выбираются случайным образом независимо друг от друга с равномерным распределением из множества {0, 1, 2, 3, 4}. Исходные данные в виде текстового файла доступны в первой колонке нижеследующей таблицы.

Все примеры из класса Gap-A   pm_gap-a.zip  106 Kb

Код Оптимум

Разрыв 
двойственности (%)

 Оптимальное решение
332 154  34.30 10, 14, 17, 33, 34, 40, 44, 50, 59, 63, 64, 78
432 155  46.02 12, 21, 35, 44, 47, 57, 58, 61, 65, 75, 80, 91
532 150  35.53 2, 4, 31, 32, 40, 42, 52, 56, 73, 77, 80, 89
632 162  39.40 10, 13, 38, 52, 63, 64, 67, 75, 82, 85, 87, 93
732 157  33.14 3, 5, 11, 17, 25, 31, 37, 51, 53, 59, 95
832 136  32.02 13, 19, 21, 22, 32, 34, 40, 56, 60, 62, 87, 98
932 133  36.73 16, 30, 37, 41, 46, 55, 56, 58, 63, 67, 72, 87
1032 127  28.82 12, 20, 21, 23, 33, 36, 38, 41, 48, 64, 67, 75
1132 163  44.14 10, 16, 23, 58, 68, 69, 74, 75, 82, 88, 94, 100
1232 123  25.85 3, 10, 18, 21, 22, 31, 35, 57, 69, 71, 87, 92, 99
1332 164  40.01 4, 9, 17, 28, 59, 66, 71, 76, 79, 82, 91, 97
1432 150  30.98 5, 11, 22, 25, 41, 55, 61, 62, 65, 75, 84, 89
1532 158  40.34 7, 10, 22, 23, 31, 32, 40, 45, 52, 54, 55, 59
1632 141  36.36 9, 10, 21, 35, 37, 39, 41, 45, 48, 67, 80, 86
1732 157  42.21 4, 13, 33, 38, 41, 65, 73, 75, 85, 90, 91, 96
1832 135  38.86 7, 11, 13, 27, 28, 30, 34, 46, 47, 48, 77, 78
1932 146  34.64 9, 32, 39, 40, 45, 56, 61, 62, 70, 72, 90, 98
2032 150  38.46 22, 26, 28, 41, 49, 61, 64, 67, 80, 84, 93, 97
2132 140  34.38 2, 13, 23, 36, 43, 48, 50, 64, 76, 77, 85, 91
2232 145  29.26 4, 5, 10, 31, 34, 42, 47, 70, 81, 92, 94, 100
2332 172  49.40 12, 13, 32, 36, 38, 44, 51, 57, 67, 71, 87, 88
2432 137  28.94 3, 7, 11, 14, 21, 23, 28, 31, 68, 74, 87, 90
2532 153  44.32 11, 25, 28, 33, 43, 47, 52, 64, 79, 95, 98, 99
2632 164  47.28 5, 9, 16, 25, 26, 28, 44, 66, 79, 91, 95, 99
2732 123  30.45 2, 6, 11, 12, 13, 21, 41, 48, 49, 63, 64, 90, 91
2832 145  30.20 9, 11, 21, 26, 33, 34, 65, 67, 76, 83, 84, 90
2932 155  41.18 2, 16, 19, 52, 55, 62, 71, 76, 77, 81, 84, 91
3032 113  32.46 9, 27, 35, 39, 43, 53, 66, 67, 72, 73, 89, 93
3132 130  30.12 1, 24, 26, 30, 31, 54, 60, 62, 63, 83, 85, 96, 99
3232 157  43.96 5, 17, 30, 33, 38, 41, 50, 55, 64, 71, 89, 95

 

Класс Gap-B

Матрица транспортных затрат (gij) содержит в каждой строке 10 небесконечных элементов. Эти элементы выбираются случайным образом независимо друг от друга с равномерным распределением из множества {0, 1, 2, 3, 4}. Исходные данные в виде текстового файла доступны в первой колонке нижеследующей таблицы.

Все примеры из класса Gap-B   pm_gap-b.zip  106 Kb

Код

Оптимум

Разрыв 
двойствен ности (%)

Оптимальное решение

331

123

35.33

 4, 16, 21, 23, 24, 25, 28, 29, 51, 58, 69, 79, 85, 91, 92

431

132

34.07

 20, 22, 32, 37, 49, 55, 60, 62, 69, 74, 80, 84, 87, 88, 92

531

135

32.55

 11, 13, 19, 23, 30, 32, 33, 34, 35, 42, 59, 73, 74, 79, 90

631

140

42.43

 1, 7, 17, 20, 24, 33, 77, 80, 83, 84, 85, 92, 95, 99, 100

731

130

33.18

 6, 12, 33, 34, 37, 38, 45, 50, 60, 69, 71, 74, 76, 77, 91

831

138

32.34

 4, 17, 25, 27, 46, 47, 54, 56, 63, 82, 84, 89, 91, 95, 100

931

172

61.06

 6, 12, 18, 19, 24, 28, 35, 37, 51, 53, 55, 61, 94, 100

1031

165

55.18

 4, 16, 17, 19, 21, 30, 36, 70, 74, 82, 84, 85, 86, 100

1131

162

44.11

 3, 7, 9, 22, 33, 35, 44, 72, 84, 86, 91, 96, 97, 99

1231

136

34.09

 1, 2, 4, 10, 11, 26, 31, 37, 41, 59, 61, 73, 75, 86, 87

1331

169

45.77

 5, 6, 7, 11, 13, 17, 26, 47, 64, 67, 79, 83, 86, 92

1431

157

47.51

 10, 20, 32, 34, 41, 42, 54, 64, 65, 72, 73, 81, 91, 100

1531

160

47.61

 7, 14, 19, 26, 44, 45, 48, 63, 65, 72, 78, 95, 96, 97

1631

140

24.53

 4, 5, 11, 12, 15, 29, 37, 41, 60, 63, 73, 77, 79, 98, 99

1731

174

52.42

 12, 16, 19, 24, 28, 42, 45, 50, 57, 59, 87, 94, 96, 98

1831

134

35.97

 5, 9, 13, 17, 23, 26, 32, 42, 54, 58, 89, 90, 94, 95, 97

1931

136

33.44

 17, 20, 30, 32, 34, 38, 39, 59, 63, 65, 78, 81, 84, 92, 98

2031

131

37.92

 7, 8, 9, 22, 32, 42, 58, 62, 67, 69, 71, 77, 83, 84, 100

2131

126

40.35

 4, 5, 10, 11, 12, 14, 17, 25, 54, 55, 60, 74, 92, 94, 97

2231

179

51.60

 7, 8, 15, 28, 49, 55, 58, 62, 67, 71, 72, 89, 90, 92

2331

134

29.93

 4, 7, 8, 15, 21, 23, 50, 52, 64, 73, 74, 84, 85, 90, 93

2431

137

38.67

 18, 25, 29, 30, 42, 48, 52, 54, 55, 68, 71, 72, 73, 78, 97

2531

124

35.48

 2, 3, 9, 10, 23, 44, 48, 60, 69, 74, 76, 85, 91, 93, 98

2631

131

31.26

 10, 17, 20, 35, 40, 44, 48, 59, 63, 77, 82, 83, 93, 95, 96

2731

159

47.60

 3, 10, 12, 20, 23, 25, 35, 38, 43, 45, 56, 57, 69, 94

2831

151

47.37

 7, 10, 17, 19, 26, 28, 29, 31, 34, 36, 48, 51, 67, 72

2931

132

33.53

 13, 27, 33, 36, 39, 43, 45, 50, 51, 52, 56, 64, 71, 79, 96

3031

144

36.73

 1, 15, 24, 25, 26, 27, 33, 39, 44, 49, 54, 65, 72, 76, 89

3131

158

40.71

 1, 12, 15, 18, 25, 34, 36, 39, 78, 82, 95, 96, 98, 100

3231

125

37.67

 5, 10, 18, 20, 28, 42, 52, 64, 67, 76, 79, 89, 91, 92, 96

Класс Gap-C 

Матрица транспортных затрат (gij) содержит в каждом столбце и каждой строке ровно 10 небесконечных элементов. Эти элементы выбираются случайным образом независимо друг от друга с равномерным распределением из множества {0, 1, 2, 3, 4}. Исходные данные в виде текстового файла доступны в первой колонке нижеследующей таблицы.

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

Код

Оптимум

Разрыв
двойственности (%)

Оптимальное решение

333

147

 39.73

 7, 18, 24, 26, 28, 29, 34, 50, 53, 57, 66, 75, 80, 92

433

145

 58.77

 29, 34, 40, 42, 47, 50, 51, 58, 59, 68, 74, 76, 88, 90

533

142

 59.56

 5, 17, 21, 33, 45, 48, 52, 55, 60, 63, 81, 90, 97, 99

633

144

 41.91

 6, 15, 21, 29, 32, 33, 38, 42, 54, 65, 70, 71, 73, 88

733

137

 41.52

 3, 33, 36, 38, 42, 49, 54, 55, 56, 65, 76, 91, 94, 96

833

144

 34.83

 11, 17, 25, 39, 45, 46, 51, 55, 60, 74, 83, 85, 86, 96

933

130

 37.65

 5, 12, 20, 22, 25, 33, 47, 57, 67, 80, 84, 93, 97, 98

1033

138

 43.06

 1, 7, 8, 12, 14, 17, 28, 32, 44, 49, 52, 63, 74, 100

1133

147

 43.36

 3, 13, 14, 18, 23, 28, 34, 37, 38, 59, 72, 83, 89, 91

1233

142

 41.17

 1, 3, 9, 14, 25, 45, 48, 52, 72, 73, 82, 88, 90, 94

1333

140

 44.39

 1, 2, 4, 23, 26, 42, 49, 55, 66, 70, 71, 86, 91, 97

1433

152

 44.20

 17, 22, 25, 39, 49, 53, 55, 65, 69, 72, 74, 79, 80, 83

1533

133

 41.94

 2, 5, 19, 22, 33, 35, 38, 51, 52, 65, 66, 67, 73, 91

1633

141

 45.24

 23, 24, 35, 37, 42, 51, 52, 71, 82, 88, 90, 96, 97, 100

1733

134

 43.98

 8, 32, 44, 52, 53, 55, 57, 65, 71, 79, 82, 89, 95, 99

1833

139

 45.56

 5, 8, 12, 18, 31, 34, 41, 51, 54, 57, 74, 76, 83, 90

1933

137

 38.16

 6, 13, 16, 22, 28, 58, 64, 65, 69, 76, 77, 87, 91, 92

2033

140

 41.56

 5, 11, 24, 27, 28, 33, 57, 61, 68, 73, 75, 84, 94, 98

2133

138

 36.30

 3, 10, 12, 15, 26, 28, 52, 57, 81, 91, 95, 97, 98, 100

2233

121

 40.94

 6, 8, 14, 17, 25, 31, 32, 33, 55, 63, 67, 75, 85, 89

2333

133

 42.29

 7, 8, 13, 21, 22, 25, 27, 42, 61, 69, 80, 88, 92, 95

2433

139

 43.92

 3, 12, 21, 29, 38, 62, 67, 74, 75, 77, 78, 85, 88, 90

2533

131

 42.17

 5, 8, 11, 27, 32, 45, 56, 62, 66, 68, 69, 71, 82, 85

2633

132

 40.18

 9, 10, 24, 27, 28, 39, 51, 55, 66, 67, 69, 71, 95, 99

2733

139

 37.31

 2, 4, 19, 31, 32, 35, 38, 39, 40, 50, 57, 71, 91, 92

2833

137

 41.92

 18, 21, 31, 42, 50, 54, 56, 57, 58, 59, 62, 73, 81, 99

2933

124

 37.73

 5, 6, 13, 23, 24, 31, 45, 53, 56, 57, 59, 61, 70, 85

3033

137

 39.29

 17, 18, 20, 35, 41, 58, 64, 65, 68, 75, 79, 90, 92, 96

3133

141

 47.59

 9, 22, 39, 45, 66, 70, 73, 75, 77, 84, 85, 90, 91, 97

3233

129

 40.96

 3, 6, 22, 25, 33, 60, 62, 68, 72, 80, 84, 86, 93, 95

ballred.gif (861 bytes) Библиотека тестовых задач ballred.gif (861 bytes) Задача о p-медиане ballred.gif (861 bytes)