Abstract: Задача о p-медиане по-прежнему остаётся актуальной, она хорошо изучена, существует широкий спектр методов её решения [1]. В ней необходимо открыть ровно p пунктов обслуживания, чтобы удовлетворить потребности клиентов с наименьшими затратами. В этой задаче, как и во многих других классических постановках, параметры считаются неизменными. Однако в реальных ситуациях такие характеристики, как спрос клиентов, их количество, затраты на обслуживание, могут меняться из-за роста цен, миграции населения и т.п. Возникает необходимость принимать решение в меняющихся условиях. В таких случаях обращаются к понятию устойчивости. В докладе изучается возможность учесть подобную ситуацию с помощью так называемой пороговой робастности [2, 3]. Рассматривается устойчивая (робастная) постановка задачи о p-медиане, где оптимизируется устойчивость, связанная со спросом клиентов. Такая задача имеет прикладное значение, она относительно новая, построение методов решения для неё представляет несомненный интерес. Основное внимание данной работы направлено на создание сложных тестовых примеров для проведения экспериментальных исследований новых алгоритмов. В процессе разработки методов решений важное значение имеет качество тестового материала. Поскольку устойчивая задача о p-медиане мало изучена, для неё не существовало библиотек тестовых примеров. Мы создали серии задач различной сложности, используя, в частности, идеи известной библиотеки тестовых задач «Дискретные задачи размещения» [4]. Размерности новых задач варьируются от 25 до 100, количество открываемых предприятий р меняется от 4 до 12. Необходимо отметить, что большинство построенных задач имеют большой разрыв целочисленности. Они требуют значительных временных затрат для таких известных решателей как CPLEX, Gurobi, LocalSolver. В докладе обсуждаются правила их построения, характеристики, сложности численных экспериментов.

Cite: Хмара И.С. , Леванова Т.В.
Решение устойчивой задачи о р-медиане
In compilation Прикладная математика и фундаментальная информатика. Материалы XIV Международной молодежной научно-практической конференции с элементами научной школы. – Омский государственный технический университет., 2024. – C.57-58. – ISBN 978-5-8149-3833-6. РИНЦ

Dates:

Published print:	Sep 18, 2024
Published online:	Sep 18, 2024

Identifiers:

Elibrary:

69141853

Citing: Пока нет цитирований