经过了长时间的学习……小编终于学会了运输问题(Transportation Problem)，可以说是很骄傲了!然而……今天老板突然给了小编一个规模巨大的问题去计算!经过了三天三夜的疯狂计算，终于没算出来……

于是乎，在"欢声笑语"中迎来了新的一期运筹学教学，为了能够完美地掌握运输问题的运输单纯形法(Transportation Simplex Method)，小编精读了经典运筹学英文教材《Operations Research Applications and Algorithms》如下图：

从第七章详细地了解了其中的原理，并且用代码实现了书中的算法!是不是很赞!秉着留书留种的原则，我们将在留言区里面把这本书的百度网盘链接给出，是不是很激动!

代码部分

关于算法的流程，上面给出的书籍中已经有了详细介绍。在这里，我们直接给出代码以及详细的注释，是不是很赞!

点击文章末尾的“阅读原文”字样即可复制粘贴下载源代码!Very Easy!

1

1

样例输入

#

3 4

10 2 20 11

12 7 9 20

2 14 16 18

15 25 5

5 15 15 10

第一行两个数字分别表示供应方数量和需求方数量

后面三行通过二维表的方式记录每个供应方到需求方的运价

最后两行分别表示每个供应方的最大供应量和每个需求方的最大需求量

样例输出

m=3 n=4

10 2 20 11 15

12 7 9 20 25

2 14 16 18 5

5 15 15 10 0

(2,1)

(2,2)

(1,2)

(1,1)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(2,3)

(2,2)

(1,2)

(1,3)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(2,4)

(2,2)

(1,2)

(1,4)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(2,2)

(2,1)

(3,1)

(3,2)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(2,3)

(2,1)

(3,1)

(3,3)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(2,4)

(2,1)

(3,1)

(3,4)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(2,4)

(2,2)

(1,2)

(1,4)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(2,1)

(2,2)

(1,2)

(1,1)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(2,2)

(1,2)

(1,3)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(1,4)

(1,2)

(2,2)

(2,4)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(2,2)

(2,1)

(3,1)

(3,2)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(2,3)

(2,1)

(3,1)

(3,3)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

(1,4)

(1,2)

(2,2)

(2,1)

(3,1)

(3,4)

上面的点构成一个闭回路(Loop)，第一个点对应为进基的非基变量

最终调运方案为：

0 5 0 10

0 10 15 0

5 0 0 0

最优值为：

335

上面列出了每一次迭代时用来调整解的环(闭回路)。