Многостадийная задача размещения
line.jpg (1129 bytes)

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

Примеры с тремя галактиками локальных оптимумов

(3-Galax)  

Класс тестовых примеров "3 галактики" очень сложный для методов локального поиска и весьма прост для метода ветвей и границ. Локальные оптимумы в данных примерах распадаются на три множества (галактики), расположенные достаточно далеко друг от друга. Значения целевой функции велики для локальных оптимумов одной галактики и малы для двух других. Глобальный оптимум расположен в одной из галактик. Для того чтобы достичь глобальный оптимум, находясь в другой галактике с малыми значениями целевой функции, необходимо посетить галактику с большими значениями целевой функции, что и представляет сложность для методов локального поиска.

Размерность примеров: 50 предприятий, 100 технологических цепочек, 100 потребителей. Множество из 50 предприятий разбито на две части: 48 предприятий с низкой стоимостью 300, и два предприятия с высокой стоимостью 20000. Каждая цепочка состоит из 5 предприятий: 4 выбираются случайно из 48 "дешевых" и пятое — одно из двух "дорогих" так, что 50 ассоциаций содержат первое "дорогое" предприятие и 50 — второе "дорогое" предприятие. 

Элементы матрицы транспортных расходов генерируются по аналогии с классом Eucl  для простейшей задачи размещения. На квадрате со стороной 7000 выбрасываются случайным образом 100 точек. Элемент матрицы с индексами ij равен евклидовому расстоянию между точками i и j. Построенная таким способом матрица удовлетворяет неравенству треугольника. 

Расположение локальных оптимумов для одного из примеров можно увидеть на диаграмме.

В таблице приведены исходные данные и результаты расчетов для 30 тестовых примеров. В первом столбце таблицы даны стартовые числа (коды) для датчика псевдослучайных чисел, позволяющие формировать данные примеры. Для удобства здесь же содержатся ссылки на файлы исходных данных в текстовом формате. Второй столбец содержит оптимальные значения целевой функции, полученные методом ветвей и границ. В третьем столбце приведены оценки разрыва двойственности.  В последнем столбце содержатся оптимальные решения (номера открываемых предприятий).

Все примеры класса Galax.zip 1320 Kb

Коды Оптимум

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

Номера открываемых предприятий

471

35789

34,1

1, 2, 3, 5, 6, 7, 12, 14, 15, 17, 18, 19, 21, 23, 24, 25, 26, 29, 30, 33, 34, 36, 37, 39, 40, 41, 42, 43, 44, 46, 47, 49

472

35282

 33,1

2, 3, 4, 5, 7, 9, 10, 12, 13, 14, 17, 18, 19, 20, 25, 27, 28, 29, 32, 39, 40, 41, 45, 46, 49

473

35880

 34,4

2, 6, 7, 9, 10, 11, 12, 14, 15, 18, 19, 20, 21, 22, 24, 26, 27, 28, 29, 31, 33, 36, 38, 40, 42, 43, 45, 46, 49

474

35916

 34,5

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 17, 18, 19, 20, 23, 24, 25, 26, 29, 32, 34, 37, 38, 40, 42, 43, 44, 45, 47, 48, 49

475

35277

 33,2

1, 3, 4, 9, 11, 12, 14, 15, 16, 19, 20, 22, 23, 24, 26, 28, 29, 30, 31, 32, 35, 36, 37, 38, 39, 40, 41, 42, 45, 50

476

34999

 32,6

2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 18, 19, 22, 25, 30, 31, 32, 33, 36, 40, 41, 43, 44, 45, 46, 47, 48, 49

477

35329

 33,8

1, 2, 4, 5, 6, 11, 13, 14, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 29, 30, 31, 33, 35, 36, 37, 38, 39, 41, 42, 43, 44, 50

478

35051

 33,6

1, 3, 4, 5, 6, 7, 8, 10, 12, 13, 15, 16, 17, 18, 19, 21, 23, 24, 29, 32, 33, 37, 39, 40, 44, 46, 50

479

35208

 32,9

1, 2, 8, 10, 12, 13, 15, 17, 18, 20, 21, 23, 25, 26, 27, 29, 30, 31, 32, 33, 35, 37, 38, 39, 43, 44, 46, 47, 48, 49

480

35114

 32,7

2, 4, 5, 7, 8, 9, 12, 13, 14, 15, 17, 18, 19, 23, 24, 25, 26, 30, 33, 34, 35, 37, 38, 41, 43, 44, 45, 50

481

35457

 33,9

1, 3, 8, 9, 13, 16, 17, 18, 19, 20, 22, 28, 29, 33, 37, 38, 40, 41, 44, 45, 48, 50

482

35248

 32,8

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 15, 16, 17, 18, 19, 21, 23, 24, 25, 26, 28, 31, 32, 34, 36, 37, 38, 39, 40, 42, 44, 46, 48, 49

483

35524

 33,7

2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 19, 20, 21, 23, 24, 25, 26, 28, 29, 33, 34, 36, 37, 38, 39, 41, 44, 45, 47, 48, 49

484

35891

 34,4

2, 3, 5, 6, 7, 9, 10, 12, 13, 17, 18, 19, 23, 28, 29, 30, 33, 36, 37, 38, 40, 41, 42, 48, 50

485

35403

 33,9

3, 4, 5, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 23, 26, 27, 29, 33, 34, 38, 39, 40, 41, 43, 44, 45, 49

486

35222

 33,4

1, 2, 3, 4, 6, 9, 10, 11, 12, 13, 14, 15, 18, 22, 23, 24, 26, 28, 29, 34, 36, 37, 38, 43, 44, 46, 47, 50

487

35635

 34,3

1, 2, 3, 6, 9, 11, 12, 16, 17, 18, 20, 22, 23, 24, 28, 29, 30, 31, 33, 34, 35, 37, 39, 40, 41, 42, 43, 45, 46, 49

488

34982

 33,0

1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 20, 22, 23, 28, 30, 32, 34, 37, 40, 42, 44, 45, 46, 47, 50

489

35903

 34,6

2, 4, 5, 7, 9, 10, 11, 13, 14, 17, 18, 20, 21, 22, 23, 27, 29, 30, 33, 34, 36, 38, 39, 41, 42, 44, 45, 46, 47, 50

490

34504

 30,9

2, 3, 4, 5, 6, 8, 10, 11, 12, 13, 14, 15, 20, 23, 25, 26, 27, 28, 29, 30, 31, 32, 35, 39, 40, 41, 44, 48, 49

491

35258

 33,5

1, 3, 4, 8, 10, 11, 12, 13, 14, 16, 17, 19, 21, 22, 24, 25, 28, 31, 32, 33, 34, 35, 37, 38, 42, 43, 46, 47, 50

492

35602

 34,1

1, 2, 3, 6, 7, 8, 9, 11, 14, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 28, 30, 32, 36, 37, 38, 40, 43, 44, 45, 46, 47, 49

493

35067

 32,6

1, 2, 3, 5, 7, 8, 9, 10, 12, 15, 18, 19, 20, 21, 22, 24, 27, 28, 30, 36, 37, 38, 39, 40, 42, 43, 48, 50

494

35304

 32,7

2, 3, 4, 5, 6, 9, 12, 13, 14, 15, 16, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 32, 34, 38, 39, 43, 45, 46, 47, 48, 50

495

35417

 33,6

1, 2, 3, 4, 5, 6, 10, 12, 13, 16, 17, 20, 22, 23, 25, 26, 27, 29, 31, 32, 34, 36, 37, 38, 40, 41, 44, 47, 50

496

35643

 34,3

4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 19, 20, 21, 23, 25, 29, 32, 36, 38, 39, 40, 41, 45, 46, 47, 48, 49

497

35259

 33,7

2, 3, 4, 5, 6, 9, 10, 11, 12, 14, 15, 18, 19, 20, 21, 24, 27, 30, 31, 32, 35, 37, 38, 40, 41, 42, 44, 46, 50

498

35393

 33,6

1, 2, 3, 4, 5, 6, 9, 10, 12, 13, 17, 20, 24, 25, 26, 27, 29, 30, 32, 35, 36, 38, 39, 42, 45, 46, 48, 50

499

35425

 33,4

2, 4, 5, 7, 8, 10, 12, 14, 15, 16, 19, 22, 25, 27, 30, 31, 33, 34, 35, 36, 37, 38, 40, 42, 43, 46, 47, 48, 50

500

35168

 32,8

4, 5, 6, 7, 9, 12, 13, 14, 15, 18, 20, 21, 23, 24, 25, 26, 27, 29, 30, 31, 32, 35, 36, 37, 40, 42, 44, 46, 48, 49