TY - JOUR

T1 - Прямое решение минимаксной задачи размещения в прямоугольной области на плоскости с прямоугольной метрикой

AU - Плотников, П.В.

AU - Кривулин, Н.К.

N1 - Плотников П. В., Кривулин Н. К. Прямое решение минимаксной задачи размещения в прямоугольной области на плоскости с прямоугольной метрикой // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2018. Т. 14. Вып. 2. С. 116–130. https://doi.org/10.21638/11702/spbu10.2018.204

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Complete solution

KW - Constrained location

KW - Idempotent semifield

KW - Rawls location problem

KW - Rectilinear metric

KW - Tropical optimization

UR - http://www.scopus.com/inward/record.url?scp=85090595752&partnerID=8YFLogxK

U2 - 10.21638/11702/spbu10.2018.204

DO - 10.21638/11702/spbu10.2018.204

M3 - статья

AN - SCOPUS:85090595752

VL - 14

SP - 116

EP - 130

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

SN - 1811-9905

IS - 2

ER -