OR stack exchange 高分问题
一位大学教授结合他的授课经历提出的一个问题："在教授运筹优化入门课程时，我常常发现，展示一些违背直觉或似是而非的结果对学生来说是一个很好的启发。我用这些例子和结果作为我们需要学习优化技巧的动机。在运筹学中，我们有哪些反直觉的结果可以用作激励性的例子呢？"
布雷斯悖论（Braess Paradox）
@Sune：我先举一个布雷斯悖论的例子抛砖引玉，即在一个拥堵的道路网络中添加一条道路反而会导致整体的旅行时间加长。
以上图为例，假设有4000辆车从START点到END点，路段上的阻抗函数均已给出，若AB之间的虚线不开通，那么存在两条路径即START-A-END（假设有a辆车选择该路径）和START-B-END（假设有b辆车选择该路径），根据用户均衡原理，当系统达到均衡时两条路径上的阻抗相同，a+b=4000，a/100+45=45+b/100，那么a=b=2000，此种情况下两条路径旅行时间为2000/100+45=65分钟
倘若AB之间的虚线开通，且假定AB上的旅行时间几乎为0，原本选择路径START-A-END的车辆中有一辆车开始尝试路径START-A-B-END，结果他惊喜地发现该路径的旅行时间=2000/100+2001/100=40.01分钟，比他原来选择的路径用时缩短了将近25分钟！于是更多的司机得知了这个消息，他们也开始选择这条路径，该路径的旅行时间也从40.01分钟持续攀升。直到这4000个人当中有2500人选择了路径START-A-B-END时，路径旅行时间=2500/100+4000/100=65分钟，与未开通AB前的时间相等，这时就不再有人来尝试这条路。但需要注意的是，选择路径START-B-END的剩余1500人，路径旅行时间=45+4000/100=85分钟，比之前多了20分钟，他们也不得不改变这条线路。最终4000辆车都选择了路径START-A-B-END，旅行时间=4000/100+4000/100=80分钟，因为谁要去选择另外的路都会是85分钟，所以AB之间线路的开通使得所有车辆的通行时间由65分钟上升到了80分钟，如果大家都同意不开通这条线路，那么就都可以得到15分钟的时间节省。
参考文献
[1] Braess, D. (December 1968). "Über ein Paradoxon aus der Verkehrsplanung". Unternehmensforschung Operations Research - Recherche Opérationnelle. 12 (1): 258–268. doi:10.1007/bf01918335. ISSN 0340-9422. S2CID 39202189.
[2] Roughgarden, Tim; Tardos, Éva. "How Bad is Selfish Routing?". Journal of the ACM. Archived from the original on 9 April 2016. Retrieved 18 July 2016.
[3] Steinberg, R.; Zangwill, W. I. (1983). "The Prevalence of Braess' Paradox". Transportation Science. 17 (3): 301. doi:10.1287/trsc.17.3.301.
[4] Boyd, Andrew. "Braess' Paradox". Engines of Our Ingenuity. Episode 2814.
[5] Dal Forno, Arianna; Merlone, Ugo (2013). "Border-collision bifurcations in a model of Braess paradox". Mathematics and Computers in Simulation. 87: 1–18. doi:10.1016/j.matcom.2012.12.001. ISSN 0378-4754.
笔者注：感觉自己当时交通规划没有好好学，完全怎么不记得有这样一个案例，就只是记下了用户均衡和系统最优的成立条件。刚巧，前两天有朋友让帮忙看看他的作业题，结果两道都答不上来，现在看其中一题就是布雷斯悖论。两道题目也放在下方，供读者参阅。
TSP问题
图为iPhone上一个用于求解tsp的app(没想到还真有人把这东西做成一个app放上去)
@LarrySnyder610：我喜欢通过旅行商问题 (TSP) 来向学生介绍优化算法的必要性。我给出问题描述，然后让他们集思广益解决问题的方法。通常，学生建议的方法类似于最近邻等方法。但最终，通常有人会说类似这样的话：
"如果我们是在计算机上寻找答案，那怎么不让计算机查看所有可能的路线，并选出最佳的一个呢？"
我询问这种方法是否甚至能适用于大型实例，通常的共识是我们能以这种方式解决数百甚至数千个节点的实例。我们共同发现，可能有 n！种可能的路线，有时学生会向下修正他们的估计，但幅度不大。
于是我说，好的，我们假设我的电脑每秒能评估 1 万亿条路线。然后：
求解一个 10 节点实例需要 3.6 微秒。（很棒）
求解一个 15 节点实例需要 1.3 秒。（还不错）
求解一个 18 节点实例需要 1.8 小时。（嗯）
求解一个 20 节点实例需要 28.2 天。（不太好）
求解一个 22 节点实例需要 35.6 年。（噢不）
求解一个 25 节点实例需要 491,857.2 年。
求解一个 30 节点实例需要数以百倍的宇宙年龄。
然后我告诉他们，Concorde iPhone app能够在不到一秒的时间内求解 30 节点实例，并且达到最优解，之后学生们便会很“容易接受”我们为什么要使用优化算法这件事情了。
几个类似于布雷斯悖论的示例
@TheSimpliFire：
（1）与布雷斯悖论类似，在斯皮克斯马和沃格林格的论文中，提出了一个悖论，在论文中称之为no-wait flow-shop悖论
车间调度问题中（job shop problem），对无等待流水车间的某些机器增加速度，实际上可能会恶化最佳完工时间。我们构建了一些实例，其中改进速度后的最佳完工时间与没有改进速度的最佳完工时间相比会变得很差。
（2）另一项反直觉的结果是贝拉迪悖论（Bélády's anomaly.）
这种现象是指当页框数量增加时，某些内存访问模式页错误的数量也会相应增加。使用先进先出 (FIFO) 页面替换算法时，通常会遇到这种现象。在 FIFO 中，页错误数可能随着页框的增加而增加或减少，但在 LRU 等最优和基于堆栈的算法中，随着页框的增加，页错误会减少。
（3）运输悖论，即在需求/供应数量减少时，运输成本可能会更高。（具体见参考文献[3]）
参考文献
[1] Spieksma, F.C.R., Woeginger, G.J. (2004). The no-wait flow-shop paradox. ScienceDirect. 33:6. pp 603-608. https://doi.org/10.1016/j.orl.2004.10.007
[2] Bélády, L.A., Nelson, R.A., Shedler, G.S. (1969). An anomaly in space-time characteristics of certain programs running in a paging machine, Commun. ACM 12:349–353.
[3] Charnes, A., Klingman, D. (1971). The more-for-less paradox in the distribution model, Cah. Cent. d’Etud. Rech. Oper. 13:11–22.
最长路径问题
@GB supports the mod strike：
在网络中找到从 A 到 B 的最短路径非常简单，以致中学生用纸笔就能做到（Dijkstra's algorithm）。
找到最长路径（无重复）要难得多。
我曾经编辑过一本数学教科书，作者们想当然地认为最长路径算法是Dijkstra's algorithm的简单修改。（奥不。。。。）
开放式车间调度问题
@Mostafa：
我在“开放车间调度问题”中也曾见到过一条与此相类似的有趣结果，即“三很容易，二很困难！”。
在 Gribkovskaia 等人（2006 年）发表于的论文中写到：
“在离散优化中，当数值参数从 2 变成 3 时，问题的复杂性经常会急剧增加。尤金·劳勒对这个问题深感兴趣，曾写道：‘遗憾的是，我们也许需要很多年才能真正理解 二 的神秘力量，（或者简·卡雷尔 [J.K. Lenstra] 所说的 三的神奇力量）：2-SAT 很容易，3-SAT 很困难，2 维匹配很容易，3 维匹配很困难。’”
然而，他们证明了一种罕见的相反行为。
Glass 等人 (2001) 证明，对于两机开放车间调度总批量问题，为了使完工时间最小化，已知一个最优计划在每台机器上包含一批、两批或三批。他们证明了找到一个两批最优计划是 NP 难题。因此，人们猜测三批计划也是 NP 难题。令人惊讶的是，Gribkovskaia 等人 (2006) 表明三批最优计划可以在线性时间内找到。
参考文献
[1] Glass, Celia A., Chris N. Potts, and Vitaly A. Strusevich. "Scheduling batches with sequential job processing for two-machine flow and open shops." INFORMS Journal on Computing 13.2 (2001): 120-137.
[2] Gribkovskaia, Irina V., et al. "Three is easy, two is hard: open shop sum-batch scheduling problem refined." Operations Research Letters 34.4 (2006): 459-464.
流水车间调度异常分析
@Mostafa：
Panwalkar 和 Koulamas (2020)最近发表了一篇非常有趣的论文，题目为：车间调度异常分析。论文中介绍了以下异常现象：
异常1：在最优计划中，单项操作的处理时间增加会导致最优目标函数值的减少。
异常2：增加作业会导致最优目标函数值的减少。
异常3：增加一台对于至少一项作业具有正处理时间的新机器将导致最优目标函数值的减少。
参考文献
[1] Panwalkar, S. S., and Christos Koulamas. "Analysis of flow shop scheduling anomalies." European Journal of Operational Research 280.1 (2020): 25-33.
P和NP
@fontanf：
经典例子：
在一个图中寻找所有边（edge）的最短路径问题属于P问题（中国邮递员问题）
在一个图中寻找所有节点的最短路径是 NP-complete（TSP问题）
调度理论中的另一个例子：
这与直觉相反，因为通常，先占使问题变得更容易，参见"Preemption Can Make Parallel Machine Scheduling Problems Hard" (Brucker et Kravchenko, 1999).
点一点「在看」支持我们~
