运筹学教学|运输问题代码分享(C++代码及详细注释)

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

1

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

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

1

代码部分

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

点击文章末尾的“阅读原文”字样即可复制粘贴下载源代码!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

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

END

编辑:唐清清(华中科技大学管理学院本科三年级,15295970390@163.com)

贺兴(华中科技大学管理学院本科三年级,hexing15@gmail.com)

代码:孙嘉轩(华中科技大学管理学院本科二年级,1143747930@qq.com)

指导老师:秦时明岳(professor.qin@qq.com)

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2017-10-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏肖洒的博客

梁桥评分系统

虽然算法很简单,就是一个计算器。 但是,其本身逻辑思维很复杂。 就是一个桥它自己的学问,让我们这些门外汉实在是汗颜啊。 所以到最后就是完成了一个很臃肿的exe...

11330
来自专栏深度学习之tensorflow实战篇

数据挖掘PageRank算法(网页排名原理)及Map-Reduce实现

方法/步骤 1 一、什么是pagerank PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google...

48390
来自专栏韩伟的专栏

第三章:数字魔法

本文与前期推送“你真的理解数码技术吗?”“字节的秘密”是同一系列。 3.1压缩魔法 在数码世界中,容量和速度总是紧缺资源,我们总是希望能用尽量少的字节,装下更...

32560
来自专栏ATYUN订阅号

NLP项目:使用NLTK和SpaCy进行命名实体识别

命名实体识别(NER)是信息提取的第一步,旨在在文本中查找和分类命名实体转换为预定义的分类,例如人员名称,组织,地点,时间,数量,货币价值,百分比等。NER用于...

99440
来自专栏ACM算法日常

除以3,乘以2(STL+排序)- Codeforces 997D

Polycarp likes to play with numbers. He takes some integer number x, writes it d...

12420
来自专栏ThoughtWorks

TW洞见〡3D打印的各种问题及解决方案

文章作者来自ThoughtWorks:贺思聪 ,图片来自网络。 3D打印机已经买回来几个月了,基本上每天都要打印一些东西,期间遇到了很多的问题积累了很多的经验...

409120
来自专栏AI研习社

Github 项目推荐 | 一个简单的英文字形转音素的 Python 模块

该功能在语音合成中是必不可少的。不像德语和西班牙语这类语言,英文的发音很难从拼写中推断出来,所以人们要知道某个单词的发音,最好的方式是查阅字典。但是,这种方法至...

22650
来自专栏Crossin的编程教室

【每周一坑】蜥蜴流感与贝叶斯定理

春季是流感的高发季节。不要觉得只是小小的“感冒”,严重起来甚至也会危及生命,而且还没有特效药。因此,身体不适请及时到医院检查。

17630
来自专栏数据小魔方

带实际执行进度的甘特图

今天要跟大家分享的图标是带实际执行进度的甘特图! ▽▼▽ 由于本图所用到的技巧和思路特别复杂,过程相对繁琐,所以本案例的介绍会省略掉很多细节性的步骤,否则图文会...

40250
来自专栏数据科学与人工智能

【Python环境】可爱的 Python: 自然语言工具包入门

鄙人并非见多识广,虽然写过很多关于 文本处理 方面的东西(例如,一本书),但是,对我来说, 语言处理(linguistic processing) 是一个相对新...

35380

扫码关注云+社区

领取腾讯云代金券