Действительно, при е [ф, z”) имеем d(vs, И) = Az” + В + В = L(Es, Et : 2), что следует из (2.7) и определения Az + В. Таким образом, при z = условия (2.4) не выполняются и соответствующее размещение не удовлетворяет ограничениям (2.2), (2.3). Очевидно, при < размещение также не является допустимым, поскольку недопустимо размещение со значением целевой функции и < z'•
Утверждение доказано.
Опишем второй этап МБА по шагам.
Шаг 1. С помощью бинарного поиска на интервале [z.L, zU] определяется интервал [ZN, zy] такой, что для значения (.N допустимого размещения не существует, а для zy существует. Для этого применяется процедура SLP. Полагаем z' := ZN. Переход на шаг 2.
Шаг 2. С помощью модифицированной процедуры SLP определяются вершины vs и vt, для которых не выполняется (2.4). Переход на шаг З.
Шаг З. Строится сеть С помощью алгоритма из [5] при z = г.' определяется кратчайший путь между Е, и Ер с множеством номеров дуг U. Длина пути является линейной функцией Az + В. Переход на шаг 4.
Шаг 4. Находится z”, для которого Az” + В = vt). Переход на шаг 5.
Шаг 5. Если е [ZN, (у] и для z” существует допустимое размещение, то переход на шаг 6.
Если е [:.N, (у] и для 3” допустимого размещения не существует, то полагаем := z”. Переход на шаг 2.
Если z” zy], то полагаем ZN, zU := zy. Переход на шаг 1.
Шаг 6. Записываются двойственные задачи (2.5) и (2.6) для пары Ц, Et. Переменные Л, К е U образуют базис в задаче (2.5). Переход к п. 6.1.
6.1. Каждой переменной Л, К е U, соответствует пара вершин ЦК), е(К) сети Nst(z) и уравнение в задаче (2.6). Решается система уравнений ib(k) е(К) = hk(z), К е U, и определяются значения переменных ii, i е 1. Переход к п. 6.2.
6.2. Решается система линейных неравенств ib(k) — hk(z), К Е U, и находится интервал [4, ф], на котором путь U является кратчайшим между Es и Et. Переход на шаг 7.
Шаг 7. Если z” е [Ч, ф], то z” — оптимальное значение целевой функции (2.1).
Стоп. Иначе полагаем := z , zU := z”. Переход на шаг 1.
Трудоемкость МБА равна О(п(т + п)(т + nlogM )). Он проверяет не только текущую точку, полученную бинарным перебором, но и некоторую ее окрестность. В МБА длина интервала линеЙности F(z) не имеет прямой зависимости от М и будет не меньше, чем в [З].
Следующий пример демонстрирует, что МБА является более ”устойчивым” по отношению к изменению начальных данных. Пусть все wr, со, i I,je .I, и ив, Ьјк,ј, К е Ј,ј К, равны 1. Тогда алгоритм из [З] будет иметь вычислительную сложность + п)т). Однако если одно из значений заменить на (Q — l)/Q, где Q — некоторая константа, то его трудоемкость возрастет до О(п(т + + nlog Q )). При этом время работы МБА практически не изменится.
В вычислительном эксперименте МБА тестировал существенно меньшее количество точек, чем бинарный алгоритм (БА). Результаты экспериментов приведены в таблице.
З. РЕШЕНИЕ ЗАДАЧИ МСС
Опишем алгоритм поиска оптимального размещения в дискретном варианте задачи (1.2), (1 А). В этом случае, размещение — это однозначное отображение л : Ј —- 1, т.е. п(ј) — номер вершины, в которую размещен объект), и заданы только ограничения на максимальные расстояния между новыми и фиксированными объектами.
ММС-задача на древовидной сети
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.