Программа вычисления нижней оценки целевой функции задачи о р-медиане

14 сентября 2018
153
Предметная область
Отрасли по ОКВЭД
Страна, регион, город Российская Федерация, Иркутская область, Иркутск
Отличия от конкурентов
Вид документа об охране ИС программа для ЭВМ
Номер документа ИС 201661376
Дата регистрации документа ИС 2016-04-05
Необходимые инвестиции для внедрения договорная
Сроки внедрения
Стоимость предоставления технологии договорная
Наличие экспертного заключения Нет

Польза для потенциального потребителя

Программа предназначена для вычисления нижней оценки целевой функции одной из базовых задач комбинаторной оптимизации - задачи р-медиан. В задаче задан граф, в вершинах которого размещены клиенты, подлежащие обслуживанию, и там же возможно размещение центров обслуживания, число которых ограничено заданной величиной р. Известны транспортные затраты на обслуживание каждого клиента из каждой вершины (матрица расстояний). Требуется разместить пункты обслуживания таким образом, чтобы суммарные затраты на обслуживание всех клиентов были минимальны. В программе реализован эвристический субградиентный алгоритм, максимизирующий недифференцирумую вогнутую двойственную функцию Лагранжа, полученную с помощью ослабления части ограничений, задающих допустимое множество задач. В качестве входных параметров программе передается имя файла, в котором содержится число вершин графа, матрица расстояний, верхняя оценка и число р. На выходе программы нижняя оценка целевой функции и список из р-вершин с лучшими оценками Лагранжа сохраняются в файл данных.