1、运筹学复习题一、选择题1若树 T 有 n 个顶点，那么它的边数一定是 （ ）An Bn-1 Cn+1 D 2n2、决策的三要素是（ ） 。A. 方案、状态和收益 B. 方案集、状态集和损益矩阵 C. 方案、状态和损失 D. 方案集、状态集和概率集3线性规划问题中只满足约束条件的解称为 ( )。A基本解 B可行解 C最优解 D基本可行解4如果要使目标规划实际实现值不超过目标值，则应满足（ ）A. B. C. D.0d0d0_d0,_d5、线性规划问题的数学模型的三个部分中不包括（ ） 。A. 约束条件 B. 最优解 C. 决策变量 D. 目标函数6线性规划一般模型中，自由变量可以用两个非负变量的
2、 （ ）代换。A和 B差 C积 D商7、针对某一特定的不确定型的决策问题，分别采用五种决策准则（等可能准则、乐观准则、悲观准则、折衷准则和后悔值准则）进行决策，其决策结果（ ） 。A. 相同 B. 一般不相同 C. 绝大多数相同 D. 不能确定8最早运用运筹学理论的是（ ）A 二次世界大战期间，英国政府将运筹学运用到政府制定计划B二次世界大战期间，英国军事部门将运筹学运用到军事战略部署C50 年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上D 美国最早将运筹学运用到农业和人口规划问题上9可用于风险条件下决策类型的是( )A最大最大决策标准 B.最大期望收益值标准C.最大最小决策
3、标准 D.最小最大遗憾值决策标准10在库存管理中， “订货提前期” ，亦可称为( )A再订货点 B.前置时间C.前置时间内的需求量 D.经济订货量11线性规划的图解法适用于( )A只含有一个变量的线性规划问题 B.只含有 2 个变量的线性规划问题C.含有多个变量的线性规划问题 D.任何情况12网络计划技术是解决哪类管理问题的科学方法？( )A环境条件不确定问题 B. 组织生产和进行计划管理C.具有对抗性局势竞争问题 D.订货与库存问题13.在网络计划技术中，以结点代表活动，以箭线表示活动之间的先后承接关系，这种图称之为( )A箭线式网络图 B.结点式网络图 C.最短路线图 D.最大流量图14.
4、网络图中，完成一项活动可能最短的时间，称为( )A作业时间 B.最早完成时间 C.最迟完成时间 D.最可能时间15.在一个网络中，如果从一个起点出发到所有的点，找出一条或几条路线，以使在这样一些路线中所采用的全部支线的总长度最小，这种方法称之为( )A点的问题 B. 最小生成树问题C.树的问题 D. 线的问题16线性规划模型的特点是 ( )。A变量个数少 B约束条件和目标函数都是线性的C目标函数的表达式短 D约束条件少得得分 1. 线性规划问题的每一个基本可行解对应可行域的一个顶点。 ( T )2. 运输问题的可行解中基变量的个数不一定遵循 mn1 的规则。 ( F )3.在线性规划的模型中全
5、部变量要求是整数。 ( F )3.在整数规划的模型中全部变量要求是整数。 ( F )4. 网络最大流量是网络起点至终点的一条增流链上的最大流量。 ( F )5. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往是不相等。 ( F )6. 单目标决策时，用不同方法确定的最佳方案往往是不一致的。 ( T )7任何线性规划一定有最优解。 （ F ）8.决策变量取 0 或 1 的线性规划是 0-1 整数规划。 （ T ）9.求最小树可用破圈法。 （ T ）10.在最短路问题中，发点到收点的最短路长是唯一的。 （ T ）10.在最短路问题中，发点到收点的最短路是唯一的。 （ F ）11.网络计划中
6、的总工期等于各工序时间之和。 （ F ）12.网络计划中，总时差为 0 的工序称为关键工序。 （ T ）得得分 15.什么叫纯整数规划和 0-1 整数规划？答：纯整数规划是指决策变量全部是整数的线性规划。二、判断题（本大题满分 12 分，每小题 2 分）三、简答题（本大题满分 4 分）0-1 整数规划是指决策变量只能取 0 或 1 的线性规划。15.什么叫后悔值？答：在决策过程中，当某种自然状态出现时，决策者必然会选择收益值最大的方案。如果由于决策失误而没有选择这一优方案，而选择其他方案，就会因此感到遗憾和后悔，这两个方案的收益值的差就称为后悔值。得得分 1.某公司决定建设设备厂，决策者有三个
7、方案可供选择，即建设大型工厂、中型工厂和小型工厂。对于产品的市场前景，存在着三种自然状态：销路好、销路一般、销路差。预测在各种自然状态下的损益值如下表所示：（单位：万元）自然状态决策方案销路很好 销路一般 销路较差建设大型工厂 72 35 28-建设中型工厂 56 38 1建设小型工厂 32 28 10试用乐观原则、悲观原则及后悔值原则分别作出选择。2.某工厂每年需某种产品 1000 件，每次订购费为 6 元。若每次货物到达后存入仓库，每件每月要付出 0.1 元存储费。若假设消耗是均匀连续发生的，且不许缺货。求最佳订货周期及最佳订购批量。3.求出下面两图中从发点到收点的最大流。每条有向边上的数
8、字为该边的容量限制。4已知某运输问题如下（单位：百元/吨）：单位运价 销地产地 B1 B2 B3 供应量（吨）A1 3 7 2 18A2 5 8 10 12A3 9 4 5 15需求量（吨） 16 12 17求：使总运费最小的调运方案和最小运费。 （建立数学模型，不求解）5. 某工程有 7 道工序，工序衔接与有关时间数据如下表，试绘制网络图。 四、计算题（ ）工序名称 A B C D E F G紧前工序 - - A、B A、B B C D、E工序时间 2 4 5 4 3 2 4（1）绘制网络图；（2）确定关键路线，求出完工工期。6.求解矩阵对策 G=（S1 ，S2，A） ，其中 32517.四
9、人完成四项工作，他们完成各项任务的时间（小时）如下表所示，如何安排四人的工作，才能使完成这四项工作总的时间消耗最少。例：求下面指派问题的最小值解：12798641250解：1279864125050231798462632408157420351841 每一行元素减去其最小值2 若有 个零位于不同的行和不同的列，问题解决。n3 否则，有两个零位于同一行，则这一行元素加一个 2，返回 1故最优解为： ，最优解值为5124314xx。763Y8求下图中从 A 到 E 的最短路线和最短路长（图中每条边上的数字为该条边的长度） 。9某厂每月需某种零件 200 件，每次订购费为 8 元。若每次货物到达后
10、存入仓库，每件每年要付出 元存储费。若假设消耗是均匀连续发生的，且不许缺货。求最佳订货周期、最6佳订购批量和总费用。10求解矩阵对策 G=（S1 ，S2 ，A） ，其中 3213511某厂组装三种产品，有关数据如下表所示。产品 单件组装工时 日销售量（件） 产值（元/件） 日装配能力A 1.1 70 40B 1.3 60 60C 1.5 80 80300要求确定两种产品的日生产计划，并满足：（1） 工厂希望装配线尽量不超负荷生产；（2） 每日剩余产品尽可能少；（3） 日产值尽可能达到 6000 元试建立该问题的目标规划数学模型12用图解法求解 z 约束条件：max213082153,4112x
11、x，13.用单纯形法求解线性规划问题用单纯形法求解线性规划问题 2153axxzs.t.0,8621x14.用表上作业法求给出的运输问题的最优解甲 乙 丙 丁 产量1 10 6 7 12 42 16 10 5 9 93 5 4 10 10 4销量 5 2 4 6甲 乙 丙 丁 产量1 1 2 1 42 3 6 93 4 4销量 5 2 4 6在最优调运方案下的运输费用最小为 118。15.某工厂有 5 个单位的能源要供给 3 个车间，供给方案及各车间获得能源后所产生的效益在下表给出，问应如何分配这些能源，使工厂的总收益最大？能源车间0 1 2 3 41 0 5 6 - -2 0 - 8 9 1
12、23 0 3 - - -1.某公司决定建设设备厂，决策者有三个方案可供选择，即建设大型工厂、中型工厂和小型工厂。对于产品的市场前景，存在着三种自然状态：销路好、销路一般、销路差。预测在各种自然状态下的损益值如下表所示：（单位：万元）自然状态决策方案销路很好 销路一般 销路较差建设大型工厂 72 35 28-建设中型工厂 56 38 1建设小型工厂 32 28 10试用乐观原则、悲观原则及后悔值原则分别作出选择。自然状态决策方案销路很好 销路一般 销路较差 最小建设大型工厂 72 35 28-28建设中型工厂 56 38 1-12建设小型工厂 32 28 10 10悲观准则选建设小型工厂。自然状
13、态决策方案销路很好 销路一般 销路较差 最大建设大型工厂 72 35 28-72建设中型工厂 56 38 156建设小型工厂 32 28 10 32悲观准则选建设大型工厂。自然状态决策方案销路很好 销路一般 销路较差 最大建设大型工厂 0 3 38 38建设中型工厂 16 0 22 22建设小型工厂 40 10 0 40悲观准则选建设中型工厂。2.某工厂每年需某种产品 1000 件，每次订购费为 6 元。若每次货物到达后存入仓库，每件每月要付出 0.1 元存储费。若假设消耗是均匀连续发生的，且不许缺货。求最佳订货周期及最佳订购批量。解： ， ，2.1.01C0D3C最佳订货量： （件）13*Q
14、102.6最佳订货周期： （天）5.0/65*Dt3. 4已知某运输问题如下（单位：百元/吨）：单位运价 销地产地 B1 B2 B3 供应量（吨）A1 3 7 2 18A2 5 8 10 12A3 9 4 5 15需求量（吨） 16 12 17求：使总运费最小的调运方案和最小运费。解： 设 为从第 产地运到第 销地的货物量。ijxij求 3231221312 54908573mn xxxxz 约束条件： 1726532133231x解得： 时，3,12,0,0,4,0,4 312321 xxx最小运费是 。65. 某工程有 7 道工序，工序衔接与有关时间数据如下表，试绘制网络图。 工序名称 A
15、 B C D E F G紧前工序 - - A、B A、B B C D、E工序时间 2 4 5 4 3 2 4（1）绘制网络图；（2）确定关键路线，求出完工工期。解：（1）(2)关键路线 ，完工工期是 12 天GDB6.求解矩阵对策 G=（S1 ，S2，A） ，其中 3251解：运用优超原理 变为 231求 ，约束条件 ，解得：min32x32x5132x求 ，约束条件 ，解得：i21y121y21y所以原矩阵对策的一个解为：，5.0,*X0,5.*7.四人完成四项工作，他们完成各项任务的时间（小时）如下表所示，如何安排四人的工作，才能使完成这四项工作总的时间消耗最少。解：指派方案为：人员 1工
16、作 4；人员 2工作 1；人员 3工作 3；人员 4工作 2消耗的最小时间为：438求下图中从 A 到 E 的最短路线和最短路长（图中每条边上的数字为该条边的长度） 。解：假设假设 分别为 1、2、3、4、5、6、7、8、9EDCBA, 21321表示 到 的路长。ijSj=0+6=6， =7 min=61213S=6+9=15, =6+6=12, =6+4=10, 42526=7+3=10, =7+5=12 ， =7+6=13 min=103S33=10+7=17, =10+9=19, =10+9=19, =10+11=21 min=174748S67S68S=17+2=199最短路线为 AB2C1D1E 最短路线长 19.
