On the Existence of an Integer Solution of the Relaxed Weber Problem for a Tree Network

Рассмотрена задача нахождения оптимального размещения вершин древовидной сети в монтажном пространстве, представляющем конечное множество. Критерием оптимальности является минимизация общей стоимости размещения в точках пространства и стоимости коммуникаций. Допускается размещение разных вершин дерева в одной точке монтажного пространства. Рассматриваемая проблема известна как задача Вебера для древовидной сети. В данной работе дано представление задачи Вебера как задачи о линейном программировании. Доказано, что множество оптимальных решений соответствующей релаксированной задачи Вебера для древовидной сети содержит целочисленное решение. Этот факт позволяет доказать существование седловой точки
доказательстве эффективности алгоритмов декомпозиции для задач, отличающихся от задачи Вебера наличием дополнительных ограничений.

Ключевые слова

задача размещения; линейное программирование; двойственность; релаксация; целочисленное решение; полиномиальный алгоритм; задача Вебера.

Литература

1. Beresnev V.L., Diskretnye zadachi razmeshcheniya i polinomy ot bulevykh peremennykh [Discrete Location Problems and Polynomials of Boolean Variables]. Novosibirsk, Sobolev Institute Press, 2005. (in Russian)
2. Nickel S., Puerto J. Location Theory. Heidelberg, Springer, 2005.
3. Zabudskii G.G., Veremchuk N.S. An Algorithm for Finding an Approximate Solution to the Weber Problem on a Line with Forbidden Gaps. Journal of Applied and Industrial Mathematics, 2016, vol. 10, no. 1, pp. 136-144. DOI: 10.1134/S1990478916010154
4. Zabudskii G.G., Koval A.A. Solving a Maximin Location Problem on the Plane with Given Accuracy. Automation and Remote Control, 2014, vol. 75, pp. 1221-1230. DOI:10.1134/S0005117914070042
5. Panyukov A.V., Pelzwerger B.V. Polynomial Algorithms to Finite Weber Problem for a Tree Network. Journal of Computational and Applied Mathematics, 1991, vol. 35, pp. 291-296. DOI:10.1016/0377-0427(91)90215-6
6. Ivanko E.E. Iterative Equitable Partition of Graph as a Model of Constant Structure Discrete Time Closed Semantic System. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2017, vol. 10, no. 4, pp. 26-34. DOI: 10.14529/mmp170403
7. Panyukov A.V. The Relaxation Polyhedron of Weber Problem. Non-Smooth and Discontinuous Problems of Control and Optimization, Chelyabinsk, 1998, pp. 171-174.
8. Panyukov A.V. Location of a Tree Network for a Finite Set. Abstracts of the Seventh Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms and Applications, Kosice, Safary University, 2013, p. 64.