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

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