运筹学破圈法例题及解题过程
大家好，我们是运球学物流六组，今天讲解的是求最小支撑数的两个方法，闭圈法和破圈法。下面是立体。先讲第一个破圈法，破圈法他的原则是任任区一个圈，然后去掉圈中最长边 到没有圈，然后先看这个三角形，它的最长边是五，然后去掉五， 然后这个地方就不构成一个圈，然后接下来看这个地方，这个也是一个三角形，然后去掉他的最长边疤， 然后他这他这还是一个还是一个联通图，去掉这这条边 之后发现这里还是一个圈，然后继续去掉那个最长边期， 然后这个地方就不构成一个圈，然后接下来看这边，然后去能去掉最长边无， 然后这个就形成了一个最小支撑数。 最后的结果就是这样。本次讲解就到这里，感谢大家观看。
粉丝991获赞7637
相关视频
24:24查看AI文稿AI文稿同学们大家好，欢迎大家一起来学习并筹学，今天我们要学习的内容是图语网络一， 主要包括图与网络的基本概念，以及我们的最小支撑数，还有我们如何用破拳法和 b 拳法去求解最小支撑数。 那么今天会涉及到的图与网络相关概念会比较多，但是呢都相对的比较简单，也希望同学们能够耐心的看下去。我们现在看一下什么叫做图， 所谓图，它其实就是点与点之间的一个连线来构成的，那它可以分为无相图和有相图，顾名思义，什么叫做无相图？也就说我们点 点与点之间的一个连线，他是没有方向的，那么有像图呢？有像图连接点与点之间的一个连线，他是有方向的， 那么我们把这种没有方向也说我们不带箭头的连线，然后我们看它称为叫做边，那么我们的无相图就是由点和边构成， 那有像图呢？我们把这种带箭头的连线，我们给它称之为叫无，那么有像图就是由点加无来构成， 那如何来表示呢？我们把无相图用一个大写字母 g 来表示 g 呢？它就是由 v 和 e 来构成，我们的 v 就代表是我们的点击和我们的 e 就代表是我们的边 结合。那如何来表示我们的一条边呢？比如说我们的一一这条边啊，一一这条边呢？我们就可以用一个哎 v 一 v 二来表示对不对？那我们用方括号 v 一 v 二，再用方括号把它括起来， 那么呢有象图如何来表示呢？有象图我们一般用大写字母 d 来表示，那它就是由 v 和 a 来构成的， 那么我们这里的 v 还是一样的，是我们的点集合，那么的 a 呢？就是我们的无集合。 那这个时候如何来表示一条弧呢？比如说我们的弧 a 一，注意这个时候是有箭头，有方向，对不对？我们可以看到 a 一是由谁指向谁，是不是有 v 二 指向 v 一，那这个时候我们 a 一的应该用 v 二，哎，指向 v 一用圆括号来表示，圆括号的一个，哎， 第一个位置代表是起点湖的起点，第二个位置代表是我们的湖的终点。好，那么我们今天主要一个概念呢，主要先讲一下无相图的相关概念，有相图的一些性质特点啊，我们在后面来进行讲解， 我们先看一下无相图中一个，嗯，概念叫做环。什么叫做环呢？也就说我们的一个边，它的两个端点都相同，我们就给它称为叫环。比如说我们 有一条边，一八这条边，哎，我们发现他的起点是唯一，终点也是唯一，这样我们就给他称之为叫一个环。好，那我们再来看一个叫多重边，或者叫平行边，什么意思呢？就说我们两个端点之间， 他有超过一条的边，我们就给他称为叫多重边。比如说啊，我们这里有两个端点， v 一和 v 二， v 一和 v 二之间，它有两条边，一个是一四，一个是一五，那这个时候呢，我们就称一四一五就为多重边，或者叫平行边。 哎，为什么要说环和多重边呢？因为如果我们一个图中既没有环， 也没有多重编，那么我们就称这样的图为简单图啊。那么以后呢，我们在实际解题的过程中，遇到的也大多都是简单图啊。 好，我们再来看什么叫做练的一个概念，由我们的点边这样一个交错形成的序列，我们就可以称为一个练。比如说，哎，唯一 我们的点一一边点 v 二，我们的点哎一四，我们的边，哎 v 四，我们的点一六，我们的边，哎 v 三点 一七边 v 五点，这样我们可以给它形成一条链。哎，我们从图中表示来看，哎，从 v 一到哎， v 二，经过 v 一，经过 v 一到 v 二，然后经过 v 四到 v 四，然后经过 v 六到 v 三，经过 v 七到 v 五，这样我们给它形成一条列。 那我们在什么叫做书等念呢？就说我们所经过，我们因为会经过点，对不对？要经过点和边，我们经过了这些点， 那么他都不相同的话，我们就给他称为叫一条初等恋。哎，我们可以看到我们上面这个例子，他是不是就是一条初等恋，对吧？那他所经过的点都不相同。 好，然后我们再来看，什么叫做圈呢？就是我们的一个起点和终点相 同的面，我们就给他称为叫做圈。比如说啊，我们这里的起点是哎 v 一，然后我们看经过了一一到达 v 二，经过一四，到达 v 四，经过一六到达 v 三，最后经过一二就到达 v 一，发现它的起点和终点都是 v 一，对不对？哎， 我们就称这样的脸为圈。比如说，哎，我们在图中给它画出来啊，从 v 一 到 v 二到 v 四到 v 三，再回到 v 一，这样我们就给它形成一个圈。哎，我们在图中是不是可以看到很多的圈，或者是 v 一， 哎， v 一， v 二， v 三，再到 v 一是不是也是一个圈哎？ v 二 v 四， v 三， v 二，是不是也是一个圈？有很多的圈，对吧？ 好，我们再来看一个概念，联通图。什么叫做联通图呢？就说我们任意两点之间至少有一条链 哎，比如说我们在这个图中，我们给他增加一个点，比如说我们给他增加一个点 v 六， 哎， v 六我就给它放在这一个孤立的点，我们发现 v 六是不是就和 v 五 以及和其他各个点都不能形成恋啊？对不对？这个时候他就不能和他形成恋，所以这个时候呢，我们就给他称为叫做不联通的图。 而我们上面啊，你看 v 上面这个图中，我们的 v 一、 v 二， v 三、 v 四、 v 五任意两点之间是不是都至少有一条链啊？ v 一到 v 二之间 啊，他至少有一条链，对吧？那么他也有其他的链，那么我们 v 一到 v 五之间是不是也有链，对吧？那这样图我们就称为叫做联通图。好， 我们了解到图的概念，我们再来了解数的概念，什么叫做数呢？哎，就是我们一个没有圈，并且它是一个联通的图，我们就称为叫做数 啊。那么我们如何去判定哎，我们的一个数呢？以及说我们或者说我们数的一个性质是什么样的呢？我们这里主要讲三个充分必要条件。第一个就说，哎，如果是一个无圈的图，并且 他的一个边数是等于他的顶点数减一，这样我们就可以判定他是数，也或者说我们数的一个性质。第二呢，就是我们说他是一个联通图， 并且一样的它的一个边数还是等于它的顶点数减一啊。另外第三个星字或者第三一个判定，就是我们说任意两个顶点之间有且仅有一条链， 哎，这就是我们经常会用到的，我们经常会用到的，还是最常用的是我们的一和二啊。好，我们有了数的概念，我们再来看什么叫做生成数，或者我们叫做 或者可以叫做支撑数啊？就说把我们图迹上的所有顶点， 把它所有的顶点用最少的边给它连接起来的竖，我们就称为生成竖，哎，比如说我们这里的图迹， 它有几个顶点，有 v 一、 v 二、 v 三、 v 四、 v 五、 v 六，六个顶点，对不对？哎，那我们要把它这六个顶点给它连接起来， 记住一注意要用最少的边给他连接起来，哎，我们看一看到这里的，比如说我们这样的给他连接起来，还有一个生成数，哎，或者说我们这样一个生成数，他的生成数有很多啊，这就举了两个例子，哎，我们注意来看一下这些生成数有什么特点啊？我们看 生成数一，哎，是不是所有顶点都在为一为二、为三、为四、为五、为六，都把它连接起来，对吧？这是他们两个共性。那我们看一下生成数一中他有多少条边啊？一条、两条、三条、四条、五条边，对吧？ 哎，顶点数为六，哎，顶点数，那么他的一个边数是不是为五？你说我们顶点数减去一，就是我们的一个边数，对不对？你再看生成数二中呢？ 是不是也是有五条边？一二三四五，对吧？刚好其实这就是我们数的一个性质啊，你说我们后面在判断的时候，哎，你判断他是不是是否形成了一个生成数，那么你可以继续他的一个性质去 判断。好，那么我们如何去找我们的生成数呢？那么这里就主要讲两个方法，一个是破圈法，第二个是 b 圈法， 什么叫做破圈法呢？哎，我们用破圈法来求支撑数，说我们要认取一个圈， 那么从这个圈中给他去掉一条边，那么他肯定就不勾成一个圈了，对吧？那么依次不断的重复我们上述的一个步骤，直到我们最后不喊圈那为止， 哎，比如说我们这里的，我们以这个图为例啊，我们来求用破圈法来求 由它的一个支撑数，我们先把它哎这样画出来任取一个圈，我们看一下任取一个圈，哎，我们比如说我们的 v 一 v 三 v 二，是不是这里有一个圈，哎，它有一个圈，我们把这个圈中任意去掉一条边，比如说我们可能把它 v 二 v 三给它去掉。好， 然后我们再要重复上述步骤，对不对？我们再取一个圈，是不是有一个为一为三、为四为二又是一个圈，那我们在这个圈中从去掉他的一条边，比如说我们去掉为三为四这条边， 好，这个时候是不是还有边啊？还有圈，哎，比如说为一为三、为五、为四为二是不是也是个圈？ 那我们在这个圈中给它去掉一条边，比如说我们去掉为四为五，好，然后我们最后看是不是还有一个圈，然后我们再从这个圈中又去掉一条边，哎，我们任意去掉一条边， 好，我们重复不断的重复，我们发现这个时候还有没有圈 是没有圈的，我们来验证一下，这个时候我们的边数是否等于我们的点数，顶点数减一有几个顶点，六个顶点，六个顶点减一五条边是不是刚好，哎，说明这个时候我们就得到了他的支撑数 好，然后我们再来看一下什么叫做 b 圈法呢？我们的 b 圈法啊，还是从从我们的图中 先任意的取一条边，然后再找与我们的已经取得这条边翼不构成圈的边一界啊。我们先，哎，最开始找的是 ei， 然后我们来找 不与一挨构成圈的边一界，然后再找不与我们的一挨一界构成边的一 k， 哎，就是这样如此的反复进行， 直到我们不能进行维持，哎，什么个意思呢？我们还是一样的通过一个图式来讲解 啊，我们从图中任取一条边，哎，比如说我们就取了一条边 v v 二，哎，比如说我们取 取这条边，好，然后正再找，在剩下的边中找边，找到了边，注意要不能和我们一找到的边形成圈，比如说我们找一个 v 二 v 三，可以吧？哎，这样 好，我们依次再从剩下的边中再去依次去找边，注意新添加的边一定不能和已找到的边形成圈，哎，那么比如说我们能不能找 v 三 v 四，可以吧？哎，我们找一个 v 三 v 四， 好，依次再找，再从剩下的边中再找。找边的时候一定不能形成圈啊，比如说 v 二和 v 四是不是就不能找？因为如果你找了 v 二 v 四，是不是这里就形成一个圈了，对吧？哎， 那我们看为四为五可以吧？好，为四为五，哎，再走，哎，为五为六可以吧？ 哎，注意，我们这个时候找的时候，你一定要将我们所有的顶点都要连接起来，并且也不能形成圈，对不对？好，最后我们再来验证一下我们有没有形成，我们已经找到了所有的， 连接到所有的顶点，对不对？然后我们看一下我们的边数是不是等于我们的顶点数减去一一二三四五，刚好说明我们也得到了他的一个支撑数，是不是很简单？好， 那么我们了解了支撑数之后呢，我们又要找一个最小支撑 数。我们在讲最小支撑数之前啊，我们先来了解一个网络的概念， 什么叫做网络呢？哎，其实很简单，给我们的一个图中他的每一条边都给他赋予一个数值，那么我们给他赋予的这个数值呢？我们就给他称为全， 那么对于这个负全的图呢，我们就给他称为叫做网络，比如说我们把这个图中我们给他每条边都加上数值， 这个时候我们就给他称为叫做网络了啊，那么我们这个边上这些数值呢，我们就给他称为叫做全。好，这就是我们的一个网络。有了网络 我们再来看最小支撑数，说如果我们的支撑数的全，哎，就是我们支撑数所有编的全支和 他是刚好是我们图记，因为我刚才讲了，我们对一个图他有哎，不止一个支撑数，对不对？他有很多个支撑数，可能会存在，可能会存在很多个支撑数， 那么最小支撑数呢？就是我们图记他所有支撑数中全最小的那一个啊，这个时候我们就给他称为最小支撑数。 好，那么我们又如何去求解我们的最小支撑数呢？我们一样的 还是用破圈法以及 b 圈法。我们先来看什么叫做破圈法啊？我们如何用破圈法来求解最小支撑数， 哎，一样的还是任取一个圈，注意，这个时候我们要去掉圈中全最大的那个边，然后一样的重复上述步骤，直到不含圈为止。哎，我们还是一样的举个例子， 那么我们先把它表示出来啊，我们任取一个圈，我们一样的取为一为三为二， 然后要干嘛要去掉这个圈中全最大的边，我们看为一为三为二，这个圈中他们的全分别是五 一、六，对不对？最大的是不是应该是六？这条边也是 v 一 v 二，所以我们要把它给去掉。好，接着我们再来找圈，哎，我们的 v 二 v 三 v 四，是不是又是一个圈？ 那在这一个圈中他们全最大的是应该是 v 三 v 四，这条边他的权重为七，全为七，那我们给他去掉， 依次再找。哎，这个时候我们是不是又发现一个圈， v 二 v 三 v 五 v 四， 这个时候我们来找这个圈中的全最大的边，是不是 v 二 v 四，把我们把它去掉。好，我们再看还有没有圈，是不是还有，哎，有一个 v 四 v 五 v 六，一样的，我们来找全最大的边，全最大的边是不是就是四？哎，刚好我们发现这里有两条边，一个是 v 四 v 六，还有我们 v 五 v 六这两条边，他们的全都最大， 这个时候怎么办呢？哎，其实我们就任选一条边就可以了啊，比如说我们把 v 四 v 六给去掉了， 注意，我们就通过这个题呢，大家可以思考一下，我们的最小支撑数，它是不是可能不为一，对不对，它的形状可能不为一， 比如说我们刚才去掉了，假如说我们去掉 v 五 v 六，是不是他又是另外一个形状了，对吧？但是我们最小支撑数他所有编的全 之和一定是一样的，哎，这个一定是一样的啊，用最小支撑数的全一定是固定的。 好，然后我们再来看用破圈啊，用 b 圈法来求最小支撑数呢，哎，从我们图记中 选一条全最小的边，哎，先从他所有权重选一条最小的边， 然后在我们以后的每一个步骤中，总是从与已知边不构成圈的未选边中选一条，哎，选最小的边直到不能进行为止，还是一样的啊。我们还是通过一个图例 来讲解，我们要先从图记中选一条全最小的边，我们看一下整个图中 全最小的是多少，是不应该是我们了 v 二 v 三最小它的全为一，对吧，那我们先把它给选出来， v 二 v 三给选出来， 接着我们再于再在剩下没有选的这些边中来找全最小的， 注意，找的剩下的全最小的边还是不能与我们已经选的边构成圈啊，我们来看剩下的边中没有找到边中全最小的是谁，这边是我们的 v 三 v 五，他的圈为二， 是最小，对吧？那我们选选出来啊，我们再选，再在剩下的边中选全最小的，这个时候是不是应该是三，也是我们的 v 四 v 五？好，我们来选出来， 一定要注意啊，我们选的边不能与已经选的边形成圈， 好，接着我们再选我们剩下的边中全最小的，这个时候是不是剩下等于是四， 哎，这时候我们有两条 v 四 v 六或者 v 五 v 六，哎，就是说我们如果选 v 四 v 六是不不会和它形成圈？那 v 五 v 六是不是也不会和它形成圈？那这个时候我们任选一条就可以了，比如说我们选 v 四和 v 六，好， 然后我们再在身下没有选的边中来找全最小的，这个时候是不是是 v 五 v 六最小任务了？四，对吧？但是能不能选？ 如果假如说我们选了选了的话，是不是他就会和哎，就会形成一个圈呐，这里对不对？说明我们这个时候哎 v 五 v 六是不能选了啊，那我们再在剩下的边中选一个全中最小的，这个时候是不是应该是五 五有两条边，到底选哪一条呢？哎，我们一样的来看， v 二 v 四可不可以选？ 假如我们选了 v r v 四是不是又形成圈了，对吧？说明我们的 v r v 四也不能选，哎，那我们来看 v 一 v 三能不能 能选呢？ v 一 v 三选呢？它会不会形成圈？是并不会形成圈啊，对吧？说明我们的哎 v 一 v 三可以把它选出来。好， 在这个时候呢，那我们其实可以不再做了，因为我们的边数其实已经刚好等于我们的点数减一了， 说明我们已得到一个最小支撑数吗？哎，当然你也可以把它选完，那我们来看吧，比如说你来看 v 一 v 二，再再剩下的编动是不是只有两条，一个是 v 一 v 二，一个是 v 三 v 四，我们看 v 一 v 二能不能选， 如果选了 v 一 v 二的话，是不是就会形成一个圈，对吧？说明我们的 v 一 v 二不能选，我们再看 v 三 v 四能不能选， v 三 v 四选了的话是不是同样也会形成圈， v 三 v 四也不能选啊？好，这样呢，我们要通过 b 圈法求得了我们的最小支撑数。好，以上呢，就是我们今天的所有内容，谢谢大家。
130睿智小课堂
04:59查看AI文稿AI文稿看看能不能啊，能不能把它变成三层的一个关系啊，就是我们把 b 一和第一去掉啊，我们取这个 a 和这个 c 一、 c 二、 c 三和 e 这样的一个关系啊。那么这个我们应该怎么做呢？啊？我们应该怎么做呢？比如说我们啊，我们来看 首先我取最短吗？那么我们算从 a 到 c 一这一块最短的是多少啊？ a 到 c 一的这一块啊，我们给他简化哦，我们争取给他简化成什么？ c 一 c 二 c 三，然后这边是一啊。我们先来看 a 到 c 一的这一块啊，是什么样的？最短是多少？我们来看啊，如果走 b 一的话，这个是十二。然后呢，如果走下面的话，这个应该是九对吧？是不是一个十二一个九啊，对吧，那么我们应该取哪个是？ 应该取九啊，对吧，我是不是最短的是九啊，对吧？那么同样的我 a 到 c 二呢？我们来看一下啊， a 到 c 二，这个是十一对吧？这块是十一，这块也是十一对不对？那么它应该是多少？就是十一对吧。那么我们再到 c 三呢？ 这个五，这个是九八对吧？这个是九，下面是十三。那我取取哪个？取小的呀，最短吗？我是不是取九啊，对吧？同样的。那么我们 c 一到一呢？我们来看啊， c 一到一这个是九，这个呢？是十四。那我们应该取哪个？取九啊，对吧，我们是不是取九啊？ 然后 c 二呢？ c 二应该是多少？六，这个是九。这个呢？这个是十一吧，对吧？六加五十一嘛，那应该我还是去九对吧？ 还是取九。那 c 三呢？十十四，那应该取多少？十呗，对吧，是不是取十啊， 这个是不是就简单了？到这大家应该知道吧，就是说我们首先不直接到一，我到其中的这个啊，这一层啊，我们都到 c 一 c 二 c 三的这一层啊。那么到这之后你再看是不是就比较简单了，对不对？是不是就比较简单了？ 因为啥？这很明显能看出来。你这 a 到一哪个最快啊？是不是上面最快啊？十八吗？对吧？九加九等十八呀，是不是他最快啊，对吧？那么我直接就选出来了，是不是很简单的这道题啊。这种方法其实很简单啊，最短入境啊。然后我们再再做一个啊，再做一个。 我们再做一道题啊。我们来看一下啊，一样的啊。说已知啊。网络图各路段的这个段路线所需的费用如下 所设图中，甲线和乙线上的数字分别代表相应的点的有关的费用。从甲线到乙线的最小的费用啊。问你最小的费用 啊，他还问你路线有几条，然后费用是多少对吧？那可能会啊，可能会有多条对吧？可能会有多条。那么我们来看一下吧。那么我们这他是这是几层啊？一层两层，三层，四层，五层，六层七层 对吧？他是不是七层啊，对不对？这个层次很多对吧？那么我们先简化呗，对吧？我们先简化一下呗。那我们怎么简化啊？ 我们应该讲话到哪啊？先讲话到哪。我是不是可以讲话到这啊，对吧？我省一层吧。我先先讲话到这吧，对吧？先讲话到这啊，讲话到这到这啊，到这。我们先写啊，到这应该是多少啊？应该是你算 你从这到这这是二一四，这是七。这个呢？三二四，这个是几啊？这个应该是九呗。那我这块是不是应该是七比较好啊，对吧？对吧，我这个是不是可以选七啊，这条线 对吧？可以选七啊。那么到这个点呢？这个点我们看三二五，这个是多少啊？这个是嗯，十对吧？十对不对？那么呢？这个呢？一五呢？这个就是六啊。然后这呢？这个三， 这个三三二，这个是八对吧？这个二一五，这个应该也是八，那个三三二，这也是八二二二。哎，这条线是不是比较短 啊，这个是多少？是六对吧？这个是六啊。那我们看这个点呢，这个点应该是多少？这个点这个三三，这个是十。那这个呢？二二四。哎，这个是不是最小啊？是吧，二二四。这应该是多少？是八 对吧？这个就是七六八，这个是二十四。是到这对吧？是这样的一个情况吗？对吧？是到这了啊。然后呢，我们下一个，我们把后面的这个算出来啊，我们往中间挤吗？对吧，前面推一个，后面推一个啊，然后我们看这个点啊，看这个点， 这个点啊，三加一加七是十一，三加二加七是十二，对吧？那应该是哪个？是不是十一啊，对吧，是不是这条线啊，对吧，这条线啊。然后我们再看这个点啊，这个点哪个能进来啊？
14叨叨张讲软考
30:20
10:42查看AI文稿AI文稿哈喽，同学们大家好啊，我们今天接着学习运筹，学运输问题中的产销不平衡问题。嗯，在实际生活当中，产销平衡其实是比较难达到的状态，多数情况下都是产量和销量是不不相等的啊，下面我们看一下这个这道具体例子我们是怎么样去操作的。 嗯，正常来说，我们拿到一道嗯，一题，嗯，这种产运输问题的题目，我们首先要去判断他的产量和销量是否相等，怎么判断呢？就是把产量的核相加，销量的核相加，然后看一下他们的值是不是相等，我们加一下三七，加三四加二九等于多少？等于一百， 不要问我怎么算那么快啊，你们应该也可以的，因为我拿计算器的二三加十六加二五加十九等于，这边是八十三，两边差相等吗？不相等是不是很显然差十七是不是？这是我们一道 到非常典型的产销不平衡问题啊。嗯，也就说我们现在怎么样子啊？我们产地 a 一 a 二 a 三的产量要多于销的 b 一 b 二， b 三 b 四的各各个销的的销量，所以我们要怎么样处理呢？此时我们就需要需要虚拟一个销的 b 五，然后我给大家操作一下， ok， 哎，不要现场画一下啊， 你们考试要自己画了，首先就要先判断，都要这么画。嗯， 打横都没变化，就打竖时候发生变化了，我们就要把四个小弟变成五个小弟，自己虚拟添加一列一列 b 二 b 三 b 四 b 五， bb 二 b 三， b 四 b 五，你看原先是不是没有 b 五的，我们现在给它虚拟这个消 d b 五，为什么呢？因为我们现在是产销不平衡，销量小于产量，所以我们增加个消 d， 把钱全部写完再讲啊。产量、产地， 肖弟，这些地方都是抄到照抄就行。 a 一、 a 二、 a 三，我写的比较快，所以说字可能有点丑。三七二十二九，这一百，为什么呢？因为我们刚刚李佳加了一百，对不对？ 十九，嗯，这里现，这里还以及这里运这里的，嗯，这里的销，我们虚拟的销。 d、 b 五的销量以及以及它的各个单位 的产，那个运，单位运价，我们等下等下再告诉大家怎么调，先把能抄的地方先抄完。 现啊，现在我们已经把题目所给的内容我们就抄上了，现在我们现在还有几个空没填，那这几空怎么填呢？啊？非常简单 啊，我们就只需要加那个像，就是就是这呢，就是这个 b 五这里的销量呢，我们就是拿总产量减去总销量，也就是我们刚求出来一百，减去这里八十三，减去多少？十七，对不对？ 这时期就是我们要把这个时期就这个值，我们要把它写到这个位置，这就是我们要填的是这个位置。然后呢，他，他这里单位应该都填多少呢？全部都设为零，全部设为零就行 啊，很简单吧，就是这么处理的，为什么呢？为什么全部设为零呢？有同学就要问，因为我们这个 b 五这个销地啊，是我们虚设的，他并不是实际存在的，比如我们这些，比如我们这些产地的产量去运到，如果这个我们我们虚设的这个销地 话，其实实在实际实际情况下，其实是在原地没有运出去的，他只是我们虚设的一个销地，其实没有运出去的，也就是没有产生任何的运价，能理解吗？这是我们虚设的一个东西而已，其实就是放在原地了，原地保存了，哎呀， 然后啊，就是这么处理的，那其实这种情况是我们产量大于销量情况，那么销量大于产量怎么做呢？很简单啊。嗯，比如如果我们这是八三，这是一百怎么办？那我们就只要虚假虚虚设一个产地， a 四这里补一 十七，能理解吗？然后那个运价全部填为零，这么大，非常简单，非常同理的。 嗯，这就是产销不平衡的初始调，初始那个呃，产销不平衡问题的这个呃运输模型该怎么建立？就是这么建立的 后，下面该怎么做？就是我前面三个视频讲的第一步先干嘛？求他的初始调运方案。用什么方法？用福格尔法，西北角法或者。嗯，最小元素法，我一般推荐福格尔法，他是最快的。然后，嗯，考试要求用，嗯，那个也可以用最小元素法，但是那个 西北教法一定不要用，除非你考试特别要求让你考这个。然后第二步干嘛？然后进行检的检验，然后进，然后检，如果检验书不通过的话，我们就进行检的调整。就是我们上个三三，前面三个视频所讲的就非常，我给大家，我给大家，嗯， 算个初始教育方案吧，因为初始教算出去，初始教育方案里面可能会出现你们会出现一点错误。嗯啊，两种方法给他试一遍，第一个我们先试，嗯，福格尔法。 嗯，我这就不具体讲 force 法是什么了，因为我在前面视频已经讲过了，这就直接给大家操作了。前听这个视频的时候，前面三个视频一定要先听完，因为我视频是有那个进阶性的，这么往下延伸的。 这里是什么？这里是我们的航伐数，这是什么？这是我们的列 叶法术， 我画快点，不想让视频太长， 嗯，这长相不平的，嗯，大家非常的经常有个疑惑的就是，嗯，很多人就疑问这个零呢，到底是先考虑还是最后考虑呢？ 我给大家给给大家一个结论，就是，如果你用福格尔法求最小，嗯，求初始调运方案的时候，这个零呢？刚开始就可以直接考虑，但是如果你用最小元素法求初始调运方案时，你这个零运价要必须要最后考虑，就是非常，就是你做多就必须要知道。这个我已经给大家讲结论了， 因为很多人私信要问我这个问题，那我们先用什么啊？弗格尔法对不对？说这个零呢？我们刚开始就要考虑，不是最后考虑， 呃，我们要找出呃最小运加和次小运加，然后把他们相减，求出他的法数，最小运加是多少零，对不对？这个零次小运加是什么？看一下是十一，随着这题十一减零是十一，下一个是什么？十四减零，十四像什么？这是十二减零至十二， 这是四，我就直接写了四五一。 然后呢，从法术里面找到最大的，找最大的是这个，这是十四，从中选出最小的那个去填最小。什么是这个零对不对？这个零对不对？我们在这里填，填多少呢？打横打竖看求出找三找一，得到一个三四个十七，从中选出最小那个。我在前面视频都讲过了，我就比较快了， 说自己选十七，选完十七后怎么办？把这个十七划掉这里减十七，变深色十七，然后继续求法数，这么一四六六算下去，好吧，我就不给他继续求完了，好吧。哦，因为不想让视频下太讲解，因为这都在前面，前面几个视频讲过副歌法了，下面我们就给他讲最小元素法。 最小元素法我说的是也是容易出，容易出错的地方，就在这里，但很多同学问我这个灵韵家到底什么时候开始考虑？我告你给讲过结论了是吧？在符合法里面你刚开始要考虑，但是在最小元素符法里面，这个灵韵家必须要最后考虑 最好元素法什么意思啊？我们要选择最小的元素开始先填对不对？但是你发现这个零肯定是最小对不对？很多人都会非常疑惑，就会直接在上面填了，但是我非常强调最小元素法这个零运加 必须必须最后考虑，所以说你刚开始要无视这个零零运价。从其他地方看填最小是哪个，我看一下应该是十一吧，十一，这填十六，填完十六，这十六被去掉了还是什么？这还剩下二十一， 那下下个是什么？下个应该是十二，十二，二十五画掉剩四，我换红笔吧，清楚点。然后剩下什么？十二后面更小，十三对不对？十三更小，这里填个四， 去掉变十五，下一什么？这边零零先不要考虑，这回列了，像十上面的是十是十四对不对？十四应该填十五，把这去掉这边十九。 好，现在是还剩什么？二三，十八，零零，对不对？选哪个？包选零二选十八，这个填十九， 去掉剩四，现在个十三和零啊，现在还有二三和零，选哪个？选二三，怎么去掉现在什么十七？现在只剩下，现在只剩下这一个零，这一个零，这一个零格了，对不对？那是不是只能填这里了？还剩多少上剩个十七对不对？ 是不是又填完了？这就这是球赛，就是我们的初始调音方案，我把这些线都擦掉， 啊，就这样吧，就这样吧，啊，这就是我们处理交易方案。所以说这是我跟你讲的产销平产销不平衡的问题。这题题目怎么做？这这节课我给大家总结一下非常重要的两点，就是第一个产销不平衡的这个模型，运输模型该怎么建？就是产量和销量，他俩看一下是不是平衡 不平衡。减减去个余数，虚拟个产地或虚拟个削地。这么做第二步容易出错点，就在于求处处调研方案的时候，这些零运价什么时候考虑？我给大家一起给大家讲个结论了，第三遍，第四遍了啊，福格尔法刚开始就要考虑，最小元素法最后考虑。 然后下节课我们将讲解运输问题中的最大的问题，如果同学们觉得这个系列对你有帮助的话，麻烦给他给阿布主点点关注，多投币点赞，多发弹幕和评论，你们支持是我更新最大动力， 最后忙着给奥斯考研进行专业和辅导，所以更新的步频大家多多见谅。同学们有需要讲解内容可以私信告诉我，那我们下节课再见。
702胖帕，
07:55查看AI文稿AI文稿好，我们来一起看一下这段路径的计算问题。呃，入图二十七杠四说是有一批货物要从城市 s 发送到城市 t， 线条上的数字代表通过这条路径的费用。 那么运送这批货物至少需要花费多少钱？这是个典型的对联路径的计算问题。 s 出发替结束，最短路径就是从出发到终点经过很多节点。那么他最短的路径，最短的那个线路是哪一条？我们要求这个 有对讲路径问题。求对讲路径问题。当我们同学们看到这一个图的时候，往往有很多人都都被吓蒙了，这怎么做？这么做 实验它是非常简单的一个题，可以说知道原理以后，这是送飞题，我们可以联想一下啊。我们可以想象一下啊，从 s 点出发到 t 点结束，那么经过很多节点。我们可以这样来想， 呃，比方说他经过的是要去计算，是要计算每一个节点，谁就从七点出发到达某个节点的最短距离。 那么比方说一，那么 s 到一对战距离多少？然后到八这点，从 s 到八对战距离多少？从一次类推最后推到到 t 对战路径多少？那么实验在计算过程中，就是 比方说我们计算一 s 到一的最短距离多少，就把最短距离写到这一的节点上，然后意思类推八的八的最短路径多少，就是 s 到八最短路径多少。我们把这个字写到这上面， 一次类推就能得到最短路径。这个这个思想是非常简单的，也是呃，可以通过这种。呃， 我们就可以通过这种想象，就可以能够理解这个非常容易理解这个思路的，就是说从起点到某一个重点节点的最短距离， 就是前一个的节点的对战距离，然后再从前一节点到当前节点的对战距离，这样以此类推。那么好，我们就计算一下这个整个图的这个对战距离多少。我们先看从 s 到一 最远距离多少。我们看 s 到一是要有很多这个路径，从 s 直接到一，或者 s 通过二到一，或者 s 通过二三等等等等，再到一。显然我们看到从 s 到一最短路径是二十五， 但也可以从 s 一到二到一，那是四十四，肯定不是占距离。那么大家看从 s 到二占距离多少呢？意思也是意思类推，也是很简单，是二十一。 那么再看 s 到八呢？四点距离多少？那么实际上就是从这两个节点出发到八，四点距离多少？我们看 一到八有几条路径，从一可以直接到八，也可以通过七到八跟二十一也可以到八。显然从一直接到八对不对六。那么从 s 到八的最小距离多少？就是二十五加六等于多少？三十一。 那么好。那么从 s 到七等于多少呢？我们可以看从一到七，或者是从一到或者从八到七，从八到七十三，就从一到八再到七 是多少？是二十五了。那肯定是从一直接到七最短呀， 多少？就是三十六。 那么 s 到三呢，占距离多少呢？我们可以看到 啊，那么肯定是从 s 到二到三，或者从从这个二直接到三，或者从二到四到三。那显然是从二到三最短二十嘛。那么从 s 到三的最小距离是二十一，加二十等于四十一。 那么 s 到四的间距是多少呢？嗯，以此类推。那么应该是二直接到四。因为二十五吗？其他的都都比这个二十五长啊。那多少？就是三四十六。 那我再接着看。那么 s 到五五最大距离多少呢？那么就看从七三四到五 占距离多少？显然我们看四十五八，这肯定长啊。四十一啊，三到五就二十。从七到五三十五，那显然是四十一。 加二十。最短是六十一，三十六，这七十一了。那肯定是这样，最短四十一。加二十多少？是六十一。 好。那么 s 到六最短距离多少呢？就是四十六和六十一。那谁最短？那显然这八十多了。这六十一加八。那六十九。这呢？ 那肯定更更远了。而且直接到节点了，没必要再绕绕一圈到这了。那那应该什么？那四到六这样距离应该是从五节点过来。五六十一，加八六十九。 好，我们再看这个节点九。那么从这些节点到九最大距离多少呢？ s 到九的最大距离多少呢？显然可以从这个这儿过来，也可以从这儿过来。那显然从这儿到这儿，那肯定不用再到这儿了。因为那肯定不能从这儿过去。是吧？ 我直接到这就到头了是吧。那么时间就是从九呢，到九最短距离是从八和七的两个节点来看。那八到九呢，是多少？是六十四，七到九呢？是，到是八十，是九十多了。那显然是从八到九最短啊。 也就是说 s 到九，通过这最短三十一，加三十三，等于六十减六十四。好，到此为止啊。 到 t。 从 s 到 t 啊，在所有的节点我们都已经标出来了，就是 s 到所有与 t 现在接点的最短距离都有了。 s 到五十六十一， s 到六十六十九， s 到九十六十四。 上就有三个节点跟 t 相连，那么我可以直接算出来就可以了。六十四道 t， 这样六十四道 t 的距离多少？六十四加十八是八十二， 那么五道题的距离就多少呢？是六十一加二十一是也是八十二。 那么从六到 t 的距离多少？是六十九加十二 是八十一，显然八十一最短是吧。那么他最远路径就是通过 s 到二，再到三，再到五，再到六，再到 t 是最短的，它占距离是八十一。那么花费呢？就是八十一万元。同学们听懂了吗？
148知~晓~
06:00查看AI文稿AI文稿运筹学一刷而过，新的一节呢，咱们来看一下线性规划问题的数学模型。首先呢咱们先来看一下这个考点分析啊， 那么本音节课呢，他主要是出现在这个大题里面的啊，那么他是先去建立这个模型，接下来呢你再通过一些方法进行一个求解，所以呢这是大题里面的第一步啊，先去把这个模型给他建立出来，我们来看一下这个模型的组成吧， 咱们孕中学的，咱们讲的是一个最值的问题啊，那也就是找一个最优的一个方案出来，一定是这个最好的方案啊，那这个方案的话，可能是你这个施工的这个费用是最大的时候，也可能你这个施工的费用呢是最小的时候，看你的需求是什么啊？那因为我们要做一个工程，比方说做一个工程吧， 比方说有这个什么项目经理啊，有这个工人呢，是不是？所以呢，咱们会有这个人员，不同的人员呢，他会有不同的工资需要你呢把他们结合在一起，找出来一种，哎，我能配比下来，我花费最少的一种情况，或者 是最多的一种情况，那么这个步骤呢，咱们就是去列他的目标函数，接下来呢咱们去列一下他的约束条件，因为完成一个项目你不可能全都是大头啊，对不对？不能全把这个领导给他安排进来，你得有几个工人啊，是不是？所以咱们对于不同的这几个变量呢，还要有不同的这些约束啊，我们呢要把这个不同的人员呢给他安排在一起， 然后呢去共同完成这件事情，所以呢就产生了这些约束条件，咱们用 s 点 t 也来表示它，最后呢，因为咱们求的是实际的问题，所以对于每个变量的一般都要求它有一个非富的一个条件啊，它这就是咱们基本模型的构成， 它是由目标函数、约束条件以及你的非富条件所构成。接下来咱们来建立一下它的一个数学模型，接下来呢，咱们来看一下例题啊，生产两种产品，分别需要在四种设备上加工单位产品所需要的这个加工时间，利润以及设备有效台式数。如 虾表问，应该如何去安排生产去获利最大？简单来讲呢，就是现在呢，有两个产品需要你去生产，那两个产品呢，有四种装备可以让你选择， abcd 是不是？那这个十二呢？是 a 的一个有效抬时术，什么叫做有效抬时术呢？先解释一下子啊，也就是你 有效的这个工作时间，这个机器，因为一个机器的话，他可能全天都都开着对不对？但是中午的时候你可能要去吃饭，你吃饭的时候机器又没有停，对不对？所以机器需要刨除这块时间，他可能没有干活， 那因为他在等着你吗？是不是因为没有人监管他容易炸了是吧？所以剩下的时间呢，咱们就称之为他是有效的一个胎儿主义，就是这个这个机器正在工作的这么一个时长啊，他并不是全天都在工作， 有效台时呢，也就是你这个机器他这个有效的工作时间啊，那排除了他休息的这个时间啊，剩下他能工作的这个效率的时间，也就是 a， a 呢，他一天呢能工作十二个小时， b 呢你就能工作八个小时，是吧？你再多的话呢，他就超标了，是吧？超标就是炸了啊，那 c 呢，能工作十六个小时，大概是这么个意思，那每一个数值呢？都给大家了解一下，他问你，我如何去安排这个生产哎，以获得最大的这个利润， 那要想获得最大的利润，那肯定是在有效的时间里面呢，你工作生产这个台时数是更长一些，对不对？那咱们要做产品的有这个一和二做多少数量呢？咱们不知道，所以咱们把这个数量呢给他设出来。 所以呢，第一步咱们再去做的时候呢，分成了三步啊。第一步呢是要去设置这个变量，咱们设生产的两种产品的产量分别为 x 一和 x 二 中获利呢，我们设为这个字母 z， 那其中 z 呢，咱们要求它获利最大，所以呢第二步咱们去列它的这个目标函数，那么目标函数呢？目标函数呢？也就是你要问你要求 东西获利最大对不对？那么这是你的利润要求，他是最大的，那他是由什么来组成的呢？利润本身呢？是不是一产品的话呢？有二哎，我升了 x 一价，那二产品呢，我能够获得三价，是不是 x 二 利润乘上你产品的数量，那就是你总共最后获利的一个情况了，那你就是把每样产品哎给他加在一起，他的获利应该去求他的最大值。那接下来呢，咱们就该去列什么？列他的一个约束条件了啊？这是你要求的东西，但是有东西约束他 什么约束条件呢？比方说你这个 a 设备吧，它能同时生产一和二，但它有效台数的话就是十二，你不能超过十二个小时，对不对？所以的话呢，咱们去建立一下它的约束条件。约束条件第一个话就是二， x 一加上两个 x 二要 小于等于十二。说的就是第一列的一个情况，一产品的话要分两小时，一个产品要分两小时，那二呢，他也要分成两小时，那你要有不同的配比，是不是 x 一生产多少， x 二生产多少，他们总共所需要耗费的时间必须要小于等于十二， 那于是你也可以列后面的这些变量了，对不对？所以还有 x 一加上两倍的 x 二要小于等于八，说的是第二列，哎，接下来呢，第三列应该是四倍的 x 一小于等于十六以及四倍的 x 二， 这个的话就咱们就列完了。在列的时候呢，我们最好还能够把这个 x 一啊对成一齐， x 二呢对成一齐，这样的话方便咱们后续的操作啊。那除了这几个约束条件呢，还需要它的一个非复变量，别忘了，所以呢还是需要 x 一， x 二要干嘛？要大于等于零啊，所以的话 整个他的数学模型就已经列完了，哎，这个东西呢，就是咱们所说的最后的一个他的数学模型，哎，应该满足这样的东西，上面有他的目标函数，下面有他的约束条件，约束条件里面必须得包含，那这些普通的这些约束条件，你正规需要有哪些约束就得给他写上去。 下面还有一个恢复的一个情况啊，所以总共来说呢，是由这三个方面所构成，这就是你的数学模型，接下来咱们来总结一下， 总结一下本节课所学内容。那么咱们首先呢先介绍了这个线线规划问题的这个数学模型大概的一个样式，哎，它是由三部分构成的， 也就是你的目标函数，约束条件以及非符条件。那么在做题的时候如何去列这样一个数学模型呢？咱们也是分成了三步，第一步呢要先去设置他的这个变量，第二步呢去把你的目标函数找出来，就是你要求什么对不对？接下来呢去建立你的这个目标函数，也就是你要求什么东， 是不是你要把它给写上来。最后呢再去根据题目所给的要求设计出来它的一个约束条件，那么如何来求解，就是咱们下一个的内容。好了，本节课就到这里，咱们来看下一节。
82一刷而过
05:28查看AI文稿AI文稿同学们大家好，我这边的话是小白心得，今天由我来给大家讲解一道最短路的一个问题。 这道题的话请选至重庆交通大学一九年的一道真题。我们先看一下题干。题干的话就是给我们一个网络图，让我们找到他的一个最最短路。 这找最短路的方法的话，主要的话是有三种方法，分别对应的是我们的确是他标号法以及我们的一个竹刺逼进法。还有一个方法就是弗洛伊德法 这边的话，我们可以看到他的一个每条路径上面的他的一个路径长度的话都是为我们一个正直。这样的话非常适合用我们的一个迪杰斯特拉标号方法， 因为的这四大方法的话就适用于路径权为正的，并且他的一个标号的一个思路的话也会比较简单。我们这道题的话主要是用这道题来回 回顾一下我们迪迦斯拉标号方法的一个做题的一个过程。然后我们先看一下第一步的话就是先给我们的一个 v 一点进行我们的一个 p 标号， p v 一等于我们一个零，然后其余个点的话记住我们的一个 t 标号， tvi 等于我们一个正无穷。 然后 i 的话是从我们的一个二到六，因为我们主主要的话是有六个点。然后我们从一开始进行我们的一个探查 pv 相邻的主要有我们那个 v 二以及我们 v 三。然后这个时候我们要比较一下他们的一个路径的一个长度了。路径的一个长度的话主要是以我们 pv 他的一个处原初始的一个长度加上我们一个路径长度，以我们 自身 v 二自带的一个他自己的一个 t 标号的一个长度进行。我们一个比较，选取较小的一个路径作为我们该点的一个临时的一个标号点。 我们可以看到 tv 二的话，他其实就是我们一个 pv 一，加上我们一个路径长度二等于我们这个零加二 与我们这个 tv 二。 tv 二的话，因为我们给他一个初始的一个正无穷，也就是说零和正无穷进行我们的一个比较，这样的话我们取较小的那个二作为我们当前的一个 v 二的一个临时标号点。所以说我们现在 tb 二他的一个标号的话，由我们的一个正无穷变为我们的一个二。 然后我们同理对我们那个 b 三也进行我们的一个标号的一个探查，可以看到 t b 三的话，他的一个标号的话从我们一个正无穷 无穷变为了我们的一个六入境这个长度。这样的话，我们对我们那个 tv 二 tv 三的一个临时标号点进行了我们的一个更改，再对我们所有的一个题标号点进行我们的一个比较，找出我们最小的那个题标号，更改为我们的一个新的一个批标号，也就是我们的一个， 也就是我们那个永久标号。我们对比我们所有的剩余的一个提标号的一个点，也就是我们二、三、四、五、六这个这这几个点中找到我们最小的那一个临时标号点，也就是我们这个 v 二这个点，它的一个标号值会最小。所以说我们把我们那个 v 二这个点的一个值改为我们的一个永久标号，也就是改为 从我们的 tv 二，改为我们的 pv 二，改为我们的 p 标号，并且他的一个标号值为二。 接下来的话，我们重新得到的一个永久标号点。 v 二点进行开始我们的一个探查。探查的话，我们对我们所有的一个引出去的一个 呃路径的一个都要进行我们的一个标号。这样我们可以看到 v 二的话，它引出来的一个三条路径，分别对应的是 v 二到 v 三，以及我们个 v 二到 v 五，以及我们 v 二到 v 四。对于这三条路径的话，用我们刚刚的一个标号的一个思路进行更改。我 我们这三个点的一个临时标号点，然后改完临时标号点之后再对我。我对于我们这些这几个临时标号点的一个职业是同样的进行。我们一个比小找小的那个临时标号点，找到小了之后，我们可以得到第二次标号的时候，他的一个呃 v 三的点，他的一个 临时标号提标号是最小的。这样子啊，我这样的话，我们就要把我们那个 v 三这个点改为我们那个朋友永久的一个标号点，改为我们这个批标号。这个时候的话，我们就得到了我们这个 v 一、 v 二、 v 三都是我们的一个批标号。批标号的话，我们从我们新得到的一个 v 三点继续开始去探查。 与 v 三相邻的话，就只有我们与 v 三相邻的一个提标号点的话，只有我们一个 v 四和我们那个 v 五。所以说我们这个这个阶段的话，只要改掉我们 v 四和 v 五的一个呃提标号的一个值，改掉之后我们同样的找出 我们最小的那一个提标号值，把它改为我们的一个批标号。然后这样的话我们就把我们这个阶段的话把我们一个 v 五也改为我们的一个批标号，改为我们 v 五。改为批标号之后，从 v 五开始去探查 v 五与非 v 五相邻的话只有我们这个 v 六， v 六的话，我们直接就改掉他的一个提标号的一个值，并且 我们这个改掉之后，这样只剩下一个点，只剩下一个点了，他这才是一个临时标号点，临时就会提标号点，因为只剩下一个点了，我们直接把这个剩余标号直接改为我们一个批标号，这个时候只有在仅剩一个 一个题标号点的时候才可以这么样。这样的话我们就是标号结束的时候，我们也同样得到了我们一个最短的一个路径，最短的路径的时候，我们要把我们一个最短路径呃写出来，并且把我们那个最短路长进行我们的一个标注。我们这个时候也可以从后面往回面去找路， 进行我们的一个验算，来验证我们找到的一个最短路径是否是正确的。所以说呃这么一样的一个思路做下来的话，就能保证我们用迪杰斯特拉方法做求找求解。我们的一个最短路的时候能保证不出错，不遗漏， 这样的话就能得到一个较好的一个分数，并且我们按照我们一样的格式进行我们的一个书写的话，也能更能让赏月经老师更能赏心悦目，知道我们的一个标号的一个思路啊！希望同学们都能够成功上岸。同学们，再见！
40小白心得
27:27查看AI文稿AI文稿下面我们介绍指派问题以及指派问题的求解方法。 指派问题是一个典型的应酬学问题， 那么第一个什么是直拍问题？ 我们举个例子，给个起震 say， 这里面的元素啊是二十五、三、四 十四、十四、十五、 九、四十六、十三、 七、八十一、十九。这个时候给一个表格，表格里面有 些数字，这个数字的实际含义可以表示成假设你是一个老板，你有四项工作要安排人做，你手下恰好有四个人，你就想每个人做一样工作。 第一个人做第一项工作需要花费你两块钱。如果你请第一个人做第二项工作，你需要花费十五块钱。如果你请第一个人做第三项工作，你需要花费三块钱。 如果你第一个人做第四项工作需要花费四块钱，第二个人做第一项工作，你要花费你十块钱。类似的就是每一行表示每 每个人的开销，那每一列表示每项工作。如果第一个人第二年，第三、第四他们做的话，需要的开销，你就想使得总的费用最少，你只想使得总的支出最少。 我们就按最简单的一个指拍方式来安排工作，第一个人做第一项工作，第二个人做第二项工作，第三个人做第三项工作，第四个人做第四项工作。那么这样我们总共就需要花费二加四加十、六加十九块钱。 这个问题的要求就是每个人只能安排他做一项工作，不能多做，也不能少做，每项工作都要有人做，这就是指 拍问题。那么实际上指派问题就相当于在这个几正里面，在这几正里面你选择四个数， 这四个数啊，位于不同行、不同列使的四个数字之和最少，就是从最终选择 卫衣不同行、不同列 的四个数字， 使得 总和最小。 那么选择哪四个数字位于不同行、不同列这个总后是最小的。我们可以通过观察知道一些信息，但是如果这个矩阵比较大，你可能很难观察出来了。 那怎么求解呢？对着我们要求解方法， 来对求解方法，我们讲匈牙利方法， 匈牙利方法是这样的，首先我们注意到 第一个人如果做第一项工作就需要花费两块钱，做第二项工作花费十五块钱，做第三项工作需要花费三块钱，第四项工作需要花费四块钱。也就是说你第一个人总归要做一个工作，他至少要花费两块钱， 那我就把第一行元素都减掉。二，把第一行的元素用啊，表示行都减去二，那我们这样就得到了零十三。一。二，那什么意思？就是说 第一个人做的事情至少要发两块钱，如果他做第一项工作，就除了这两块钱，不需要多花费钱。如果做第二项工作除了这两块钱，需要多花费十三块钱，如果做第三项工作， 那么就需要多花费一块钱，如果做第四项工作需要多花费两块钱，也就是说选择的四个数字之和我都啊 选择的四个数字之和至少是二。你第一行，你至少要选一个数字，那至少是二。那么看看第一行选的数字会多出来多少 多少多少。因此我们要从啊原来几这里面选择四个不同行、不同列的数字，使得总和最少，就必须在第一行选择一个，那就相当于在这里的第一行要选择一个数字，选择的数字再加上二，就是最后的总和了。 那类似的，对第二行来说，我把第二行也减掉他的最少的啊，最小的元素是 第二行的这些元素是这个是，那么就得到了六零十十一。那这个道理也是一样的，就是第二个人他总归要做一项工作， 那第二个人的费用呢？至少是事，我就把这个事除掉，那么看看他剩下还要多给他多啊，还要多支出多少钱？如果他做第一项工作就多支持六块钱，如果做第二项就不需要多支出。 那类似的，第三行我要减掉他的最小元素，最小元素是九，那么这样一减的零 五七四，那第四行我也减掉他的最小元素，第四行的最小元素呢？是 七，那这样就得到了零一四二，得到一个新的急症。 那我们看看，如果新的几个里面选择四个不同的数，选在位于不同行不不同列的数字，数的总和最小，那么原来这里面选择的四个数字，不同行、不同列的最小，就要加上这些就可以了。好， 那类似的对列我们也这样处理，比较，第一项工作他总归要安排哪个人做，第二项工作总归要安排哪个人做，第三项工作总归要安排哪个人做 啊？我们把这个数字改成十三，在这十页。好，第四项工作 总归要安排人做。我们看看第三项工作，不管安排哪个人做，他至少都需要花费四块钱， 如果让第一个人做，就要花费十一块钱，让第二人做花费十块钱，第三、七块。第四，也就说对于第三项工作，我不管哪个人做，我至少要花费四块钱，那我看看啊， 第三项工作如果安排第一个人，除了这四块钱，他还需要多花费七块钱 啊，最多花费六块钱，这三块钱零啊，那第一列啊，第一列零六零零，第二列十三零五一， 对第四项工作也是这样的，对第四项工作不管安排哪个人来做，至少需要花费两块钱，那么我们看看他除了这两块钱还要超出多少？零九二零， 那这样，原来在这个几这里面找四个数字最小，那就相当在这里面找四个数字最小，在这个数字最小啊，我们注意到 第二行只有一个零，如果说我就让第二个人做这项工作，会我选择这个数字，哎，第三行只有这个零，我选择这个数字，第一行有两个零，那么可以选择这个，也可以选择这个选择的一律有两个。第四行有三个选择，一律有三，但是因为前面接 选的这两个，所以这第一点你这个不能选，你这个不能选，那么剩下的，那么我们再看看剩下的，我们可以选这一个啊， 啊，那这个就不能选这个，选这个，那这样我们就找到了四个位于不同行不同列的元素，都是零元素，都是零元素，也就说任何费用都不超出来，那这肯定是最最少的数字之和， 也就是说我们应该选择啊，应该选择原来几正里面的，原来几正里面的对应的这么四个元素， 第一个是这个是，第二个是这个是，第三个是这个九， 第四个是这个零，那这样四个数字之和最小的，那就是四加四、 四加四加九、 加十一啊，等于二十八、二十八。 那我们再看一个例子，再看一个例子，如果说啊，这样的表格或者矩阵是这样一个矩阵， 但是说我们的 c 是这样的，是五行五列的 是十二七九七九八九六六六 七十七、十二、十四、 九十五、十四六六十 四、十七十九。如果说举正 是这样的这个矩阵，我们也称为效力矩阵。那类似的，我们按照前面的方法， 这找到每一行的最小数，找到每行第一行的最小数是七，第二行的最小数是六，第三行最小数是七，第四行的最小数是六，第五行的最小数是四，也就说 这五项工作你至少要罚这么多钱，这，那看看还会不会超出？那我们就对这个几针变换，那就是第一行减掉七， 第二行减掉六，第二行都减掉六，第三行都减掉七，第四行都减掉六，第五行都减掉四，那这样就得到了急症，五零二 零二二三零零零 零十五零十 五七二 九八零零四零六 三六五，也就说至少要发这么多钱。让我们再看看每一列，每一列的最少费用都是零，所以不需要再进行变换，再进行变换。 好，我们现在来圈一下这些零，嗯，第三个人呢？啊，他只有一 一项工作费用为零，这这个全了之后，第一项工作就安排我们把这个化掉，把这化掉，那么对第二项工作只有安排第二个，对，安排第一个人做，他才为零，然后把这个化掉， 然后啊第五项工作只有安排第二个人，他的费用为零，那么既然第二人做了第五项工作，他就不能做前面两个工作， 那么第三项工作啊，只能安排在第四个人为零，那么第四个人就不能做这项工作啊，刚才这个圈出来了，嗯，那这样话，我们总共只圈出了四个零，那没有找到位于 不同行不同列的五个零，如果是五个零，那就不需要多任何费用， 那怎么办呢？那也就是说我们想啊， 继续按照前面的方法进行变换啊，画出更多的零，画出更多的零，那么这里圈出了四个零，我就想啊，把这里面的所有的零元素都不变， 把这所有颜色都固定出来，再通过每一行每列都减掉一个数，那么我用直线把这些零全部固定住，我们想用最少的直线把它固定出这圈中的四个零，我就用四条直线把， 把这个固定出。 好，那这样话，我们用了四条直线就把所有的零都给固定住了，都给固定住了， 那么剩下的这八个数没有被固定住，剩下八个数字里面最小的啊，是最小的数字是二，是二， 也就是说对第三个人来说，对第三个人来说， 如果不考虑第一项工作的话，他安排其他工作，他至少需要花费两块钱，需要花费两块钱，那也就是说我先把这两块钱啊预算出来， 那么这样就变成了啊，我第三行都减掉二，第三行都减掉二啊，这样第三行就变成了负二八三五零啊，八三五零， 那意意味着，如果说啊，我的总费用支出两块钱，如果安排第一个人做的话，啊，安，安排第三人做第一项工作，那么他就要退回两块钱，如果安排给啊， 如果第三个人做最后一项工作，那么他不需要费用，那这个这项费用，这样，这样我们就把这个哦，这个元素变成零，零了，把这个二就改变成了零，哦，变成零， 那第五横 我也剪掉啊，我也剪掉这第五五个人啊，我也先给他两块钱， 如果他做第一项工作，他就退回两块钱。做第二项工作，我还再给四块钱，再给一块钱，四块钱，三块钱，其他的元素是不动的。五零二零二二三零零零 九八零零四。我们说前面你这个线把直把这一个啊零度固定住了，那么第一行固定住了，第二行 固定住了，第四行固定住了，但是第一列固定的这两个零又变成 for 了啊，变成相同的 for 啊，就这两个数，没有，本来应该是零，变成了 for， 没有固定注，没有固定注，因为它是相同的 for， 所以我们将第一列， 我们将第一列用这个表示第一列，我们把它加上，哦，加上，也就说对第一项工作，对第一项工作啊，第一项工作，大家都啊， 先拿出啊，两块钱给给老板，拿出两块钱的给老板，那么这样第一列就变成了啊，第一列就变成了七 四零九零，七四零九零，那这样话，我们就知道这个零元数就变得更多了，零元数变得更多了，好，我们将这里改成 七四零九零 七四零十一零， 我们 就将这里改成七四零十一零，这就相当于第一列加上了二。好，那现在我们看一下， 现在就说原来的零都啊，没有变啊，但是这个二又化成了零啊，注意这个二最小 的元素，他变成了零。现在我们再看一下啊，再看一下第 第五项啊，第五个人才只有做第一项工作才为零，所以我安排第五个人做第一项工作，那这个就划掉， 现在我们看看第二项工作只有安排第一个人做，他才啊，费用为零，那么第二项工作安排第一个，第一个人就不能做这项工作。 来，现在我们看看啊，第三个人，第三个人，嗯， 第三个人现在说他不能做第一项工作了，那他只能做第五项工作为零，那我就他不能啊，第五项工作就不能安排第二个人做了，把这个零化掉。 好，这已经圈出三个人了，还剩下啊，第二个人没安排和第四个人没安排，然后可以安排 六个人啊，我让他做第三项工作或这个都可以。如果安排做第三项工作，那他就不能做第四项工作，那第三项工作已经被第二人做，他就不能被第四个人，第四个人只能做。这样， 这样我们就恰好圈出了五个零，位于不同行不同列的啊，五个数，也就我们对应圈出的是这个啊，七啊，啊，零啊，六、 九六啊，全程的这么五个数字，他们的核实最小最小。 那这个思想就是啊，只派问题的匈牙帝啊。向上访， 我们总结一下这个 求解方法的步骤。 第一步呢，先将 c 每一行和每一列都减去， 将没行没列 中的所有元素 都剪去 该行该练 中的最小该行或者该列啊每一行或每一列都减去该行或者该列中的最小元素。第二步，如果 圈出了啊，圈出了啊，如果是 n 行， n 个零，则结束。 如果没有穿出 n 个零，那么我们用不要去穿出了啊， 否则我们进了，下一步， 我们找一下这里设圈出了 k 个零，那么就用 k 条直线 拍一条直线，我们把所有的零度固定住，叫做覆盖零， 铺盖全部的零， 那未覆盖住的 为覆盖度的行或者是列，都减去 读前去 所有未未覆盖的元素中的最小元素， 这小元素。然后啊，还有并将复数，复数也要并将复数所在的 横或者是裂都加上 这个最小元素， 将其发为零。 那么这样就是多出了啊，一些零元素啊，多出演一些零元素，八百零。那么回到 有一道二继续做，有一道二紧张，这是第一步， 第一步，先把每一行都减掉，这些元素，第一行减掉，第二行减掉，第三行减掉，第四行减掉啊，在第一点减掉，第二点减掉，第三点，第四点，第五点都减掉。 然后我们圈圈出了四个零啊，没有圈出五个零，因为有五行，这样我们就用四条直线把所有的零都覆盖掉，那么没有覆盖住的八个元素里面，十五七个里面找到最小的啊，八 个数里面的最小的数二。然后啊，将没有覆盖住的第三行，第五行都减掉二，但是会出现负二，对，出现负二，我们把这里第一列加回负二，那么这样就多出那些零。我们继续去圈啊，如果圈出了五个零，那就结束了。 这就是指派问题的求解方法。 那么具体的啊，一些啊细节和一些结论，大家可以看课本，或者看我更详细的视频。
80xuzhijun
07:17查看AI文稿AI文稿嗯，大家好啊，承接上面两个视频，这节课给大家带来的是运输问题解的调整这块内容，如果同学们觉得 up 讲的还可以的话，点个赞，关注一下，多发弹幕和评论互动一下，有问题私信我都会回复， 觉得哪里讲的不好我都会吸取经验。话不多说，开始今天的内容。嗯，今天这道题是华南理工大学二零一三年的考研试题。嗯，我这道题来源是从梅书文老师的作本， 嗯，运筹学解题技巧归纳里面摘取的，然后这本书很好书，有需要的大家可以买来去参考一下。然后，嗯，我是直接就，嗯，先去把他那个嗯初始调运方案先给 摘过来，这样就不算了。前面两个视频你教他一下怎么算了，我就直接摘就过来了， 我就直接摘取过来啊，一二四五一四。嗯，这就是初始要用方案。嗯，如果不知道怎么求的话，可以去看一下。来，我去我主页看下前两个视频，有给大家详细讲解怎么计算， 然后结束。嗯，我也不算了，然后直接就啊，直接就 再去过来。然后啊，你们会看这个减数，通过会发现这有个减减数为负数负一啊，这是个运输问题，运输问题是个机械化问题，减减数要求都大于等于零，但是你这里出现的负一是小于零的，所以说 现在不是自由调音方案，需要进行解的调整，这是我们今天要讲内容解的调整，然后我们进入解的调整的内容。 嗯，介的调整呢是？嗯，运用的是必回路法，然后他是在初始调运方案的那张表上进行的，你要注意分清楚啊，我先给他画一下 啊，这张表是检验数表，一定要分清楚，一定要分开，单单独换。这张表是出这张表是初始调运方案的表，你的你的，你的，那个简单调整的那个必回入法是在初，嗯，是在调运方案的那张表进行的，千万不要在检验数那张表进行， 这一定要切记。在这里还钓鱼，你发现负一吗？就是在， 在啊，在这个位置是这个位置，对吧？我们要在这个位置他减速算负数，那我们以这个位置作为掉路格作为起点，然后使用必回路法，必回路法在上节课，那个在那个什么，嗯，算减速，那节课上面应该讲过了，然后现在就是这样子，必回路一下， 嗯，必回路线，然后然后同理。嗯，掉入格是加号，转一次，弯减一次，再变一次，再变加减加减，然后我们取选取带负号箭头的，这这这两个格一定选取带负号箭头。这两个格子里面他他有两个调音量吧？ 一个是一，一个是四，选起他们调运量里面最小者一四，那么肯定选一，对吧？那么做一，那么我再给他列张表， 呃，三百张表，就是我们调整后的那个调运方案，那么我们我们调整量就是一 上面已经比出来，上面这个比比的方法是调整量，就是为了找出调整量是多少，那我们这里就是，嗯，加一减一，加一减一，那么这应该是一一减一没了，那么就是三六， 然后再检查一下，发现是没有问题的，然后就是那么这一张表，好吧，就是我们调那个调整后的调音方案， 你调整后干嘛呢？然后再重复上面的步骤，再继续算减数，嗯， 用微释放，这应该是再用微释放，因为第一遍初始调用方法你已经用了一次微释放了，再用微释放计算 检验书表，嗯，不会用微书法算的话，就主页，我看完上一个视频都已经讲解过了，我就直接用了。在这里 这视频主要讲解是解的调整，就当你检验数出现了复数情况下，就是出现了小预定情况下，就要进行解的调整，用的方法就是必回路法。 ui pj 零零零零零 零零四六七风十一。 此时你会发现可以观察现在算出来减数表，新的这张减数表里面发现所有的减数都是大于等零了，说明他此时什么已经满足了最优调研方案的条件。 就写一句话，因为此时减元数表中的减元数，嗯，均大于多零固，此方该方案一定是最后调用方案。那么此时我们那个这张这个解解的调整只要调一次就很简单，那么有时候我们会遇到题目就会出现，嗯，随便举个例子吧，如果这是负一，那么我们就要继续重 重复上面操作，又去去那张吊运表里面，到这个位置作为掉入量，又又寻找必回路法去寻找去，嗯，去重新用必回法去调解的调整，然后再算减一数，然后再再去判断， 直到就到最后刚刚那样子，前数全部大于等于为止，就算出了最后交易方案，那我们再去算他的 最后运价。运价其实就是你的运量成硬的掉成硬的运价，总运价的运量成运价的全部相加，那么也就是， 那就是一乘十，加上二乘六，加上一乘七，加上三乘五，加上六乘九，加上四乘五，然后算上就是他的总运价了。那还是要提醒一下你这个运价是一定在那个调运方案，调运方案那张表去乘，你千万不要用这张表去乘， 这张表是结束你用去，因为上面这张表是调运方案的表，调运方案的的 里面这个数字是他调运量，上面右上角这个是调运加，他俩相乘，那全部相加才是他的总运加，那你下面这张表里面的格子是什么？这个是简约数，它代表是不含不同的含义好吗？所以说不要填，填错 那么几个调整。我给大家讲到这，下节课就给大家讲啊，特殊的运输问题，比如求最大值的问题该怎么算？那后面题目会越来越复杂了。好，谢谢大家，今天就讲到这里。
253胖帕，
01:55查看AI文稿AI文稿一九四三年，正值第二次世界大战，关键点在北大西洋战场上，是英美联军与德国纳税的关键角逐点。而德国舰队呢，时常的去袭击英美舰队的运输船，造成被击沉率高达百分之二十五， 数以百万吨级的物资，无法及时有效的运送到前线的将士手中。而这是一场决定人类生死存亡的战局。 万分危急之下，英美统帅决定我们集聊数学家，来吧，看他们有没有什么办法。所以，一批精通统计的数学家就来到前线。经过一番调研，他们发现， 其实德国军队啊，压根就不知道英美舰队的准确出航时间，他只是以很高频次在海上游荡，以其有更高的概 去遭遇英美的舰队，从而进行打击。那此刻最好的办法是什么呢？就一定不是分散出行，而应该是集中出行。什么意思？ 如果我们今天有五个小孩犯了错误，如果你这五个小孩分别回到自己家中，那老师去抓你，到哪家都会有所收获，一定一抓一个准。但是，若你们五个人都倒在一人的家里呢？那这个概率就只有百分之二十了，对不对？ 随两军统帅紧急修正方略，改分散出行，为集中出行，所有的舰队共同驶出港口，共同破危险区域，用集中的火力掩护运输队伍，然后再各自驶离。而 这一举措，成功的将被击沉率从百分之二十五骤降至百分之一。而这门学问，他的英语就算 opposno 瑞斯，而取中文叫做运筹学，取的是运筹帷幄之中，决胜千里之外的意思。而在这里，何为数学的力量？他是国之兴亡的后盾。
154是苡沫苡佑爸爸呀
05:48查看AI文稿AI文稿指派问题解法，匈牙利法参考教材管理运筹学，韩博堂制作者，杨成制作日期，二零二二年七月三十日邮政创新工作室和 euronyat 学院联合出品， 请看例五、甲、乙、丙、丁四个人 abc 第四项任务，不同的人做不同的工作，效率不同，如何指派不同的人去做不同的工作室，效率最高？最终答案，假作 c， 乙作 a， 丙作 b， 丁作 d 匈牙利法解题步骤，解类似运输问题的最小元素法 m 乘 m 矩阵第一步，造林，各行各业减其最小元素。 第二步，圈林，寻找独立的零元素，圈之若被圈零数安等于 m， 则以求解进行指派。若 ns and m， 则进入下一步。第三步， 划线一、无圈零的型，打钩。二、打钩形上含零的裂，打钩。三、打钩裂上圈零行，打钩。四、重复二、三指，无钩可打。五、对没有打钩的型，划一直线，打钩裂，划一直线。 第四步，增加独立林元素，直线为覆盖的元素，找一最小值为划直线的型，减去这一值，以划直线的列加上这一值， 返回。第二步，进行型检验，对 c 一进行主行检查，每行只有一个未标记的零元素时，用欧记号将该元素圈起，然后将被圈起的零元素所在列的其他未标记的零元素用记号呈划去 重复型检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素为止。进行力检验 与进行型检验类似特殊问题的处理，一、若人数与工作数不等，要求每人只完成一项工作，则需你若干行列，效率天灵。二、若某些人可以做几件事情，则和转化为相同的几个人来接受指派，其费用系数相同。 三、若可以重复工作的人不确定，可新增一个虚拟的人，其做每项工作的效率值均为最优。 四、若某人必不做事某项工作，则将其价值系数设为 n。 若某人必做某项工作，则已经指派该行，该列退出计算。 五、若原问题求利润的最大值，则先将效率矩阵变换，即从中找出最大值，减去所有价值系数，形成新的效率矩阵，再按照匈牙利法求解。请看例题，从 abcd 一、五人中挑选四人去完成四项工作，以至每人完成各项工作的费用。如下表规定每项工作只能由其中一人单独完成，而每人最多只能承担其中一项工作。 又假定 a 必须保证分配一项工作的，因为某种原因不能承担第四项工作。在上述条件下，如何分配工作是完成这四项工作的费用最少。最终答案， a 做二 b 做三 c 做一 d 不做一做四。
