粉丝28获赞188
嗯,各位同学好啊,今天给大家带来一道是广东工业大学二零一三年一道考博士题,嗯,题目不难啊,就给大家讲一下什么叫做标准形式,什么叫队友规划。其实就是写出他的标准字形和他的队友问题。 首先我们写出它的 boss 型, boss 型首先就有四条要求,第一条呢就是,呃,你的你一定得是极大化问题,求 max, 然后你的毕业值一定都得是大于等于零, 然后然后你的决策变量都得是大于等于零,然后你这里必须都得是等师,那你就会发现这道题有哪些不满足的呢?我们来看一下。嗯,这里发现这有个这有个负是不满足毕列都大于等于零,对不对 啊?这还有这两个都不是等式,然后还有什么呢?还有这里都没有满足啊,决策标大于等于零,那么要 怎么做呢?我们现在开始写一下。首先, 首先呢,这个角色边上是 x 二小于等于 x 三五月数,我们就,呃,另 x 二一撇等于负的 x 二啊, x 三等于 x 三一撇减去三, x 三两撇, 然后,嗯,然后我们再让第三条约数两边同乘,负一,两边同乘,负一会变成什么样子呢?负二倍的 x 一加上 x 二加上 x 三小于等于五,应该是这样子吧,没有算错啊。嗯, 然后这样就会发现还有还有什么问题呢?这个小于等于,这个小于等于零,我们要给他们都加上他们的松弛变量,一个是加 x, 一个是加 x 五, 然后这里是等号,就不用变了,好吧,然后我们再把我们这些换圆以后的东西再往里面往,往这里面带,往圆方程里面带,然后最后结果会是什么样子的呢?我们来写一下,一定要仔细,要不要写错?三个 c 减去两倍, x 二 加上六倍的 x 三一撇减去六倍的 x 三两撇。因为 x 二和 x 三已经被我们幻影换掉了嘛,所以说我们要写进去啊,写着我们幻影幻影以后的形式,再加上 x 一,加上 减去啊,减去负 x 二一撇,加上 x 三一撇减去 x 三两撇,加上 x 等于二十三倍的 x 一加上 x 三一撇减去 x 三两撇等于二十二。 嗯,两倍的 x 一加上 x 二一撇减去 x 三一撇加上 x 三两撇,再加上 x 五等于五。然后是还有什么情况呢? 呃,然后就是 x 一大于等于零, x 二一撇大于等于零, x 三一撇, x 三两撇大于零,这其实可以一起写的 啊。然后我们不是添加两个,两个添加两个松弛变量吗?就一个 x, 一个 x 五,那么要不在他的目标函数里面体体现出来,怎么体现呢?松弛变量他的系数是零,加上零倍的 x 四,加上零倍的 x 五, 这样子我们就把写出了他的标准形式了。然后我们去我们检查一下是否,嗯,在根据那四条规则来检查一下他是否满足那四条原则是不是最大的问题 啊?是不是约束条件全部都是等式,然后毕列子是不是都大于等于零啊?然后决策量是,决策量是不是都大于等于零啊?是不是已经都满足了呢?那么这就是他的标准形式,你考试时候一定要把刚刚那过程都写出来好吗?然后我们就会写,那我们先下面就写他的对耳问题,有点乱,我把它重新写一下, 还有其他都有问题,嗯,都有问题的话就可以直接写,嗯,你们可能是不懂的话,就可以直接上面写 y 一 y 二,哎呀,后面红币重复了,就写 y 一 y 二 y 三, 那么就是,呃, max 的对偶问题,就是 minima, minima omega 等于二十倍的 y 一,加上二十二倍的 y 二,减去五倍的 y 三,然后符号我们最后先不写啊,最后 我们根据节目来判断符号,我们先把它的数值都写好,那么我们就打竖看,这打竖看,那么就是,嗯, x e 的系数都打数看,那么就是 y 一加上三倍的 y 二,加上两倍的 y 三,这,嗯,这边就写写目标函数的系数,三二六,这应该是三二六, 那我继续看 x 二的系数, x 二应该是一零负一,那么就是 y 一减去 y 三, 然后再看 x 三的系数, x 三系数应该是一一复一,一定要看清楚,比如这第二条约数是没有 x 二的,这一定要看清楚啊。然后 x 三的系数是一一复一,那么就 y 一加上 y 二,减去 y 三, 然后我们就判断他的符号了,外衣外衣的符号,外奥的符号, y 三的符号,嗯,怎么判断呢?我们这是求极大化问题的队友问题,那么从大化小,那么就是约束,约束变变量不变,那么原问题的约,原问题的约束呢?是对你的他队友问题的角色变量,那么既然,那么原问题的 原问题的约束要变的话,那么这里,那么这里是不是就是要小于等于变成大于等于,那么第一个对应的就是大于等于,那么这这个等于的话,等于还是最简单的,就直接写无约束就好了。 然后这里还有个,嗯,大。第三条,约束是大于等于,那么这条写小于等于,然后,嗯,约大化小,极大化变成极小化,那么就是,呃,约束法,变量不变,角色变量不变,那么角色变量他对应的是对有问题的约束,那么约束是不变的,那么全部都照 超,那么大于等于,小于等于五约数,那么就写等于,那么这就是他的队友问题,这么就写出来了。这东西你要多做,多做的话你就会发现。嗯,刚开始不好记吧,反正就是 max 变成 minima。 呃,约束法, 嗯,决策变量不变,我们这些反和不变都都说的是它的那个符号,不是指它的数值啊。决策变量不变,那么 minima 到 max, 那么就相反呗。 我偷懒了,就直接写了约束不变,角色变量反就就都指的上的符号,然后 这个反呢,是从他原问题里面去看,而而原问题的约束呢,又对你的队友问题的决策变量,说明原原问题约束如果是大于等于反过来的话,小于等于的话,那他体现在他队友问题,你应该体现在他的那个决策变量上,一定要弄清楚,不要弄反好吗?就这一点, 那么这道题,那他的标准形式和队友队友规划也就写出来了。所以说你不要看他的是考博的题目,其实很简单的一道题目,很非常非常常规的一道题目,所以说,哎呀,挺适合刚开始学英雄学的同学来巩固一下这道知识点。嗯,考的像是比较全面的人, 所以说那这道题我们就讲到这啊,如果有问题的话可以避战,私信我或者加群。嗯,在姐姐应该有群的,然后加下那个群,然后来通过群来联系我啊,我们下次再见,谢谢大家。
首先看一下科室,一限行规划问题,有三个考点,第一个限行规划问题的建模,第二个画标准型,第三个铺结法。 先看一个例题,某消费者要购买营养品,要求维生素 ab 含量分别不少于九单位和十九单位。 先有四个品牌都含有这两种样品,其含量售价如下面所示。问,消费者应如何购买这四种样品才能达到维生素含量,并且花钱最少? 我们来解析一下。首先假设 spa 为第二种营养品的购买量, i 等于一到四费为总的费用, 那么他的模型就是这样的,我们来看一下种的费用, 显然就是这样一个柿子,因为这四种样品单价分别是三十五,三十六、十五十,然后购买量是 x i, 所以说就是这个柿子, 那这个呢,我们就称之为目标函数,我们要求花强对手,所以说就是求他的最小值。 下面这部分呢,就称之为约束条件,他要满足两个约束,第一个呢就是维生素 a 的含量要大于等于九,可以看到 四类品牌维生素 a 含量分别是一零二二,所以说就是第一个不懂事。总理呢,维生素 b 的含量要不少于十九,那么就是第二个不懂事。 那么第三个就表示啊,他的购买量必须是恢复的, 那么其中 x 一到 x 就称之为决策变量, 那么这就是限行规划的。一般 城市 首先一定要要求决策变量恢复, 那么用矩阵表达形式就是这样子的。其中大 x 是由 x 一到 x n 构成的一个列项量, 我们称之为角色项链,大 c 呢是由 c 一到 c n 构成的链项链,我们称之为价值系数项链, b 呢,是由 b 一到 b 安构成的列项量,称之为资源项量。 那么有这个不懂事,左边的这些系数构成的举占大 a 就称之为技术巨战。 那么再来看线型规划的标准型是这样一个形式 的,要求有这么几点,第一个目标函数必须是求他的最大值。第二个约束条件必须是董事约束。 第三个注意右侧 bra 他必须是恢复的。 第四个对 fg 来讲也必须是对付的。下面我们来看个例题,将这个模型转化为标准型。 提到过标准型要满足这四个条件,那我们来看一下如何去进行转化。 那么第一步呢,可以先看一下变量个数,并将一有的变量转化为对付要求。那么可以看到这个题里面有三个决策变量,其实 x 一是小一点零, s 二大一点零, s 三没有要求, 那么转换肺部要求,我们就令 s 一一撇等于负的 x 一,那么 s 一小一点零就等价于 s 一一撇大一点零, 那么 x 三是没有约束的。那我们就引入两个角词,变量, x 三一撇和 x 三两撇, 那么 x 三可以用 x 三一撇减去 x 三两撇,因为 x 三没有要求,就是可以为负为零为正,那么对于两个正的变量相减 也是可以为父为零为证的。 这样的话,我们先将 s 一 x 二三转化为 s 一一撇, x 二 x 三一撇 x 三两撇。 第二步呢,通过增加变量,将不等式约束转化为等式约束。那可以看到有三个约束条件, 不同时约束有两个,第一个呢是小于等于,第二个呢是大于等于,那么第一个呢? 小一点七十二,那我们就可以加上一个正的变量,让这个不懂事转化为懂事。 你说加一个 x 等于第二个呢?是大于四,那我们就再减去一个正的变量,就是减去 x 五,那么就变成等于四了, 这样的话,第一个不懂事就转化为占一个懂事,第二不懂事就转化为占一个懂事。 那么对于第三个来讲,我们要求说这个右侧这部分 b i 都必须是恢复的,所以说我们两边同时成一个负一,哎,就变成这样一个形式了,同理还要再保证 x 和 x 五必须也是恢复的, 这样约束条件就完毕了。那么再来看目变函数,我们要转化为最大值的形式,这个数就可以啊,零 w 等于负罪,那么求对的最小值就变成求 w 的最大值, 那么这样的话就目标函数啊转化为这样一个形式,其中目标函数里面的 x 一、 x 二、 x 三也用这四个变量来替换,这样的话 这个标准形式就确定了。我们再来看利用图解法求无限性规划问题。先看这个例题, 那么他的解析步骤有这几步,第一步,先建立坐标系,做约式条件的董事图形,那我们将这个三个约束条件 不等号、边位等号来做这大小直线。 第二步呢,我们带入零零点,确定解的可行欲。比如说对于第一个不懂事,我们要求是左侧小于钉子,那么我们左侧带 零弦是零,满足小丁,所以说这个零是这个不等式的一个解,那么对于这个直线来讲的话,他翻了 下面和上面两部分,那么零码组为说他下面的所有这些都是小顶四的,比如说对他来讲是取了这个下侧部分整理,对第二个我们看到 代入零的话,是不满足大于等于二的,比如说零不是他的一个几,那么对于这个直线来讲的话,他在上侧才是这个不等式的几,比如说他要取于上侧这部分, 咱们同理对于第三个直线来讲啊,代入零是满足小的,第三你说零的这部分区域啊, 他能满足这个等式不等式要求,就是说对他来讲的话,这个直线那就取了,还有零的这个区域,就说他的左侧区域,这样我们再对这三部分取一个交集, 那么前可以看到白色这个区域就是这个约束条件对应的可行域。 第四步呢,将目标函数进行变形,那么可以看到横坐标是 x 一,正坐标是 s 二,那么 x 二用 x 一来表示,那么用斜结式来表示,就是这样一个形式,其中斜率是负二分之一, 结局呢是二分之最。 那么球弟弟大 也是求这条直线的结距最大,那首先先让这个结距为零,先画 x 二等于负的二分之一 b x 一这条直线,然后让他来上移,然后跟这个可行域,他最上面这个焦点就表示这个最大的拮据, 讲此事就是在这个位置, 那么此时可以看到结局为字,所以说定的这件方程就是这样的, 那么此时可以看到九十二分之一等于四,得到 c 等于八, 那么此时顿顿起就是 s 一零一零 s 二等于四,怎么了?再看 这个题目,同理还是将这个约束条件对应的可信誉来找到,那么可以看到就是黄色这部分区域, 接下来将这个目标转目标函数转化为 x 二,用 s 一表达的形式斜六是负三,结句是对求这个对的最大值,还是求这个拮据的最大值? 先画 s 二等于负的三个 s 一这条直线,然后呢结局最大,那你表示这个直线往右或者说往上移, 那么最极端情况下显然就是一到这个位置,那么此时可以看到这个目标还是个直线, 和这个边际是重叠的。我们假设对这个焦点分别是 b 和 c, 那么可以看到 b 和 c 上的所有点都是队友点,所以说此时他有无穷的个队友点, 那么 b 就是有这条直线和这条直线的焦点,所以得到是 x 一等于三分之十一, s 二就是一,此时带入目标还是可以得到 c 一等于一个十二, 另外的话他就是一种无穷大的纠结了。那么再看这个题目,那么先将这个约束条件对应这个方式 给画出来,要求这个是小于,等于就说他的下册,比如说这部分是可行域, 那么同理目标函数的话,用 sk 表示 x 二,然后结局为零的话就是这一条虚线,然后最最大的话就是将这个直线往硬引, 那么此时可以看到这类题型是无界界的,比如说这个直线啊,可以一直往右移,一直移下去,就说他的紧,一说属于无从大了,所以说我们就称之为无界界。 那么再看这个题目,还是先将这两个 不懂事对应的这个边界画出来,那么其中这个是第一个不懂事的边界,这个呢是第二个不懂事的边界,那么第一个要求是小等二,所以说对这个接下来讲,他取他的下册, 第二个呢去取他的上色,那我们可以看到他们这两个是没有交集的,所以此时可行欲是空脊,那么此时就是没有可行结的。 那么我们来总结一下第一个呢,现行规划解的情况,凡唯一自由解、无穷多自由解、无解、解无可行解四种情况。第二呢,若现行规划可信誉,团贷得可信誉,一定是一个 初级,什么初级呢?我们通过这两个图来看就明白了。那么对初级来讲的话,我们在这个边界上任取两个点,然后来连一个线段, 那么这两点之间的这个线带上所有点都是在这个可行域里面的,而奥吉呢就不行了,比如说我们取这个点,再取这个点,那么这两个点之间的连线可以看到红色这个 线和点就不在这个可行域里面了,那么此时我们就称之为凹级。 那么第三个,若性性规划最有解存在,则最有解,或者说是最有解之一,一定是普及上的经典。什么意思呢?当这个。
我们第一个知识点是把它画成线标准型,然后首先我们来看将下列线型规划问题变成标准型, 首先看这个线性规划是最求 z 的最大,然后这个他目标函数,这个是他的约束条件,然后呢,首先标准型的条件其实就是求他的最大,然后并且让所有的约束条件就是这些地方都变成等于号。然后呢还有就是所有的决策变量均大于零, 这些变量决策变量均是大于零的,所以像看这个就不符合。然后还有最后一个条件是右端向为非负,右端向为非负,这个线性规划他这边是非负的,所以就不用管了,然后这个是最大,所以这也不用画了,然后加,就看这个约束条件化为等于号,还有所有 左侧边量都大于零,这里边 x 一和 x 都是大于零的,只有 x 三是无约束的,所以说就把 x 三变成 x 三撇,减去 x 三撇撇,让他等于 x 三,然后另其中的 x 三和 x 三撇撇大于零即可。然后 然后我们就看这个小于和大于等于,如果是小于等于的话,就要引入一个松弛变量,引入一个松弛变量 x 四,让他加上 x, 因为他是小于等于的,所以如果要是加上一个正数的话,他肯定还会更小于等于,所以说就让他加上一个 x 四, 这边大于等于三,因为他是大于等于,所以减去一个大于零的数,他肯定还会更大于,所以就让他减去一个 s 五等于零,然后这个时候这个约束条件就变成了,这个就 变成了这样,然后呢所有的决策变量均大于零,此时他的标准型就变成了麦克斯 z, 等于这前面都不变。负二 x 一加上 x 二,加上三倍的 x 三片减 x 三片片,然后加上零, 这个地方是零,因为他本来就是不存在的,所以说就让他前面系数为零,零 x 四加上零 x 五。然后以上就是对标准型的求解。
同学们大家好,我是米然学姐,我将带你们用二十个短视频通关运筹学,助力大家一刷而过。首先我们来看一下线性规划数学模型的一般形式,那它主要有三个要素构成, 一个是决策变量,也就是这里的 x 一、 x 二,一直到 xn 这 n 个变量。第二个是目标函数,也就是这里求极大值或极小值的函数。 第三个约束条件,也就是这里大过号内所包含的。呃,所有等式或不等式叫做现行规划问题的约束条件。 这是线性规划问题的标准形式,它包含三个特点,第一个目标函数是要求求最大值的函数。第二个约束条件都为等式方程,而且 右端的长竖向 b、 i 都要求大于或者等于零。第三个,所有的决策变量 xj 都要是大于或等于零的非负数。那基于以上三个标准形式的特点,可以总结出划标准型的五个步骤。 第一步是对目标函数进行转换,如果原问题是求极小值函数,那我们可以把目标函数乘以负一来化成求极大值的问题,也就是这样。 第二步是对资源限量进行转换,如果方程右端出现小于零的长数项必挨,那我们可以把方程两边同时乘以负一,把资源限量转化为非负数。 第三步是对约束方程进行转换,也就是需要把不等式转换为等式,那如果出现小于等于长 横竖向的约束方程,我们可以在啊方程左侧加上一个大于零的松弛变量, 这样就可以把它变成一个等式方程。第二种情况,如果约束方程是大于等于某个长数项,那我们可以在这个方程的左侧减去一个大于等于零的剩余变量,来把它变成等式。 第四步是对决策变量进行变换。如果我们存在无约束的变量 xj, 也就是说它的取值可以大于等于零,也可以小于零,那我们可以通过构造两个大于等于零的新变量 xj 片和 xj 片片, 令 xj 等于 xj 片减去 xj 片片,这样就满足了决策变量全 都是非负数的条件了。如果存在 xj 小于等于零的变量,那我们可以令 xj 片等于负的 xj, 那显然 xj 片也是满足大于等于零的条件的。 下面是一道考试当中求标准型的例题,我们还是按刚才的五个步骤来进行。首先呢,对目标函数进行变换,因为原目标函数是求最小值的,所以我们要把它画求最大值函数,也就是令这片等于负 z 得到最大值函数, 也就是下面这样。第二步需要对资源限量进行变换。我们可以看到第三个约束方程右端的长竖向是负五,那我们就可以把方程两端同时乘以负一,把这个长竖向画成正数,也就 是下面这样。第三步是对约束条件进行变换。我们可以看到第一个约束条件,他是小于等于号,那我们就在不等式左侧加入一个大于等于零的松弛变量 x 四,来把它画成下面这样的等式。 第四步,我们可以看到第二个约束条件,它是大于等于号,那我们就在不等式左侧减去一个剩余变量 x 五。 x 五要求大于等于零,那就得到这样变换后的等式。 最后一步,我们对决策变量进行变换,因为这里的 x 三取值是无约束的,也就是它既可以取正值,也可以取副值。那标准型要求我们的所有变量都是非负的,所以就需要构造两个新的变量, x 三和 x 三片片 全部大于等于零,然后用这两个变量的差值来替换 x 三,这样就满足决策变量非富的条件了。那最后呢,我们就把原问题画成了如下的一个标准形式,这道题也就完成了。 最后提醒大家,考试当中如果遇到划标准型的题,可以按照目标函数、资源限量、 接触条件、决策变量这四步的顺序来进行,画完之后默念四句口诀验证,确保我们不会出错。这里大家记得截图保存,下一节我们来讲解图解法,记得关注我,轻松通关运筹学。
同学们大家好,欢迎大家一起来学习运筹学。今天我们要学习的内容是线性规划与单纯刑法三,主要讲一下大 m 法和两阶段法。 那么在上一节课我们讲单纯刑法中,我们讲了第一步是不是要找到一组初始基本可行解,那如何去找这组初始基本可行解呢?是不是通过我们的系数矩阵中去找有没有对应的 单位证已构成我们的可行机?那我们在上一节课的例题中呢,通过哎加入了松弛变量之后,是不是能够很容易的找到对应的单位证?那我们是不是所有的题都能够很容易的找 到单位?正当我们来看一下这样一个例题,例题一,用单纯刑法求解下列线性规划。当然我们的第一步要把这个一般型化成标准型,我们来看一下 目标函数是求最大值约束条件,第一个是大于等于号,说明我们要给他减去一个剩余变量, 哎,第二个小于等于要加入一个松弛变量,那我们的第三个他是等号,但是右边是长数,上为负,所以我们要给他乘以一个负一,等号两边乘以负一。 这个时候呢,我们给它加入两个松弛变量 x x 五,可以把它化成标准形。化为标准形之后,我们再来看它的系数矩阵,我们的系数矩阵是一个 三行五列的举重,那我们举重 a 的质是不是应该是等于三的?那我们要找到一个,哎,我们的可行机是不是要找到一个三阶单位正,也就说我们要找到三个线性无关的单位列向量所构成的机举证。 好,我们来看一下此时举重 a 中他只有最后一列为单位列项量,对吧? 哎,说明这个时候我们只找到一个机项量,那么我们也就说我们这个时候只有一只能找到对应的 x 五可以作为我们的机变量,那么我们还需要找两个哎机项量,那这个时候我们没有机项量,我们就给他 添加人为的给他添加两个虚拟变量 x 六、 x 七,目的呢就是为了要构成我们的机项量, 我们给他添加这个人工添加的这两个虚拟变量 x 六、 x 七,我们就把它称为叫做人工变量,我们添加的目的呢,就是为了能够构造出我们的哎单位列项量出来啊。我们来看一下添加之后的系数矩阵是怎么样的, 我们添加了人工变量之后的系数矩阵变成了这样,这个时候我们看一下我们的第五列,第六列、第七列,他们是不是都刚好是三个线性无关的单位列项量哎,所以我们是不是他就能够 可以构成一个可行机啊?注意,我们这里的单位证,三界单位证 并没有说要严格要求,必须是哎,一零零零,一零零零一这样的一个排序啊,就我们只要找到三个线性无关的单位列项量就可以了。 好,那我们添加了人工变量,虽然说我们构造出了我们所需要的可行基,你说我们这里的基变量是 x 五、 x 六、 x 七作为我们的基变量,我们的哎基项量就是我们的第五列,第六列、第七列,对吧? 添添加了人工变量之后呢,但是他实际上相当于是改变了我们的约束条件,那这种情况会对我们的求 有什么样一个影响呢?我们来看一下我们人工变量的一些情况啊。首先我们看一下什么时候需要构造我们的人工变量,也就是说如果我们的系数矩阵中 不存在单位矩阵,说我们添加了松石变量之后,还是找不到一个单位矩阵,这个时候我们就给他添加一个非负的人工变量,注意添加的人工变量也是要求非负啊,这样我们就可以给他构成一个单位矩阵 哎,但是呢,我们来看分析一下人工含有人工变量的时候,我们最有解的一个情况,如果我们的线性规划问题有最有解,那么他的一个人工变量一定是为零的。也就说 如果你的追由解中含有人工变量,说明你这个追由解并不是追由解啊,你说你是没有追由解的 好,那么其实给我们提供了一个解题思路对不对?哎,你人工变量你要有自由解,你人工变量一定是为零的,那我们怎么去求解呢? 就说我们要使人工变量为零,也就说因为我们添加人工变量,最开始他是作为一个机变量的对不对?那我们要尽量的让人工变量从机变量中出机,让他变成非机变量。 最后我们求解,哎,我们的基本可行解动飞机变量都是等于零的,这样是不是就使人工变量为零呢?好,那么我们的求 具体的求解方法呢?可以分成大 m 法和两阶段法。接下来我们具体的来看,首先我们来看大 m 法, 我们的大 m 法呢?假如说我们的原问题是求目标函数是求一个最大值,那我们把在他的一个约束条件中加入了人工变量之后,哎,我们构造出了一个哎可行机, 这个时候呢,我们又要做一个什么样的改变呢?我们注意要在目标函数中我们人工变量对应的系数,如果原问题是求最大值, 那么你人工电量的系数应在目标函数的系数应该是负 m。 我们这里的 m 是一个任意 大的一个正数,你不用哎,不需要知道他具体的值是多少,你就可以把它想象成反正是比你解题过程中所遇到的正数都要大的一个数就可以了。 那么这个时候我们想一下,目标函数中你要求最大值,你目标函数中减了一个任意大的正数,那你要使目标函数实现最大化,你是不是就一定要使人工变量从积变量中换出才可以啊? 同样的,如果我们语言问题是求最小值,那么这个时候我们人工变量在目标函数中的系数,我们要设为 a m, 也就是说要加 m 乘以一个人工变量,这个一样的,你目标函 说要求最小值,而你给他加入了一个非常大的正数,这个时候你要实现你目标的最小化,你是不是也一样要将我们的人工变量从基变量中换出,对吧? 好,这就是我们的一个思路。那具体的我们来看一下如何用大 m 法进行求解。 我们还是以利利一为例啊,我们先把它画成了这样一个标准型,接着 因为我们在现在这个标准型中,我们找不到一个可初始的基本可行解,不能够很容易的找到一个初始基本可行解,对不对?那么我们就给他添加人工变量 x 六 x 七。注意,我们要使人工变量, 因为我们语言问题,目标函数是求最大值,所以呢,我们要在此时目标函数中,哎,人工变量的系数设为负 m, 这里的 m 就是一个任意大的正数,从而我们看一下我们改后的一个数学模型是怎么样的, 一定要标明 m 是任意大的证书啊,注意,这里一定是减 m x 六,减 m x 七。好,那么我们后续的求解过程呢,就是来求解这个大 m 法的数学模型就可以了, 我们来看如何求解,和我们单纯刑法就基本上差不多了啊,第一步还是要构建舒适单纯刑法啊,把我们的决策变量表示出来,以及我 们决策变量在目标函数中的价值系数也要表示出来。注意, x 六 x 七,它们的价值系数分别是负 m 啊, 我们的哎系数举证也表示出来,我们的长数项哎,长数项链就代表的是我们的初始基本可行解。诶,在我们初始单词形表中啊,它代表是我们的初始基本可行解 好,以及我们的基变量和基变量在目标函数中的系数都表示出来,这样我们就把初始的单纯型表构建好了。 我们第二步一样的要求减元数,并且判断我们此时的减是否为最优减,我们目标函数是求最大值,我们的 sigma j。 注意,还 记不记得 c 干嘛借,如何求的 c 借减去 c i 乘以 a i 借之和。比如说我们这里的三减二 m 怎么求的 三哎,他就应该等于三,减去负 m 乘以一个负,四,哎减去四 m, 再减去零乘以一,哎,减去零乘以一,减零再减去负 m 乘以二,哎,就是相当于加上二 m, 每一个 segment 减就这样计算出来。计算好之后,我们是不是要进行一个判断,判断我们的是否此时的基本可行减,是否为最优减。那我们来看一下含有人工变量的时候, 我们的最优解如何进行判断呢?注意我们这里还是以目标函数求最大值的来讲解啊。我们来看一下, 如果我们的检验数都满足 sigma 键全部小于等于零,并且,哎,注意这里是和我们没有人工变量的一个差异啊。红色文,红色字体表示我们与我们上一节课讲的判断检验数中的一个差别。 我们先是要求 sigma g 全部小于等于零,并且我们的机变量中要没有人工变量,这个时候我们才能得到最优解,那最优解的情况也是一样的,如果非机变量的解数都 小于零,那么就是唯一的作用减。如果飞机变量的减减数有为零的,我们就是一个多重减, 那如果我们的检验数虽然都满足了 sigma 键小于等于零,但是我们发现机变量中有非零的人工变量,这个时候我们就说没有可行解啊,我们的问题是没有可行解的, 那如果说我们减约数大于零,并且我们对应的哎,我们的系变量 x, k 的系数列项量全部都小于等于零,这个时候我们称为叫做哎无借减,这是和我们 普通的单身刑法是一样的啊。好,我们来看一下我们此时 sigma g 是属于什么情况。 三减 m 是一个任意大的正数,那我们的负 m 是不是是一个非常非常小的数?负数,那你负二 m 也是一个非常非常小的负数,那你加上一个三也是一个非常非常小的负数,对吧?所以三减二 m 为负, 那 m 是一个非常大的正数,二加 m 肯定是也是一个非常大的正数,这里也一样, m 是一个非常大的正数,那你二 m 是一个更大更大的正数,对吧?即使你再减了一个负一,那你也,哎,对它的影响不大,还是一个正数 啊,负 m 为负。这个时候我们发现我们的减元数没有满足全部小于的零,并且,哎,我们 大于零的减元数,他所在列的系数列项量也并不是全部小于等于零,说明我们还没有得到这由减,也并不是无借减,我们要继续进行下一步,那我们要进行一个基变化, 这边画的时候我们要选择什么?我们要判断 sigma 界选择 sigma 界最大的, 哎,我们刚才讲了这两个为正,谁更大一些啊?二加 m 还是负一加二 m, 一定要记住, m 是一个非常非常大的正数,你这里二 m 又是一个 m 两倍的非常大的增数,乘了一个两倍,是不是非常大更大一些?所以他应该是,哎,我们相要大于二加 m 啊,你实在不知道怎么闭上,你就假如说 m 可以等于一万十万啊,去,哎,比较一下你就知道了啊。好, 那么我们选择它 sigma 界最大的列的变量 x 三作为我们的近机变量。接着我们是不是要判断我们的初机变量?哎,那我们要计算我们的 sita i c 台怎么计算?我们的 bi 除以 aik, 我们四除以一等于四,十除以二等于五,一除以一等于一, 然后选择 cta i 中的最小值一所对应的行变量 x 七作为初级变量,对不对? 好,这样我们确定了主圆出机行进机列的交叉位置就是我们的主圆。然后我们要怎么样? 是不是我们要哎进行机变化,构建一张新的大学型表,我们 新的基变量有哪些? x 六 x 五不变,只有我们 x 七已经由 x 三来代替了,那么这里的系数也要表示 x 三的价值系数是负一, 然后我们这里的系数就要以主元一为核心,进行一个初等的行变化,让主元元素变成一,主元列的其他元素变成零。好,这里我也就不再细讲了啊, 好,那么这样我们又得到了第二张单算心表,我们继续哎,是不是要重复我们步骤二、三,从我们要再次计算检验数好,计算出来,我们再来判断我们的检验数是否满足全部小于等于零。 哎,五减六 m 肯定是为负,对吧?五 m 为正,负 m 为负,一减二 m 也为负。我们发现有还有为正的减元素,说明还没有得到我们的最优减。那么我们要以哎 最大的景元素,它所在列的变量作为新的禁机变量,再次计算我们的 cta, 选择 cta 中的最小者五分之三,它所在 旁的变量作为初级变量,再次进行一个迭代,这个时候主圆哎就是我们的这里的五,那么我们再次构建一张新的表,这个时候我们的基变量应该是 x 二, x 五, x 三呢? 以组元五为核心,哎,进行一个初等行变化,这样我们又得到了第三张表,再次计算我们的检验数,哎,我们来看一下,这个时候检验数 m 为正,那么负 m 为负,一减 m 也为负,但是我们这里还有一个五减元数,还有为正的,对不对?虽然说我们发现看一下这里的我们的计变量已经没有人工变量了,但是我们还没有得到最优解,我们还要继续进行 叠带,我们的 a 选择结数最大的,它所在列的原变量作为近期变量, x e 作为一个新的近期变量,再次计算我们的 c 塔 i cta, 注意这里为负,哎,就直接不不用计算啊,我们只寻找为正的系数, 五分之三十一除以五分之三等于三分之三十一,那这个时候我们 x 五又作为我们的初级变量,好, 进行一个基变化,再次以五分之三为主元进行一个初等行变化,得到我们新的单纯新调。最后我们再次计算我们的 c c 个码记,好,我们判断一下,最后 c 个码记 负五负,哎,五减 m 为负,三分之三十八减 m 也为负,满足全部小于等于零,说明我们已经得到了最优解,对不对? 好,那我们的最有解是什么呢?我们来看一下是唯一最有解还是多重解?我们的飞机变量是不是 我们的飞机变量是不是?是全部飞机变量有哪些?哎, x 四 小于零, x 五小于零, x 六小于零, x 七小于零,说明我们的飞机变量全部小于零,我们得到的是唯一的最优解,对不对?那么最优解是谁?就是 x 一等于三分之三十一, x 二等于十三, x 三等于三分之 十九。那我们的目标函数就是把我们 ax 分别带入到目标函数中,求出来最大值应该是三分之一百五十二。注意,我们这就是我们大 m 法来求解含有人工电量的进行规划问题 计算呢,相对来说比较繁琐,那么我有一个小小的呃,窍门嘛,可以减少计算量,就是我们 这里我们看第一步,我们在第一张表中 x 七作为了初级变量之后,对不对? x 七作为初级变量之后,我们的它永远注意我们的人工变量,只要作为初级变量,它不可能再作为近级变量,所以呢, 我们他作为初期变量之后,这一列就可以不用再计算了。同样的,我们在第二张表中 x 六又作为了初期变量,也就是我们的人工变量,所以我们后面,哎,第三张表和第四张表中 后面两列人工变量所在的列我们可以不用计算了啊,就是你如果要想减少你的一个计算量的话,是可以不用计算的。好,这就是我们的一个大 m 法。
运筹学一刷而过,新的一节呢,咱们来看一下线性规划问题的数学模型。首先呢咱们先来看一下这个考点分析啊, 那么本音节课呢,他主要是出现在这个大题里面的啊,那么他是先去建立这个模型,接下来呢你再通过一些方法进行一个求解,所以呢这是大题里面的第一步啊,先去把这个模型给他建立出来,我们来看一下这个模型的组成吧, 咱们孕中学的,咱们讲的是一个最值的问题啊,那也就是找一个最优的一个方案出来,一定是这个最好的方案啊,那这个方案的话,可能是你这个施工的这个费用是最大的时候,也可能你这个施工的费用呢是最小的时候,看你的需求是什么啊?那因为我们要做一个工程,比方说做一个工程吧, 比方说有这个什么项目经理啊,有这个工人呢,是不是?所以呢,咱们会有这个人员,不同的人员呢,他会有不同的工资需要你呢把他们结合在一起,找出来一种,哎,我能配比下来,我花费最少的一种情况,或者 是最多的一种情况,那么这个步骤呢,咱们就是去列他的目标函数,接下来呢咱们去列一下他的约束条件,因为完成一个项目你不可能全都是大头啊,对不对?不能全把这个领导给他安排进来,你得有几个工人啊,是不是?所以咱们对于不同的这几个变量呢,还要有不同的这些约束啊,我们呢要把这个不同的人员呢给他安排在一起, 然后呢去共同完成这件事情,所以呢就产生了这些约束条件,咱们用 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 二要干嘛?要大于等于零啊,所以的话 整个他的数学模型就已经列完了,哎,这个东西呢,就是咱们所说的最后的一个他的数学模型,哎,应该满足这样的东西,上面有他的目标函数,下面有他的约束条件,约束条件里面必须得包含,那这些普通的这些约束条件,你正规需要有哪些约束就得给他写上去。 下面还有一个恢复的一个情况啊,所以总共来说呢,是由这三个方面所构成,这就是你的数学模型,接下来咱们来总结一下, 总结一下本节课所学内容。那么咱们首先呢先介绍了这个线线规划问题的这个数学模型大概的一个样式,哎,它是由三部分构成的, 也就是你的目标函数,约束条件以及非符条件。那么在做题的时候如何去列这样一个数学模型呢?咱们也是分成了三步,第一步呢要先去设置他的这个变量,第二步呢去把你的目标函数找出来,就是你要求什么对不对?接下来呢去建立你的这个目标函数,也就是你要求什么东, 是不是你要把它给写上来。最后呢再去根据题目所给的要求设计出来它的一个约束条件,那么如何来求解,就是咱们下一个的内容。好了,本节课就到这里,咱们来看下一节。
同学们大家好,我是米然学姐,我将带你们用二十个短视频通关运筹学,助力大家一刷而过。这节视频我们来讲一下图解法的求解步骤。 线性规划问题有两种求解方法,图解法适用于有两到三个变量的问题,单纯性法适用于任意变量,但必须要将一般形式变成标准形式。当我们遇到只有两个决策变量的线性规划问题的时候,就可以用图解法来进行求解。 图解法有三个步骤,首先是根据全部约束条件作图来画出目标问题的可行域,然后画出目标函数的等值线,然后找出使目标函数达到最优的移动方向,然后将 等直线往最优移动方向平移,找到最优点,求出最优值。我们用图解法来求解一下下面这道立体。 首先我们画出坐标系,然后第一步根据约束条件来画出可行欲。第一个约束条件是 x 一加一点九, x 二大于等于三点八,我们画出他的等直线, 因为这里 x 一和 x 二前面都是正号,所以在这条直线的上方, x、 e、 x 二都增大,是满足大于等于三点八的区域。同样做出第二个约束条件的等直线,它的曲值范围是在直线的上方, 那第三个约束条件取置范围在直线下方,最后一个取置范围也是在直线下方。最后这四个区域重叠的部分就是 这个线性规划问题的可行域,也就是这里的四边形区域。那第二步要做出目标函数的等值线,这里目标函数是二二, x 一加 x 二,我们让他等于零,然后判断他的最优移动方向, 因为目标函数要求的是最大值函数 x, e, x 二,前面也都是正好,所以在 x e x 增大的时候,目标函数也是增大的。也就是说在等式线向上平行移动的时候, x, e, x 增大,目标函数就去进最优。那第三步, 将目标函数等直线往最优移动方向平行移动,计算他在可行预的每一个点内的函数值,然后找到最大函数值。一般来说,我们只需要在可行预的 每一个顶点分别计算他的函数值。呃,然后找出最大或最小的,也就是最优值就可以了。那这道题在分别计算之后,我们可以看出 目标函数在这一点就是七点六二这一点的时候取得最大值,那这点就是这个问题的唯一最优解,最优值是十七点二,那么这道题就得出答案了。 最后要提醒大家,用图接法作图的时候要注意三点,首先是可行解的区域一定要画正确了,要准确判断约束条件大于等于的方向和小于等于的方向。 第二点是目标函数的移动方向一定不能画错,要看清楚他是最大值函数还是最小值函数。最后一点就是目 标函数的直线一定是要平行移动的,不能出现偏差,否则最后我们算出来的直也是会有偏差的。这里记得截图保存,下一节我们会讲解图截法的几点启示,记得关注我,带你轻松通关运筹学!
嗯,大家好啊,承接上面两个视频,这节课给大家带来的是运输问题解的调整这块内容,如果同学们觉得 up 讲的还可以的话,点个赞,关注一下,多发弹幕和评论互动一下,有问题私信我都会回复, 觉得哪里讲的不好我都会吸取经验。话不多说,开始今天的内容。嗯,今天这道题是华南理工大学二零一三年的考研试题。嗯,我这道题来源是从梅书文老师的作本, 嗯,运筹学解题技巧归纳里面摘取的,然后这本书很好书,有需要的大家可以买来去参考一下。然后,嗯,我是直接就,嗯,先去把他那个嗯初始调运方案先给 摘过来,这样就不算了。前面两个视频你教他一下怎么算了,我就直接摘就过来了, 我就直接摘取过来啊,一二四五一四。嗯,这就是初始要用方案。嗯,如果不知道怎么求的话,可以去看一下。来,我去我主页看下前两个视频,有给大家详细讲解怎么计算, 然后结束。嗯,我也不算了,然后直接就啊,直接就 再去过来。然后啊,你们会看这个减数,通过会发现这有个减减数为负数负一啊,这是个运输问题,运输问题是个机械化问题,减减数要求都大于等于零,但是你这里出现的负一是小于零的,所以说 现在不是自由调音方案,需要进行解的调整,这是我们今天要讲内容解的调整,然后我们进入解的调整的内容。 嗯,介的调整呢是?嗯,运用的是必回路法,然后他是在初始调运方案的那张表上进行的,你要注意分清楚啊,我先给他画一下 啊,这张表是检验数表,一定要分清楚,一定要分开,单单独换。这张表是出这张表是初始调运方案的表,你的你的,你的,那个简单调整的那个必回入法是在初,嗯,是在调运方案的那张表进行的,千万不要在检验数那张表进行, 这一定要切记。在这里还钓鱼,你发现负一吗?就是在, 在啊,在这个位置是这个位置,对吧?我们要在这个位置他减速算负数,那我们以这个位置作为掉路格作为起点,然后使用必回路法,必回路法在上节课,那个在那个什么,嗯,算减速,那节课上面应该讲过了,然后现在就是这样子,必回路一下, 嗯,必回路线,然后然后同理。嗯,掉入格是加号,转一次,弯减一次,再变一次,再变加减加减,然后我们取选取带负号箭头的,这这这两个格一定选取带负号箭头。这两个格子里面他他有两个调音量吧? 一个是一,一个是四,选起他们调运量里面最小者一四,那么肯定选一,对吧?那么做一,那么我再给他列张表, 呃,三百张表,就是我们调整后的那个调运方案,那么我们我们调整量就是一 上面已经比出来,上面这个比比的方法是调整量,就是为了找出调整量是多少,那我们这里就是,嗯,加一减一,加一减一,那么这应该是一一减一没了,那么就是三六, 然后再检查一下,发现是没有问题的,然后就是那么这一张表,好吧,就是我们调那个调整后的调音方案, 你调整后干嘛呢?然后再重复上面的步骤,再继续算减数,嗯, 用微释放,这应该是再用微释放,因为第一遍初始调用方法你已经用了一次微释放了,再用微释放计算 检验书表,嗯,不会用微书法算的话,就主页,我看完上一个视频都已经讲解过了,我就直接用了。在这里 这视频主要讲解是解的调整,就当你检验数出现了复数情况下,就是出现了小预定情况下,就要进行解的调整,用的方法就是必回路法。 ui pj 零零零零零 零零四六七风十一。 此时你会发现可以观察现在算出来减数表,新的这张减数表里面发现所有的减数都是大于等零了,说明他此时什么已经满足了最优调研方案的条件。 就写一句话,因为此时减元数表中的减元数,嗯,均大于多零固,此方该方案一定是最后调用方案。那么此时我们那个这张这个解解的调整只要调一次就很简单,那么有时候我们会遇到题目就会出现,嗯,随便举个例子吧,如果这是负一,那么我们就要继续重 重复上面操作,又去去那张吊运表里面,到这个位置作为掉入量,又又寻找必回路法去寻找去,嗯,去重新用必回法去调解的调整,然后再算减一数,然后再再去判断, 直到就到最后刚刚那样子,前数全部大于等于为止,就算出了最后交易方案,那我们再去算他的 最后运价。运价其实就是你的运量成硬的掉成硬的运价,总运价的运量成运价的全部相加,那么也就是, 那就是一乘十,加上二乘六,加上一乘七,加上三乘五,加上六乘九,加上四乘五,然后算上就是他的总运价了。那还是要提醒一下你这个运价是一定在那个调运方案,调运方案那张表去乘,你千万不要用这张表去乘, 这张表是结束你用去,因为上面这张表是调运方案的表,调运方案的的 里面这个数字是他调运量,上面右上角这个是调运加,他俩相乘,那全部相加才是他的总运加,那你下面这张表里面的格子是什么?这个是简约数,它代表是不含不同的含义好吗?所以说不要填,填错 那么几个调整。我给大家讲到这,下节课就给大家讲啊,特殊的运输问题,比如求最大值的问题该怎么算?那后面题目会越来越复杂了。好,谢谢大家,今天就讲到这里。