РОССИЙСКАЯ ФЕДЕРАЦИЯ
ФЕДЕРАЛЬНАЯ СЛУЖБА ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ
ГОСУДАРСТВЕННАЯ РЕГИСТРАЦИЯ ПРОГРАММЫ ДЛЯ ЭВМ

Номер регистрации (свидетельства): 2016613761

Дата регистрации: 05.04.2016

Номер и дата поступления заявки: 2016610980 09.02.2016

Дата публикации: 20.05.2016

Контактные реквизиты:
vil@icc.ru
	
Автор:
Васильев Игорь Леонидович

Правообладатель:
Федеральное государственное бюджетное учреждение науки Институт динамики систем и теории управления имени В.М. Матросова Сибирского отделения Российской академии наук (ИДСТУ СО РАН)

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

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

Тип реализующей ЭВМ: IBM РС-совмест. ПК

Язык программирования: С++

Вид и версия операционной системы: Windows ХР/7/8

Объем программы для ЭВМ: 9,1 Кб