Аннотация:
В классической сетвой задаче размещения (Facility Location Problem, FLP) требуется разместить предприятия в вершинах заданного графа сети так, чтобы с минимальн
ыми затратами на открытие предприятий и транспортировку продукта единовременно удовлетворить спросы всех клиентов, находящихся в вершинах сети. Естественным обо
бщением классической задачи являются задачи с дополнительными ограничениями на объемы производства предприятий (Capacitated FLP, CFLP), а также с ограничениями
на пропускные способности коммуникаций сети (Restricted FLP, RFLP). В докладе рассматриваются задачи RFLP и однородная CFLP на простейших типах графов таких ка
к пути, звезды, деревья, графы с ограниченной древовидной шириной. Приводятся недавние результаты, полученные совместно с соавторами, по уточнению сложностного
статуса и построению точных полиномиальных (и даже линейных), а также псевдополиномиальных алгоритмов решения для частных случаев рассматриваемых задач.
|
