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

Библиографическая ссылка: Цидулко О.Ю.
О задаче размещения с дополнительными ограничениями на графах древесного вида (Facility location problems with capacity constraints on tree-like graphs)
Вторая конференция Математических центров России 07-11 нояб. 2022