РЕШЕНИЕ ЗАДАЧИ О P-МЕДИАНЕ В ЦЕЛОЧИСЛЕННОЙ ПОСТАНОВКЕ (100,00 руб.)

Естественные и технические науки, № 5, 2016 Математическое моделирование, численные методы и комплексы программ Забудский Г.Г., доктор физико-математических наук, профессор, ведущий научный сотрудник Омского филиала Института математики им. <...> С.Л. Соболева Сибирского отделения Российской академии наук РЕШЕНИЕ ЗАДАЧИ О P-МЕДИАНЕ В ЦЕЛОЧИСЛЕННОЙ ПОСТАНОВКЕ Задача о p-медиане в целочисленной постановке решается с помощью алгоритма ветвей и границ. <...> Нижние границы целевой функции вычисляются с использованием лагранжевой релаксации. <...> Lower bounds of the goal function are calculated by lagrangean relaxation. <...> Постановка задачи и ее свойства Дано n объектов, соединенных сетью дорог известной длины. <...> Необходимо расположить заданное количество (p) пунктов обслуживания на сети дорог так, чтобы сумма кратчайших расстояний от пунктов обслуживания до объектов была минимальной. <...> На практике эта задача возникает, например, при размещении складов или подстанций в электросетях. <...> Граф G=(V,E) без петель и кратных ребер, где V − множество вершин, |V|=n, E − множество ребер. <...> Пусть dij0 кратчайшее расстояние от вершины i до вершины j или стоимость прикрепления j к i (т.е. объект j обслуживается пунктом i). <...> В работе [4] указывается, что в качестве области размещения пунктов обслуживания достаточно рассматривать вершины графа (объекты). <...> Вершины графа, в которые размещаются пункты обслуживания, будем называть медианными, иначе − немедианными. <...> Введем переменные xij следующим образом: xij=1, если вершина j прикрепляется к вершине i , иначе xij=0. <...> 0,1 , iV j V. , (5) Условия (2) означают, что каждая вершина прикреплена только к одной вершине; (3) − число медианных вершин p; (4) − вершина не может быть прикреплена к вершине, которая не является медианной. <...> Двойственная задача Лагранжа Среди различных двойственных задач двойственная по Лагранжу привлекает особое внимание. <...> Она приводит к различным алгоритмам решения как линейных задач большой размерности, так и задач выпуклого и невыпуклого <...>