运筹学复习题及参考答案

第1页共13页中南大学网络教育课程考试复习题及参考答案运筹学一、判断题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。[]2.线性规划问题的每一个基本解对应可行解域的一个顶点。[]3.任何线性规划问题存在并具有惟一的对偶问题。[]4.已知yi*为线性规划的对偶问题的最优解，若yi*＞0，说明在最优生产计划中第i种资源已完全耗尽。[]5.单纯形迭代中添加人工变量的目的是为了得到问题的一个基本可行解。[]6.订购费为每订一次货所发生的费用，它同每次订货的数量无关。[]7.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。[]8.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。[]9.对于原问题是求Min，若第i个约束是“＝”，则第i个对偶变量yi≤0。[]10.用大M法或两阶段法单纯形迭代中若人工变量不能出基(人工变量的值不为0)，则问题无可行解。[]11.如图中某点vi有若干个相邻点，与其距离最远的相邻点为vj，则边[vi,vj]必不包含在最小支撑树内。[]12.在允许缺货发生短缺的存贮模型中，订货批量的确定应使由于存贮量的减少带来的节约能抵消缺货时造成的损失。[]13.根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。[]14.在线性规划的最优解中，若某一变量xj为非基变量，则在原来问题中，改变其价值系数cj，反映到最终单纯形表中，除xj的检验数有变化外，对其它各数字无影响。[]15.运输问题是一种特殊的线性规划问题，因而其求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。[]16.动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。[]17.一个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行方案的选择。[]18.在物资价格有折扣的存贮模型中，计算费用时必须考虑物资本身的费用。[]19.若线性规划问题具有可行解,且可行解域有界,则该线性规划问题最多具有有限个数的最优解。[]20.对一个有n个变量，m个约束的标准型线性规划问题，其可行域的顶点数恰好为mnC个。[]21.Dijkstra算法（T、P标号算法）要求边的长度非负。[]22.在求网络最大流问题中，最大流的流量是惟一的，但最大流不一定惟一。[]23.在其他费用不变的情况下，随着单位存贮费用的增加，最优订货批量也相应增大。[]24.状态转移方程为状态变量和决策变量的函数关系。[]25.任何线性规划问题一定有最优解。[]26.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字若从单纯形表中删除，将会影响后面的计算结果。[]24.影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的两个概念。[]28.指派问题效率矩阵的每一行（或每一列）元素分别减去一个常数，将不影响最优指派方案。[]29.任意可行流的流量不超过任意割集的割量。[]30.当订货数量超过一定的值允许打折扣的情况下，打折扣条件下的订货批量要大于不打折扣时的订货批量。[]31.检验数Rj表示非基变量xj增加一个单位时目标函数的改变量。[]32目标函数极大化（MAX型）的指派问题，是将目标函数乘以“－1”化为求最小值，再用匈牙利法求解。[]33.动态规划的基本方程是将一个多阶段决策问题转化为一系列具有递推关系的单阶段的决策问题。[]第2页共13页34.运输问题用闭回路法和用位势法求得的检验数不相同。[]35.容量网络中可行流是最大流的充要条件是不存在发点到收点的增广链。[]36.在其他费用不变的情况下，随着单位缺货费用的增加，最优订货批量也相应减小。[]二、建模题：1.某炼油公司为提高炼油能力和增加企业经济效益，经研究有五种技术改造的投资方案可供选择，它们所需的投资费用年收益如表1所示。其中：方案1和方案2只能选择其中一种，不能兼而实现，并且，如选择方案2，则方案3必须同时选择，或者都不选择。现该公司可供支配的资金总额为：第一年有650万元，第二年仅有460万元。技术履行的结果要求至少应增加出油能力500桶/天，但又不得超过1100桶/天。为了确定该公司总经济效益最大的投资方案，试建立该问题的线性规划模型。表1投资方案表方案序号技改方案内容决策变量投资（万元）年收益（万元）第一年第二年1更新旧装置，提高炼油能力500桶/天X12002001002建造新装置，提高炼油能力1000桶/天X23001502003往新厂建输油管，提高炼油能力100桶/天X315050504往老厂建输油管，提高炼油能力50桶/天X410070305增加槽车运输能力，能提高出油20桶/天X55040202.某钢厂轧制的薄铜板知卷宽度为100CM，现在要在宽度上进行切割以完成下列订货任务：24cm宽的75卷，40cm的50卷和32cm宽的110卷，长度都是一样的。试求解决切割方案的线性规划模型，使切割剩余的边料最少。3.写出下面线性规划问题的对偶问题。1231312323231MinZ=5x+4x+3x2x+7x88x+5x-4x154x+6x=30x,x0,x自由变量4.写出下面线性规划问题的对偶问题：1212121212max70303954055450..93720,0zxxxxxxstxxxx三、填空题：第3页共13页1.某公司利用三种原料生产五种产品，其有关数据如表2，企业的决策是这五种产品各生产多少使企业获利最大。表2产品原料万件产品所用原料数（千克）资源量（千克）ABCDE甲乙丙0.510.500.50.50－0.51.510.5111151210.5万件产品利润（万元）41051010.5已知该问题建立的线性规划模型的最优单纯形表如表3所示，根据提供的信息完成填空。表3cj41051010.5000CBXBx1x2x3x4x5x6x7x8b10.5010x5x7x4121012000.25-0.5-1.50011-1.5-0.5-1010-201101.250.5－Z-1.5-1-5.500-10-101)该问题的最优解。2)目标函数值。3)设y1,y2,y3为相应的对偶变量，则y1,y2,y3的含义可表述为：。4)对偶问题的最优解是。5)企业的关键资源是。2.已知某求极大值（Max型）的线性规划问题初始单纯形表及最终单纯形表如下，根据表中提供的信息及单纯形表迭代规律完成填空。1)该规划问题的初始基本可行解为。2)初始单纯形表中，若选变量x3入基，则出基变量为，目标函数增加值为。3)单纯形表迭代时，围绕主元，通过线性变换需把入基列变成。4)最终单纯形表中，基变量为。5)最终单纯形表中，系数a＝。6)最终单纯形表中，x1的值b=。7)最终单纯形表中，检验数c=,d=,e=。四、计算题：Cj41500CBXBx1x2x3x4x5bθ0x43141080000x5214013000－Z415000……0x40-1/2-21-3/235004x11a201/2b－Zc-1d0e-6000第4页共13页1.对于线性规划模型1212121212max70303954055450..93720,0zxxxxxxstxxxx，请先把模型化成标准型，然后用单纯形表迭代求其最优解。2.某厂从国外引进一台设备，由工厂A至G港口有多条通路可供选择，其路线及费用如图1所示。现要确定一条从A到G的使总运费最小的路线，请将该问题描述成一个动态规划问题，然后求其最优解。3.已知某运输问题的供输关系及单位运价表如下表示：产地销地B1B2B3产量A14258A23537A31324需求量485①列出产销平衡表，并用行列差值法给出该运输问题的初始基可行解。②用位势法求初始可行解对应的各非基变量的检验数。③求出该运输问题的最优解。4.求下面网络节点1到节点7的最短路径。5.把下列线性规划问题化成标准型，然后用单纯形法求最优解及目标函数值。v2v3v4v6v7v14655567v541812AB1C2G2030图1B2C1C3D11D21706050400030403010第5页共13页123512423452456min3225262380jzxxxxxxxxxxxxxxxx　(1)　　(2)(3)6.某商店拟购进一种应时商品出售。经估算，在未来旺季中每出售一箱可净得利润5000元，如旺季过后则只能削价出售，每箱要赔本2000元。这种商品的需求情况经统计分析，具有以下的分布规律：需求量（箱）012345概率P（R）0.050.10.250.350.150.1现商店经理需作出订购该商品多少箱的决策，其最优决策是订购多少箱？获利期望值为多大？最小损失期望值又是多大？7.已知线性规划问题：12341341234jmaxZ256=x+x+x+x2x+x+x82x+2x+x+2x12x0,j=1,2,3,4其对偶问题的最优解为：**124,1yy，要求：①写出该问题的对偶问题。②应用对偶规划的性质，求原问题的最优解。8.某公司打算在三个不同的地区设置4个销售点，根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的利润如表1所示。试问在各个地区应如何设置销售点，才能使每月获得的总利润最大？其值是多少?表1销售店利润地区012341016253032201217212230101416179.某公司每年需电感5000个，每次订购费50元，存贮费为1元/个·年，不允许缺货。若采购少量电感每个单价3元，若一次采购1500个以上则每个单价1.8元，问该公司每次应采购多少个？10.某地的电力公司有三个发电站，它们负责5个城市的供电任务，其输电网络如图4所示。由图可知，城市8由于经济的发展，要求供应电力65MW，三个发电站在满足城市4、5、6、7的用电需要量后，它们还分别剩余15MW、10MW、40MW，输电网络剩余的输电能力见图4节点上是数字。三个发电站在满足城市4、5、6、7的用电需要量后，剩余发电能力共有65MW，与城市8的用电量刚好相等。问：（1）输电网络的输电能力是否满足输电65MW的电力；（2）如不满足，需要增建或改建那些输电线路?10204015MW1010MW25第6页共13页11.有A、B、C、D四项任务需分派给甲、乙、丙、丁四个人去做，这四个人都能承担上述四项任务，但完成各项任务所需时间如下表所示。问应如何分派任务可使完成任务的总工时最少？要求①建立该问题的线性规划模型。②用匈牙利法求出其最优解。任务人ABCD甲917167乙1271416丙8171417丁7911912.设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可选择，而进口港又有三个可选择，进口后可经由两个城市到达目的地，其间的运输费用如图所示（单位：百元），试把该问题描述成一个多阶段决策问题，并用动态规划方法求解。13.试用表上作业法求解下面运输问题的最优解。（要求用行列差值法给初始解，用位势法求检验数。）销地产地B1B2B3供应量A16424A28575需求量3332040307040203010405603030303040401050AB1B2B3C1C2C3D1D2E第7页共13页参考答案一、判断题：1.√2.╳3.√4.√5.√6.√7.√8.√9.╳10.√11.╳12.√13.╳14.√15.╳16.√17.√18.√19.╳20.╳21.√22.√23.╳24.√25.╳26.╳27.√28.√29.√30.√31.√32.╳33.√34.╳35.√36.╳二、建模题：1.见教材1.2节线性规划问题建模。2.解：设在100cm宽的薄铜板上能切割40㎝宽的薄铜板U个，32㎝宽的薄铜板V个，24㎝宽的薄铜板W个，则有以下切割方式：UVW余料24①2