[音乐] 收拾因毁坏神算法板引致的混乱后 仙人告诉诸葛亮混乱虽平，但历史亦因此改变 命令诸葛亮前往各处历史变更之处，帮助历史回到正轨 诸葛亮首先前往商代，到达商代后，诸葛亮需要辅助太上老君 及哪吒击败通天教主，打斗中，通天教主集合手下道士 布下万仙阵，在使出数把 奇剑，以六个气场包围加强守阵 太上老君派出哪吒破阵，并指出若可以若找出气场包围中最弱道士 即可击溃守阵，哪吒未能找出守阵的最弱点，便请诸葛亮 相助，于是诸葛亮召出时空飞龙相助 哪吒跟这个太上老君需要跟这个邪恶的通天教主 进行一个大斗法，但是这个通天教主也不是省油的灯 所以呢他也设计了一个非常厉害的一个万仙阵来对抗这个哪吒的攻击 这个万仙阵呢基本上就是在一个三维的网格上面，在每一个网格的点都放一个道士 这个总共有一万个这样子的道士呢 来保护这个通天教主跟他的教坛 除了这个万仙阵之外呢，这个通天教主他也懂法术的，他还有 四把非常厉害的飞剑，他就利用他的法术跟他的飞剑呢就产生了不同的气墙 我们可以在这里已经看到在他的两旁跟他的脚底呢已经有三道的气墙了，另外一道气墙 在这里 每一道气墙呢都会有一些气可以保护 这个通天教主，但是最厉害就是所有的气墙的保护的能量结合起来的话 对这个通天教主的保护呢就是最大的，而且 出来这个结合出来的能量也可以保护在这个气墙 可以覆盖的到这个万仙阵，如果这个万仙阵 的这个道士的位置是在这个气墙的合成的 保护之下呢，这个道士也是会给这个气墙呢可以保护到的 好了，幸好呢我们的太上老君呢已经把这个通天教主 他这个不同的气墙它的数学表达式都已经计算了出来，所以我们就 知道了每一道气墙就有一条的不等式，总共是六道道气墙，所以我们有六条的 这个不等式呢来设计出来的，而且呢这个太上老君 也找到原来在这个气场保护之下，但是呢如果 哪吒可以攻击里面不同的这个 道士呢，他也是有可能的对这个 道士以至整个万仙阵呢进行破坏的，这是基于这样子的一个 目标函数来去告诉我们 攻击不同点的道士他可以产生的破坏是多少的 这个太上老君呢就是建议的我们需要做的 哪吒需要做的就是在这个气墙当中找到攻击点最弱的一点 如果可以把这个找到出来了，就攻击上面这个道士，然后呢，如果因为他攻击最弱这一点呢 哪吒如果把这个道士这个打败的话 他就可以呢把整个万仙阵呢也破坏了 好了，我们就一起来看一看这个我们要解决所谓是个 气墙的问题，我们已知呢就是在三维空间当中我们有六道的气墙 这是都是平面的气墙来的，我们也已知一个目标的函数，这个目标的函数 就是帮助我们量度我们如果对这个不同的道士 进行在这个气墙保护之下的道士进行攻击的话，我们可以造成的 伤害是多少，我们需要找到就是找到最弱的这个地方 就选取这个道士呢要攻击他，如果可以把他打败的话，那我们就可以把整个万仙阵都破坏了 原来这个好像听起来挺复杂的 一个问题呢有一个非常简单的一个<br>MinZinc 模型 这个 MinZinc 模型里面就是对每一道的气墙它的不等式 就是作为我们这个问题里面的 约束，然后呢我们要最大化的就是 要找到一个点，这个点的就是 如果我们攻击这个点的话，我们就可以对这个万仙阵达到最大的破坏的 这个万仙阵里面受到这个气墙保护里面最弱的一点，这个就是我们需要找到的一点 好了，其实我们刚才呢看到的一个问题呢就是一个 很简单的线性的规划的问题，每一个线性规划的问题我们都有 n 个变量 而且呢我们里面也需要有 m 个 m 条的约束，这个 m 条 约束他们都是线性实数的不等式来的 而且呢我们要求呢每一个变量呢它们都是非负的来的 而且我们也有一个线性的这个目标函数，我们要求呢 就是要满足了所以的线性的约束之外 也需要呢把这个目标函数最大化，这个呢就是线性规划问题了 好了，如果我们要为这个线性规划问题 求解呢，我们要看看这个里面不同约束 到底在这个几何上面来讲它们是什么样子的 其实呢我们在我们这个一个线性规划问题里面每一个不等式呢 就是代表在一个 n 维空间里面的一个超平面，这个 n 是什么呢，就是我们这个线性规划问题 里面这个变量的个数，在我们的问题 里面我们只有三个变量，所以呢我们是一个三维的问题 所以我们已经可以看见这个三维的这个坐标了，因为呢我们 里面的约束都是一个不等式，所以呢我们每一个的 不等式呢代表了这个超平面是用来帮助我们 在用于给我们一个限界的 因为每一个变量都是非负的，所以呢我们就知道了 这三个平面就是代表这三个变量非负的约束 然后呢，我们其它的这个约束呢就代表这个超平面 另外一个约束就代表另外一个超平面呢，另外一个约束就代表另外一个超平面呢，那然后呢我-<br>们就可以看看 所以的超平面呢混在一起了，因为我们的不等式都是 小于等于的，所以我们这个每一个平面，超平面它们 都是要往里面走的，所以呢我们就可以把这六个超平面呢它们的相交点 都算出来，算出来的相交点呢都是我们显示 利用这个就是我们的相交点出来的多面体的 每一个顶点，好了，你们有可能发觉我们出来这个 多面体里面只有五个面，但是我们是有 六个超平面的，其实如果你们看近处我们发现 上面这一块的超平面它跟我们这个多面体只是在这一个点有相交的，而且呢它是在 我们这个相交的地方的上面呢，所以呢，所以这个超平面<br>里面基本上就没有贡献一个面给这个多面体了 那现在我们就可以比较清楚一点可以看见我们这个六个超平面它们相交 出来的一个多面体，我们要注意呢就是如果一个线性规划问题它是有最优的解呢 它们的可行解呢都会给包含 在一个多面体的内部的，所以这个多面体呢就是包含了 我们整个问题里面的可行解的，我们呢可以放大 把这个多面体的放大去看一看，更重要的一个一个观察就是什么呢 就是如果我们这个问题是有一个最优解，这个最优的解一定是在这个多面体的 某一个顶点上面呢，有可能是这个、 有可能是这个，也有 可能是其它的顶点上面。 啊，这个就是我们要知道对这个 线性规划问题的，需要知道的一个非常重要的观测。 好了，那我们现在有了这个线性规划的问题，我们怎么可以 解决这些问题呢？我们刚才已经提到了，如果这个问题里面是有一个最优的解呢， 那它最优的解呢，一定是在这个多面体的上面的某一个<br>顶点上面，所以我们的求解的过程呢，也挺简单的。 说起来啊，就是呢，我们首先就需要呢，可以找到、 跳到这个多面体 某一个顶点上面。 然后呢，我们在到了一个顶点上面呢，我们就又看看它旁边相邻的顶点。 看看呢，会不会它相邻的顶点呢，会有某一个顶点呢，它的目标函数的值呢，是会 比我现在在的一个顶点上面呢，比较好的。 如果是好的话，我们就跳到这个相邻的顶点上面。 然后，到了一个新的顶点上面呢，我们就重复刚才要做的事情，就是看看它相邻的地方， 会不会有另外一个顶点呢，它的目标函数的值呢，是比我现在在的这个顶点上面是比较好的。 我们就重复重复做这个动作呢，直到我们没有办法再找到在现在的顶点上面 找到在旁边呢，有更好的一个顶点。 然后呢，我们就可以 返回目前我们在的顶点，这个就是呢，我们的 这个问题的最优的解了。 当然呢，讲起来好像非常简单。 其实有两个非常主要的问题呢，我们还没有回答的，第一个问题呢，就是我们 怎么样可以找到第一个这个顶点呢，我们可以<br>跳上去呢？第二个问题呢，就是我们到了一个顶点上面 我们怎么可以看看旁边的相邻的顶点，而且呢，找到一个比 我现在的顶点更好的一个顶点呢，这个两个都是需要我们解决的问题来的。 在我们开始介绍我们怎么解决这个线性规划问题之前 呢，我希望可以提醒大家呢，有可能你们在中学高中的时候，已经学过一个 我们叫高斯-乔丹的消去法的一个算法。 这个算法呢，是帮助我们解决类似下面的 方程组的它们的解的。 譬如说，我们有 3条 的这个等式，而且呢，这个等式它们都是线性的。 我们看看第3条等式呢，我们其实可以把它 改写呢，其实变成这个 z=-y。 然后呢，我们有了这个之后呢，我们就可以把这个 -y呢，在它的两组的两个等式里面呢， 把这个z变成了-y ，然后呢，我们就得到从第一条 得到第 1.1 条，第二条呢，我们得到这个第 2.1 条。 然后呢，我们 这个 1.1 条呢，其实我们也可以在进行重写。 我们知道呢，y 呢是等于 2分之5减2分之1乘以 x 的。 有了这个之后呢，我们可以 把这个 y 呢，就放到这个代入这个第 2.1 里面，我们就可以得到呢，原来 x 是会等于1的，有了 x 等于1之后呢，我们 把这个 x 等于1呢，代入我们之前的这个等式呢，我们可以 求到呢，原来 y 是要等于2， z 是等于-2的。 这个呢，就是我们这个方程组的一个解了。 那当然呢，你说<br>啊，我们从前在中学已经学过这个高斯-乔丹的消去法了，其实我要提醒大家呢，就是在这个 问题里面，我们每一条的等式呢，其实呢，是代表 一个平面或者是一条线，在这个，在我们这个问题里面，因为我们有3个变量 所以呢，每一条的等式呢，就是在三维里面的一个平面或者是一条线。 然后呢，其实我们所谓是未知组的方程求解呢，就是希望把这个不同的平面跟不同的线呢 它们的相交点找出来。 但是另外一个更重要的一个 观测呢就是什么呢，我们其实在做每一步的时候呢， 我们的进行一个我们叫代入的操作，所谓是代入的操作，就是我们把 z 是等于-y 的，那我们就在其它的等式 里面呢，把所有的 z 我们都把它代入了，这个-y 这个值、 这个表达式在里面。 最重要呢，就是 我们这个代入这个操作呢，是一个等价的变换，就是最重要是什么呢？ 我们进行一个代入的操作的时候，我们虽然是把我们的等式 的表达式呢是改变了，但是呢，对我们整个问题的解呢是没有改变的。 所以我们就说代入这个 操作呢，是等价的变换来的。 为什么我们要提醒大家这个高斯-乔丹的消去法呢？因为 在我们在下面要介绍这个算法呢，我们是经常需要利用这个代入 这个操作呢，我们要记住这个代入的操作呢是个等价的变换来的。 好了，我们现在可以回到我们之前的问题，如果大家还记得呢，我们之前的问题呢 是由几条的不等式组成的。 我们第一件事情要做呢，就是把我们的不等式<br>我们这个不等式的约束呢，改写成为等式的形式。 那么怎么做呢？如果大家还记得呢，我们譬如说第一条的不等式呢，就是说 2x+2y+3 是小于等于30这个常数的。 就是说 我们30这个常数呢，是比这个 表达式呢是要大的，所以30减去这个表达式之后呢， 我们应该还有一个为正的数值在的。 那我们就 引入一个我们叫松弛的变量。 这个松弛的变量呢，就是代表 或者是说我弥补呢我们不等式两边的一个差异。 就是这个常数减了这个表达式之后，它的差异是什么呢？就是一个正的 变量出来的。 我们对所有的不等式呢 都引入一个新的，是我们叫松弛的变量。 那我们就可以把我们原来的不等式呢就变成一个等式的形式出现了。 而且 我们希望大家要注意呢，我刚才是用 这个常数去减这个表达式的，是因为我要 确定呢保证呢，这个松弛的变量呢它是非负的。 然后，我们也需要为这个问题的加进另外一条等式，这个等式呢，是 用来代表我们这个目标函数这个变量的，我们就 引入一个新的变量，我们就叫 obj 吧。 然后这个 obj 呢就是我们要最大化这个目标函数了。 有了这个之后呢，我们也要介绍另外一个概念呢，我们叫基可行解 的形式，什么叫基可行解的形式呢？一个基可行解的形式呢就是一批的 等式，如果这一批的等式呢，都满足下面3个条件呢，我们就说这个， 这一批的等式呢它们就是一个基可行解的形式出现了。 首先呢，就是在一个基可行解的形式出现 的等式呢，它的变量呢是分为两组的。 出现在我们等式的右手边的，跟出现我们等式的左 手边的，出现在我们的等式的右手边的变量呢， 绝对不会出现在我们等式的左手边，出现在我们左手边的变量呢，绝对不会<br>出现在我们等式的右手边的。 如果他们出现在我们的左边的话， 我们叫这一类的变量呢，就是我们的基变量。 如果一个变量是出现在 我们的等式的右手边的话，比如说在这里呢就是 x、 y跟这个z呢，就是我们叫它们叫 非基变量。 好了，这个是就两个的要求，第三个要求是什么呢？我们是要求呢 除了这个是表达我们的目标函数这一行 之外呢，其它的等式呢，我们要求它的 常数呢，它的值呢为这个非负的。 这个呢，如果3个条件都满足的话， 我们就说这一批的等式呢，它们就是以这个基可行解 形式出现了。 我们刚好刚才呢我们引入了不同的 松弛变量之后呢，我们的等式呢， 就刚好已经是满足了基可行解形式的 3个条件了，所以我们就有一点运气挺好哈。 好了，为什么基可行形式的等式是那么重要呢？ 原来如果我们的这个等式是以这个基可行解 这个形式出现的话，我们就非常容易在这个等式里面呢 把一个解求出来。 而且这个解呢，我们称这个"解"叫基可行解。 这个解是怎么求出来？非常简单，就是把所有的 非基的变量我们都赋予它0这个值。 非基的变量就是在这个等式的右手边的变量，在这里就是X Y跟Z我们都赋予这个0这个值给它。 然后呢，所有的基变量在就是在这个等式左手边的变量呢，它们就等于 这个等式右手边的这个常数了，所以呢obj呢 就是等于0， s1等于30，s2是等于25，s3就是等于20，这个呢就是我们这个基可行解形式 这一批的等式，它的一个基可行解了。 那为什么这个基可行解那么特别呢？为我们要特别介绍呢？ 原来一个基可行解呢 是非常重要的，因为每一个基可行解都对应 在我们这个多面体上面的一个顶点。 我们刚才提到这个基可行解呢？就是赋予X、 Y、 Z这三个变量的值都是为0，所以呢 其实我们已经找到我们这个多面体的第一个顶点了，所以哪吒呢就可以 跳到这个多面体的第一个顶点上面了。 哪吒发现了第一顶点，他也跳了上去了。 我们在下面呢，就会介绍一个叫单纯形的算法，就是帮助这个哪吒呢 可以从一个顶点跳到另外一个这个目标函数值比较好的顶点，然后最后就可以把线性规划这个问题把它解决了。 其实在后面呢，我们会把这个算法的伪代码是会显示给大家看的，所以在这里我们只是做一个简单的描述。 好了，开始的时候呢我们有一个假设，就是我们的这个<br>要解决这个问题呢，已经是满足了基可行解这个形式的。 然后呢？这个算法非常简单，就是把下面三个步骤呢，重复做一个循环。 这三个步骤呢，就是第一就是要 找一个换入的变量出来。 然后呢 ，也需要找一个换出的行。 然后呢，找出这个换出的行，我们就可以进行转轴的这个操作了。 然后呢，这个循环会继续，直接到我们再找不到这样子的 这个换入的变量我们就停止了。 当然呢，什么叫寻找一个换入的变量呢？ 就是在我们目标函数这一行里面，我们就看看它右手边所有的非基变量。 然后呢，我们希望可以找到一个非基变量它的系数为正的，那如果大家还记得的话 所有的变量都是非负的，所以如果这个非基变量它的系数为正的话 就是说如果我把这个非基变量增加的话，我们就可以帮把这个目标函数的值呢，也可以增加了。 所以我们就可以随便，如果多于这样一个非基变量的话 我们就可以随便呢，选择其中一个作为我们的换入的变量。 然后第二步呢，就是在不在目标函数这一行下面其他的 等式，我们需要就找一个一行来帮助我们去 去把我们刚才选择这个非基变量，把它的值增长的。 如果有多于这样子的一行呢的话，我们就需要选取帮助把 这个非基变量增长幅度最小的这一行来用，我们这一行叫换出行。 那这个换出行怎么帮助我们把我们选取的非基变量的值 增加呢？就是利用一个所谓我们叫这个转轴这个操作。 这个转轴呢这个操作其实就跟我们之前看过的高斯—乔丹消去法里面的 代入就是一模一样，所以呢，我们就会把这个换出的行把它改写，改写到呢 本来是非基变量的，我就把它移到另外 一边，移到这个左手边把它变成一个基变量。 有了这个改写之后呢，我们就会从这个整个系统里面所有的等式里面 出现我们选择了这个非基变量的地方呢，进行一个替换。 然后呢，我们这个非基变量就再不会在这个等号的右手边再出现。 就是带代表呢，它就正式地变成一个基变量了。 这个就是我们的所谓是转轴这个操作 我们就会把这三个步骤呢重复直到我们 再找不到一个在这个目标函数这一行里面。 再找不到一个非基变量，它的系数为正的，那我们就可以停止了。 听到这里，有可能你觉得还不明白这个单纯形算法是怎么搞的。 所以呢，我们下面就利用我们故事里面的问题呢 就把算法做一个演示。 好了，这个就是我们本来的问题 刚加进我们的松驰变量之后，如果大家还记得，那我们很幸运 因为现在我们的等式已经满足了这个基可行解这个形式了，因为我们 有一批的变量就是我们非基变量呢，就是在等号的右手边<br>出现，然后也有另外一批的变量我们叫基变量呢 只会出现在等号的左手边，而且最重要呢，就是除了这个目标函数这一行呢 我们所有的这个常数都是非负的。 好了，到了这一点之后呢，我们当然就要需要在我们目标函数这一行找到一个变量 一个非基变量它的系数为正的，我们发现所有的<br>变量它们的系数都为正的，那我们就可以随便去选择一个了。 那我们就选择X这个变量吧。 好了，选择了X这个变量我们就需要在下面的一行呢 找出一个我们选取一个我们叫换出行。 这个换出行呢，第一就是我们选取X这个变量呢 我们需要它之前的这个系数一定为负的，然后呢 有了我们发觉呢在这个情况之下，我们三行都满足这个条件的。 然后我们就看看每一行，如果我们利用第一行呢，我们原来可以把X这个值呢 从0就增长到15，为什么是15呢？就是30除以2。 如果我们利用第二行来为这个X做增长呢， 我们就可以把它增加从0到25就是25除以1； 如果用第三行的话，我们发现可以把X呢增长到10。 如果大家还记得 我们如果有多于一行可以帮助我们把这个X这个变量增长的话，我们要选取 就是增长地最小的这一行，所以在这里我们选取第三行呢，来作为我们换出行。 那现在我们就可以进行这个所谓是转轴这个操作了，所谓转轴呢就是 首先我们把选取的换出行把它改写，怎么改写呢？就是把我们这个非基变量 移到左手边，然后把本来的基变量呢 移到这个右手边，就是得到下面这个形式。 做好这个之后呢，当然非常重要的就是把在其他地方出现在这个等式， 其他等式出现X的这个地方呢，我们要把它替换它右手边这个表达式。 做完这个之后，我们就完成这个转轴这个操作了。 我们就会得到下面这个等式，我们发现下面这个等式呢也是满足这个 基可行解这个形式的。 为什么啊？我们也有一批的变量只会出现右手边 另外一批变量就是我们基变量只会出现在 这个出现在左手边，而且呢，除了这个目标函数这一行之外呢 我们所有的常数呢都是非负的，所以呢我们就可以从这个等式里面呢 可以找出一个我们叫基可行解了。 我们基可行解怎么找出来呢，就是把 所有的非基的变量呢，都定为0，然后呢，所有的基函数呢 就是取值就是它右手边这个常数，所以呢这个就是我们新的基可行解了。 我们发现这个基可行解呢，它的目标函数的值是30，刚才我们找到 这个顶点呢它的目标函数的值是0，所以我们已经找到一个更好的基可行解了。 我们就看看这个基可行解在哪里，因为我们知道每一个基可行解都是对应在我们这个多面体上面的一个顶点的。 所以我们就去到应该从刚才的 (0, 0, 0) 去到这个 (10, 0, 0) 就是呢，哪吒呢就会从一个角一个顶点跳到另外一个顶点。 因为我们知道这个顶点呢跟原来的顶点是相邻，而且呢它的目标函数的值更好的。 做完这个之后呢，我们还是要继续的，我们要重复刚才讲过的 三个步骤。 所以呢，我们从这个之后呢我们也需要在这个目标函数这一行里面 选取一个它的系数为正的一个变量，我们发现呢现在呢 所以的变量它们的系数都是负，除了 z 这个变量 它的有一个正的系数，所以呢我们就选取了这个 z 这个变量呢作为我们的换入的变量了。 然后，我们当然也需要去检查下面三条的 这个等式哪一条可以作为我们的换出行呢？ 如果我们用第一行的话，我们可以发现根本就陷固在里面，就是说呢陷的可以无限的增加。 另外一条呢，15 除以 2.5 的话，我们发现会把这个 z 从 0 变回这个 6，如果用第三行的话，就是 10 除以 这个 0.5 呢我们可以把这个 z 增加到这个 20。 我们当然要选取就是增长最小的一行，所以呢我们就利用第二行。 所以现在我们就可以进行这个转轴了这个操作，就是把这一行 改写，改写呢就是把我们原来选取这个非基变量呢，把它移到这个左手边变成一个基变量。 原来的基变量了就移到这个右手边，所以呢，这个就是我们可以得到的重写之后这个等式。 重写之后，当然还没完成，我们还需要把这个我们这个等式里面所有出现在右手边的 z呢，就做出一个替换，然后z就不在会在这个等式的右手边再出现了。 有了这个之后，大家也应该同意也应该看到呢 就是我们新的这个等式，它也是满足这个基可行解这个形式的。 因为所有的常数都是非负的，而且根据这样子 求出来这个基可行解我们新的目标函数的值是39比刚才的30是更好的。 最重要是什么呢，我们发现如果我们希望再重复刚才的这个步骤呢 是没有东西可以做了，因为我们现在在目标函数这一行里面呢 所有的变量它们的系数都是一个负数，所以呢我们再找不到一个换入的变量。 这个就是代表什么呢？我们可以停止我们这个算法了，因为我们刚才找到 这个基可行解就是我们这个问题最优的一个解了。 好了，我们看看本来我们是在 (10, 0, 0) 了，我们现在要去到新的一点那就是 (7, 0, 6) 就是呢在上面这一点，这个呢 就是我们这个线性规划问题里面的最优一个点了。 好了，我们刚才已经看见过一个演示，我们现在就把 这个单纯形这个算法它的伪代码给大家看一看。 如果大家还记得我们的假设就是，本来我们这个问题呢 已经是满足了所有基可行形式出现的，然后我们就可以调用这个simplx这个单纯形这个算法了。 刚才已经看到了，它里面最重要的就是一个循环。 这个循环里面有三个步骤。 第一个步骤，就是在我们目标函数这一行里面呢 我们希望去找出一个变量，就是一个非基的变量，它的系数为正的。 然后呢，我们就在下面的其它的等式呢 通常它们都是这个形式出现的就是<br>x=b+cy+... 但是呢，我们只会去检查这个等式里面的 y 它的系数为负值的这样子的行。 不然的话，我们就根本不会去检查这个行，如果我们发现有多于一个行呢 这个 y 它的系数都是负值的话，我们就要选取一行这个 -b 除以 c 这个值为最小这一行。 好啦，有了这个之后，我们就进行这个转轴这个操作。 就是把这一行，我们选取这一行呢把它改写，而且改写之后呢我们也需要把y 在这个其它的等式的右手边出现的地方呢，做一个替换然后y就不会再出现在我们的等式的右手边。 所以 y 就正式变成了一个基变量了。 然后呢，我们知道经过这个转轴这个操作之后 然后呢，我们的这个等式又在满足基可行时这个形式了。 好啦，我们就重复重复把这三个步骤去做，直到我们有两个可能性，我们就会停止这个循环的。 第一个可能性，就是在我们的目标函数这一行里面，我们再找不到任何的变量它的系数为正的。 如果是这样子呢，我们会停止这个循环。 又或者呢，我们是找到这样子的一个非基变量它的系数为正的。 但是呢，在下面呢我们找不到任何一个等式，我们选取这个变量呢 它的系数为负值的，如果我们找不到这样子的一行的话，那我们也是需要停止的。 如果我们是第一个原因要停止的话，恭喜你们啦，我们已经找到最优的解了。 但是如果我们是因为是第二个理由去停止这个循环的话，就代表了我们这个问题呢 就没有最优这个解的。 好了，这个就是我们这个单纯形这个算法的伪代码。 我刚才只是把这个伪代码一行一行介绍一下。 我不知道你们心里面会不会 有很多的问题，就算你们没有，我就会提出一系列的问题给你们思考一下。 第一，为什么我们需要在目标函数里面选取一个变量的时候呢，我们要选取一个系数为正的一个变量呢？ 其实我刚才解释这个算法的时候也有提过，因为所有变量它都是非负的，如果 它的系数为正，在一个目标行数阶行里面是系数为正，就是说如果我们把这个变量的值增加的话 我们就可以帮助吧这个目标函数的值也相加。 因为我们要做这个最大化，所以当然我们希望我们的目标函数是越大越好，所以我们选取这个换入 这个变量呢，我们希望选取一个系数为正的一个变量的。 然后，选取的一个换入的变量之后，我们要选取一个 等式，在下面的其它等式选取一条等式，但是呢我们有两个要求，第一 这个等式里面我们选取这个变量了，它的系数一定是要小于 0 的。 如果有多余这一条这样子的等式呢，是满足这个 c 小于 0 这个条件呢，我们就要选取呢一条的等式就是 -b 除以 c 是比较小、，最小的一条。 为什么我们要满足这两个条件呢？ 其实呢，如果你们想一下，如果 我们选取这个换出行的时候，不跟随这个规定。我们不跟随这个规定，我们还是选取的这个换出行 然后也进行这个转轴这个操作，会有什么 情况会发生呢？聪明的你们呢，应该也想到了，如果我们不跟随这个规定 的话，然后我们做这个转轴这个 这个步骤的话呢，我们发现，我们出来的等式呢就再不会满足基可行解 这个形式了，就是会出现了有某一些的等式，它的常量是会变成一个负值的数。 好了，另外一个问题就是这个算法到底它会不会停止的？因为我们看见里面有一个循环在里面。 好了，看起来呢，我们当然我们这个算法应该是停止的。 因为呢，我们先跳上其中的一个顶点。 然后呢，我们就希望跳到一个相邻的这个顶点，它的目标值呢是比我们现在的 这个顶点呢是好的，然后我们也知道一个多面体的话，如果我们有有限的 超平面的话，它的顶点也是的数目是有限的，所以 那我们的这个算法不应该一定是停止吗？ 原来呢在一些不常见的情况，而且没有太大意义的问题的情况之下呢， 我们刚才介绍这个算法是会出现这个死循环这个问题的。 就是我们不断在两个顶点呢跳来跳去就是不会停止的。 所以，现代的我们这个算法呢都是做了 不同的改进，就是避免这个死循环这个问题的。 好了，我们的算法在结束的时候呢我们有两个可能性。 第一个可能性呢就是当我们在我们的目标函数这一行里面再找不到一个 变量，它的系数为正的， 然后呢我们就可以说：啊，我们已经找到最优这个解了。 这个是为什么呢？到了这个情况就是代表了我们目标函数里面所有的变量。 就是在右手边的变量了，它的系数都为一个负数，就是说无论 怎么样的话，因为我们的变量都是非负的，所以呢我们已经没有可能再把我们的目标函数的值呢 再提高了，所以我们已经找到最大的值，所以呢我们其实也已经找到最优的 一个解了。 但是为什么如果是我们找到这样子的一个变量，但是我们找不到 一个等式，我们选取这个变量，它的系数 c 要小于 0 这样子的情况之下，我就说我们这个问题呢是没有最优解的。 这个其实就是代表的我们选取这个变量可以无限的去增加，然后 就是代表我们的目标函数的值呢也是无限的增加，就是我们这个问题 是没解的，所以就是说它也是没有一个最优的解。 好了，好像我们已经把这个 算法呢已经教完了，其实呢我们还有一个非常重要的 问题呢还没有解释呢，就是我们这个单纯形的算法里面，它 假设我们一开始的时候我们的问题已经是满足了基可行解这个形式的。 但是我们当时非常好运气，因为我们一加上这个松弛变量之后呢，我们的等式呢已经是满足了这个形式。 我们看看下面这个例子好不好？这个新的例子，也是个非常 简单有三个变量的不等式，而且也有一个非常简单一个线性的目标函数。 如果我们像之前增加了这个松弛的变量之后，我们就会得到了这样子的等式。 然后如果我们也像从前一样，把所有在右手边的非基变量定为这个 0，然后呢所有的基变量在左手边，都取这个每一行的这个常数为它的值的话 我们发现出来这个赋值呢就有x=0，y=0，z=0，这个没问题啊。 objective 这个 obj=0 也没问题，s1=4 也没问题，但是对最后两个的 松弛变量 s2 跟 s3 呢我们拿到一个值是负的一个值。 如果大家还记得呢我们 引入这个松弛变量的时候呢，我们也要求松弛变量呢它的值呢也是 非负的，所以根本我们现在得到的这个负值呢根本就不是我们这个问题 的一个解，根本就不是一个解，所以呢我们就还没有 找到这个问题的这个多面体的上面的一个顶点的。 所以现在的问题就是我们怎么才可以找到一个初始的基可行解呢？因为我们看到这个 例子里面呢发现这个不是那么简单的。 好了，其实呢我们要做呢就是引入一个人工的变量 A，所谓是人工的变量呢 就是这个变量从来没有在我们这个问题里面出现过的，跟其他变量一样 我们也要求呢这个人工的变量 A 呢是非负的。 好了，我们就可以把这个 A 呢随便的加到我们的不等式里面，然后当然呢我们也会 像从前一样引入了这个松弛的变量，就等到我们就可以拿到下面这个等式了。 但是，除了这个之外呢我们也需要引入一个新的目标函数。 我们这个目标函数呢就是 -A。 如果大家还记得呢，我们现在是做最大化的优化的。 要把一个 -A 最大化呢，其实就是把 A 的值呢 最小化。 好了，有了这个之后，但是呢我们还是 我们的等式还是没有满足我们的基可行解这个形式的，然后我们可以 怎么做呢？我们就可以看看非这个目标函数这一行，就是看看下面这三行。 我们选取其中一行，选取哪一行呢？就是这个常数值除以 A 这个系数，<br>它的比值为最小的值这一行。 如果我们选取第一行呢，我们得到的就是 4这个比值，这个呢是 -5，这个是 -1，所以呢我们就应该选取第二行了。 选取这一行之后呢我们就需要做一个转轴这个操作，就是把 A 这个变量呢调到这个左手边，把s2调到这个右手边，我们得到下面 这个等式的，我们的意思呢就是希望把A由一个 非基的变量变为一个基的变量。 好了，做了这个改写之后呢我们还需要做另外一点，还有 一个问题。 就是为什么我们要选取一个常数值除以 A 的系数 最小的值的这一行来做这个转轴的操作呢？我希望大家可以去想一下。 好了，我们改写之后呢，我们还是需要把 A在其他地方出现的地方做一个替换，然后呢 A才会正式的变成一个基变量的，所以我们做了这个替换之后呢 这个就是我们现在的等式的情况了。 但是我们当然明白呢，我们现在的等式呢跟我们原来的问题是等价的。 好了，但是呢这个新的等式呢它是已经满足了我们的 基可行解的这个形式的。 为什么？除了这个目标函数这一行呢我们发现 所有其他行的常数呢都是非负的，而且呢我们也有一批的非基的变量只会出现在右手边。 另外一批就是基变量只会出现在等号的 左手边，所以我们就可以利用这个基可行解的形式，求到一个基可行解了。 这个基可行解，就是分别把所有的非基变量变为赋值为 0，然后所有的基变量都赋值给它右手边的这个常数， 然后我们也可以看到它的目标函数的值是-5 的，这个是没问题的。 好了，有了这个之后，我们已经到了我们这个新的问题一个顶点，所以呢我们就可以应用我们这个 刚才提过这个单纯型的这个算法，然后就为这个问题呢求这个最优这个解。 好了，我们调用了这个单纯形这个算法之后呢，这个就是我们的结果。 有了这个结果呢就非常好了。 为什么呢？我们发现我们得到的这个最优这个解，里面是 A 是等于 0 的。 A 是等于 0 是代表什么呢？就是说我们所有有A 的地方呢都可以放 0 这个值在里面。 放 A 如果为 0 的话，我们原来这三行的等式呢就是跟我们原来的问题的等式呢是等价的。 就是说呢因为我们有一个解是 A 为 0，就是说我们原来的问题呢 也是有解的，就是我们原来的问题呢是可行的。 有了这个之后呢我们就可以把 在这三行里面的 A 这个项呢把它移除，移除之后呢我们就出了这三行的 等式，我刚才已经讲过了，这三行的等式是跟我们原来的等式是等价的，而且呢 有一个好处，如果大家看清楚呢，我们发现这三行是满足了我们基可行解的这个形式的一个要求的。 就是我们有非基的变量，也有基的变量 最重要就是所有常数都是非负的。 但是当然，大家不要忘记我们原来，我们要解决这个问题的，原来的目标函数。 原来的目标函数呢，有可能它的在等式的右手边用的 变量呢，不是我们现在的非基变量，所以我们就需要利用下面的等式呢 做这个替换。 然后呢，把我们这个目标函数这一行里面右手边所有的 变量呢都是我们上面的非基变量。 那然后，我们就成功地为了我们原来的问题找到一个初始的基可行解的形式了。 好了，现在我们就真的可以去解释我们这个单纯形这个算法了。 首先就是我们给定就是一个以等式形式出现一个线性的规划问题。 其实我们单纯形这个算法呢，是分为两个阶段的。 第一阶段呢，其实我们要测试、 要检查就是我们原来这个问题是否可以给满足的。 可以给满足的话，我们才去尝试把它最优的解决去找出来。 我们怎么去检查我们原来的问题可否可满足呢？<br>刚才已经看过就是，我们首先要引入一个人工的变量 就是在我们问题里面没有出现过一个变量。 然后呢，我们也要引入一个假的，新的目标函数就是负A，就是它意思我要把这个负A最大化， 其实就是把这个A最小化，然后呢？我们可以通过这个转轴的 这个操作呢，把我们的等式变为一个初始的基可行解的一个形式。 然后呢，我们就可以应用我们 之前讲过这个单纯形这个算法呢，把这个负A最大化了。 好了，找了这个最优的解出来之后，如果我们发现我们的目标函数的值是大于0的话 就怎么样呢？原来我们就可以结论呢，就是我们原来这个问题呢<br>是不可以满足的，因为它的最优的一个解呢 这个A最小的值，我们最小的值也不是0的。 就是说，我们原来这个问题的等式是不可以满足的。 如果这个我们目标函数为0，就是代表我们原来的问题，它们是可以满足的。 有了这个之后，那我们就可以进入我们的这个 这个算法的第二个阶段，就是尝试把这个问题最优的解找出来。 我们首先呢就需要把我们这个刚才引入这个人工变量把它移除。 移除了之后，我们还需要把我们 原来这个问题这个目标函数里面的要用这个非基变量去改写，而且表达出来。 然后呢，我们已经保证了我们新的等式是会满足这个 基可行解这个形式的，然后我们就可以再调用这个 单纯形这个算法为我们问题，去为这个最大化的目标函数值求解了。 这个就是我们两个阶段的单纯形这个算法。 其实呢，除了这个单纯形这个算法之外呢，还有其他的 我们可以解决这个线性规划问题的算法的。 其中一个比较有名就是一个内点法。 这个内点法呢，其实呢，我们要特别地提两个内点法的算法，第一个呢 就是Khachiyan它的椭圆的算法，这个是比较特别，就是 它就是提出第一个可以在多项式时间之内 之内，这个时间复杂性提出来的这个 算法呢，可以去把线性规划问题去解决的。 另外一个就 Karmarkar提出的这个内点的算法。 这个算法比较特别呢，就是因为这个第一个比较实用的一个可以解决线性规划<br>问题一个内点法的算法来的。 其实呢，在现代的这个商业的线性规划的求解区里面呢，其实都 肯定有实现这个不同的内点法来帮助去解决这个线性规划的问题。 这个内点法，有一个最大的好处呢，就是它对于处理非常大型的<br>线性规划问题呢？它比我们刚才介绍的这个 单纯形的算法是效率高非常多的。 但是呢这个内点法就很少应用到我们离散优化里面的，因为在离散优化问题里面我们 需要解决的情景呢，通常都是一批的我们叫混合整数线性规划问题。 这个题目呢，就是我们下一节课需要介绍的。 好了，有些人可能会问，这个线性规划问题呢 其实是一个实数的一个问题，我们是搞这个离散优化问题的，为什么我们要 对线性规划问题呢有兴趣呢？为什么我们要 学这个题目呢？其实呢，线性规划问题应该是现代最通用的优化问题。 就是第一个现代最通用的问题优化的一个框架。 它是在第二次世界大战之后开发起来的，虽然它只可以为 这个实数的约束求解，而且只是为这个线性的约束求解，但是它其实的应用也挺的。 包括这个网络流这个问题，或者是最短的路径的问题。 但是最重要呢，这个线性规划呢，也是解决线性规划的算法呢 也是可以作为我们解决这个混合整数规划问题的 求解的算法的一个基础，其实这个混合整数规划呢就是 一种的离散优化的技术来的，所以我们对这个线性规划求解的算法我们是有兴趣的。 好了，我们可以来一个总结：就是我们 介绍了一个线性规划问题，是一类非常重要的优化问题。 我们在这一节课里面也介绍了这个单纯形这个算法。 这个单纯形这个算法呢，其实在实际应用当中，其实当今其中一个最重要的这个 解决线性规划问题一个算法。 虽然它的最差的情况之下呢，它的时间复杂度就是 指数级的，但是在实际的应用当中我们从来 对有意义的线性规划问题呢，我们 从未遇到过这样子的复杂度的，所以它平常用起来呢，它的效率也是非常高的。 而且呢，最重要我们为什么要学这个单纯形这个算法呢？因为这个单纯形的这个算法 可以作为我们将会介绍这个混合整数规划问题的求解一个算法的一个基础。 我们刚才也提到过，有其他线性规划的算法，包括这个刚才提到过的这个内点法。 其实呢，线性规划这一方面呢我们还有 更多更多需要学习的东西，包括我们没有时间 提到过的对偶性、 互补松驰性 对偶单纯形的算法，原始对偶单纯行的算法。 但是呢，我们都没有 时间在这些题目上面花时间了。
