Институт вычислительной математики и математической геофизики СО РАН

Тезисы докладов

В работе рассматривается хорошо известная задача о p-медиане. Задано два конечных множества I={1,..,m}- возможные пункты размещения для p предприятий и множество потребителей J={1,..,n}, а также матрица транспортных затрат на обслуживание потребителей. Требуется найти подмножество предприятий мощности p, чтобы обслужить всех потребителей с минимальными транспортными затратами. В работе исследовано поведение стандартного алгоритма локального спуска. Показано, что среднее число шагов для достижения локального минимума растет не быстрее линейной функции, если p - фиксированное число, и не быстрее квадратичной, если p - линейная функция от n. Полученные оценки не зависят от применяемых стратегий спуска. Приведены результаты численных экспериментов, показывающие влияние стратегий спуска на относительную погрешность получаемых локальных минимумов, число шагов алгоритма и время счета.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 2005, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 2005, Сибирское отделение Российской академии наук, Новосибирск
Администратор страницы: sojconf@sscc.ru