运筹学学习如何入门?

运筹学是一个子方向很多的学科,线性规划,整数规划非线性规划,随机过程,随机规划,存储量,博弈论,鲁棒优化,最优控制。。。每一个方向里面全是数学,有浅一点的,有很深的,一大堆符号,要都学,学很久,而且也会学得很痛苦,因为他们之间虽然有关系,但是关系不密切。刚开始,我觉得有必要知道这门学科的灵魂

上面强调说不要一上来就去钻,例如一上来就学最最基本的线性规划,是因为如果这么学,其实你学的是优化部分的应用数学,不是运筹学。运筹学不仅仅包括优化。优化只是理论部分。例如线性规划是一种刻画某些现实问题的模型,如果只关注于线性规划本身,那其实有很大一部分是在关注线性规划的数学理论。解线性规划里面的数学理论就多了去了:线性不等式的代表性,对偶理论,各种单纯性法,椭圆法和各种内点法,现在还在发展。里面每一个理论都不是随便看看就能通的,特别对于数学基础不算很好的同学而言。有些教授对里面的数学还讲一些high level的想法,但是国内教科书一般就直接上定义XXX,定理XXX,两下就可以晕了。。。运筹学现在很受关注,很多社科和工科学生都在接触,花太多时间在数学理论部分上,对他们而言挺可惜的。

关键是,对大多数人,里面的数学压根不需要学,我们有软件解!有不少还是开源的!这个自己搜搜就好,其它回答也提到一些了。现在运筹学领域的专家们都给我们把各种解法自动化了,何必不好好利用,还自己慢慢理解算法?再慢慢编程?

所以如果只是入门,最重要是看看这一大堆运筹学里面不同的理论都是干什么的,哪些模型好解,哪些难解,现在很多我们接触到的模型都有定论的。
运筹学里面其实更重要的是建模。换言之,就是看现实问题和数学语言是怎么对应的。这个因为考试的原因,太容易被忽略了其重要性。

建模这事情说难不难说易不易。易在好像就是定义几个变量,定义一下变量之间的关系和目标函数。难在
1. 对现实问题要看透:什么才是问题里面的最重要的因素,抓住重点
2. 找到最合适的数学语言和它对应,
3. 模型要尽量容易解

第一点是因问题而异的,没法聊。第二点是可以通过了解各种模型适用于刻画具有什么结构的问题来达到。运筹学里面有很多模型。举几个例子:
1. 线性规划能表示所有有线性结构的问题,例如做采购,我们知道了每家供应商的固定价格和最大供应量,我们希望最小化成本,那总成本=单价×数量,这个就是这个问题里面的线性关系。
2. 整数规划能处理一些线性规划处理不了的问题。例如还是采购,假如选了某家供应商,每选定一个供应商,还要增加一个固定成本,于是我们就要多设一个变量来代表是不是选了这个供应商,这时候就需要整数限制。不然那个变量解出来等于0.5,我们只选半个它?
3. 当现实问题涉及多个参与者,每个参与者都有自己优化的东西,这时候就涉及互动,就可以将博弈论派上用场了。
4. 如果见到一个系统是随时间变化的,就可以考虑用最优控制。
等等等等。

懂了对自己身边的具体问题建模,再拿个软件解一下模型,对大部分人就够了。所以要看书或者看视频自学的话,第一步是,每一章只看前面讲建模(modeling或者formulation)那一节。够用了。

但是对于要更深入地去懂运筹学还不够。
做得好的运筹学问题都是这样的:
1. 深刻认识现实问题
2. 用数学语言描述问题(建模)
3. 用数学工具研究模型
4. 再把研究出来的成果从数学语言翻译成我们能看懂的语言(例如汉语,英语。。。)

前面我们只聊到1,2和一点点3,真正的美出现在4。4的重要意义在于如果我们把一个问题解出来了,但是看不懂解出来的是什么,那么我们对这个问题其实是没有增加多少认识的。有些时候还会导致其他问题,例如你在解决某个现实问题的时候,你把一个计算机解出来给你的解拿来用了,发现现实情况不像你想象中那样,那怎么办?是计算机算解错了吗?还是你的模型没建好吗?如果有人给你投资做一个某些方面的优化系统,人家能信得过这样靠建个模型解个解得出的方案吗?大多数不懂你在做什么的人是不会信的。所以好的解可以提供insight!(能让人读懂的现实含义)

例如Kelly Gambling,假如已知有n匹马,他们胜率分别是b_i,跑第一的话投1块钱能赢o_i块钱,你总共有100块钱(你可以当成一百万,具体数目不重要,关键是比例),投到第i匹马的钱是100p_i。假如你要买马买无数次,那应该怎么分配你的钱到各匹马上去?这个问题的解就是p_i和b_i成比例。给我们的insight就是,获胜几率大的多放点钱,几率小的少放点钱,就是这么简单。这个model的解给了我们分散投资的idea。

这是最简单的情况,马和马之间是indepedent的,如果是投资股票,股票之间可能有相关性,如果这个相关性很重要,建模的时候就把它也考虑进去,得到考虑了相关性的解,再试图去interpret你的解。如果相关性不太重要,就没必要把模型搞复杂。
能得到给我们insight的解难吗?当然难!

要想4出现,前面的1,2,3一定要简洁而深刻。模型既能抓住问题的重点,还要足够简单,不然最后出来的结果怎么可能让人看得懂。这里头需要的可不仅是扎实的数学基础,数学只是描述问题的一种语言,更重要的还是对具体问题的认识和对建出来的模型的预判。

对于一个现实问题,建立一个简单好解又能较好地描述现实情况的模型,是一种艺术。这是数学界甚至科学界追求的美的原则:simple and elegant.

一般运筹分两块:优化(optimization);概率+随机(probability+stochastics)

以MIT开的课程为例。

先说优化:

强烈推荐教材《Introduction to Linear Optimization》by D. Bertsimas and J. Tsitsiklis. 这是MIT两门研究生(博士和硕士)运筹学课程,15.081(6.251)和15.093,的教材。两位作者都是MIT运筹学中心ORC的教授,其中D.Bersimas是目前ORC的co-director之一,美国工程院院士(运筹优化领域)。这本书讲解非常详细,读起来比较愉快。

15.093资料链接:Optimization Methods
15.081资料链接:Introduction to Mathematical Programming

如果希望只是了解运筹学的基础(即入门),15.093是比较合适的课程,覆盖了线性规划(modelling, simplex method, duality thoery, network problem)以及简单的整数规划,动态规划非线性规划。这门课侧重运用,要就是理解算法并且能运用到学术或者实际问题中;是COD项目的必修课。其他答案提到运输问题,排班问题等都有涉及。这是给非运筹学专业或研究中不需要较深优化理论的学生开的课。这门课比较通俗易懂,老少咸宜。懂基本的线性代数就可以上。读教材的话一般可以略过证明。

15.081是MIT运筹学博士一年级必修课。我的科研用到优化的理论,故即便不是运筹博士我也选了。这门课主要侧重优化理论的搭建,对于定理的讲解会深入许多,作业和考试均以证明为主。如果以后有志于做这方面的工作,可以学习这门课。这门课涵盖的内容略少于15.093,但是深度比较大。如果本科数学基础比较好(特别是代数)或者像我一样有学习的必要性的,可以选这门课。这门课也是可以用来入门的,不过如果不是今后有必要,时间成本会比较大。

除了这两门基础课,还有较深入的整数规划(15.083/6.859),网络优化(15.082)以及近年来兴起的鲁棒优化(robust optimization,在确定性问题中引入随机性,15.094)等。非线性优化(15.084)也是优化理论很重要的内容。

概率与随机:
我主要不是这个领域的,所以选过的都不是以理论为核心的课。
理论课:15.085 Fundamentals of Probability; 以及其他advanced课程
偏应用的:1.203,6.262等等很多,内容主要是随机过程,排队论等。

一个管理科学专业的师兄,课程设置三学期运筹学,分别为数学规划、随机模型、决策方法、前两门必修,第三门选修。

只推荐数学规划和随机模型,以下书籍推荐按数学功底划分 由易到难

一 运筹学教程 胡运权 清华出版

二 运筹学 《运筹学》教材编写组 清华出版

(以上两版是最最常见和考研最多被指定的教材 难度低 可供参考资料多 缺点在于一些证明不够清晰)

三 运筹学原理与方法 邓成梁 华科大出版
(线性规划部分写的特别详细 初学者都是从线性规划开始学 单纯形法的推导看了就喜欢 缺点在于线性规划太详细所占整本书比例大导致其他部分写的不太好)

四 运筹学:数学规划 黄红选 清华出版
(清华工业工程专业本科生讲义 论证推导详细 只是需要一定的线代基础 清华工科线代几何两学期 周学时为4+3 好像是吧 所以他们用起来感觉会好很多)

五 随机运筹学 胡奇英 清华出版
(复旦管院第二学期运筹学所用讲义 其实还是很友好的一版书 读起来还是很舒服的 个人感觉偏重计算 理论性也很好 感觉不到特别也感觉不到缺点)

六 运筹学 刘桂真 高教社
(山东大学运筹学是国家级精品课程 刘桂真教授在图论领域也很权威 这门课由山大数学系开的 里面证明很数学化 课后习题也有部分(花式)证不等式 所以除了对高代有要求 数分功底也不能差 不过现在部分高校经管专业也是学数分高代 追求严谨性和烧脑的话 选这本没错)

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: