In this study we discuss the use of the simplex method to solve allocation problems whose flow matrices are doubly stochastic. Although these problems can be solved via a 0 - 1 integer programming method, H. W. Kuhn [1] suggested the use of linear programming in addition to the Hungarian method. Specifically, we use the existence theorem of the solution along with partially total unimodularity and nonnegativeness of the incidence matrix to prove that the simplex method facilitates solving these problems. We also provide insights as to how a partition including a particular unit may be obtained.
References
[1]
Kuhn, H.W. (1991) On the Origin of the Hungarian Methods. In: Lenstra, J.K., et al., Eds., History of Mathematical Programming, Elsevier, Amsterdam, 77-81.
[2]
Tanaka, Y. (2017) Proposal 2033. Mathematics Magazine, 90, 383-384. (See also, (2018), 91, 392.)
[3]
Diestel, R. (2010) Graph Theory. 4th Edition, Springer, Heidelberg.
[4]
Hall, P. (1935) On Representatives of Subsets. Journal of the London Mathematical Society, 10, 26-30. https://doi.org/10.1112/jlms/s1-10.37.26
[5]
Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2009) Introduction to Algorithms. 3rd Edition, The MIT Press, Cambridge.
[6]
Nocedal, J. and Wright, S.J. (2006) Numerical Optimization. 2nd Edition, Springer, Berlin.
[7]
Schrijver, A. (2003) Combinatorial Optimization. Springer, Berlin.
