运筹学-思维起搏 2023.8.8

是大学选修课程思维起搏的课外拓展，主要介绍生活中的运筹学，会涉及运筹学知识，同时融入生活场景，《优化之道：生活中的运筹学思维》这本书可以一读。导图介绍了一些博弈策略，如以牙还牙、智猪博弈等

思维起搏作业

• 书名：生活中的运筹学 作者：韩红梅 出版社：电子工业出版社 出版时间：2017-07 ISBN：9787121316739
  • 七桥问题（欧拉问题） 汉密尔顿问题 最短路（最近邻点法、扫描法） 最小生成树 网络图
  • 第6章 图论问题
    • （‘jie 桥即街道，所以逛完所有街道属于欧拉问题）
    • “汉密尔顿问题”，这个问题是由英国数学家汉密尔顿提出的，问题的原型是这样的：在一种旅游类游戏中，世界是用一个规则的实心十二面体来表示的，它的20个顶点就是全世界最著名的20个城市，现在要求游戏者“绕行世界”，从某个“城市”出发，沿着这个“世界”的棱，通过每个“城市”恰好一次，最后再回到自己出发的地点。也就是说，找一条沿着十二面体各边通过每个顶点刚好一次的闭回路（’jie 城市即点，所以汉密尔顿与欧拉的区别是一个是走完所有的边（桥），一个是走完所有的点（城市）,而最短路和最大流不要求走完）
      • 哈密尔顿图https://blog.csdn.net/happylife1527/article/details/7956904 定义1 如果经过图G的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。所经过的闭途径是G的一个生成圈，称为G的哈密尔顿圈 定义2 如果存在经过G的每个顶点恰好一次的路，称该路为G的哈密尔顿路，简称H路 由于完全图一定是H图，所以由闭包定理有： 推论1：设G是n≧3的单图，若G的闭包是完全图，则G是H图 推论1：设G是n≧3的单图。 (1) 若δ(G)≧n/2,则G是H图(Dirac定理); (2) 若对于G中任意不相邻顶点u与v，都有d(u)+d(v)≧n,则G是H图.(Ore定理)
    • 6.2.5 网线连接问题
      • 现在要在某五个地区之间连接网线，如图6-38所示，其中A、B、C、D和E分别表示这五个地区，两点之间的连线表明这两个地区间方便连接网线，而连线上面的数字表示这两个地区之间的距离，单位是千米。如何设置最佳的网线连接方案，确保每个地区都能连接网线，并且网线的总长度最小呢？
      • 要能连接到每一个地区，同时要让这个连接线路最短，这就是一个求各点的最短连接线路的问题（不属于最短路问题）
    • 判断最小生成树是否唯一
      • https://www.cnblogs.com/wkfvawl/p/9845689.html 在构造最小生成树的时候有可能会选择不同的边，这样构造的最小生成树不相同，但是最小生成树的权是唯一的！ 毫无疑问，无向图中存在相同权值的边是最小生成树不唯一的必要条件（但不是充分条件）。正因为如此，如果无向图中各边的权值都不相同，那么在用Kruskal算法构造最小生成树时，选择的方案是唯一的 这里给出判定最小生成树唯一的算法思路： 1.对图中的每一条边，扫描其他边，如果存在相同权值的边，则对此边做标记。 2.然后使用Kruskal（或者prim）算法求出最小生成树。 3.如果这时候的最小生成树没有包含未被标记的边，即可判定最小生成树唯一。如果包含了标记的边，那么依次去掉这些边，再求最小生成树，如果求得的最小生成树的权值和原来的最小生成树的权值相同，即可判断最小生成树不唯一
• 旅行商问题
  • 旅行商问题（travel salesman problem，TSP）是指有一个旅行推销员想去若干城镇去推销商品，而每个城镇仅能经过一次，然后回到他的出发地。给定各城镇之间所需要的旅行时间（距离或成本）后，试问该推销员应怎样安排他的旅行路线，使他对每个城市恰好经过一次的时间最短（距离最小或成本最低）？
  • 旅行商问题类似于物流中的配送路线问题。当企业用自有车辆运输时，车辆往往要回到起点，比较常见的情况是车辆从配送中心出发到指定的配送点送货并回到配送中心。要解决这类问题，就需要找到一个走遍所有地点的最佳顺序，以求运行时间或距离最小化
  • TSP问题是图论中的一个经典问题，用图论的语言描述就是：在赋权图中，寻找一条经过所有节点，并回到原点的最短路
  • 旅行商问题的求解算法
    • 最近邻点法
      • 该算法十分简单，但它得到的解并不是十分理想，有很大的改善余地。该算法最大的优点就是计算简单快捷，因此，可以用来解决简单的TSP问题
      • 最近邻点法的基本步骤如下：（1）以发点作为整个回路的起点，首先寻找距发点最近的一个节点，将其加入，形成一条路；（2）在余下的节点中，寻找距刚加入路中的节点最近的一个节点，并将其加入到路中；（3）重复步骤（2），直到图中所有的节点都加入到路中为止；（4）将最后一个加入的节点和发点连接起来，形成一个回路
    • 扫描法
      • 此方法属于先分群再排路线的方式。该方法采用极坐标来表示各需求点的区位，然后任取一需求点为起始点，定其角度为零度，以顺时针或逆时针方向，以车容量为限制条件进行服务区域之分割，建构车辆排程路线
      • 扫描法可以用来解决配送路线的设计问题，因为在配送问题中，需要考虑配送车辆的载重和最大运行时间，所以，扫描法较最近邻点法又增加了许多约束条件。用扫描法确定车辆运行路线的方法简单易行，甚至可以用手机计算完成。一般来说，它求解所得方案的误差率在10％左右，这样水平的误差率通常是可以被接受的。因为调度员往往在接到最后一份订单后的一个小时内就要制定车辆运行路线计划
      • 扫描法的具体步骤如下：（1）将仓库和所有的停留点的位置画在地图上或坐标图上。（2）通过仓库位置放置一直尺，直尺指向任何方向均可，然后顺时针或逆时针方向转动直尺，直到直尺交到一个停留点。询问：累计的装货量是否超过了送货车的载重量或载货容积（注意首先要使用最大的送货车）。如是，将最后的停留点排除后，将第一辆车的停留点确定下来。再从这个被排除的停留点开始继续扫描，从而开始一条新的路线。这样扫描下去，直至全部的停留点都被分配完毕。（3）安排每辆车运行路线的停留点的顺序，以求运行距离最小化
• 网络图
  • 通常，在一个项目的网络图中，只有一个起点，也就是第一项工作的左端节点；只有一个终点，也就是最后一项工作的右端节点。另外，还需要从起点开始，按照每个节点出现的先后顺序对节点进行编号，编号从1开始，即起点的编号是1
  • 清楚了上述规则之后，还需要注意的是，我们在绘制网络图时只需注意箭头方向、连线连接方式、连线上的工作代号和持续时间、连线是虚线还是实线，而不必在乎连线是否曲直、长度是多少、形状是直线还是折线或者曲线，因为这些并不表示具体的含义
  • 在网络图中，还需要注意一些细节
    • 其一，网络图中只能有一个起点和一个终点，不能有多个起点和多个终点。因为网络图的起点表示整个项目的开始，而终点则意味着整个项目的结束。有多个起点或者多个终点就意味着网络图还未画完整
    • 其三，网络图不能出现缺口。一个项目的计划必须是流畅无阻的，如果网络图中出现缺口，就意味着从起点开始，按照网络图来执行工作，到达不了终点，也就是说这个项目还缺少一些必要的工作。出现了缺口，同样说明网络图还没画完整
    • 其四，相邻两个节点之间只能有一项工作。我们知道，每项工作的前后都连接着一个节点，但是每两个节点之间也只能有一项工作，否则就无法确认在这两个节点之间应该执行哪项工作
  • 每项工作的最早开始时间就是这项工作所能执行的最早时间，最早完成时间就是这项工作能够结束的最早时间。同样的，最迟开始时间就是这项工作开始执行的最晚时间，最迟结束时间就是这项工作能够结束的最晚时间
    • 主要方法是从前往后计算。在网络图中，我们通常假设整个项目的开始时间是0，也就是第一项工作的开始时间是0。接着，我们根据网络图中的箭头顺序和各项工作的持续时间，从整个项目的起点开始计算，就能迅速得到每个项目的最早开始时间，当然，也就得到每个项目的最早结束时间，因为最早结束时间等于最早开始时间加上这项工作的持续时间
    • 另外，每项工作的最早结束时间都会成为它的紧后工作的最早开始时间，因为它们是按照先后顺序执行的
    • 如何计算网络图中各项工作的最迟开始时间和最迟结束时间？主要方法是从后往前计算。在网络图中，整个项目都有一个确切的结束时间，也就是这个项目的起始时间加上整个项目的持续时间。例如，在网络图7-9中，如果这个项目是从0这一时刻开始的，那么这个项目的结束时间就是18，也就是终点所表示的时间是18。现在，需要从后往前进行分析。显然，最后一项工作是F，它的最迟结束时间必然是18，在这时候，用最迟结束时间减去这项工作的持续时间2分钟，也就得到了F的最迟开始时间，应该是16
    • 工作的机动时间和工作总时差
      • 在从两个角度得到各项工作的开始时间和结束时间之后，根据这些条件，我们能够很清楚地知道每项工作是否能够机动，并且可以计算出它的机动时间。有的工作并不需要一定在某个时刻开始执行、一定在某个时刻结束，在不耽误整个项目进度的前提下，这个可以自由变动的时间范围就是这项工作的机动时间，机动时间就等于这项工作的最迟开始时间减去最早开始时间，或者最迟结束时间减去最早结束时间。例如，从图7-13中可以得到，C、D和E的机动时间都是11分钟
      • 某些工作的总时差就是这些工作所共有的机动时间。例如，C、D和E这三项工作的总时差就是11分钟，如果B占用了7分钟的机动时间，那么D和E就只剩下4分钟的机动时间了
    • 关键工作
      • 在一张网络图中，总有一些工作并没有机动时间，必须严格地按时开始、按时结束。这些工作就是我们需要注意的关键工作。通常，在一个项目中，如果关键工作出现了一时的暂停或者延后等问题，那么，这个项目就不可能按时完成，整个项目都需要延后。而对于某些具有机动时间的项目来说，即使出现暂停或者延后，但是只要在机动时间内，就不会对整个项目的进展产生影响
      • 因此，根据图7-13，可以清楚地看到工作A、B和F的机动时间都是0，因此，这些工作都是泡茶这个项目中的关键工作。那么，只有这些工作都能够严格地按时执行，最后才能保证整个泡茶项目在时间为18的时候结束。在一个项目中，关键工作需要重点照顾，优先分配时间和资源。这些关键工作组成的工作路线叫作关键路线，例如，在图7-13中，A—B—F就是一条关键路线。通过网络图求得一个项目的关键路线，在项目管理中非常重要
      • 其实，关键路线本质上就是网络图中从起点到终点的最长路径，比较简单的网络图也可以通过直接观察来寻找网络图中从起点到终点的这条最长路径，这就是这个项目中的关键路线
      • 比较甘特图和网络图，就可以发现网络图比甘特图更加简洁、方便，各项工作之间的逻辑关系更加清晰，同时还可以比较方便地计算各项工作的机动时间，从而能够发现项目中的关键工作，得到项目的关键路线，帮助我们管理整个项目1
• 思维起搏个人总结
  • 博弈论/（美）约翰·冯·诺依曼著；刘霞译.——沈阳：沈阳出版社，2020.7ISBN 978-7-5441-8184-6
    • 博弈的分类
      • 若根据博弈中的参与者是否达成一个具有约束力的协议来划分
        • 合作博弈
          • 当相互作用的局中人就博弈过程制定了一个具有约束力的协议时，这个博弈就是合作博弈
        • 非合作博弈
          • 如果局中人之间没有制定这项协议，那么该博弈就是非合作博弈
          • 在经济领域，人们所谈论得最多的博弈是非合作博弈
          • 一般来说，非合作博弈比合作博弈简单，其理论也远比合作博弈成熟
      • 博弈论是这样一个过程：它是个人或团体在一定规则约束下，依据各自掌握的关于别人选择的行为或策略，决定自身选择的行为或策略的收益过程
      • 二人零和博弈
        • 这种博弈是一种非合作、纯竞争型的博弈。现实中的博弈案例包括两人下棋、打乒乓球等。在这种博弈中，一人赢就意味着另一人必然输，一人胜一筹，另一人必输一筹，两者的净获利相加始终为零
        • 在解决这类问题时，人们常会使用传统的决定论，并遵循其中的最大最小原则。具体来说，就是每一位参与者都会猜，为了让自己最大程度失利，对手会实行什么策略，并据此制定出最优策略。冯·诺依曼利用线性运算等数学方法成功证明了在二人零和博弈中可以找到一个最小最大解
        • 利用线性运算，二人零和博弈的参与者就能根据对应的概率分布，随机选择最优策略中的步骤，使双方利益最大化或相当。这一博弈论的深层意义在于，所得的最优策略与对手在博弈中的操作没有依存关系。简言之，其理性思想就是“抱最好的希望，做最坏的打算”
        • 企业之间的完全竞争所能达到的均衡是一种非合作博弈均衡，即纳什均衡。在这种稳定状态下，企业要销售产品，就会按照其他企业的定价来定价，消费者要购买产品也会参照各企业的定价来决定是否购买。企业的目标是实现利润最大化，消费者的目标是争取产品效用最大化。由于这是一种零和博弈，所以两者的利润之和是零。此时，企业所制定的产品价格就等于边际成本。企业之间处于完全竞争的状态时，非合作行为能保障社会的经济效率。如果企业进行合作并采用垄断价格，那么就可能影响社会经济效率
    • 博弈论定律
      • 零和博弈
        • 零和博弈属于非合作博弈。即参与博弈赛局的双方，在严格遵守博弈规则的前提条件下，若是其中一方可以获得利益，也就意味着另一方的利益必然受损。所以，博弈双方的收益和损失之和永远为零，即博弈双方不存在合作的可能
      • 重复博弈
        • 可以将重复博弈总结成三个基础特征：第一，在进行重复博弈的过程中并没有“物质”上的关联，简言之就是上一个阶段所进行的博弈，并不会改变接下来所要进行的博弈结构。第二，在进行重复博弈的每个阶段，所有的参与者都能够看到前面的参与者所做出的决策。第三，对于参与重复博弈的参与者而言，他们所获得的收益是在每个阶段所获得收益的加权平均数
        • 重复博弈中信息的完整性，能够影响博弈的最终结果的主要原因是，当参与博弈的人自身的所有信息都不被他人所了解时，那么他能够在整个重复博弈的过程中建立良好的声誉，借此他极有可能获得长远的利益
      • 囚徒困境
        • 在囚徒困境中，所有的囚徒虽然选择了合作，而且不会向警察或者法官说出事实，还能为其他人带来利益，让所有人都无罪。但是当对方的合作意图并不是非常明显，或者无法确认时，出卖自己的同伙便能够让自己减刑或者立即释放，而且同伙可能也会为了自身的利益而招供出自己，在这种情况下，出卖自己的同伙是能够让自身的利益最大化的
      • 智猪博弈
        • 我们可以将小猪的这种方法称为“坐船”，或者“搭便车”，暗示人们在某些情况下，若是选择注意等待时机，将是一种明智之举，即，不为才能有所为
• 书名：优化之道：生活中的运筹学思维 作者：刘强 出版社：中国铁道出版社 出版时间：2018-05 ISBN：9787113243654
  • 前言
    • 以牙还牙 降低已发生事情的机会成本 斗鸡博弈 猎鹿博弈 智猪博弈 市场先到后到威胁 贪心算法细分 最短路（设备更新、迪杰斯特拉算法） 最小连接线路（普里姆算法、克鲁斯卡尔算法）
    • 一个懂运筹的人无论做什么，都会体现出“效率”和“利益”二字，这是因为运筹的本质就是用最小的成本，获得最大的利益。运筹学本来就是一门“急功近利”的学科
    • 学习运筹学到底难不难呢？如果你学习运筹学是用来做学问，是要成为运筹学专家。那么，这将是一件非常困难，需要付出极大心血的事
    • 第一章　人人都需要运筹学
      • 1.2　运筹学能帮助我们做什么
        • 对于“以牙还牙”策略，有以下四个特点
          • 友善：“以牙还牙”者开始一定采取合作态度，不会背叛对方
          • 报复性：遭到对方背叛，“以牙还牙”者一定会还击报复
          • 宽恕：当对方停止背叛，“以牙还牙”者会原谅对方，继续合作
          • 不羡慕对手：“以牙还牙”者个人永远不会得到最大利益，整个策略以全体的最大利益为依归
        • 从统计的结果来看，在众多策略中，“以牙还牙”确实是最有效的。曾连续数年击败由计算机科学家、经济学家和心理学家等团队所提出的策略。因此，在人际关系中，如果遇到了不讲信用的背叛者，最好的策略就是同意选择背叛，并且终止这种合作关系。这样才能确保自己的最大利益
        • 不好看的电影最好不要忍着看完
          • 沉没成本是指已经付出且不可收回的成本。沉没成本常用来和可变成本做比较，可变成本可以被改变，而沉没成本则不能被改变。因此，上面两难境地中，电影票的价钱可以算作决策时的沉没成本，我们需要考虑的是要不要继续在这部电影上花时间，因此，可变成本就是看这部电影的时间
          • 从运筹学的角度来看，在决策的时候，考虑的应该是如何让自己的利益最大。从理性的角度来看，没有必要考虑那些已经无法改变的沉没成本，应该考虑那些可以改变的成本，将这些成本降到最低，这样才能让自己的利益最大化
          • 最好的选择是离开电影院，不再继续看电影，这样我们只是花了点儿冤枉钱，还可以腾出时间做一些其他更有意义的事来降低机会成本；而选择继续看电影，就意味着还要在这部电影上花费不必要的时间，还要继续受罪，这时候付出的成本就不仅仅是票价了
      • 1.3　那些不会运筹的倒霉蛋
        • 如果我们能从全局来考虑问题，不被眼前的胜利冲昏头脑，可以为了最后的胜利牺牲眼前的利益，只有这样，才能够使我们笑到最后
        • 运筹学的主要内容分为三个部分：如何规划、如何计划和如何决策。因此，在遇到生活中的问题时，我们可以先判断这个问题属于哪个方面，然后再用运筹学的相关方法来解决
        • 例如，在选择投资方案时，采用运筹的方法进行合理规划，能带来更高的收益；在制订计划时，用运筹的方法进行合理安排，可以节省时间；在博弈过程中，用运筹的思想做出最佳决策，从而战胜对手等
    • 第九章　运筹学在人际关系中的应用
      • 9.3　为什么有些时候不必谦虚
        • 在斗鸡博弈中，对每一方来说，都没有一个确定的最佳策略。因为任何一方都不能够确定对方会采取怎样的策略，对方既可能选择前进，也有可能选择后退，对方也无法摸清我方的策略。这也说明“斗鸡博弈”不像之前“交换密封袋子”的博弈一样，不能准确预判博弈的结果
        • 在日常的人际交往过程中，如果遇到“斗鸡博弈”这样的场景，我们应该怎样对待呢？此时没有必要采取谦虚态度了，应敢于展示自己的实力，坚定迅速地采取前进的策略，用强硬的态度迫使对方后退，因为对方见到我方采取前进策略，从自身的利益出发，对方必然也不会选择前进，而会采取后退策略。此时我方能获得1个单位的收益，对方需要承担1个单位的损失。因此，在“斗鸡博弈”场景中，个性张扬一点，向对方展示自己的实力，往往能够得到一个对自己有利的结果
        • 如果不能依靠额外的信息来为决策提供参考，那又该怎么办呢？这时候就需要敢于亮剑，坚定、迅速地采取前进的策略，迫使对方后退，因为对方见到我方采取前进策略，从自身利益出发，必然不会前进，而是采取后退策略。这时候，我方就能获得1单位的收益，而对方需要承担1单位的损失。因此，“狭路相逢勇者胜”、“敢于亮剑”还是有一定道理的，至少是包含运筹学知识的
      • 9.4　什么情形下合作最有利
        • 为什么婆媳之间容易发生不信任的冲突呢？因为婆媳中的任何一方在选择忍让的策略时，如果对方选择斗争这一策略，对于对方来说，是很有利的，但对于自己来说，是很不利的。在“猎鹿博弈”中，一旦合作猎鹿的协议达成，如果对方选择背叛协议，私自去猎兔。那么，对方的收益肯定会下降。因此，无须担心对方不肯合作
        • 在现实生活中，在博弈时，不合作时双方的收益都会下降，此时就会出现合作共赢的纳什均衡，相当于“猎鹿博弈”中双方都选择猎鹿。要建立稳定的合作关系，需要让选择背叛的一方付出更大代价，让背叛得到的收益比双方合作时小得多
      • 第五章　运筹学在市场竞争中的应用
        • 第七章　运筹学在人力资源中的应用
          • 7.4　管理者应该怎样防止员工“搭便车”
            • 在员工中，既有能力较强，工作认真的“大猪”，也有经常偷懒、依赖别人的“小猪”。从上面的分析可知，“小猪”知道“大猪”会将事情做好，会等待“大猪”弄来食物。也就是说，某些员工知道别人会帮助自己完成某些工作，因而在一旁偷懒。对于这些提供帮助的员工，也许是为了整个项目的进度，也许是出于责任心，但却给了别人偷懒的机会
        • 5.3　淘宝和易趣，市场先到者和后到者之间的竞争
          • 在市场竞争中，并不一定是先到者会阻击后到者，对于后到者来说，也不一定不能在市场中立足。当然，这一切都取决于先到者阻击的成本，以及市场是否还是蓝海。如果阻击成本很高，会导致阻击后自己的收益下降，或者市场远未成熟，先到者无力阻击，此时先到者的阻击就不可信，不可能变成现实，此时是后到者进入市场的最好时机
  • 第四章　运筹学在商场中的应用
    • 用贪心法解决问题
      • 虽然不能用数学模型求解，但可以用动态规划方法分析问题。这个问题采用的是一种比较特殊的动态规划方法，运筹学中称为贪心法。相同的是，贪心法同样可以将问题化繁为简，和动态规划一样，贪心法也需要将问题不断细分。不同的是，贪心法并不需要比较各个小问题的最优解，用贪心法即可每次直接找到提供最优方案的小问题，不用在不同的细分问题之间比较和选择。无论如何，两者的核心思想和主要步骤差不多
      • 首先，对最优方案进行定性分析 （1）如果单买口味不同的两瓶酸奶，这个方案一定不会是最优方案。因为两瓶口味不同的酸奶一起买是打9折，比9.5折更优惠。因此，最优方案中一定不会出现两瓶口味不同的酸奶 （2）如果单买一瓶酸奶，另外两瓶不同口味的酸奶一起买，这个方案也一定不是最优方案。因为三瓶口味不同的酸奶一起买是打8.5折，比两瓶打9折和一瓶打9.5折更优惠 （3）如果出现两瓶口味不同的酸奶一起买，另外一种口味的酸奶和这两种口味中的一瓶一起买，如一瓶原味和一瓶红枣味一起买，一瓶原味和一瓶草莓味一起买，或者一瓶原味和一瓶红枣味一起买，一瓶草莓味和一瓶红枣味一起买，或者一瓶原味和一瓶草莓味一起买，一瓶草莓味和一瓶红枣味一起买，它们的花费都是12×0.9×2=21.6元。这时也不可能是最优方案，因为将三瓶口味不同的酸奶一起买，另一瓶单买，这样会更优惠，此时的花费是18×0.85+6×0.95=21元 综上可以发现，只要是需要不同口味的三瓶酸奶，即可放到一起购买，这样会获得更多的优惠。同理，只要是需要不同口味的两瓶酸奶，也可以放到一起买，这样总比单买优惠一些
      • 注意，贪心算法一定要建立在严谨的逻辑分析和在对问题的全面考虑之上，不能仅凭直觉和经验断定最优方案一定会出现在细分后的某个小问题中
    • 4.4　超市怎样开放收银台最合适
      • 最好采用一支队伍两个收银台的形式
  • 第三章　运筹学在运输中的应用
    • 3.3　快递运输选择距离最短的运输路线
      • 迪杰斯特拉算法
        • 一条最短路径往往是由一段段的最短路径组成。例如，A—B—C—D—F这条从A点到F点的最短路径中，其中任何一小段路线都是其起点到终点的最短路径。对于那些不在最短路径之中的连线，也不可能包含在其他的最短路径中。例如A—C，不包含在最短路径A—B—C中，那么A—B也就不可能包含在从A点到F点的最短路径中
        • 因此，在求从起点到距离较远的终点的最短路径时，可以先求出从起点到较近点的最短路径，逐步进行拓展，得到从起点到较远的点的最短路径，直到找到从起点到终点的最短路径为止。对于那些已经发现的不包含在最短路径中的线路，将其从图中删去，这样即可将问题不断简化
    • 3.4　自来水管道选择长度最小的连接线路
      • 普里姆算法
        • 这种方法的核心思想是从某一点着手，找到能够连接其他点的最短连线，并将这条连线加入最短连接线路中，依此类推，不断连接到其他点，从而得到完整的最短连接线路
        • 因此，这个问题的具体解决思路如下：如果从A点着手，只需要找到连接A点的最短连线。从图3-13中可知，连接A点的最短线路是A—E，它的长度是2。因此选择A—E作为最短连接线路中的一条，E点已经在最短连接线路中。然后再寻找最短的连线，这条连线可以和A或E相连，依此类推，每次都向最短连接线路中加入一个新的点，直到所有的点都能连接在一起
      • 克鲁斯卡尔算法
        • 如果说普里姆算法是从点的角度来考虑问题，从图中的某一点开始，依次找到能够连接新的点的最短连线，这些连线一起组成了所有点之间的最短连接线路。那么克鲁斯卡尔算法就是从边的角度来考虑问题，将长度较短的边尽可能地放到最短连接线路中
        • 例如，对于图3-13来说，可以选择最短的一条线路A—E放到最短连接线路中，再从剩下的线路中选择最短的一条，也就是A—B放到线路中。依此类推，直到所有点之间都能连接
        • 但需要注意的是，如果两点之间已经是连通的，就没有必要在方案中加入这两点之间的线路了。例如，在A—E和A—B都加入最短连接线路中，虽然B—E是剩下的线路中最短的两条线路之一，但是由于B和E都已经在线路中，所以这条就不能再加入，否则就是多余的了
  • 第十章　运筹学在家庭生活中的应用
    • 要想找到最佳换车时机，就是要让第1年年初到第6年年初的汽车驾驶总花费最低，也就是寻找图10-1中从A到F的最短路径。可用迪杰斯特拉算法寻找从A到F的最短路径
• 书名：生活中的运筹学 作者：韩红梅 出版社：电子工业出版社 出版时间：2017-07 ISBN：9787121316739
  • 第3章 整数规划：最优解必须是整数的规划问题
    • 整数规划 背包问题 多目标规划（先将次要目标化为条件，接着对主要目标采用平方加权） 逆向归纳法 鹰鸽博弈
    • 背包问题：现在有三件物品和一只容量为10千克的背包，这三件物品的重量依次是3千克、4千克和5千克，它们的价值分别是4元、5元和6元。每件物品只有一个，请问将哪些物品装入背包可使这些物品的重量总和不超过背包容量，并且能得到最大的总价值？ 从题干中可以看出，这是规划问题中的“选择题”，对于每一件物品，只能选择放进背包或者不放进背包，如果放进背包则用1表示，不放进背包则用0表示，那么，这个问题就成了典型的0-1规划问题。假设第一件物品是否放入背包用 x1表示，第二件物品是否放入背包用 x2表示，第三件物品是否放入背包用x3表示，其中，x1、x2和x3是0或者1
  • 第4章 动态规划：将复杂问题分解的思维
    • 这就是动态规划的巧妙之处，我们从解决最小的问题开始，一步一步，就能很轻松地解决稍复杂的小问题，最后也就解决了原来的复杂问题，得到了最优的方案。也可以这么说，动态规划是一个连续决策的过程，需要从最基础的问题开始，找到每一步的最优方案，也就得到了最终的最优方案 总之，动态规划中最核心的是问题的细分，如何细分问题往往决定了解决问题的难易程度，细分不当，甚至会得不到最优的方案。至于如何细分问题，可以从接下来的几个例子中好好体味
  • 第5章 多目标规划：化繁为简的规划方法
    • 如何装配电视机 某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利90元；黑白电视机的销量是30台，每台可获利30元。该厂确定的目标如下。第一优先级：装配电视机的数量尽量满足市场需要。第二优先级：充分利用装配线，每周至少开动40小时。第三优先级：允许装配线加班，但加班时间每周尽量不超过10小时。该电视机厂应该如何安排装配线？ 首先，分析问题，列出未知数。在这个问题中，具有三个不同优先级的目标，这是一个多目标规划问题。假设每周为黑白电视机分配x小时，为彩色电视机分配y小时。其次，列出问题的各项目标。根据问题和所设的未知数，可以得到每周的黑白电视机产量是x台，彩色电视机的产量是y台。因此，可以得到如下目标。第一优先级的目标：x– 30和y– 24。第二优先级的目标：40≤x+y。第三优先级的目标：x+y≤50。最后，确定简化多目标的方法 根据题干中各目标的优先级，首要的目标是装配电视机的数量尽量满足市场需要，而次要的目标则是确保装配线每周的开动时间为40～50小时（加班10小时）。因此，这个多目标规划问题适合采用消去次要目标的方法。将两个次要目标变为规划问题中的条件：40≤ x+y≤50 对于首要的目标：确保电视机的数量尽量满足市场需要，市场需要的值就是那个理想值。因此，又适合采用平方加权的方法。其中，黑白电视机满足市场需要的目标是(x-30)2，彩色电视机满足市场需要的目标是(y-24)2，我们要做的就是让这两个目标值尽可能小 那么，如何给它们设置权重呢？由于彩色电视机的利润比黑白电视机要高，并且刚好是黑白电视机的3倍，所以在设置权重的时候，最好将彩色电视机的权重设为黑白电视机的3倍，以体现出彩色电视机的重要性。同时，它们的权重加起来等于1，因此，可以得到黑白电视机的权重是0.25，彩色电视机的权重是0.75，也就得到总的目标是：0.25(x-30)2+0.75(y-24)2 在这个多目标规划问题中，我们灵活使用了两种方法，先将次要目标化为条件，接着对主要目标采用平方加权的方法，将这个多目标规划问题简化成一个单目标规划问题。从这里也可以看出，对于一些多目标规划问题，我们可以灵活地采用各种不同的方法，将多目标规划问题简化为单目标规划问题
  • 第9章 静态博弈：不分决策先后的博弈过程
    • 群体之间的斗争“鹰鸽博弈” 以上博弈都是在个体与个体之间进行的，但在现实世界中，往往群体与群体之间也会进行博弈，尤其是在生态环境中，例如，外来物种和本地物种在争夺自然资源上就进行着博弈。捕食者和被捕食者也在不断进行着博弈。当然，在人类社会中，也存在群体间的博弈，而在每个群体内部又包含了个体与个体之间的博弈。接下来，我们介绍一种非常典型的群体之间的博弈，叫作“鹰鸽博弈” 在大自然中，鹰是一种凶猛的鸟类，给人的印象是强者；而鸽的性情温和，比较瘦小，给人的印象是弱者。因此，鹰搏斗起来总是凶悍霸道、全力以赴、孤注一掷，除非身负重伤，否则决不退却。而鸽一贯都是用叫声来进行恫吓，没有伤害对手的实力，往往委曲求全。如果鹰同鸽搏斗，鸽就会迅即逃跑，因此鸽不会受到伤害；如果鹰同鹰搏斗，就会一直打到其中一只受重伤或者死亡才罢休；如果鸽同鸽相遇，那么谁也不会受伤 现在假设每只动物在搏斗中都选择两种策略之一，即“鹰策略”或者“鸽策略”。对于为生存竞争的每只动物而言，如果自己采取“鹰策略”，而对手采取“鸽策略”，那么自己就会赢得这场博弈，收益为2；如果对手采取“鹰策略”，而自己采取“鸽策略”，那么自己就会输掉这场博弈，收益是-1，也就是承受1单位的损失；如果双方都采取“鹰策略”，那么，就会两败俱伤，双方都会受到严重的伤害，这时各自的收益都是-2,；如果双方都采取“鸽策略”，此时双方相安无事、和平共处，各自的收益都是1 “鹰鸽博弈”和“斗鸡博弈”非常相似，但是不同于斗鸡博弈，鹰鸽博弈是群体博弈，一个是侵略群体，另一个是和平群体。我们需要用长远的眼光来看待这场博弈的最终结果，同时还要考虑群体内部的斗争。各物种之间的鹰鸽博弈是大自然中的基本博弈现象。例如，在只有鸽子的环境里，突然加入的鹰将大大获益，并吸引同伴加入。但结果并不会是鹰将鸽消灭干净，而是以一定比例共存，因为当鹰群过大时，由于鸽的资源是有限的，就会发生内部斗争，有一部分鹰就会被其他鹰消灭，这时候，鹰和鸽之间的均衡就已经到来了；同样的，如果鸽群数目过小，那么鹰也会为了争夺鸽群资源而发生激烈的内部斗争，这时候鹰的数量同样大量减少，直到能和鸽的数目相匹配 从上述博弈过程中可以发现，在群体博弈和内部斗争（也是一种博弈）两者的综合作用下，鸽群和鹰群在同一个环境中按照一定的均衡比例实现了共存，这就是生态环境中物种之间的稳定现象。可以看出，在一个生态环境中，弱者并不会完全消失，强者也做不到独霸所有资源，这种均衡带来的稳定对生态环境具有非常重要的意义
  • 第10章 动态博弈：有先手和后手之分的博弈过程
    • 委托人和代理人问题 从这个博弈过程中也可以看出，对于委托人来说，要想让代理人同意自己的委托并且自觉地努力工作，只给予代理人不错的报酬还不够，还需要采取激励措施，让代理人在努力工作时得到更多的收益。或者，对代理人的工作进行有效监督，让代理人在懒惰状态下的收益减少，代理人在这样的监督下也就不会偷懒了
    • 从上述静态博弈和动态博弈之间的对比可以发现，生活中的动态博弈往往是建立在沟通的基础上的，在静态博弈中如果双方进行沟通，分先后做出决策，也就变成了动态博弈。这种沟通还是非常必要的，因为能够避免“两败俱伤”的最差情形出现
• 任何图中，奇点的个数为偶数个，不要把奇点和孤立点弄混了