【运筹笔记】MOOC运筹学-江西财经大学
最近在家焦虑地等待学校给我邮寄毕业证，2022春节之后就要去入职了，年前时间比较空闲，就想了解一下国内的运筹学教授内容和国外有什么区别，于是去中国大学MOOC搜了一下运筹学的公开课。大概有三四门关于运筹的国家精品课程吧，想着听一下然后写一些观后感、笔记啥的。纯属写着玩，里边不会重复太多课堂内容，更不会涉及理论公式推导之类的，希望可以多写一些对某节课或者某块知识个人的理解和感悟。（顺便丰富一下#运筹优化#这个tag）
第一篇先分享一下江西财经大学的运筹学吧，链接在下面👇
课程大纲：
1 绪论
2 线性规划模型
3 线性规划的解法
4 对偶理论与灵敏度分析
5 运输问题
6 目标规划
7 整数规划
8 动态规划
9 图与网络优化
2 线性规划模型
3 线性规划的解法
4 对偶理论与灵敏度分析
5 运输问题
6 目标规划
7 整数规划
8 动态规划
9 图与网络优化
1-4 就不写了吧，纯理论的东西。
5 运输问题：
这一章的问题背景是由工厂（产地）向销售商（销地）配送货物，假设有m家工厂和n家销售商，任意工厂和销售商之间有路径相连，且单位运输费用给定为aij，每家工厂的产量不同，每家销售商的需求量也不同，但是所有工厂的生产总量和所有销售商的需求总量相等（产销平衡），求最小化总费用。这是一个非常经典的运筹学问题，而且基于此问题可以演变出很多变形问题，例如：
（1）如果产销不平衡怎么办？供给量大于需求量还好说，需求量大于供给量的时候该优先分配给哪家销售商，又该牺牲哪家销售商？
（2）不是所有工厂和销售商之间都有路径相连，例如工厂A和销售商BC之间存在天然地理位置障碍无法运输怎么修改模型参数？
（3）想象一下把所有产地和销地之间加一层中间商，有点像神经网络一样，即工厂只能向多家中间商送货，再由多家中间商向各个终端销售商供货，又该怎么建模？
以上三种假设情况似乎更加符合现实生活中的情形，当然我们还是从最最基础的供需平衡运输问题开始讲起。视频课中老师首先引入了供需平衡表，然后利用表上作业法求解此问题，最后基于表上作业法的结果给出结论。其基本步骤是：
（1）利用最小元素法，或者沃格尔法找到一组基可行解；
（2）求出所有空格检验数（闭回路法或位势法）；
（3）如果所有空格检验数都大于0，意味着无论怎样变更现有的运输方案，都只会增加现有的总运输成本，也即现有的运输方案已经是最优的运输方案。
（4）如果出现<0的空格检验数，意味着存在一种方法，可以让我们的运输方案在依旧满足所有约束条件的前提下，减少现有的总运输成本，所以我们要对现有的可行解进行调整，继续逼近最优解。
（5）如果出现=0的空格检验数，意味着存在一种方法，可以让我们在变更运输方案的同时，保持总运输成本不变，即存在无穷多种最优解。
这里我所理解的表上作业法，实际融合了“贪心思想+local search方法”。首先，贪心的思想体现在第（1）步，当我们使用最小元素法时，本质上就是一种贪心，类似于背包问题里先放性价比最高的物品一样。使用沃格尔法则是另一种贪心的思想，也即我想要最小化我的风险，这里建议去听一下视频，老师讲解得非常清晰。总而言之，无论是最小元素法还是沃格尔法，都可以快速帮助你寻找到一组“比较优的”可行解，而且背后都有经济学意义作为支撑，但是两者作为贪心算法，无法保证得到的解一定是最优解。因此，我们需要提到"local search"的思想，也即当我已经有了一组可行解，并且它已经是“局部最优”的可行解的时候，我们为了去寻找“全局最优”的最优解，往往需要尝试性地在局部最优解的附近进行搜索，通俗点说就是我需要退一步，跳出死胡同，通过一些细微的变动，看看局部最优解是否可以被进一步优化。这也就是闭回路和位势法的基本思想，通过对运输量做-1，+1的闭环微调，看看能否进一步降低总运输成本。
顺便一提：表上作业法大概率只适用于小规模问题和学校考试，因为一旦工厂和销售商的数量增加，且不说计算量也跟着增加，就是把这张m*n的表完整地画出来可能也没有这么大的纸供你画。另外业界很多问题现在也不是单纯的运输问题了，通常会牵扯进货物的成本、售价、储存费用等等，所以可能多目标优化会是更好的解决方案，例如同时max利润和min（运输费用+存储费用），甚至会结合时间序列去进行时间维度的预测，例如淡旺季的需求量是不同的等等。
6 目标规划（多目标优化）：
这一章实际上就是多目标优化的问题。两种思路：
（1）不同目标之间有先后顺序，即优先满足目标1，其次满足目标2，再次满足目标3，以此类推，有多个目标函数；
Obj1: min d1 Obj2: min (d2+d3) Obj3: min (2*d3+d4) s.t. constraints1 constraints2 constraints3在具体实施的时候，首先计算满足目标1时的决策变量，然后将目标1转变成新的约束条件，再次计算满足目标2时的决策变量（注意：此时目标1由于已经被满足且放在约束条件中，因此无论决策变量怎么改变，都始保证足目标1维持在“自己的最优解上”）。
（2）不同目标之间无先后顺序，但人为赋予不同权重，多个目标整合在一个目标函数当中；
Obj: min a1*d1 + a2*(d2+d3) + a3*(2*d3+d4), 其中a1,a2,a3是权重系数
s.t. constraints1
constraints2
constraints3 个人感觉多目标优化很难得到最优解，实际上也很难去定义什么是最优解。目标的设置很大程度上取决于具体的建模场景，现实生活中并没有那么绝对的优先级或者权重，而且不同人对于“目标”的理解和描述也不一样。一句“尽量减少加班”的目标可以被理解为多个含义，自然也就有多种不同的建模方式：（1）希望员工6点下班；（2）禁止员工6点之后下班；（3）对6点之前下班的员工给予奖励；（4）对6点之后下班的员工给予惩罚。即便是我充分理解了业务需求，做到了100%完美的数学建模，多个目标之间的权重也是很难去衡量的，只能依靠经验或者依靠后期的仿真实验数据来得到一个较好的权重，而这个较好的解离最优解之间究竟还有多少差距，恐怕只有上帝才能知道了。 7 整数规划与指派问题：
这一章主要讲授的是运筹学中很重要也是日常应用非常多的整数规划/混合整数规划/0-1整数规划问题。以及三种方法：分支定界法、割平面法、隐枚举法。
实际上，从线性规划问题（Linear Programming）到整数规划问题（Integer Programming），看似只引入了“决策变量为整形”这么一个约束，但实际上对于问题的求解效率影响非常大。原本线性规划问题的可行域通常是一个凸集（你可以把它理解为凸多边形或者凸多面体），但是整数规划问题中的可行域则变成了空间中的一群离散的点。原本在线性规划问题的凸集上可以通过画图法或单纯型法快速逼近到最优解，到了整数规划中由于离散形式的可行域，则无法迅速逼近于最优点。因此，最笨的方法就是枚举。
（1）枚举法。枚举法在对于0-1类型的决策变量，且变量个数不多的时候较为有效。例如，有3个0-1类型的决策变量，它们解的组合类型也只有23个：(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)，只需要把这8组解依次带到约束条件中去判断是否符合所有约束条件，再将符合约束条件的可行解求出目标函数，判断目标函数大小后即可找到最优解。当然，缺点也很明显，那就是当变量数量多的时候，解的组合数将呈指数增长。
（2）分支定界法（Branch & Bond）。简单、有效、但是是否能够快速得到最优解要看运气😂。有时候将整数规划松弛为线性规划的时候，恰好两者的最优解相等，直接一步求出来整数规划的最优解，连分支都不用分。但有时候要一步一步分到最最底层才能判断出哪个是最优解。其核心思想就是先将整数规划松弛成线性规划，找线性规划的最优解，看看是不是符合整型约束，不符合就分枝取整，然后再针对分出来的枝重复上述步骤。
（3）割平面法（Branch & Cut）。和B&B类似，但是会提前寻找一些valid inequality去切割线性规划的可行域（注意，这里并没有把整数规划的可行域给切掉，相反切掉的是松弛成线性规划过程中增加的空间），目的是提高搜索效率，这里有一篇关于割平面法的知乎👇，里边有更为细致的讲解。
最后还有指派问题的匈牙利解法，非常精妙的一种方法。指派问题的现实场景建模并不难，无论是平衡指派问题还是不平衡指派问题，求解器都能够较快地求解。
8 动态规划
我突然觉得动态规划是你在没有足够的“能力”或“算力”的情况下，被迫选择的一种优化思想。为什么这么说呢？拿本单元中的两类问题举例，求最短路径时，当你拥有计算机辅助求解时，40多条不同的路径只需要暴力枚举就可以，但是如果你是在学校的纸质考试中，你只能选择用“逆推”的思想从后往前一步步求最优路径，看似计算量比暴力枚举要小很多，但这其实是由于人类没有可以媲美计算机高效的“算力”而去做的妥协。类似的背包问题，实际上将此类整数规划送给求解器去解根部不需要转化成动态规划去做，而是依靠求解器内部的整数规划算法很快就可以得到答案，但是为什么我们要把它转换成多阶段动态规划去做呢？实际上还是因为我们手工用B&B求解整数规划太慢了，没有计算机那么高的效率，于是去寻找更高效的动态规划帮我们解答。
另一点想说的是，动态规划实际上更像是一种思想，而非一种方法。如果刷过Leetcode的朋友都有了解，在算法题目当中很重要的一类题目就是动态规划，有些题目基于现实，有些题目天马行空，总之就是那些题目未必有着对应的项目或者程序落地，反而是在训练你的这种思维，如何找到状态转移方程，如何找到初始状态，如何判断迭代完成，这些才是动态规划的艺术所在。
9 图与网络优化
这一章主要讲4个问题，都没太接触过，只知道做仓网规划的时候可以用到最小费用最大流问题。以后业界接触到了再补充吧。
（1）最小支撑树
（2）最短路
（3）最大流
（4）最小费用最大流
--------------------
建立于2022-01-12
慢慢写吧，实在一次性写不了太多
更新于2022-01-19
#运筹优化##慕课网#
腾讯公司福利 441人发布
