Finding all vertices of a convex polyhedron
Tóm tắt
The paper describes an algorithm for finding all vertices of a convex polyhedron defined by a system of linear equations and by non-negativity conditions for variables. The algorithm is described using terminology of the theory of graphs and it seems to provide a computationally effective method. An illustrative example and some experiences with computations on a computer are given.
Tài liệu tham khảo
Arrow, K. J., L. Hurwicz, andH. Uzawa: Studies in linear and nonlinear programming. Stanford: Stanford University Press 1958.
Balinski, M. L.: An algorithm for finding all vertices of convex polyhedral sets. J. Soc. Indust. Appl. Mathem.9, 72–88 (1961).
Hadley, G.: Linear programming. Reading, Mass: Addison-Wesley Publ. Co. 1962.
Filipovitch, E. I., andO. M. Kozlov: On an estimate of the number of iterations in some linear programming methods. In: Mathematical methods of optimal planning. Novosibirsk : Nauka 1966 [in Russian].
Klee, V.: On the number of vertices of a convex polytope. Canadian Journal of Mathematics16, 701–720 (1964).
Motzkin, T. S., H. Raiffa, G. L. Thompson, andR. M. Thrall: The double description method. In: Contributions to the theory of games, vol. II. Princeton: Princeton University Press 1953.
Saaty, T. L.: The number of vertices of a polyhedron. The American Mathematical Monthly62, 326–331 (1955).