导图社区 运筹学备考
- 245
- 16
- 3
- 举报
运筹学备考
运筹学课程的备考考点：100%规则、运输问题表上作业法、整数规划的应用、图与网络（最小路问题、最大流问题）、一台机器，ｎ个零件的排序问题、对策论、排班问题、自制外购问题、套裁下料问题、配料问题等。
编辑于2022-06-29 09:39:46- 运筹学
- 系统科学
- 万事法则（听说能解决90_的问题）2025.8.5
1）找个爱好，过好自己的生活。你必须为生活而工作，而不是为工作而生活。 2）他人如何度过休息时间、如何花钱、如何生活与你无关。聪明人会专心走自己的路，不去管别人选择了什么路线。盯着你要去的地方，不去理会别人在做什么。不去理会，你就更容易不去评判。一旦评判，你就会对自己进行分类，这就使你更难做到灵活，更难在各种情况下应对自如。评判别人反过来也会让你把自己关进鸽子笼——这可不是一个好地方。 3）得有一条线，你不能超越它。你得知道那条线画在哪里。别人不需要知道，但当他们要求你越过这条线时，你就可以告知他们它的存在。
- 塔勒布智慧箴言录 2025.8.6
1）历史上各种悲剧的源泉，不外混淆了别人的“无条件”与“有条件”。 2）只有当拒绝收下一笔钱比收下这笔钱让你感觉更好时，你才算是富有。 3）不要太过大声地抱怨别人对你的不公，你可能会提醒那些缺乏想象力的敌人该怎么做。
- 也许你该找个人聊聊 2025.8.7
1）揭示我们共通的人性，让我们更清楚地了解自己。 2）拯救我们的不再是任何道理或技巧，只有直面的勇气。 3）承认本身，就是最隐蔽也最关键的改变。
运筹学备考
社区模板帮助中心，点此进入>>
- 万事法则（听说能解决90_的问题）2025.8.5
1）找个爱好，过好自己的生活。你必须为生活而工作，而不是为工作而生活。 2）他人如何度过休息时间、如何花钱、如何生活与你无关。聪明人会专心走自己的路，不去管别人选择了什么路线。盯着你要去的地方，不去理会别人在做什么。不去理会，你就更容易不去评判。一旦评判，你就会对自己进行分类，这就使你更难做到灵活，更难在各种情况下应对自如。评判别人反过来也会让你把自己关进鸽子笼——这可不是一个好地方。 3）得有一条线，你不能超越它。你得知道那条线画在哪里。别人不需要知道，但当他们要求你越过这条线时，你就可以告知他们它的存在。
- 塔勒布智慧箴言录 2025.8.6
1）历史上各种悲剧的源泉，不外混淆了别人的“无条件”与“有条件”。 2）只有当拒绝收下一笔钱比收下这笔钱让你感觉更好时，你才算是富有。 3）不要太过大声地抱怨别人对你的不公，你可能会提醒那些缺乏想象力的敌人该怎么做。
- 也许你该找个人聊聊 2025.8.7
1）揭示我们共通的人性，让我们更清楚地了解自己。 2）拯救我们的不再是任何道理或技巧，只有直面的勇气。 3）承认本身，就是最隐蔽也最关键的改变。
- 相似推荐
- 大纲
运筹学备考
建模题 （课本内容）
４.１人力资源分配的问题
排班问题
根据工作时长判断在某一班次的人数共有多少
４.２生产计划的问题
自制外购问题
外包协作铸件是指让别人做且仅做铸造这一道工序，且自己不需参与到别人做的工作中；不是别人协作你和你一起做，也不是做完所有工作，铸件只指铸造，不是把整个产品做完，剩下的机械加工和装配都要自己做
从软件计算结果可以得出
１.最大利润为２９４００元，其最优的生产计划为全部由自己生产的产品甲１６００件，铸造工序外包协作而其余工序自行生产的产品乙６００件
２.从相差值一栏中可知，如果全部由自己生产的产品乙的单位利润再增加２元，达到每件１２元，那么全部自制的产品乙才有可能上马生产；铸造工序外包协作而其余工序自行生产的产品甲利润再增加０.５元，达到１３.５元，才有可能上马生产
３.从对偶价格栏可知铸造每工时的对偶价格为０.３元，这样如果有人以低于铸造的对偶价格来提供铸造的工时（ｊｉｅ 相当于增加了本厂的工时，由本厂铸造，但出了钱后本厂的工时可以延长，相当于用别人的机器自己的人工，假设影响工时的是机器的工作时长限制），则可以购入来获取差价；同样如果有人要购买该公司的铸造工时，则出价扣除成本外，还必须高于其对偶价格，否则就不宜出售。相当于企业水平是０.３，如果比市场水平先进，则出售，如果不如，则购买。至于装配每工时的对偶价格为０，这是由于在此生产计划下还有４０００个装配工时没有用完
４.从常数项数范围栏可知，当铸造工时在０到１００００小时之间变化时其对偶价格都为０.３元
５.从目标函数系数范围一栏中，当全部自己生产的每件产品甲的利润在１４元到正无穷内变化时，其最优解不变；当铸造工序外包协作而其余工序自行生产的每件产品乙的利润在８.６６７到１０元内变化时，其最优解不变
最优产品加工方案
用ｘｉｊｋ表示产品ｉ在工序ｊ的设备ｋ上加工的数量（ｊｉｅ因为有３种产品，需经过A，Ｂ两种设备，每种设备有不同数量或型号），（工序A用１表示，工序B用２表示，例如ｘ１２３表示产品I在工序B上用设备B３加工的数量）
产品在两个工序上加工的数量相等
４.３套裁下料问题
不同方案可以裁下不同规格的圆钢，设按方案Ⅰ 、 Ⅱ 、 Ⅲ、 Ⅳ下料的原材料根数分别为 x j (j=1，2,3,4)，（ｊｉｅ 相当于方案是一个大钢材，可以分割成不同长度的小钢材，一根大钢材可以分割成多根小钢材）不同方案可以得到方案对应的钢材，各种长度的钢材需不少于所需的数量
现有一批某种型号的圆钢长 8 米， 需要截取 2.5 米长的毛坯 100 根， 长 1.3 米的毛坯 200 根。 问如何才能既满足需要， 又能使总的用料最少？（ｊｉｅ 相当于切割材料使之成为可以投入使用的材料）
４.４配料问题
某人每天食用甲、 乙两种食物（如猪肉、 鸡蛋） ，其资料如下： 问两种食物各食用多少， 才能既满足需要、 又使总费用最省？
若为不同产品原材料规格要求不同，且含量不为１且含量可变化，则设ｘｉｊ表示第ｉ（分别用１，２，３表示产品甲，乙，丙）种产品中原材料ｊ的含量，例如ｘ２３表示产品乙中第３种原材料的含量。如产品甲规格要求为原材料１不少于５０％，则有ｘ１１＞＝０.５＊（ｘ１１＋ｘ１２＋ｘ１３），甲产品的单价为５０元每千克，则甲产品的利润为５０（ｘ１１＋ｘ１２＋ｘ１３）（ｊｉｅ 三种原材料共同构成产品的重量）
汽油混合问题
设ｘｉｊ为标号为ｉ的航空汽油所用标号为ｊ的标准汽油的数量，这样ｘ１１＋ｘ１２＋ｘ１３＋ｘ１４为１号航空汽油的总产量，蒸汽压力的约束条件｛［７.１１×１０（ｅｘｐ－２）＊ｘ１１＋１１.３８＊１０ｅｘｐ（－２）＊ｘ１２＋５.６９＊１０ｅｘｐ（－２）ｘ１３＋２８.４５＊１０ｅｘｐ（－２）＊ｘ１４］／（ｘ１１＋ｘ１２＋ｘ１３＋ｘ１４）｝＜＝９.９６＊１０ｅｘｐ（－２）；辛烷数的约束条件［（１０７.５ｘ１１＋９３ｘ１２＋８７ｘ１３＋１０８ｘ１４）／（ｘ１１＋ｘ１２＋ｘ１３＋ｘ１４）］＞＝９１
３.１００％规则
目标函数决策变量系数的百分之一百法则：对于所有变化的目标函数决策变量系数，当其所有允许增加百分比和允许减少百分比之和不超过百分之一百时，最优解不变（ｃ１＋ｃ２＋．．．＋ｃｎ）＜＝１００％（其中ｃ１表示目标函数对应的ｘ１的系数ｃ１的实际增加量减去允许增加量的百分比）允许增加为上限减现在值，允许减少为现在值减下限，实际增加量为实际预计变化后的量减现在值（假设现在还没增加，即实际増加量为实际预计增加量）
同样有约束条件中常数项的百分之一百法则：对于所有变化的约束条件中的常数项，当其所有允许增加百分比和允许减少百分比之和不超过百分之一百时，其对偶价格不变。其中ｂｊ的允许增加百分比的定义同ｃｉ的允许增加百分比
注意
当允许增加量（减少量）为无穷大时，则对于任一个增加量（减少量），其允许增加（减少）百分比都看成零
百分之一百法则是判断最优解或对偶价格是否发生变化的充分条件，但不是必要条件。当允许增加百分比超过１００％时，我们并不知道其最优解或对偶价格是否发生变化
百分之一百法则不能应用于目标函数决策变量系数和约束条件中常数项同时变化的情况，在这种情况下，只有重新求解
对偶价格的定义：当约束条件中的常数项增加一个单位时最优目标函数值改进的数量。当求目标函数的最小值时，改进的数量应该是减少的数量，所以影子价格即为负的对偶价格。资源对最优化目标所产生的边际作用称为影子价格。原问题的第ｉ个约束条件的右端常数项ｂｉ增加一个单位，最优目标函数值就增加ｙｉ＊
对偶价格与目标函数取极大极小无关
７.运输问题表上作业法
确定初始基本可行解
西北角法
从表的左上角（即西北角）的变量ｘ１１开始分配运输量，并使ｘ１１取尽可能大的值；划去某一行或列后又出现新的西北角，继续使西北角分配可以分配的最大运输量，直至所有行列均划完
最小元素法
就近供应，即对单位运价最小的变量分配运输量
划去行列，在剩下的矩阵里找到运价最小的变量ｘ１３，取ｘ１３＝ｍｉｎ（７，４）＝４，Ａ１产量改为３，B３销量改为０，并划去B３列
注意
１.当我们取定ｘｉｊ的值之后，会出现Aｉ的产量与Bｊ的销量都改为０的情况，这时只能划去Aｉ行或Ｂｊ列，但不能同时划去Aｉ行与Ｂｊ列
２.用最小元素法时，可能会出现只剩一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或这一列中除去已填上的数外填上一个０，不能按空格划掉。这样可以保证填过数或０的格为ｍ＋ｎ－１个，即保证基变量的个数为ｍ＋ｎ－１个
最优解的判别
闭回路法
用闭回路法检验，首先要找到每一空格与部分基格构成的闭回路，方法是：从空格出发，沿水平或垂直方向前进，如遇基格转９０度（转向处称顶点）前进，也可穿越基格继续前进（注意：遇到空格不能转向，必须穿越继续前进），但最后要回到原来的空格，目的是围成一个矩形的，或各边顺次垂直的曲折多边形的闭合回路。
闭合回路的顶点除去起始和终了是同一个空格外，其他所有顶点均为基格。 若把出发的空格作为第一个顶点，其他依次为第二第三第n 个顶点，则我们定义该空格所对应的非基变量x i j 的检验数为ｓｉｇｍａｉｊ等于第一顶点的运价减第二顶点的运价加第三顶点的运价减第四顶点的运价．．．等于基数顶点运价之和减偶数顶点运价值之和。 在由最小元素法得到的初始调运方案中，六个空格所对应的闭回路如下，x １３，x １２，x ３２，ｘ３３， x １３.以空格ｘ１３为例，从x１３出发的闭回路相应的检验数为。ｓｉｇｍａ１３＝４－３＋２－１＝２。 将以上结果列入运输表中，并用括号将检验数括起来，以免与运输量相混淆。检验数的经济含义是在保证产销平衡的前提下，空格的调运量增加一个单位，相应在空格闭回路的偶数顶点均减少一个单位，奇数顶点均增加一个单位后，所引起的总的运费的改变量。正的空格检验数意味着总的运费将增加，负的空格检验数意味着总的运费将减少，因此如果全部检验数大于或等于零，则改变调运方案将使总的运费增加。只有当存在负的空格检验数时，改变调运方案才可能使总的运费减少。 最优解的判别准则：若所有检验数都非负，则得到最优解，即及相应的运输方案最优。
位势法
（１）仅考虑基变量所对应的运价。（２）在表的下面增加一行，在右边增加一列，分别称为位势行和位势列。在新增加的行列中，分别填上一些数字，分别称为行位势和列位势。使表中各个数恰好等于它所对应的行位势与列位势的和。 表中用ui 表示行位势，vj 代表列位势。ui ，vj 可看成是运输问题的对偶变量。行位势与列位势是满足ｍ＋ｎ－１个方程：u i ＋v j ＝c i j。ci j为 所有基格处的单位运价。 如ｕ１＋ｖ１＝１ ｕ１＋ｖ２＝３ ｕ３＋ｖ２＝２ ｕ３＋ｖ３＝１ ｕ１＋ｖ４＝６ ｕ２＋ｖ４＝３ 只要任选其中一个值，其余的数值就可以推算出来。例如我们选定v １＝１ 而推出其他的行位势ui 与列位势ｖｊ。 （３）计算各空格处的检验数：ｓｉｇｍａi j ＝c i j －（ui ＋vj ）。按此公式计算出的检验数与闭回路法的结果是一致的。 虽然ui ，vj 的解值有无数多组，但所有格子处的行列位势之和ui ＋vｊ是不变的，因而检验数并不因ui ，vｊ的取值不同而发生改变。
调运方案的改进－闭回路调整法
一般取绝对值最大的那个负空格检验数所对应的非基变量作为调入变量，然后再确定调出变量。由于调入变量是非基变量，因此由调入变量出发，一定可以找到唯一的一条闭回路，而它的其他顶点均为基变量。 例如调入变量x ３４所对应的闭回路的顶点为x ３４，x ３２，x １２，x １４。找到调入变量所对应的闭回路后，以调入变量为第一顶点，沿着闭回路某一前进方向，比较各偶数顶点的调运量，找出其最小值，那么最小值所对应的变量为调出变量，而这个最小值就是调整量。例如偶数顶点的运量都是３，故最小值也为３，从x ３２，x １４中任选一个作为调出变量。 在调入变量所对应的闭回路中，所有奇数顶点的运量都加上调整量，所有偶数顶点的运量都减去调整量。而该闭回路顶点以外的地方，所有运量都不变。调整后x ３４＝３，ｘ１２＝６，ｘ１４＝０，都是基变量的值。x ３２＝０，但它是非基变量，故作为空格。由于原x ３４处的检验数为－１，而调整量为３，故调整后运费下降了一乘以三等于三元。调整时唯一的一条闭回路上的某一基格在调整后被换成了空格，而其他格子位置未变，因此调整后的那些数字格不再含有闭回路，故新方案仍是基可行解。 得到新的调运方案以后，再作最优解的检验。如果所有检验数都非负，则已得到最优解。 如果仍有检验数为负，则需继续调整，直到得到最优解为止。 所有空格检验数非负则所确定的调运方案最优。它所对应的目标函数值即最小总运费为Z＝１×４＋３×６＋６×０＋３×６＋１×５＋４×３＝５７元
找多个最优方案
与单纯形表法一样，只需看最优方案中是否存在非基变量的检验数为０，则为多个最优解，如ｓｉｇｍａ１１＝０，为求得另一个最优解，只要把ｘ１１作为入基变量，调整运输方案，就可以得到另一个最优方案
产销不平衡运输问题的表上作业法
当产大于销时，假定有一个储藏地，产地到储藏地的单位运价为０；如果销大于产，则假定有一个生产地，由该生产地到销地的单位运价为０,要注意一些特殊说明，比如某销地的需求必须满足，则由假想产地到此销地的单位运价为M.M是一个充分大的正数，远远大于任一有限数；假定的储藏地的收量为原总产量与原总销量之差，而假想产地的发量为原总销量与原总产量之差
８.整数规划的应用建模
１.投资场所的选择
选择地点建立销售部，设０－１变量，ｘｉ＝（１，当Aｉ点被选用；０，当Ａｉ点没被选用）
２.固定成本问题
各种容器的固定费用只有在生产该容器时才投入，为了说明固定费用的这种性质，设ｙｉ＝（１，当生产第ｉ种容器即ｘｉ＞０时；０，当不生产第ｉ种容器即ｘｉ＝０时）
ｍａｘＺ＝４ｘ１＋５ｘ２＋６ｘ３－１００ｙ１－１５０ｙ２－２００ｙ３
为了避免出现某种容器不投入固定费用就生产这样一种不合理的情况，必须加上约束条件：ｘ１＜＝ｙ１Ｍ，ｘ２＜＝ｙ２Ｍ，ｘ３＜＝ｙ３Ｍ；这里M是一个充分大的数。从一个容器至少要２个劳动力约束条件可知，各种容器的制造数量不会超过２００台，我们可以取M为２００．ｘ１－２００ｙ１＜＝０，ｘ２－２００ｙ２＜＝０，ｘ３－２００ｙ３＜＝０.当ｙｉ＝０，即对第ｉ种容器不投入固定费用时，有ｘｉ＜＝０，则第ｉ种容器必不能生产；当ｙｉ＝１时即对第ｉ种容器投入固定费用时，ｘｉ＜＝２００，则第ｉ种容器生产的数量要小于等于２００，这是合理的
３.指派问题
ｘｉｊ＝（１，当指派第ｉ人去完成第ｊ项工作时；０，当不指派第ｉ人去完成第ｊ项工作时）
每人只能干一项工作（ｘ１１＋ｘ１２＋ｘ１３＋ｘ１４＝１）；每项工作只能由一个人干（ｘ１１＋ｘ２１＋ｘ３１＋ｘ４１＝１）
４.分布系统设计
工厂 A 1 和 A 2 生产某种物资。 由于该种物资供不应求， 故需要再建一家工厂。 相应的建厂方案有 A 3 和 A 4 两个。 这种物资的需求地有 B 1 ,B 2 ,B 3 ,B 4 四个。 各工厂年生产能力、 各地年需求量、 各厂至各需求地的单位物资运费 c ij 这是一个物资运输问题， 特点是事先不能确定应该建 A3 还是 A4 中哪一个， 因而不知道新厂投产后的实际生产物资。 为此， 引入 0-1 变量：ｙｉ＝（１，若建工厂；０，若不建工厂） 再设 x ij 为由 A i 运往 B j 的物资数量， 单位为千吨； z 表示总费用，单位万元
在A１地已有一个工厂，在A2，A3，A4，A5地中再选择几个地方建厂 设ｘｉｊ为从Ａｉ运往Ｂｊ的运输量 ｙｉ＝（１，当Aｉ厂址被选中时；０，没被选中时） ｍｉｎｚ＝１７５ｙ２＋３００ｙ３＋３７５ｙ４＋５００ｙ５＋８ｘ１１＋４ｘ１２＋３ｘ１３＋５ｘ２１＋２ｘ２２＋３ｘ２３＋４ｘ３１＋３ｘ３２＋４ｘ３３＋９ｘ４１＋７ｘ４２＋５ｘ４３＋１０ｘ５１＋４ｘ５２＋２ｘ５３，其中前４项为固定费用，后面的项为运输费用 对A１厂来说其产量限制的约束条件可写成ｘ１１＋ｘ１２＋ｘ１３＜＝３０；对A2．．Ａ５准备选址建设的新厂来说，只有当选为厂址建设，才有生产量，它们的产量约束条件为ｘ２１＋ｘ２２＋ｘ２３＜＝１０ｙ２
５.投资问题
项目A：从第一年到第四年每年年初需要投资，并于次年回收本利１１５％，但要求第一年投资最低金额为４万元，第二／三／四年不限。这里的次年不是当年，也就是不是第二年初，而是第二年末，从而该笔收回款只能在第三年初用于其他项目的投资款
ｘｉＡ，ｘｉＢ，ｘｉＣ，ｘｉＤ分别表示第ｉ年年初给项目A，B，C，D的投资额 该公司第一年初有１０００００元，所以有ｘ１Ａ＋ｘ１Ｄ＝１０００００ 第二年ｘ２Ａ＋ｘ２Ｃ＋ｘ２Ｄ＝１.０６ｘ１Ｄ 第三年ｘ３Ａ＋ｘ３Ｂ＋ｘ３Ｄ＝１.１５ｘ１Ａ＋１.０６ｘ２Ｄ 第四年ｘ４Ａ＋ｘ４Ｄ＝１.１５ｘ２Ａ＋１.０６ｘ３Ｄ 第五年ｘ５Ｄ＝１.１５ｘ３Ａ＋１.０６ｘ４Ｄ
项目B：第三年初需要投资，到第五年末能回收本利１２８％，但规定最低投资金额为３万元，最高金额为５万元。 设ｙｉＡ，ｙｉＢ，是０－１变量，并规定ｙｉｊ＝（１，当第ｉ年给ｊ项目投资时；０，不投资） 从对项目A的投资额的规定知ｘ１Ａ＞＝４００００ｙ１Ａ，ｘ１Ａ＜＝２０００００ｙ１Ａ；则有当ｙｉＡ＝０时，ｘｉＡ必取０；当ｙｉＡ＝１，这里的２０００００是一个足够大的正数，使第１年给项目A的投资额不会超过它 项目B：ｘ３Ｂ＜＝５００００ｙ３Ｂ，ｘ３Ｂ＞＝３００００ｙ３Ｂ
项目C：第二年初需要投资，到第五年末能回收本利１４０％，但规定其投资额或为２万元或４，６，８万元 设ｙ２Ｃ是个非负整数变量，并规定ｙ２Ｃ＝（４，当第２年投资C项目８万元时；３，当第２年投资C项目６万元时；２，４；１，２；０，０） 项目C：ｘ２Ｃ＝２００００ｙ２Ｃ；ｙ２Ｃ＜＝４且ｙ２Ｃ为非负整数 目标是第五年末手中拥有的资金最大，则ｍａｘＺ＝１.１５ｘ４Ａ＋１.４０ｘ２Ｃ＋１.２８ｘ３Ｂ＋１.０６ｘ５Ｄ
９.３复杂情况下有优先权的目标规划
１０.３动态规划应用（１）
一，资源分配问题
二，背包问题
三，生产与存储问题
四，系统可靠性问题
１１.图与网络模型
１１.２最短路问题
解：图上标号法（最短路）（１）给ｖ１永久性标号［０，ｓ］，给ｖ２，ｖ４，ｖ３临时性标号（３，ｖ１），（５，ｖ１），（２，ｖ１）；（２）给ｖ３进行永久性标号［２，ｖ１］，给ｖ２，ｖ４临时性标号（３，ｖ１），（３，ｖ３）；（３）给ｖ４进行永久性标号［３，ｖ３］，给ｖ６临时性标号［８，ｖ４］；（４）给ｖ６进行永久标号［８，ｖ４］
例１ 由于ｖ５没能标号，因此不存在从ｖ１到ｖ５的有向路
例２ 无向图最短路的求法只将弧改成边即可
Fｌｏｙｄ算法 即矩阵算法，通过比较直达和中转，写出迭代矩阵，可求出任意点间的最短距离
选址问题
在一次灾害救援中，需要在如图8-4-5所示的灾区设置一个医疗救护点，由于条件限制，只能在图中5个受灾居民点之一设置。灾区现有交通道路如图8-4-5所示，线条旁边的数字为受灾居民点相互之间达到的路程（单位：百米）。图8-4-5 选址问题中的道路网络试问：（1）医疗救护点应设在何处才可使各受灾居民点都离得较近。（2）据统计，受灾居民点ｖ１到ｖ５的伤员人数分别为10人、22人、16人、6人、5人，如果考虑使伤员行走总路程最短，则医疗救护点应设在哪里？解：（1）第1个问题称为“中心选址”问题，实质上是找一个“中心”顶点ｖｋ，使得该点距离网络中最远顶点的距离尽可能短，即其中，ｄｉｊ为n个顶点的网络中任意顶点ｖｉ到ｖｊ之间的最短路。考虑题目要求，显然使用Floyd算法求解更简便，求解结果如下（过程请读者自己完成），即解得“中心”顶点应为ｖ３，即医疗救护点应设置在3号居民点，可以保证其他居民点到该处的距离不超过27百米，总体较近
（2）第2个问题称为“重心选址”问题，是指找一个网络的“重点”顶点ｖｌ，满足该点到各顶点处的距离加权和最小化，即其中，λｉ为顶点ｖｉ处的伤员人数，ｄｉｊ是ｖｉ到ｖｊ的最短路距离，表示各处的伤员到达顶点ｖｊ处的总路程，对其求最小化。显然，需要先用Floyd算法求ｄｉｊ，然后求得λｉｄｉｊ及ｖｌ。解得“重点”顶点应为ｖ２，即在考虑伤员人数因素情况下，医疗救护点应设置在2号居民点，可以保证所有伤员到该处的总路程最短，为625百米
设备更新问题
ｖ１，ｖ２，ｖ３，ｖ４，ｖ５，ｖ６第一年初，二，三，四，五，第五年末 一个方案为第１年初购置新设备使用到第２年底（第３年初），第３年初再购置新设备使用到第５年底（第６年初） 第二个方案为第１年初购置新设备使用到第３年底（第４年初），第４年初再购置新设备使用到第５年底（第６年初），这两个方案使得总的支付为最少，均为５３
１１.３最小生成树问题
在图G（G１，G２．．．）中找到一个圈（ｖ１，ｖ７，ｖ６，ｖ１），去掉其中权数最大的边［ｖ１，ｖ６］，得（Ｇ１，Ｇ２.．．）如图（ｂ）所示
１１.４最大流问题
（０，无穷大）（＋ｖ１，６）
在某次抗险救灾活动中，部队需要从驻地分别在A1和A2的两处快速运送救援人员到两个灾难发生地C1和C2 该问题中存在2个出发地和2个目的地，可以通过增加虚拟发点和虚拟收点将其转化为标准的最大流问题，相应的虚拟弧上的容量可设置为无穷大 图8-5-12 转化为单一发点和单一收点的网络
一条河流穿过某城市，河流两岸、河中岛屿及它们之间存在若干桥梁，如图8-5-14所示，图中数字为桥的编号。在一次战争中，需要炸断桥梁阻挡敌人，同时需要考虑战后重建问题，试问至少要炸断哪几座桥，才能完全切断两岸的交通  图8-5-14 桥梁与陆地间关系构成的网络 解：将图中的各陆地作为图中的顶点，桥作为连接顶点的弧，桥的数量作为弧的权值，得到如图8-5-15所示的网络模型，A为始点，F为终点，则原问题转化为求网络关于起点A和终点F的最小截集。图8-5-15 例8.5.5对应的网络模型求解图8-5-15网络模型中的最小截集，可以使用最大流标号算法，也可以罗列出所有截集然后比较得到最小截集，具体求解过程从略，最后得到该网络的最小截集如图8-5-16所示，为Ｃ，Ｆ Ｃ，Ｄ Ａ，Ｅ。图8-5-16 例8.23的求解结果根据题意，得到最终结果为应该炸掉3座桥，分别为第6号、第7号和第13号，这是能够切断两岸交通并炸掉桥梁数量最少的方案
ｖｓ和ｖ１是最终获得标号的顶点，图中其他顶点均无法获得标号，则可令Ｖ１＝｛ｖｓ，ｖ１｝，Ｖ２＝｛ｖ２，ｖ３，ｖ４，ｖｔ｝，则截集（Ｖ１，Ｖ２）＝｛（ｖｓ，ｖ２），（ｖ１，ｖ３）｝就是容量网络D的最小截集，相应截量为ｃ（Ｖ１，Ｖ２）＝ｃｓ２＋ｃ１３＝４＋２＝６，与最大流的流量相等。找出了最小截集，就指明了如果要增加这个网络的最大流量，弧（ｖｓ，ｖ２）和（ｖ１，ｖ３）为瓶颈所在，必须列为优先考虑
无向图直接赋可能的方向
１２．排序与统筹方法
排序
一台机器，ｎ个零件的排序问题
零件到达机器，依次加工，加工完成后离开，每个零件需等待上一个零件加工完成后才能进行加工，类似同一群人体测，停留时间为自己加工的时间和等待加工的时间。为使各个零件平均停留时间最少，则需按照加工时间从少到多排出加工零件的顺序，加工时间越少的零件排在越前面。六个零件的停留时间为T１＋T２＋Ｔ３＋Ｔ４＋Ｔ５＋Ｔ６＝Ｐ１＋（Ｐ１＋Ｐ２）＋（Ｐ１＋Ｐ２＋Ｐ３）＋．．．＋（Ｐ１＋Ｐ２＋Ｐ３＋Ｐ４＋Ｐ５＋Ｐ６）＝６Ｐ１＋５Ｐ２＋４Ｐ３＋３Ｐ４＋２Ｐ５＋Ｐ６，平均停留时间为总停留时间／６.其中T表示停留时间，P表示加工时间，一个零件等待加工的时间就是在它之前的零件的加工时间
两台机器，ｎ个零件
我们应该一方面把在车床上加工时间越短的零件，越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越短的零件，越晚加工，也就是说把在磨床上加工时间越长的零件，越早加工，以便充分利用前面的时间
若最短时间既在第一道工序也在最后一道工序，则最短往后排，减少机器空转时间
两台机器ｎ个零件的排序问题，使得全部任务的总时间最短的排序算法： （１）在加工所需时间表上选出最短加工时间ｔｉｊ，这是第ｉ工序加工ｊ零件所需时间，当ｉ＝１时，将零件ｊ的加工顺序尽量靠前，若ｉ＝２时，将零件ｊ的加工顺序尽量靠后； （２）在表上划去零件ｊ的所在行，回到步骤（１）
ｍ台机器ｎ个零件找不到类似的有效算法，但可以用整数规划的方法解决
在表中找出最短加工时间是０.２５，它是第二道工序磨床加工零件２所需时间，把零件２放在加工顺序的末尾，并在表中划去零件２所在行；又找出最短加工时间为０.５，与二工序有关，放到除第五外的加工顺序的末尾，划去行；０.７５，与一工序有关，排在第一位，划去行；１，一工序，排在第二位，划去行；只剩零件４没有排序，零件４只能在第三位加工
总加工时间为７小时，第一个加工的零件的一工序加工时间加上一零件二工序加工时间，加二零件二工序加工时间，加三零件二工序加工时间，加四零件二工序加工时间，加五零件二工序加工时间。一零件一工序加工时间不管，从二机器开始加工算起，在二工序加工完某零件前下一待二工序加工零件已在一工序完成加工。即某二工序加工时间可以承载正在加工零件及该零件前的一工序加工时间，如二零件二工序加工时间为１.２５，可以承载二零件一工序加工时间１.０；三零件二工序加工时间１.７５＋１.２５（可以理解为停留时间）可以承载三零件一工序加工时间（也可理解为停留时间）１.０＋１.２５（一零件一工序时间不算，因为它在二工序开始之前，即视一零件一工序时间为０）；四零件二工序１.２５＋１.７５＋２.５＞１.０＋１.２５＋１.５；五零件二工序１.２５＋１.７５＋２.５＋０.５＞１.０＋１.２５＋１.５＋１.５
网络图
１３.存储论
１３.１经济订购批量存储模型
１３.２经济生产批量模型
１５.对策论
最优纯策略，２×２矩阵混合策略 代数方法加数字就可求混合策略
甲队无论乙队采取什么策略都采用一种策略ａ１，乙队无论甲队采取什么策略都采用一种策略ｂ２，把ａ１，ｂ２称为局中人甲乙的最优纯策略，并把（ａ１，ｂ２）称为对策G在纯策略下的解，又称（ａ１，ｂ２）为对策G的鞍点 这种纯策略只有当赢得矩阵A＝（ａｉｊ）中等式ｍａｘｉｍｉｎｊａｉｊ＝ｍｉｎｊｍａｘｉａｉｊ成立时，才存在（通常取＜＝号）
在甲的赢得矩阵中，甲选（在行中选）策略中让自己最大损失为所有策略中最大损失最小的；乙选（在列中选）策略中让甲最大获得为所有策略中最大获得最小的


优超原则
某策略优于另一策略时，表示此策略优超另一策略，可划去另一策略行（对甲）或列（对乙），其中对甲来说行中各值越大越优；对乙来说列中各值越小越优。划去后矩阵与原矩阵对策等价，有相同的矩阵策略解
得出甲选择不同策略的概率分布，称混合策略。
［５ ９ ｙ ８ ６］１－ｙ ｘ １－ｘ Ｅ（ｘ，ｙ）＝５ｘｙ＋９ｘ（１－ｙ）＋８（１－ｘ）ｙ＋６（１－ｘ）（１－ｙ）＝－６ｘｙ＋３ｘ＋２ｙ＋６＝（－３ｘ＋１）（２ｙ－１）＋７，甲选第一行的策略的概率为１／３，第二行为２／３；乙选第一列策略概率为１／２，第二列为１／２
计算题
单纯形法的表格形式
若所有非基变量的检验数小于等于0，则X为最优解，B为最优基。若其中至少一个非基变量的检验数为0，则还有其他的无穷多的最优解。jie若非基变量检验数为0，且非基变量为加入的松弛变量，则有唯一最优解（画线句并不对，仍有无穷多最优解）
无论目标函数是求极大还是求极小，有最优解的条件都是所有检验数小于等于０
若目标函数求极大，则选最大检验数，最小ｔｈｅｔａ；若目标函数求极小，则取最小检验数，最大ｔｈｅｔａ
大M法
目标函数为求极小值，化为极大值的目标函数加入的为-M；目标函数求极大值，目标函数中加入的为M。至于加入多少个人工变量，视约束条件的个数和基变量的个数决定，若差两个系数为１的基变量且约束等式为二个，则加入两个人工变量。
将基变量按约束条件中１的位置排序比较好
对偶单纯形法
转化成适合对偶解法的标准型，目标函数取极大，b值取负数，检验数取负数中的极大值，theta取极小值；b列全是非负，则得到对偶规划的最优解（即正在用对偶单纯形法求解的线性规划问题），最优解为b列值，最优函数值为-z;若在确定换入变量时a均为正，则无可行解；若要求该对偶规划的对偶问题的最优解，通过将检验数反号即可得到。
用对偶单纯形法解含大于号的约束条件问题时比用大M法简便
灵敏度分析
其最优单纯形表如下
当 C 1 由－1 变为 4 时， 求新问题的最优解
由表可知， C1 是非基变量的价值系数， 因此 C 1 的改变只影响σ 1， σ 1’＞０，可见最优性准则已不满足， 继续迭代（σ 1’＝σ 1＋△C１）
讨论 C 2 在什么范围内变化时， 原有的最优解仍是最优解
要使原最优解仍为最优解， 只要在新的条件下满足 σ ≤0 成立， 因为 x 2 是基变量， 所以所有的 σ 值都将发生变化
灵敏度分析总是在最优表上进行
增加新约束 ， 求新问题的最优解
将原问题的最优解代入新增约束，不满足新增加的约束条件， 因此引入松弛变量 x 7 后， 新增约束变为，加进最优表得
若右端列向量ｂ变化 ，求新问题的最优解
因为－1 小于 0， 因此继续迭代
ｊｉｅ Ｂ的逆为最优单纯形表中最后约束个数列的矩阵
匈牙利法求解指派问题
求时间最少的效率矩阵
所画（） 0 元素少于 n（n＝4）， 未得到最优解， 需要继续变换矩阵（求能覆盖所有 0 元素的最少数直线集合）
未被直线覆盖的最小元素为 c ij =2, 在未被直线覆盖处减去 2， 在直线交叉处加上 2
若求极大值如利润极大，需用一个矩阵中最大数减矩阵中所有数
判断题
对偶问题
如果线性规划问题存在可行解， 则其对偶问题也一定存在可行解； 错误， 当原问题有无界解时， 其对偶问题无可行解
任何线性规划问题具有唯一的对偶问题。 正确
简答题
图解法
化为标准形式
写出原问题的对偶问题
把一个问题化为它的对偶问题：min则y（约束条件的符号）不变（从约束条件出发的对偶问题的变量的符号不变），x反号 前提：原问题的常数项为正，若常数项为负，则需乘以负１使常数项为正
利用对偶性质写出对偶问题的最优解
对偶定理
若原问题有最优解，则对偶问题也有最优解，且最优目标函数值相等
互补松弛性
当一对对偶规划达到最优时，若一个问题的某个变量为正数，则相应的另一个问题的约束必取等式；或者一个问题中的约束条件取不等式，则相应的另一个问题的变量必为０（ｊｉｅ 将最优解代入原约束条件，若约束条件两边取不等号，将该不等式称为严格不等式，则对偶问题对应的变量取０且对偶问题对应的约束条件取等号）
还可以采取将原问题和对偶问题都化为含松弛变量的标准型，当原问题松弛变量不为０时（即约束条件取不等式），对偶问题对应的变量取值为０；当对偶问题对应原问题最优解不为０（为正）时，有最优解对应约束条件的松弛变量为０，即不含松弛变量的约束条件取等式
单选题
线性规划问题的可行域是一个凸集，它们有有限个顶点，若存在最优解，则至少有一个可行域的顶点是最优解。因此，只要比较各顶点处的目标函数值就能找出最优解
矩阵的初等行变换不包括的形式有（D） A. 将某一行乘上一个不等于零的系数 B.将任意两行互换 C. 将某一行乘上一个不等于零的系数再加到另一行上去 D.将某一行加上一个相同的常数 ｊｉｅ答案是正确的
求解线性规划的单纯形表法中所用到的变换有（C） A.两行互换 B.两列互换 C.将某一行乘上一个不为 0 的 系数 D 都正确
线性规划模型作为最简单的数学模型，它的特点是 :D A .变量个数少 B .约束条件少 C .目标函数的表达式短 D .约束条件和目标函数都是线性的
关于单纯形法的说法不正确的是B Ａ．只要人工变量取值大于零，目标函数就不可能实现最优 B．增加人工变量后目标函数表达式不变 Ｃ．所有线性规划问题化为标准形后都含有单位矩阵。 Ｄ．检验数中含 M 时，如果 M 的系数为负，则检验数为负
关于线性规划的最优解判定，说法不正确的是(C) Ａ．如果是求最小化值，则所有检验数都小于等于零的基可行解是最优解。 Ｂ．.如果是求最大化值，则所有检验数都大于等于零的基可行解是最优解。 Ｃ.求最大化值时，如果所有检验数都小于等于零，则有唯一最优解。 Ｄ.如果运算到某步时，存在某个变量的检验数大于零，且该变量所对应约束方程中的系数列向量均小于等于零，则存在无界
关于求最小化值的单纯形算法，下列说法不正确的是(C) Ａ.通常选取最大正检验数对应的变量作为换入变量。 Ｂ.通常按最小比值原则确定离基变量。 Ｃ若线性规划问题的可行域有界，则该问题最多有有限个数的最优解。 Ｄ.单纯形法的迭代计算过程是从一基个可行解转换到目标函数更小的另一个基可行解
在用单纯形法求解线性规划问题时，下列说法错误的是:D A.如果在单纯形表中，所有检验数都非正，则对应的基本可行解就是最优解 B.如果在单纯形表中，某一检验数大于零，而且对应变量所在列中没有正数，则线性规划问题没有最优解 C.利用单纯形表进行迭代，我们一定可以求出线性规划问题的最优解或是判断线性规划问题无最优解 D.如果在单纯形表中，某一检验数大于零，则线性规划问题没有最优解
单纯形法解 LP 问题时，不正确的说法有（C） Ａ.将进基变量所在列转化为与离基变量所有列一样 Ｂ.转化时可将主元行除以主元素 Ｃ.转化时可将主元列除以主元素 Ｄ.转化时不可将其中两行互换位置
关于 LP 的基的说法不正确的是（B） Ａ.基是约束方程系数矩阵中的一个子矩阵 Ｂ.基解中非零值的个数大于等于约束方程数 Ｃ.基中的每一个列向量称为基向量 Ｄ.与基向量对应的变量称为基变量
线性规划中( )不正确。（B） A .有可行解必有可行基解 B .有可行解必有最优解 C .若存在最优解，则最优基解的个数不超过 2 D .可行域无界时也可能得到最优解

下面哪些不是线性规划问题的标准形式所具备的:C A.所有的变量必须是非负的 B.所有的约束条件（变量的非负约束除外）必须是等式 C.添加新变量时，可以不考虑变量的正负性 D.求目标函数的最小值
X 是线性规划的基本可行解则有（C） A.X 中的基变量非零，非基变量为零 B．X 不一定满足约束条件 C．X 中的基变量非负，非基变量为零 D．X 是最优解
极大化线性规划,单纯形法计算中，如不按最小比值原则选取（）变量,则在下一个解中至少有一个变量的值为负。（ A） A.换出变量 B.换入变量 C.非基变量 D.基变量 ｊｉｅ 最小比值原则是根据比值ｔｈｅｔａ（ａｉｋ＞０）取最小来选取换出变量
有 3 个产地 4 个销地的平衡运输问题模型具有特征（D） A 有 7 个变量 B有 12 个约束 C有 6 约束 D 有 6 个基变量 ｊｉｅ ｍ＋ｎ－１＝３＋４－１＝６
运筹学的原意不包含运作管理
系统设计不是运筹学的研究范围
运筹学模型只有符合模型的简化条件时才有效
劣解不属于运筹学求解目标