Locational Problems And Mathematical Programming

1.

Introduction.

The most simple locational problem has its mathematical origin in classical geometry, where it is known as Steiner's Problem [l]. It appeared, in a slightly generalized form, in the pioneering work

Über den Standort der Industrien

of Alfred Weber [2]. This form qf the problem, which we shall call the Steiner-Weber Problem, asks for a point in the plane that will minimize the weighted sum of distances to n given points in the plane. In spite of the simple and explicit form of the problem, relatively little is known about its solution, either analytically or computationally. The purpose of this paper is to discuss the problem from the point of view of mathematical programming. In Section 2, certain general properties and a set of necessary and sufficient conditions for a solution are derived. In Section 3, a problem dual to the Steiner-Weber Problem is formulated. This problem has a linear objective function and quadratic constraints; it possesses all of the desirable properties of the dual in linear programming and its solution yields a solution of the Steiner-Weber Problem trivially. In Section 4, some preliminary conclusions concerning computation are presented. Economic applications are the subject of a joint paper with R.E. Kuenne [3], to be published shortly; detailed computational methods will be treated in a later paper.

2.

Statement of the Steiner-Weber Problem

. Although the simpler properties of the problem have been amply discussed in the literature, for the sake of completeness and to establish notation, we shall restate the problem and derive some basic results here.