《运筹学》期末试卷答案2

7/7《运筹学》期末试卷2答案得分一、(2’×6)选择题：1.A2.C3.D4.C5.D6.C得分二、(2’×6)填空题：1.（0,2）2.03.n+14.多阶段决策5.伏格尔法6.0得分三、(12’)考虑线性规划问题：这里是一个正数。假定给约束条件加上松弛变量使得问题转化为标准形式。考虑以为基变量的基本解，证明其为基本可行解。证明（1）中定义的基本解是最优的。 (已知)解：(1)以为基变量，由约束条件可以得到： ,,, 因此，该基本解是基本可行解。(2)利用最优性条件，若则为最优解。这里， ， ，， 所以，。得分四、(10’)某企业拟生产三种产品，每种产品的单位劳动力和原材料需求量如下：产品劳动力（小时/件）原材料（公斤/件）134243356三种产品的利润分别为25元/件，30元/件，22元/件。现该企业可在如下两处厂址选择一处，两地的主要区别在于劳动力和原材料的供给能力不同（见下表）。厂址可提供的劳动力（小时）可提供的原材料（公斤）1100100290120此外，由于生产机器的特殊性，如果产品3被生产，则其产量不得低于3件。请问该企业应在何处建厂以使总利润最大（建立适当的数学规划模型，不必求解）。解：设分别为产品1,2,3的生产量，M是一个很大的正数，并引入0-1变量,maxs.t.,得分五、(12’)现要在5个工人中确定4个人来分别完成4项工作中的一项。由于每个工人的技术特长不同，他们完成各项工作所需的工时也不同。每个工人完成每项工作所需工时如下表。工作工人ABCDI9437II4656III5475IV7523V10674试找出一个工作分配方案，使总工时最小。解：本题属于“不平衡”指派问题，故先虚拟一项工作E，设每人完成E所用的时间都是“0”，从而转化为5个人完成5项工作的平衡指派问题。再用匈牙利法求解，得最优解为：I—C，II—A，III—B，IV—D，V—E，即应安排工人I、II、III、IV分别完成工作C、A、B、D，此时总工时最小为3+4+4+3=14。得分六、(10’)假设有9个城市之间要架设电缆，已知城市之间的可行线路和费用如下图所示：v2v88v2v88v3256275462754v7v775v1v6v1v6331334133411v5vv5v9v44141试问：要将所有城市连通，至少需要几条连接边？试求一个费用最小的架设方案。解：1）要将所有城市连通，至少需要8条连接边。2）即求最小支撑树，最小费用为17。11311342231得分七、(12’)如图给出的是连结某产品产地和销地的交通图。弧表示从到的运输线，弧旁的数字表示这条运输线的最大通过能力。现要求制定一个运输方案，使得从运到的产品数量最多，指出该网络的最大流量和最小割集。513951394656449105解：用标号法得到的最终结果为：13(11)9(9)13(11)9(9)4(0)5(5)6(6)5(4)6(4)4(3)4(3)9(9)10(8)5(5)因此，该网络的最大流量为20，最小割集为。得分八、(12’)一项小修计划包括的工作如下表所示。工作网络说明最少工时（d）正常工时（d）成本斜率（元）A(1,2)6920B(1,3)5825C(1,4)101530D(2,4)3510E(3,4)6915F(4,5)1240正常计划工期与最小工期各是多少天？日常经营费为50元/天，最佳工期应是多少天？列出每项工作的相应工时。解：113245ABDCEF(6,9,20)(10,15,30)(5,8,25)(3,5,10)(6,9,15)(1,2,40)关键路径：1345工期19天。首先选择工作E压缩（费用15），可压缩2天。此时，关键路径为2条：145和1345工期17天。首先选择工作F压缩（费用40），可压缩1天；再选择工作C，E同时压缩（费用45），可压缩1天。此时，关键路径为3条：1245,45和1345工期15天。不能继续压缩，因为无论怎样选择都超过了日常经营费为50元/天。