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

Yoshihiro Tanaka

No 331, Discussion paper series. A from Graduate School of Economics and Business Administration, Hokkaido University

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 (search for similar items in EconPapers)
Pages: 8 pages
Date: 2018-10
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/2115/71733 (text/html)
https://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/71733/1/DPA331.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hok:dpaper:331

Access Statistics for this paper

More papers in Discussion paper series. A from Graduate School of Economics and Business Administration, Hokkaido University Contact information at EDIRC.
Bibliographic data for series maintained by Hokkaido University Library ().