文章基本信息

标题：Using the Simplex Method for a Type of Allocation Problems
本地全文：下载
作者：Yoshihiro Tanaka
期刊名称：American Journal of Computational Mathematics
印刷版ISSN：2161-1203
电子版ISSN：2161-1211
出版年度：2019
卷号：09
期号：02
页码：25-31
DOI：10.4236/ajcm.2019.92002
出版社：Scientific Research Publishing
摘要：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.
关键词：Allocation Problems;Hall’s Theorem;Totally Unimodular Matrix;Simplex Method