3. Итерационный процесс для решения задачи построения 1-медианы в случае бесконечного графа, вложенного в евклидову плоскость, состоит в следующем [8].

Пусть G - бе .конечный полный граф, представляющий евклидову плоскость, и пусть - заданное подмножество вершин, состоящее из п точек с координатами (х;, yi), i = 1, 2, . . ., га. Требуется выбрать некоторую точку г/ ) для расположения в ней медианной вершины и чтобы при этом выражение

было минимальным; здесь Vi - вес точки с координатами (х;, yi) и dim евклидово расстояние:

dim-V[{i-m) + {yi-ym)].

В точке минимума мы имеем: 1 = 1/

Vi (У1 - Ут)

= 0.

Эти уравнения можно решить итерационным методом, представив их предварительно в следующем виде:

(3) (4)

Начиная с некоторой точки (xm, J/m)i можно вычислить расстояния dim, а затем, используя выражения (3) и (4), найти новое лучшее приближение для (х^, т). Затем заново вычисляются расстояния dim и координаты Хт и Ут- Процесс продолжается до тех пор, пока не стабилизируются величины х„ и ут-

Используя описанный итерационный метод, найти 1-медиану в том слз^ае, когда множество S состоит из следующих точек: (2,2), (2,6), (4,8), (5,5), (6,1), (8,6) и (9,3) с весами для всех вершин, равными = 1.

Показать, что результат в этом итерационном процессе при нахождении глобального оптимума для (х„, ) не зависит от выбора начального расположецид этой точки.

4. Распространить приведенную выше итерационную схему на обилий случай нахождения р-медианы. Позволяет ли этот обоб-ш;енный метод получать глобальный оптимум для р-медианы?

5. Пусть граф G = {X, Г) является деревом и после удаления ребра {Xi, Xj) распадается на две связные компоненты Gi = (Xj, Г) viGj = {Xj, Г), где Xi 6 Xi, xj Xj-a Xi \j X] = X. Введем обозначение:

Показать, что медиана x графа G удовлетворяет условиям:

(i) если V (Xi) V (Xj), то ж 6 X

(ii) если I {Xi) v {Xj), то х не меняется при замене графа G графом G}, у которого вес вершины xj полагается равным Vj + -\- V (Xj). Учитывая эти факты, дать алгоритм для нахождения медианной вершины в дереве, который был бы более эффективным, чем непосредственное использование уравнений (6.2) и (6.3) (см. 113]).

7. Список литературы

1. Beale Е. М. L. (1970), Selecting an optimumsubset. Integer and nonlinear programming, Abadie, Ed., North Holland, Amsterdam.

2. Cabot A. v., Francis R. L., Stary M. A. (1970), A network flow solution to a rectilinear distance facility location problem, AIIE Trans., 2, p. 132.

3. Christofides N., Eilon S. (1969), An algorithm for the vehicle dispatching problem, Opl. Res. Quart., 20, p. 309.

4. Christofides N., Eilon S. (1972), Algorithms for large scale travelling salesman problems, Opl. Res. Quart., 23, p. 511.

5. Cooper L. (1963), Location-allocation problems. Ops. Res., 11, p. 331.

6. Curry G. R., Skeith R. W. (1969), A dynamic programming algorithm for facility location and allocation, AIIE Trans., 1, p. 133.

7. Efroymson E., Ray T. L. (1966), A branch and bound algorithm for plant location. Ops. Res., 14, p. 361.

8. Eilon S., Watson-Gandy C. D. Т., Christofides N. (1971), Distribution management: mathematical modelling and practical analysis. Griffin, London.

9. Ellwein L. В., Gray P. (1971), Solving fixed charge location-allocation problems with capacity and configuration constraints, AIIE Trans., 3, p. 290.

10. Elson D. G. (1972), Site location via mixed-integer programming, Opl. Res. Quart., 23, p. 31.

11. Garfinkel R. S., Nemhauser G. L. (1972), Integer programming, Wiley, New York,

12. Goldman A. J. (1969), Optimal locations for centres in a network, Trans. Sci., 3, p. 352.

13. Goldman A. J. (1970), Optimal centre location in simple networks. Paper FP 6.1, presented at the 38th National Meeting of the Operations Research Soc. of America, Detroit.

14. Goldman A. J., Mayers P. R. (1965), A domination theorem for optimal locations, Ops. Res., 13, 13-147 (Abstract).

15. Gray р. (1967), Mixed integer programming algorithm for site selection and other fixed charge problems having capacity constraints. Department of Operations Research, Report No. 6, Stanford University.

16. Hakimi S. L. (1965), Optimum distribution of switching centres in a communications network and some related graph theoretical problems.

17. Hakimi S. L. (1964), Optimum locations of switching centres and the absolute centres and medians of a graph. Ops. Res., 12, p. 450.

18. Jarvinen P., Rajala J., Sinervo H. (1972), A branch and bound algorithm for seeking the p-median, Ops. Res., 20, p. 173.

19. Kerningan B. W., Lin S. (1970), An efficient heuristic procedure for partio-ning graphs. Bell Syst. Tech. J., 49, p. 291.

20. Levy J. (1967), An extended theorem for location on a network, Opl. Res. Quart., 18, p. 433.

21. Lin S. (1965), Computer solutions of the travelling salesman problem. Bell. Syst. Tech. J., 44, p. 2245.

22. Maranzana F. E. (1964), On the location of supply points to minimize transport costs, Opl. Res. Quart., 15, p. 261.

23. Marsten R. E. (1972), An algorithm for finding almost all the p-medians ot a network, Paper 23, Northwestern University, Evaston, Illinois.

24. Rao M. R. (1972), The rectilinear facilities location problem. Working paper No. F7215, The graduate school of management. University of Rochester, Rochester, New York.

25. Revelle C. S., Marks D., Liebman J. C. (1970), An analysis of private and public sector location models, Man. Sci., 16, p. 692.

26. Revelle C. S., Swain R. W. (1970), Central facilities location. Geographical Analysis, 2, p. 30.

27. Rojeski P., Revelle C. S. (1970), Central facilities location under an investment constraint. Geographical Analysis, 2.

28. Sa G. (1964), Branch and bound and approximate solutions to the capacitated plant-location problem. Ops. Res., 17, p. 1005.

29. Spielberg K. (1969), An algorithm lor the simple plant location problem with some side conditions. Ops. Res., 17, p. 85.

30. Spielberg K. (1969), Plant location with generalized search origin, Man. Sci., 16, p. 165.

31. Surkis J. (1967), Optimal warehouse location, XIV Int. TIMS Conf., Mexico City, Mexico.

32. Teitz M. В., Bart P. (1968), Heuristic methods for estimating the generalized vertex median of a weighted graph. Ops. Res., 16, p. 955.