运筹学教程第四版习题答案

下面我们介绍指派问题以及指派问题的求解方法。 指派问题是一个典型的应酬学问题， 那么第一个什么是直拍问题？ 我们举个例子，给个起震 say， 这里面的元素啊是二十五、三、四 十四、十四、十五、 九、四十六、十三、 七、八十一、十九。这个时候给一个表格，表格里面有 些数字，这个数字的实际含义可以表示成假设你是一个老板，你有四项工作要安排人做，你手下恰好有四个人，你就想每个人做一样工作。 第一个人做第一项工作需要花费你两块钱。如果你请第一个人做第二项工作，你需要花费十五块钱。如果你请第一个人做第三项工作，你需要花费三块钱。 如果你第一个人做第四项工作需要花费四块钱，第二个人做第一项工作，你要花费你十块钱。类似的就是每一行表示每 每个人的开销，那每一列表示每项工作。如果第一个人第二年，第三、第四他们做的话，需要的开销，你就想使得总的费用最少，你只想使得总的支出最少。 我们就按最简单的一个指拍方式来安排工作，第一个人做第一项工作，第二个人做第二项工作，第三个人做第三项工作，第四个人做第四项工作。那么这样我们总共就需要花费二加四加十、六加十九块钱。 这个问题的要求就是每个人只能安排他做一项工作，不能多做，也不能少做，每项工作都要有人做，这就是指 拍问题。那么实际上指派问题就相当于在这个几正里面，在这几正里面你选择四个数， 这四个数啊，位于不同行、不同列使的四个数字之和最少，就是从最终选择 卫衣不同行、不同列 的四个数字， 使得 总和最小。 那么选择哪四个数字位于不同行、不同列这个总后是最小的。我们可以通过观察知道一些信息，但是如果这个矩阵比较大，你可能很难观察出来了。 那怎么求解呢？对着我们要求解方法， 来对求解方法，我们讲匈牙利方法， 匈牙利方法是这样的，首先我们注意到 第一个人如果做第一项工作就需要花费两块钱，做第二项工作花费十五块钱，做第三项工作需要花费三块钱，第四项工作需要花费四块钱。也就是说你第一个人总归要做一个工作，他至少要花费两块钱， 那我就把第一行元素都减掉。二，把第一行的元素用啊，表示行都减去二，那我们这样就得到了零十三。一。二，那什么意思？就是说 第一个人做的事情至少要发两块钱，如果他做第一项工作，就除了这两块钱，不需要多花费钱。如果做第二项工作除了这两块钱，需要多花费十三块钱，如果做第三项工作， 那么就需要多花费一块钱，如果做第四项工作需要多花费两块钱，也就是说选择的四个数字之和我都啊 选择的四个数字之和至少是二。你第一行，你至少要选一个数字，那至少是二。那么看看第一行选的数字会多出来多少 多少多少。因此我们要从啊原来几这里面选择四个不同行、不同列的数字，使得总和最少，就必须在第一行选择一个，那就相当于在这里的第一行要选择一个数字，选择的数字再加上二，就是最后的总和了。 那类似的，对第二行来说，我把第二行也减掉他的最少的啊，最小的元素是 第二行的这些元素是这个是，那么就得到了六零十十一。那这个道理也是一样的，就是第二个人他总归要做一项工作， 那第二个人的费用呢？至少是事，我就把这个事除掉，那么看看他剩下还要多给他多啊，还要多支出多少钱？如果他做第一项工作就多支持六块钱，如果做第二项就不需要多支出。 那类似的，第三行我要减掉他的最小元素，最小元素是九，那么这样一减的零 五七四，那第四行我也减掉他的最小元素，第四行的最小元素呢？是 七，那这样就得到了零一四二，得到一个新的急症。 那我们看看，如果新的几个里面选择四个不同的数，选在位于不同行不不同列的数字，数的总和最小，那么原来这里面选择的四个数字，不同行、不同列的最小，就要加上这些就可以了。好， 那类似的对列我们也这样处理，比较，第一项工作他总归要安排哪个人做，第二项工作总归要安排哪个人做，第三项工作总归要安排哪个人做 啊？我们把这个数字改成十三，在这十页。好，第四项工作 总归要安排人做。我们看看第三项工作，不管安排哪个人做，他至少都需要花费四块钱， 如果让第一个人做，就要花费十一块钱，让第二人做花费十块钱，第三、七块。第四，也就说对于第三项工作，我不管哪个人做，我至少要花费四块钱，那我看看啊， 第三项工作如果安排第一个人，除了这四块钱，他还需要多花费七块钱 啊，最多花费六块钱，这三块钱零啊，那第一列啊，第一列零六零零，第二列十三零五一， 对第四项工作也是这样的，对第四项工作不管安排哪个人来做，至少需要花费两块钱，那么我们看看他除了这两块钱还要超出多少？零九二零， 那这样，原来在这个几这里面找四个数字最小，那就相当在这里面找四个数字最小，在这个数字最小啊，我们注意到 第二行只有一个零，如果说我就让第二个人做这项工作，会我选择这个数字，哎，第三行只有这个零，我选择这个数字，第一行有两个零，那么可以选择这个，也可以选择这个选择的一律有两个。第四行有三个选择，一律有三，但是因为前面接 选的这两个，所以这第一点你这个不能选，你这个不能选，那么剩下的，那么我们再看看剩下的，我们可以选这一个啊， 啊，那这个就不能选这个，选这个，那这样我们就找到了四个位于不同行不同列的元素，都是零元素，都是零元素，也就说任何费用都不超出来，那这肯定是最最少的数字之和， 也就是说我们应该选择啊，应该选择原来几正里面的，原来几正里面的对应的这么四个元素， 第一个是这个是，第二个是这个是，第三个是这个九， 第四个是这个零，那这样四个数字之和最小的，那就是四加四、 四加四加九、 加十一啊，等于二十八、二十八。 那我们再看一个例子，再看一个例子，如果说啊，这样的表格或者矩阵是这样一个矩阵， 但是说我们的 c 是这样的，是五行五列的 是十二七九七九八九六六六 七十七、十二、十四、 九十五、十四六六十 四、十七十九。如果说举正 是这样的这个矩阵，我们也称为效力矩阵。那类似的，我们按照前面的方法， 这找到每一行的最小数，找到每行第一行的最小数是七，第二行的最小数是六，第三行最小数是七，第四行的最小数是六，第五行的最小数是四，也就说 这五项工作你至少要罚这么多钱，这，那看看还会不会超出？那我们就对这个几针变换，那就是第一行减掉七， 第二行减掉六，第二行都减掉六，第三行都减掉七，第四行都减掉六，第五行都减掉四，那这样就得到了急症，五零二 零二二三零零零 零十五零十 五七二 九八零零四零六 三六五，也就说至少要发这么多钱。让我们再看看每一列，每一列的最少费用都是零，所以不需要再进行变换，再进行变换。 好，我们现在来圈一下这些零，嗯，第三个人呢？啊，他只有一 一项工作费用为零，这这个全了之后，第一项工作就安排我们把这个化掉，把这化掉，那么对第二项工作只有安排第二个，对，安排第一个人做，他才为零，然后把这个化掉， 然后啊第五项工作只有安排第二个人，他的费用为零，那么既然第二人做了第五项工作，他就不能做前面两个工作， 那么第三项工作啊，只能安排在第四个人为零，那么第四个人就不能做这项工作啊，刚才这个圈出来了，嗯，那这样话，我们总共只圈出了四个零，那没有找到位于 不同行不同列的五个零，如果是五个零，那就不需要多任何费用， 那怎么办呢？那也就是说我们想啊， 继续按照前面的方法进行变换啊，画出更多的零，画出更多的零，那么这里圈出了四个零，我就想啊，把这里面的所有的零元素都不变， 把这所有颜色都固定出来，再通过每一行每列都减掉一个数，那么我用直线把这些零全部固定住，我们想用最少的直线把它固定出这圈中的四个零，我就用四条直线把， 把这个固定出。 好，那这样话，我们用了四条直线就把所有的零都给固定住了，都给固定住了， 那么剩下的这八个数没有被固定住，剩下八个数字里面最小的啊，是最小的数字是二，是二， 也就是说对第三个人来说，对第三个人来说， 如果不考虑第一项工作的话，他安排其他工作，他至少需要花费两块钱，需要花费两块钱，那也就是说我先把这两块钱啊预算出来， 那么这样就变成了啊，我第三行都减掉二，第三行都减掉二啊，这样第三行就变成了负二八三五零啊，八三五零， 那意意味着，如果说啊，我的总费用支出两块钱，如果安排第一个人做的话，啊，安，安排第三人做第一项工作，那么他就要退回两块钱，如果安排给啊， 如果第三个人做最后一项工作，那么他不需要费用，那这个这项费用，这样，这样我们就把这个哦，这个元素变成零，零了，把这个二就改变成了零，哦，变成零， 那第五横 我也剪掉啊，我也剪掉这第五五个人啊，我也先给他两块钱， 如果他做第一项工作，他就退回两块钱。做第二项工作，我还再给四块钱，再给一块钱，四块钱，三块钱，其他的元素是不动的。五零二零二二三零零零 九八零零四。我们说前面你这个线把直把这一个啊零度固定住了，那么第一行固定住了，第二行 固定住了，第四行固定住了，但是第一列固定的这两个零又变成 for 了啊，变成相同的 for 啊，就这两个数，没有，本来应该是零，变成了 for， 没有固定注，没有固定注，因为它是相同的 for， 所以我们将第一列， 我们将第一列用这个表示第一列，我们把它加上，哦，加上，也就说对第一项工作，对第一项工作啊，第一项工作，大家都啊， 先拿出啊，两块钱给给老板，拿出两块钱的给老板，那么这样第一列就变成了啊，第一列就变成了七 四零九零，七四零九零，那这样话，我们就知道这个零元数就变得更多了，零元数变得更多了，好，我们将这里改成 七四零九零 七四零十一零， 我们 就将这里改成七四零十一零，这就相当于第一列加上了二。好，那现在我们看一下， 现在就说原来的零都啊，没有变啊，但是这个二又化成了零啊，注意这个二最小 的元素，他变成了零。现在我们再看一下啊，再看一下第 第五项啊，第五个人才只有做第一项工作才为零，所以我安排第五个人做第一项工作，那这个就划掉， 现在我们看看第二项工作只有安排第一个人做，他才啊，费用为零，那么第二项工作安排第一个，第一个人就不能做这项工作。 来，现在我们看看啊，第三个人，第三个人，嗯， 第三个人现在说他不能做第一项工作了，那他只能做第五项工作为零，那我就他不能啊，第五项工作就不能安排第二个人做了，把这个零化掉。 好，这已经圈出三个人了，还剩下啊，第二个人没安排和第四个人没安排，然后可以安排 六个人啊，我让他做第三项工作或这个都可以。如果安排做第三项工作，那他就不能做第四项工作，那第三项工作已经被第二人做，他就不能被第四个人，第四个人只能做。这样， 这样我们就恰好圈出了五个零，位于不同行不同列的啊，五个数，也就我们对应圈出的是这个啊，七啊，啊，零啊，六、 九六啊，全程的这么五个数字，他们的核实最小最小。 那这个思想就是啊，只派问题的匈牙帝啊。向上访， 我们总结一下这个 求解方法的步骤。 第一步呢，先将 c 每一行和每一列都减去， 将没行没列 中的所有元素 都剪去 该行该练 中的最小该行或者该列啊每一行或每一列都减去该行或者该列中的最小元素。第二步，如果 圈出了啊，圈出了啊，如果是 n 行， n 个零，则结束。 如果没有穿出 n 个零，那么我们用不要去穿出了啊， 否则我们进了，下一步， 我们找一下这里设圈出了 k 个零，那么就用 k 条直线 拍一条直线，我们把所有的零度固定住，叫做覆盖零， 铺盖全部的零， 那未覆盖住的 为覆盖度的行或者是列，都减去 读前去 所有未未覆盖的元素中的最小元素， 这小元素。然后啊，还有并将复数，复数也要并将复数所在的 横或者是裂都加上 这个最小元素， 将其发为零。 那么这样就是多出了啊，一些零元素啊，多出演一些零元素，八百零。那么回到 有一道二继续做，有一道二紧张，这是第一步， 第一步，先把每一行都减掉，这些元素，第一行减掉，第二行减掉，第三行减掉，第四行减掉啊，在第一点减掉，第二点减掉，第三点，第四点，第五点都减掉。 然后我们圈圈出了四个零啊，没有圈出五个零，因为有五行，这样我们就用四条直线把所有的零都覆盖掉，那么没有覆盖住的八个元素里面，十五七个里面找到最小的啊，八 个数里面的最小的数二。然后啊，将没有覆盖住的第三行，第五行都减掉二，但是会出现负二，对，出现负二，我们把这里第一列加回负二，那么这样就多出那些零。我们继续去圈啊，如果圈出了五个零，那就结束了。 这就是指派问题的求解方法。 那么具体的啊，一些啊细节和一些结论，大家可以看课本，或者看我更详细的视频。

大家好，下面我们来给运筹学划重点，运筹学使用最广泛的教材就是清华大学出版社的运筹学教材编写主编写的运筹学的第四版，他的封面是这样的， 这个书有两个版本，一个是加了本科版，一个不加本科版，那么我们给他发重点的是不加本科版的，这是一个比较详细的版本，发重点的目的是为了更好的指导大家学习，指导大家更好的通过考试。 那么在运筹学学习过程中啊，有哪些是我们重点要学习的，有哪些是重点要考试的内容呢？下面我们跟大家简单的介绍一下。首先我们整个概况一下，第一章序论基本上不会考，那么第二章是最重要的， 第二章是非常重要的，那么考试的主要内容都是集中在第二章里面，第二篇，特别是第二章啊，第三章这是经常考的啊，第四章也会考，第五章也会考，但呢，因为 这些内容都是我们要讲的内容，所以都会涉及到考试，都会涉及到，那么很多学校可能啊，在上课时候只会上第四，第五，第六，第七， 第八，第九，第十啊，十一章啊，那么上到十二章，那么大概一个学期的课就结束了，那么第七篇以后基本上都属于第二个学期的课。好 好，我们来看一看第一篇序论，那么在序论这这里面我们跟大家说的，这里只是大家看一看就可以 没了，这里根本不会考，只要大家了解一下运筹学，这里其实都没有必要看啊，这里都不会考，这是第一章的重点啊，第一章可以说只是大家知道运筹学是一个很有用的课程，运筹学是 一个很好的课程，运筹学的知识比较广泛，运筹学的发展也比较啊长，这是第一章的重点，第一章其实就是没有重点，他也不会考。

第五章线性目标规划在线性目标规划这里面啊，这个数学模型很重要，怎么写出它的模型，要明白这些意义，只要明白就可以了，知道什么是绝对，什么是硬约束，什么是软约束，这是非常重要的一个意识啊， 这个是非常重要的，什么是正负偏差这个含义啊，优先因此啊，目标函数怎么定啊？这个是没有必要看，你只要能够把这个例子看明白就可以了啊，把这个例子对照一下，哪些是业余时，哪些是软元素，注意这个模型怎么写啊？一、 一般的没有必要，那图解法是容易考到的，因为图解法是可以在短时间内做出来的，所以不用费考，所以建议大家重点看看这几个例题啊，看这个几个例题啊，至于说单词写法，你只要知道思想，但是来说考试一般不会考，为啥呢？因为 单证刑法在前面已经考过了，如果这里再考单证刑法，那这个计算量太复杂，计算量太大，所以一般的话老师也不会考这边单证刑法 当然偶尔考到他也并不难啊，主要大家注意看看这个立体就可以了啊，当然我们认为啊，不太会考这个，这个就是说自己应用几率的话，那我觉得更不会考到了，只要大家会建模啊啊，像这个每一张的应用几率你都可以不看，只要你会去做练习就可以了啊，这些助记也没有什么用 啊，所以说具体建议大家好好做一做这几个计算题啊，这个都是跟前面一样的啊，特别是某一个问题啊，你怎么写出他的目标规范模型来，对吧？以及怎么去求解他啊？求求他恋爱期都建的好好做一做，因为这也是锻炼你剑魔的一个能力，剑魔你求解的能力。

我们第一个知识点是把它画成线标准型，然后首先我们来看将下列线型规划问题变成标准型， 首先看这个线性规划是最求 z 的最大，然后这个他目标函数，这个是他的约束条件，然后呢，首先标准型的条件其实就是求他的最大，然后并且让所有的约束条件就是这些地方都变成等于号。然后呢还有就是所有的决策变量均大于零， 这些变量决策变量均是大于零的，所以像看这个就不符合。然后还有最后一个条件是右端向为非负，右端向为非负，这个线性规划他这边是非负的，所以就不用管了，然后这个是最大，所以这也不用画了，然后加，就看这个约束条件化为等于号，还有所有 左侧边量都大于零，这里边 x 一和 x 都是大于零的，只有 x 三是无约束的，所以说就把 x 三变成 x 三撇，减去 x 三撇撇，让他等于 x 三，然后另其中的 x 三和 x 三撇撇大于零即可。然后 然后我们就看这个小于和大于等于，如果是小于等于的话，就要引入一个松弛变量，引入一个松弛变量 x 四，让他加上 x， 因为他是小于等于的，所以如果要是加上一个正数的话，他肯定还会更小于等于，所以说就让他加上一个 x 四， 这边大于等于三，因为他是大于等于，所以减去一个大于零的数，他肯定还会更大于，所以就让他减去一个 s 五等于零，然后这个时候这个约束条件就变成了，这个就 变成了这样，然后呢所有的决策变量均大于零，此时他的标准型就变成了麦克斯 z， 等于这前面都不变。负二 x 一加上 x 二，加上三倍的 x 三片减 x 三片片，然后加上零， 这个地方是零，因为他本来就是不存在的，所以说就让他前面系数为零，零 x 四加上零 x 五。然后以上就是对标准型的求解。

同学们大家好，欢迎大家来到运筹学速成课，在接下来的三个小时里，我会和大家一起去学习运筹学的考点内容，争取让大家用最短的时间学会这门课的知识，顺利通过期末考试。 现在开始，请同学们跟着老师的上课节奏，认真学习每一章节的考点知识，课后再通过每一章节配套的讲义和题库及时巩固练习。相信通过这三个小时的学习，同学们都可以轻松通过期末考试。 我们的复习课主要包括以下几个考点，首先就是线性规划的基本概念和单纯刑法。线性规划问题可以说是我们整个运筹学课程的核心，他的求解方法是普通单纯刑法。后面我们学 习的队友问题、整数规划、目标规划和运输问题其实都是线性规划问题，只不过他们加上了一些特殊的条件，因此他们的求解方法也都是由普通单纯刑法衍生而来。 可以说普通单纯刑法是我们后面所有现行规划问题求解的基础，所以同学们课后一定一定要去题库里多加练习，直到完全掌握。 第二章对偶问题其实就相当于转变视角，站在对方的角度去建立一个模型，他其实还是一个现行规划问题求解对偶问题采用的方法是对偶单纯心法。 除了求解，队友单纯刑法还衍生出两个更深层次的问题，灵敏度分析和影子价格。这部分难度较大，同学们一定要认 认真学习。第四章整数规划就是在普通线性规划问题上加上了整数约束，这样变量就只能取整数。他的求解方法我们主要学习分支定界法和割平面法。 整数规划中有一类比较特殊，它的变量只能取零或一，叫做零一整数规划，这类问题我们主要采用匈牙利法去求解。 第六章目标规划则是在普通先进规划问题上加上了目标约束求解目标规划我们依旧是采用单纯刑法。 第七章运输问题其实就是一个系数矩阵非常特殊的现行规划问题，所以我们采用一种比较特殊的运输问题的单纯刑法去解决它，而指派问题又是一种比较特殊的运输 问题，同时他也是一种特殊的零一整数规划问题。可以看到我们整个运筹学主体其实就是线性规划问题进行求解，所以这部分的学习是非常重要的，他大概会占整个期末考试的八九十分的分值， 每一部分的内容都可能出一道十几分的大题，但同学们也不要被吓到，这部分在考试中其实都是有固定套路的，只要掌握基本套路和方法，大题肯定是没有问题的， 所以同学们一定要认真听讲，做好笔记。除了使用以上这些数学模型来解决管理决策问题之外，我们学习的最后一个考点网络模型则是采用图的方式来表示管理决策问题。我们需要重点关注的就是最短路问题的求解， 难度不大，但几乎是必考题，希望同学们一定要认真学习。其实运筹学一共也就这么多考点，而且难度不大，解题都有一定的套路，平时上课掌握的不够好的同学也不用紧张， 只要跟着老师一起学完这三个小时的内容，一定可以轻松通过考试。那话不多说，接下来跟着老师一起进入具体章节的学习吧！同学们好，今天我们来学习运筹学的内容， 我们将整个课程分为六张讲解，分别是线性规划、对偶问题、整数规划、目标规划、运输和指派问题以及网络模型。每一张中都有相应的考点题型，每个题型都有一两种解题方法， 同学们一定要认真听讲，争取在看视频的过程中就掌握所有的考点。每一章中的基础概念也会通过选择题、判断题和填空题等题型来考察。今天我们来学习第一章线性规划。 这一章需要我们掌握线性规划的数学模型的构成要素和特征，还要求大家学会建立线性规划的一般模型和化标准型， 也要学会用图解法和单纯刑法，求最优解。下面让我们正式进入第一章的学习。 首先我们通过例题一来学习数学模型的构建。题目说工厂每月生产 a、 b、 c 三种产品，单件产品的原材料消耗量、 设备台时的消耗量、资源限量及单件产品利润如下表所示。 三种产品最低月需求量和最高月需求量我们从题目中都得到了，让我们建立该问题的数学模型，使每月利润最大，大家可以先按暂停自己先思考一下， 现在我们来一起看一下。 我们知道因为产品的数量决定利润，所以我们先设 x 一、 x 二、 x 三分别为产品 a、 b、 c 的产量。为了使每月销量最大，我们根据单件产品利润列出柿子 x z 等于十 x 一加十四 x 二加十二 x 三，再根据资源限量列出前两个不等式，然后根据需求量列出下面三个不等式。 又因为产量大于等于零，列出 x 一 x 二， x 三大于等于零，这样模型就建好了。模型的建立是多数线性规划计算题的第一步，所以同学们一定要牢牢记住这个知识点。 接下来我们来学习数学模型的一些基本概念。第一点，线性规划的数学模型是由决策变量、目标函数及约束条件三个要素构成。刚刚的例题一中， x 一 x 二， x 三就是决策变量函数 z， 也就是式子 max z 等于十 x 一加十四， x 二加十二 x 三便是目标函数。不等式组为约束条件。 再来看数字模型的特征，总共有两点，第一，解决问题的目标函数是多个决策变量的限行函数。第二，约束条件是一组多个决策变量的限行不等式或等式。 注意，这里的目标函数与约束条件都是线性的。然后就是线性规划的一般模型的表达式。 假设线性规划数学模型中有 m 个约束，有 n 个角色变量，目标函数的变量系数用 c j 表示， c j 就称 为价值系数。约束条件的变量系数用 a i j 表示， a i j 称为工艺系数。 约束条件右端的长数用 b i 表示， b i 称为资源限量。这样线性规划的数学模型的一般表达式可写成下面这种形式。 同学们需要做笔记的地方记得暂停，把重要的知识点都记下来，学会建立线性规划的一般模型后，我们来学习图解法。图解法的第一步就是确定可行域， 也就是分别求出每个满足约束，包括变量非负要求的区域，它们的交集就是可行域。第二步呢，是绘制目标函数直线，我们先通过原点做一条 使量指向点 c 一 c 二，这个使量的方向就是梯度方向，是目标函数增加最快的方向。然后我们再做一条与这个使量垂直的直线，这条直线就是目标函数直线。 第三步就是求最优解，我们根据目标函数求最大值还是最小值来上下移动直线， 直线与可行域相交的点，也就是使得目标函数达到最值的点，对应的坐标就是最优解。 一般我们将目标函数直线放在可行域中，如果是求最大值，那么直线沿着始量的方向移动，如果是求最小值，则沿着反方向移动。接下来我们通过例题来加深 理解。例题二，求解线性规划。首先我们根据括号里的四个约束确定可行域，就是图中橙色的区域。我们过远点做一条使量指向 c 一 c 二，也就是点五二， 然后做垂直于该使量的直线，也就是目标函数直线。因为这里是求最大值，所以我们沿使量的方向移动直线，直线与可行域的边相交的最远点三二就是最优解。 将最由解带入目标函数，就算出最由值， z 等于十九，这样我们就解完了。考试时我们需要做出这样的图像，这里我们补充解的四种形式，唯一最由解、多重解、无借解、无 可行解，其中唯一罪忧解多重解的情况为有罪忧解无解解无可行解的情况为无罪忧解。然后我们再来看第二节线性规划的标准型。 首先我们要知道标准型长什么样子。大家记住这个口诀，最大等式双非负。 其中最大是指目标函数求最大值，当然也可以求最小值。等式是指约束条件都为等式方程。 双飞负是指变量 x j 和长数 b i 都大于等于零。这个口诀是我们判断标准型的关键点，有了这个基础，我们才会画标准型。接着就是画标准型的方法。这 这里我们给同学们例局六种常见的非标准形式，以及相应的划标准形的方式。第一，如果目标函数是求最小值，那么我们就将极小值问题化为极大值问题， 就是令 z 等于负 f， 把 mean f 变成 max z。 大家这里要特别注意一下他们的最有解相同但最有解的目标函数值相差一个负号， mean f 等于负 max z。 第二，如果约束条件小于等于常数 b i， 那么我们引入一个松弛变量 s s 大于等于零，这样就将约束条件化为 a i 一 x 一加 a i 二 x 二，一直加到 a i n x n 加 s 等于 b i。 第三，如果约束条件大于等于常数 b i， 则我们引入一个剩余变量 s s 也是大于等于零。然后将约束条件化为 a i 一 x 一加 a i 二 x 二，一直加到 a i n x n 减 s 等于 b i。 特别注意，这里是减去一个非负数。 第四，若变量无符号要求，那么我们可以转化为 x j 等于 x j 撇减 x j 两撇， x j 撇和 x j 两撇大于等于零这种形式。 第五，当某个约束是绝对值不等式时，我们一般先将绝对值不等式化为两个不等式，再分别 化为等式。第六，当长数 b i 小于零时，因为等式左边的细数可以是负的，但是左边的变量和右边的长数必须是非负的，所以我们在方程左右都乘以负一，将右边的长数化为正整数。 以上就是划标准型的方法，没有记住的同学记得拖动进度条再重新听一下。下面我们实操一下例题三，将下列线性规划化为标准形式。大家用我们刚刚讲到的方法尝试自己先做一下。 好的，做完的同学，我们一起对一下答案，看看你做 做的是否正确。没做完的同学不要着急，暂停继续做，我们一起来看。因为这是一个极小值问题，所以我们首先将极小值问题化为极大值问题。然后第一个约束条件为绝对值不等式， 我们先将其化为两个不等式，因为两个不等式都是小于等于二十，所以我们各自引入松弛变量 x 四 x 五，将其化为等式。 第二个约束条件是 x 一大于等于五，所以我们引入剩余变量 x 六，将其化为等式， x 一减 x 六等于五。 然后是第三个约数中长数负八是负数，所以我们在方程两边都乘以 负一，将右边长数化为正数，化成了负 x 一减八， x 二等于八。 最后，所有变量 x j 均大于等于零，这样就化为标准型了。因为我们需要先把数学模型化为标准型后，才能通过单纯型法计算。所以可以说，化标准型是我们运用单纯型法的基础。 接着我们来学习线性规划的有关概念。这个式子是前面线性规划标准型的矩阵形式。式中 a 是 m 乘 n 的系数矩阵， m 小于等于 n， 并且 r a 等于 m， 所以显然 a 中至少有一个 m 乘 m 子矩阵 b 使得 r b 等于 m。 这里还有几个需要记忆的概 概念。第一个概念是，当 a 中的 m 乘 m， 此举证 b 满足 r， b 等于 m， 那么我们称 b 是线性规划的一个机举证，简称 g。 当 m 等于 n 时，那么基矩阵为一。当 m 小于 n 时，基矩阵就可能有多个，但数目一定不超过 cnm。 第二个概念是，基矩阵对应的列项量称为基项量，其余列项量称为非基项量， 机像量对应的变量称为机变量，飞机像量对应的变量称为飞机变量。 然后是一些解的概念，可行解是满足所有约束式一点二及一点三的解。四、最优解是满足式一点一 的可行解，即是使得目标函数达到最大值的可行解。五、对某一确定的 g b， 令飞机变量等于零，利用式一点二解出 g 变量，那么我们称这组解为 g b 的基本解。 对任意一组基本解都有，基变量的个数等于约束条件的个数等于 m， 非基变量的个数等于变量的个数减，约束条件的个数等于 n 减 m。 六、若基本解是可行解，则称其为基本可行解。七、若最有解是基本解，则称其为基本最有解。解的关系是基本最有解是基本可行解，也是基本解，大家可以做一下比 g 还有其他几个概念。八、基本可行解对应的基称为可行机，基本最优解，对应的机称为最优机，最优机也是可行机。九、设 k 是 n 维空间的一个点级， 对任意两点， x 一、 x 二属于 k， 当 x 等于 a， x 一加一减 a， x 二属于 k， a 大于等于零，小于等于一时，则成 k 为突级。 从直观上讲，凸级没有凹入部分，其内部没有空洞，所以右边这两个图形都不是凸级。考试中可能会出选择题让同学们判断什么图形为凸级。十、设 x 一， x 二到 s， k 是 n 为欧式空间的 k 个点若存在满足 lemonda 一， lemonda 二到 lemonda k， lemondai 大于等于零，小于等于一， 那么打 i 的和等于一。使 x 等于 sigma k， i 等于一，那么打 i x i 则称 x 为 x 一 x 二到 x k 的凸组合。凸组合就是要满足两点，线性组合和系数和为一，这个一般不作为考点。 十、一、设 k 是突级， x 属于 k， 若 x 不能用 k 中两个不同的点 x 一 x 二的凸组合表， x 等于 a， x 一加一减 a x 二， a 大于零小于一，则 称 x 是 k 的一个极点或顶点。最后一个概念是线性规划的基本定理，这个地方大家一定要记住。定理一，若线性规划可行解， k 非空，那么 k 一定是突击。 定理二，线性规划可行解， k 中的点 x 是几点的冲要条件为 x 是基本可行解。 定理三，若限期规划有最优解，则最优值一定可以在可行解集合的某个极点上到达。最优解就是极点的坐标项链。 接下来我们继续通过下面的几道例题来理解概念。例题四，取 g、 b 一、 b 二分别指出 b 一和 b 二对应的基变量和非 基变量，求出基本解，并说明 b 一、 b 二是不是可行机。给大家一点时间思考并做一下。 好，我们一起来看一下。矩阵 b 一是取 x 一、 x 三的系数，所以对 b 一来说， x 一、 x 三为机变量， x 二、 x 四为非机变量。 我们令飞机变量 x 二、 x 四都等于零，就得到基本解为 x 等于十五零十零的转制。其中第一是可行机，同 因为矩阵 b 二是取 x 二、 x 四的系数，所以对于 b 二来说， x 二、 x 四为基变料， x 一、 x 三为飞机变料，基本解为 x 等于零，十零一百的转制。 b 二是可行机。立体五、现有线性规划问题，求出所有的基本解。基本可行解，并作图标出所有基本解所对应的几点。 首先我们先把线性规划模型化为标准型，并写出系数矩阵 a。 然后我们在草稿纸上列出所有可能的子矩阵，并计算他们的智， 除去 z 不等于 m 的矩阵，剩下的子矩阵就是基矩阵。同学们可以暂停自己算一下 本题的基，举证就是这九个，同学们可以自己对一下。 然后根据这九个矩阵，我们可以令飞机变量等于零，算出这九个机对应的九个基本解。基本解中满足所有变量非负这个条件就是基本可行解。 排除基本解中含复式的解，得到的就是本题的基本可行解。本题有这三个基本可行解。最后一步，我们作图标出所有基本解所对应的几点，这题就解完了。