管理运筹学期末复习资料【韩伯棠】

1、运筹学（Operational Research）复习资料第一章 绪论一、名词解释1.运筹学：运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。二、选择题1.运筹学的主要分支包括（ ABDE ）A图论 B线性规划 C非线性规划 D整数规划 E目标规划2. 最早运用运筹学理论的是（ A ）A . 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署 B . 美国最早将运筹学运用到农业和人口规划问题上C . 二次世界大战期间，英国政府将运筹学运用到政府制定计划 D . 50年代，运筹学运用到研究人口，能源

2、，粮食，第三世界经济发展等问题上第二章 线性规划的图解法一、选择题/填空题1.线性规划标准式的特点： （1）目标函数最大化（2）约束条件为等式（3 决策变量为非负（4 ) 右端常数项为非负2. 在一定范围内，约束条件右边常数项增加一个单位： （1）如果对偶价格大于0，则其最优目标函数值得到改进，即求最大值时，最优目标函数值变得更大，求最小值时最优目标函数值变得更小。 （2）如果对偶价格小于0，则其最优目标函数值变坏，即求最大值时，最优目标函数值变小了；求最小值时，最优目标函数值变大了。 （3）如果对偶价格等于0，则其最优目标函数值不变。3.LP模型（线性规划模型）三要素：（1）决策变量 （2）

3、约束条件 （3）目标函数4. 数学模型中，“s·t”表示约束条件。5. 将线性规划模型化成标准形式时，“”的约束条件要在不等式左端加上松弛变量。6. 将线性规划模型化成标准形式时，“”的约束条件要在不等式左端减去剩余变量。7下列图形中阴影部分构成的集合是凸集的是 A 【解析】：如何判断是凸集？ 凸集：两点之间连线在图内 凹集：两点之间连线在图外8. 线性规划问题有可行解且凸多边形无界，这时 C A没有无界解 B 没有可行解 C 有无界解 D 有有限最优解9. 对于线性规划问题，下列说法正确的是（ D ）A. 线性规划问题可能没有可行解 B. 在图解法上，线性规划问题的可行解区域都是“

4、凸”区域C. 线性规划问题如有最优解，则最优解可在可行解区域顶点上到达 D. 上述说法都正确第三章 线性规划问题的计算机求解一、名词解释1.相差值：相应的决策变量的目标系数需要改进的数量，使得决策变量为正值。2.对偶价格（影子价格）：约束条件右端常数项增加一个单位而使最优目标函数值得到改进的数量。二、选择题/填空题/判断题1.松弛变量：表示没使用的资源或能力的变量。2.剩余变量：表示最低限约束的超过量。3.线性规划问题解的情况：（1）如果某一个线性规划问题有最优解则一定有一个可行域的顶点对应最优解（2）线性规划存在有无穷多个最优解的情况。（3）线性规划存在无界解，即无最优解情况。（4）线性规划

5、存在无可行解的情况。4. 如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。【正确】5. 百分之一百法则：（1）对于目标函数决策变量系数时，当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变。（2）对于约束条件右端常数项变化时，当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，对偶价格不变。* 允许增加的百分比 = 增加量 / 允许增加量=增加量/（上限当前值） * 允许减少的百分比 = 减少量 / 允许减少量=减少量/（当前值下限） * 当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许增加（减少）百分比均看作0；6.

6、在线性规划问题的标准形式中，不可能存在的变量是D .A可控变量 B松驰变量 c剩余变量 D人工变量 7.看图填空题：【详见：课本例题P29 / 平时测验试卷】第四章 线性规划在工商管理中的应用一、选择题/判断题1.线性规划可以解决： （1）人力资源分配问题 （2）生产计划问题 （3）套裁下料问题（4）配料问题 （5）投资问题第七章 运输问题一、选择题/填空题/判断题1.产销平衡问题：总产量=总销量2.平衡运输问题即是指m个供应地的总供应量 D n个需求地的总需求量。A 大于 B 大于等于 C小于 D 等于3.产销不平衡问题：（1）总产量>总销量：增加假想销地（2）总产量<总销量：增

7、加假想产地4. 物资调运问题中，有m个供应地，Al，A2，Am，Aj的供应量为ai(i=1，2，m)，n个需求地B1，B2，Bn，B的需求量为bj(j=1，2，n)，则供需平衡条件为 =二、构建模型题【运输问题】考题：某化学公司有三个原料基地，每天要把生产的原料运往、四个工厂，各原料基地的产量分别为16吨、10吨、22吨，各工厂的需求量分别8吨、14吨、12吨、14吨,各原料基地到各工厂的运价（百元/吨）如下表所示。问应如何组织调运才能使总运费最少，请画出产销平衡与运价表？工厂运价基地B1B2B3B4产量A1A2A34281210543111196161022销量8141214【解析】本题为产

8、销平衡问题。 答案略.第八章 整数规划一、名词解释1.纯整数规划：在整数规划中，所有的变量都为非负整数。2.混合整数规划：在整数规划中，有一部分变量为负整数。3. 0-1规划：在整数规划中，变量的取值只为0和1。二、选择题1.整数规划可以解决： （1）投资场所的选择 （2） 固定成本问题 （3）指派问题（4）分布系统设计 （5）投资问题2.整数规划问题中，变量的取值可能是D。A整数 B0或1 C大于零的非整数 D以上三种都可能3.整数规划类型包括（ CDE ）A 线性规划 B 非线性规划 C 纯整数规划 D混合整数规划 E 01规划三、构建模型题【指派问题】考题：有四个工人，要分别指派他们完成

9、四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。解：引入01变量 xij，并令 xij = 1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)构建0-1规划模型：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作) x31+

10、x32+ x33+ x34= 1 (丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 为0-1变量，i,j = 1,2,3,4第九章 目标规划一、名词解释1. 目标规划：解决存在多个目标的最优化问题的方法二、选择题1.目标规划可以解决： （1）企业生产问题 （2）商务活动问题 （3）

11、投资问题 （4）裁员问题 （5）营销问题2. 正、负偏差相乘积为零。即：d+×d-=0三、构建模型题 【目标规划模型】 考题：详见书本课后习题。（必考）第十一章 图与网络模型一、名词解释1. 最小生成树问题：在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。2.树：无圈的连通图3.最大流问题：在网络图中，在单位时间内，从发点到收点的最大流量二、选择题/填空题/判断题1.一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。【正确】2.点和边构成：无向图。点边交错在一起，最终重合成为：圈3.点和弧构成：有向图。

12、点弧交错在一起，最终起点和终点重合成为：路 4.最短路问题-双标号法：对图中的点vj赋予两个标号（lj ,kj），第一个标号lj表示从起点vs到vj的最短路的长度，第二个标号kj表示在vs至vj的最短路上vj前面一个邻点的下标。5.图论可以解决： （1）最短路问题 （2）最小生成树问题 （3）最大流问题 （4）最小费用最大流问题 （5）七桥问题三、构建模型题1.用破圈法求最小生成树问题：【答题模板】 解：（1）在原图G中，任找一个圈（ ， ， ， ），去掉最大边 , ，得到生成子图G1;（2）在生成子图G1中，任找一个圈（ ， ， ， ），去掉最大边 , ，得到生成子图G2;（3）在生成子图G

13、2中，任找一个圈（ ， ， ， ），去掉最大边 , ，得到生成子图G3; . . . . . . . . .（6）在生成子图G5中，再也找不到任何一个圈了，得到最小生成树。如下图所示.2.求最大流问题：【答题模板】 解：（1）对图中的流量表示做一下改进，如图所示；（2）选择路V VV ，可知pf= ，改进的网络流量图如图；（3）选择路V VV ，可知pf= ，改进的网络流量图如图；（4）选择路V VV ，可知pf= ，改进的网络流量图如图；（5）在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为 。最大流量图如图所示。第十二章 排序与统筹方法一、填空题/选择题/判断题Ø 1.一台机器、n个零件的排序问题：加工时间短的零件放在前面，加工时间长的零件放在后面。Ø 2.两台机器、n个零件的排序问题加工时间短的零件放在后面。第十五章 对策论一、名词解释1. 二人有限零和对策（矩阵策略）：指有两个局中人，每个局中人的策略集的策略数目都是有限的；每一局势的对策都有确定的益损值，并且