Optimization Online


On the use of the simplex method for a type of allocation problems

Yoshihiro Tanaka(tanaka***at***econ.hokudai.ac.jp)

Abstract: 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 [4] suggested the use of linear programming in addition to the Hungarian method. Specifically, we use the Birkhoff’s theorem to prove that the simplex method enables solving these problems. We also provide insights how to obtain a partition that includes a particular unit.

Keywords: allocation problems, Hall's theorem, Birkhoff's theorem, simplex method

Category 1: Combinatorial Optimization (Other )

Citation: Discussion Paper Series (Hokkaido University), Ser. A, No. 2018-331, October 2018

Download: [PDF]

Entry Submitted: 10/31/2018
Entry Accepted: 11/02/2018
Entry Last Modified: 10/31/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society