zbMATH — the first resource for mathematics

Investigation of the Weber problem and of stability of its solution. (Russian) Zbl 0653.90014
Investigated is the Weber problem and the stability of its solutions. This problem consists in locating facilities \(Y=\{y_ 1,y_ 2,...,y_ m\}\) so as to minimize \[ F(y_ 1,y_ 2,...,y_ m)=\sum^{n}_{i=1}\sum^{m}_{j=1}P_ j(x_ i)d(x_ i,y_ j)+\sum^{m-1}_{j=1}\sum^{m}_{k=j+1}P_ j(y_ k)d(y_ k,y_ j). \] The Weber problem on median graphs can be solved by an algorithm of D. K. Zambitskij [Izv. Akad. Nauk Mold. SSR, Ser. Fiz.-Tekh. Mat. Nauk 1980, No.2, 76-78 (1980; Zbl 0457.05026)] for trees, which is used to construct a complementary network for each cut of the graph, then determine in this network a minimal flow yielding which facilities must be located left or right from the cut.
Let \(Y_ s\) denote the set of facilities \(y_ i,y_ k,y_{\ell},..\). which must be located in vertex \(s_ 0\). Then the following theorem holds: If the location \((Y_ s,Y_ t)\) is optimal and \(Y_ s\neq \emptyset\), \(Y_ t\neq \emptyset\) then \((Y_ t,Y_ s)\) is not optimal.
In the case when the weight P(x) given for each vertex x is linearly dependent from parameters an algorithm is presented for the solution of the Weber problem.
Reviewer: V.K.Sibirskij
90B05 Inventory, storage, reservoirs
90B10 Deterministic network models in operations research
Full Text: EuDML