|
This article is cited in 1 scientific paper (total in 1 paper)
Applied mathematics
Direct solution of a minimax location problem on the plane
with rectilinear metric in a rectangular area
P. V. Plotnikov, N. K. Krivulin St. Petersburg State University, 7–9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation
Abstract:
A minimax single-facility location problem with rectilinear (Manhattan) metric is examined
under constraints on the feasible location region, and a direct, explicit solution of the problem
is suggested using methods of tropical (idempotent) mathematics. When no constraints are
imposed, this problem, which is also known as the Rawls problem or the messenger boy
problem, has known geometric and algebraic solutions. In the present article, a solution to
the problem is investigated subject to constraints on the feasible region, which is given by a
rectangular area. At first, the problem is represented in terms of tropical mathematics as a
tropical optimization problem, a parameter is introduced to represent the minimum value of
the objective function, and the problem is reduced to a parametrized system of inequalities.
This system is solved for one variable, and the existence conditions of solution are used to
obtain optimal values of the second parameter by using an auxiliary optimization problem.
Then, the obtained general solution is transformed into a set of direct solutions, written in
a compact closed form for different cases of relations between the initial parameters of the
problem. Graphical illustrations of the solution are given for several positions of the feasible
location region on the plane.
Keywords:
Rawls location problem, constrained location, rectilinear metric, idempotent
semifield, tropical optimization, complete solution.
Received: December 27, 2017 Accepted: March 15, 2018
Citation:
P. V. Plotnikov, N. K. Krivulin, “Direct solution of a minimax location problem on the plane
with rectilinear metric in a rectangular area”, Vestnik S.-Petersburg Univ. Ser. 10. Prikl. Mat. Inform. Prots. Upr., 14:2 (2018), 116–130
Linking options:
https://www.mathnet.ru/eng/vspui362 https://www.mathnet.ru/eng/vspui/v14/i2/p116
|
Statistics & downloads: |
Abstract page: | 169 | Full-text PDF : | 40 | References: | 20 | First page: | 8 |
|