运筹学复习题及参考答案

1、中南大学现代远程敎育课程考试复习 题及參考答案运筹学一、判断题：1. 图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。（）2. 线性规划问题的每一个基本解对应可行解域的一个顶点。（）3. 任何线性规划问题存在并具有惟一的对偶问题。（）4. 已知y：*为线性规划的对偶问题的最优解，若y：*>0,说明在最优生产计划中第i种资源己完全耗尽。 （ ）5. 单纯形迭代中添加人工变量的目的是为了得到问题的一个基本可行解。（）6. 订购费为每订一次货所发生的费用，它同每次订货的数量无关。（）7. 如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。（）8. 用单纯形法

2、求解血x型的线性规划问题时，检验数Rj>0对应的变量都可以被选作入基变量。（）9. 对于原问题是求Him若第i个约束是“ = ”，则第i个对偶变量yiWO。（）10. 用人M法或两阶段法单纯形迭代中若人工变量不能出基（人工变量的值不为0）,则问题无可行解。 （ ）11. 如图中某点Vi有若干个相邻点，与其距离最远的相邻点为vj,则边vi,vj必不包含在最小支撑树内。 （ ）12. 在允许缺货发生短缺的存贮模型中，订货批量的确定应使由于存贮量的减少带来的节约能抵消缺货时造成的损失。（）13. 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具

3、有无界解。（）14. 在线性规划的最优解中，若某一变量xj为非基变量，则在原来问题中，改变其价值系数cj,反映到最终单纯形表中，除xj的检验数有变化外，对其它各数字无影响。（）15. 运输问题是一种特殊的线性规划问题，因而其求解结果也可能出现下列四种情况之一：有惟一最优解,有无穷多最优解，无界解，无可行解。（）16动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。（）17. 个动态规划问题若能用网络表达时，节点代表各阶段的状态值，各条弧代表了可行方案的选择。 （ ）18. 在物资价格有折扣的存贮模型中，计算费用时必须考虑物资本身的费用。（）19. 若线性规划问题具有可行

4、解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解。（）20. 对一个有n个变量，m个约束的标准型线性规划问题，其可行域的顶点数恰好为个。（）21. Dijkstra算法（T、P标号算法）要求边的长度非负。（）“22. 在求网络最大流问题中，最大流的流量是惟一的，但最大流不一定惟一。（）23. 在其他费用不变的情况下，随着单位存贮费用的增加，最优订货批量也相应增人。（）24. 状态转移方程为状态变量和决策变量的函数关系。（）25. 任何线性规划问题一定有最优解。（）26一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字若从单纯形表中删除，将会影响 后面的计算结果。（）27.

5、 影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的 两个概念。（）28. 指派问题效率矩阵的每一行（或每一列）元素分别减去一个常数，将不影响最优指派方案。（）29. 任意可行流的流量不超过任意割集的割量。（）30. 当订货数量超过一定的值允许打折扣的情况下，打折扣条件下的订货批量要人于不打折扣时的订货批量。（）31. 检验数Rj表示非基变量xj增加一个单位时目标函数的改变量。（）32. 目标函数极人化（MAX型）的指派问题，是将目标函数乘以“一1”化为求最小值，再用匈牙利法求解。 （）33. 动态规划的基本方程是将一个多阶段决策问题转化为一系列具有递推关

6、系的单阶段的决策问题。34. 运输问题用闭回路法和用位势法求得的检验数不相同。（）35. 容量网络中可行流是最人流的充要条件是不存在发点到收点的增广链。（）36. 在其他费用不变的情况卞，随着单位缺货费用的增加，最优订货批量也相应减小。（）二、线性规划建模题：1女子体操团体赛规定：（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡木、鞍马和自由体操。（2）每个运动员最多参加3个项目，并且每个项目只能参赛一次。（3）每个项目至少要有人参赛一次，并且总的参赛人次数等于10。（4）每个项目采用10分制计分，将10次比赛的得分求和，并排序，分数越高成绩越好。已知代表队5 名运动员各单项的预赛成绩

7、如表7所示。表7项目人员高低杠平衡木鞍马自由体操甲8.69. 78.99.4乙9.28. 38.58. 1丙8.88. 79. 39.6T8. 57.89. 57.9戊8.09.48.27.7为安排运动员的参赛项目使团体总分最高，请建立该问题的线性规划模型。2. 某钢厂轧制的薄铜板知卷宽度为100CM,现在要在宽度上进行切割以完成卞列订货任务：24cm宽的 75卷，40cm的50卷和32cm宽的110卷，长度都是一样的。试求解决切割方案的线性规划模型，使切割 剩余的边料最少。三、填空题：1卞面为一线性规划模型（Max型）迭代过程中的某一单纯形表，表中Cb列表示对应基变量的价值系 数。G行表示各

8、变量的价值系数。要求：Cj( )()()()()CbXB隔心屁b4()11202J206()0121-1130-Z030-2-2-260(1)把单纯形表中的空格补充完整。(2)基本可行解为：x*=（)T(3)目标函数值为：z=（）。(4)当前基本可行解是否是最优解。（）注：填是或不是2.已知某线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表见卜表，请将表中空白处数字填上。CJ2-11000CBXBX1X：X3X4X5X<5b0X4311100600X51-12010100X«11-100120-z2-1100000X4()()1()-1-2()2Xi()()0.5(

9、)1/21/2()()x2()()-1.5()-1/21/2()-z()()()()()（ 丿()四、简答题：1. 某公司利用三种原料生产五种产品，其有关数据如下表，企业的决策是这五种产品各生产多少使企业获 利最大。产品原料万件产品所用原料数（T克）资源量（T克）ABCDE甲0. 510. 500.55乙0. 500. 51.5112丙0. 5111110. 5万件产品利润（万元）41051010. 5已知该问题建立的线性规划模型的最优单纯形表如下表所示，请回答下述问题:（1）写出该问题的最优解及目标函数值。（2）写出该问题的对偶问题（需指明对偶变量的含义）。（3）对偶问题的最优解是多少？（4

10、）哪些资源是企业的关键资源？为什么？cj410b1010. 5000XbX1x：X3X4X5X6：7Xsb3X512101 200104X70. 25-05-1. 500 11-151.250Xt-0.5-1010 -2010. 5-Z"1. 5-1-5. 500 -10-10-110五、写出下面线性规划问题的对偶问题。Mm Z = 5xx+4x2 + 3x32x1 +7x3 > 88x1+5x2-4x3 <154x2 十 6x3 = 30 x2,x3 no,X自由变量六、计算题：maxz = 3“ +5x2A； < 41 对于线性规划模型2儿512 ，请先把模型化

11、成标准型，然后用单纯形表迭代求其最优解。st.< 3兀 +2x2 <18兀丹心no2. 某建筑工地每月需求水泥量为1200吨，每吨定价为1500元，不允许缺货。设每吨每月的存储费为价格 的2%,每次订货费为1800元，需要提前7天订货。试求经济订购批量、每月总费用和再订货点。3. 已知某运输问题的供输关系及单位运价表如下表示：BiB：b3产量Ai4258A三3537A31324需求量1S51）列出产销平衡表，并用行列差值法给出该运输问题的初始基可行解。2）用位势法求初始可行解对应的各非基变量的检验数。3）求出该运输问题的最优解。4. 求下面网络节点1到节点7的最短路径。5某商店拟购

12、进一种应时商品出佔:。经估算，在未来旺季中每出售一箱可净得利润5000元，如旺季过后 则只能削价出售，每箱要赔本2000元。这种商品的需求情况经统计分析，具有以下的分布规律：需求量(箱)012345概率P (R)0. 050. 10. 250. 350. 150. 1现商店经理需作出订购该商品多少箱的决策，其最优决策是订购多少箱？获利期望值为多人？最小损失 期望值又是多大？6. 已知线性规划问题： max Z=2x1+x2+5x$ + 6x42X+x3+x4 <8< 2x1+2x2+x3+2x4 <12Xj>0,j=l,2,3,4其对偶问题的最优解为：y： = 4,y=

13、l,要求： 写出该问题的对偶问题。 应用对偶规划的性质，求原问题的最优解。7. 某公司打算在三个不同的地区设置4个销售点，根据市场预测部门估计，在不同的地区设置不同数量的 销售店，每月可得到的利润如表1所示。试问在各个地区应如何设置销售点，才能使每月获得的总利润最 大？其值是多少？表1地区012341016253032201217212230101 116178. 用隐枚举法求解下面01型整数规划问题:Max Z = 2xk + x2 -xY + 3x2 +x3 < 24x2 +x3 < 5s./+ 2x2 -x3 < 2X + 代< 4xx2,x5 = 0 或19某地

14、的电力公司有三个发电站，它们负责5个城市的供电任务，其输电网络如图4所示。由图可知，城 市8由于经济的发展，要求供应电力65W,三个发电站在满足城市巾、5、6、7的用电需要量后，它们还 分别剩余15MW、10MW、40W,输电网络剩余的输电能力见图4节点上是数字。三个发电站在满足城市4、5、6、7的用电需要量后，剩余发电能力共有65MW,与城市8的用电量刚好相等。问：(1)输电网络的输电能力是否满足输电65MW的电力：(2)如不满足，需要增建或改建那些输电线路?图410设需要某物品12件/天，不允许缺货，存贮费率为002元/件一天。为满足需要，可以采取订购或自 行组织生产。有关数据如下：订购自

15、行生产提前期或生产准备期8天13天物品单位11元/件9. 6元/件每次订购费或准备费20元90元补充速率OO25件/天试决定经济的物品供应来源：订购或自行生产？订购或自行生产的经济订购批量、存贮水平及费用各 是多少？11 设某工厂自国外进I I一部精密机器，由机器制造厂至出丨I港有三个港I I可选择，而进I I港又有三个可 选择，进II后可经由两个城市到达目的地，其间的运输费用如图所示(单位：百元)，试把该问题描述成 一个多阶段决策问题，并用动态规划方法求解。12. F图表示7个城市间拟修建一条连接各个城市的通信线路，各边的权数表示两个城市之间线路的修建 费。求连接各城市通信线路最小修建费用方

16、案。D13.赛格工厂生产汽车零件，供“S”型轿车配套所用。由于轿车市场供不应求，故该厂生产汽车零件 需求比较稳定，每月约3万个，平均每天1000个。按该厂生产能力，如果单为“S”型轿车配套，每天生 产能力可达5000件，故在每个月中，仅安排一部分时间生产为“S”型轿车配套的零件，其余时间生产为 其他型号汽车配套的零件。因此在生产为“S”型轿车配套零件前，生产设备要提前一天进行调整，每次 为调整而花的费用为2000元。此外，由于“S”型轿车生产厂实行“准时生产制”(Just in time),只允 许该厂每天送1000个零件，因此，其余部分只能在本厂储存起来，每个产品储存费用为0.05元/天，现

17、 在的问题是该厂应怎样安排该零件生产批量，使总费用最低？(计算生产批量、生产周期及总费用)，再 订货点是多少？715参考答案一、判断题:1. J2.X3. V4. J5. J6. J7. J8. J9.X10. V11.X12. V13. X14. V15. X16. V17. V18. V19. X20. X21. J22. V23. X24. J25. X26. X27. V28. V29. J30. V31. V32. X33. J34. X35. V36. X二、线性规划建模题：1. 解：此题为0 1规划问题，设X,为第名运动员（1=甲，乙，丙，丁，戊）参加第j个项目的比赛, C1J为

18、运动员1参加j项目的成绩，则有：乞护3 ,i=l,5i乞% 21, j=l,4i另另® = 1002.解:设在100cm宽的薄铜板上能切割40 cm宽的薄铜板U个，32 cm宽的薄铜板V个，24 cm宽的薄铜板W个，则有以卞切割方式:如U2110000V0103210W 余料2402142120411222044为上述第j种切割方式切割100 cm铜板数，有:Min Z=2X +4x2 十 12x3 +4x4+12x5 +20x6 +4x7 x1+x2+x3> 50x2 +3x4+2x$+x6>110x2+2x3+x5+2x6+4x7 > 75xj>0(j=l

19、,.-7)三、填空题:1.Cj(4)(2)(6)(0)(0)52召X2心兀b4（X1）112021206（X3）0121-1130-20-30-2-2-260（1）单纯形表填空如上表示。（2）基本可行解为：X*=（20,0,30,0,0）T（3）目标函数值为：Z=（260）。（4）是2. 已知某线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表见卜表，请将表中空白处数字填上。CJ2-11000cBXEXix2X3X4X5X6b0X4311100600X51-12010100X611-100120-z2-1100000X4(0)(0 )1(1 )-1-2(10)2Xi(1)(0 )0.

20、5(0 )1/21/2(15)(-1)X：(0 )(1 )-1.5(0 )-1/21/2(5)-z(0 )(0 )(-1.5)(0)(-1.5)(-0.5 )(一25)注计算方法如下：（!）单纯形表中基变量的系数列向量为单位列向量，检验数为0。'1-1-2'（2）从最终单纯形表中抄出最优基的逆矩阵Bl=01/21/2,根据单纯形表的计算公式0-1/21/2P（=B»X严分别算出单纯形表中Xj的系数列向量、检验数和基变量的值。四、简答题1（1）最优解为：X=（0,0Q05，10Ol25）T, Z=110o（2）设yby2,y3为甲、乙、丙三种资源出售带来的价值增值，则对

21、偶问题为：（1分）nun z =+12)、+ 10.5y3（L5 分）05) + 05儿+05丫3 >4（L5 分）Ji+比 nio(L5 分)05比-05丫2+丫3 n5(L5 分)15儿+ y3 nio（1分）+ y2+y3 >10.5（1分）>00=1,2,3)（1分）3.从原问题最优单纯形表的检验数知对偶问题的最优解为：Y = （）L）.）3）= a（M0） o4甲、丙资源是企业的关键资源，因为其影子价格分别为1,10,均人于0,意味着增加这两种资源的 量，企业的利润会增加。五、写出下面线性规划问题的对偶问题。解：其对偶问题为：max w = 8）+15）、+ 30儿

22、（2 分）+ 8 y2 =5（2 分）5）+4）异4（1 分）7 ）'i - 4儿 + 6y3 < 3（2 分）yi>0,y2<0.y3为自由变量（3分）六、计算题：1.解：添加松驰变量X3,X4,X5把模型化成标准型：max z = 3丐 + Sx2兀 + x3 =4 2/+ xA =12（5 分）$/<3 + 2x2 + x5 =18x;. >0（7 = 1,.5）单纯形表迭代过程如下：（每一单纯形表各占6分，其中正确写出基变量1分，b列1分，其余计算4分）cj35000CBXBXiX：X3X4X5be0X31010040X402010126 0X53

23、2001189-z35t00000X310100445X20101/2060X5300-1162-z3t00-5/20-300X30011/3-1/325X20101/2063Xi100-1/31/32-z000-3/2-1-36最优解为:X =（xpx2,x3,x4,x5）r = （2,6,2,0,0/,（1 分）Z=36（1 分）（2分）（5分）2解：Ch=30 （元/吨月人 Co=1800 （元/次）,R = 1200 （吨/月） 故0 =胯=严普 = 379.5（吨）最小费用：产= j2RQCh =5/2x1200x30x1800 = 11384.2（元/月），（5 分）再订货点：L=

24、RTl= 1200X74-30 = 280 吨。（3 分）3 产大于销，增添假想销地B4,列出产销平衡表（3分），用行列差值法给初始解（5分）如下表示:产地Bib3b3b4产量行差值Ai4（X）2 (8)5（X）o（X）82,2,3Az3（X）5 (O)3 (5)0 (2)73,0,2A31 (4)3 (X)2 (0)0（X）41,1,-需求量4852列差值2,2,-1,1,31,1,22,- 用位势法求初始可行解对应的各非基变量的检验数：对基变量有：R旷® （uKj尸0,求出行、列位势，如表示：（10分）产地Bib3b3b4产量行位势Ai4（X）2 (8)5（X）0（X）8Ui=0

25、Az3（X）5（0）3 (5)0 (2)7u：=3A31 (4)3（X）2 (0)o (X)4U3=2需求量4852列位势V1=1vz=2vj=0V4= 3利用&产厂（叶可求出非基变量的检验数:Rll=5 , Rj3=5, R4=3 , R.21=l 9 R.32= 19 R-34=l o 选x理为入基变量，作闭回路调整，调整量为0,如表示：（3分）也产地BiBib3B4行位势Ai4<X)2 (8)5（X）0（X）ui=0Az3（X）5（X）3 (5)0(2)uz=2A31 (4)3 (0)2 (0)0（X）U3=l列位势Vi=0v2=2v3=lv4=2再次利用Rj=cy（Ui+

26、Vj）求出非基变量的檢验数:（3分）Rm=4, Ri3=4, Rn=2, R2i=l> R22=l, RJ7=T°当前调运方案为最优方案，如上表示，最小运费Z=2X8 + 3X5 + 1X4 = 35。（1分）4. 2.用T、P标号算法： 给V】点标P标号，其他点标T标号，为+ 8。（1分） 从V】点出发，修改巾、V3、点的T标号，并把其中最小者改为P标号。T（v2）=4=P（v2）, T"尸6, T（g）=5=P（vJ。（2 分） 从刚刚获得P标号的点v2出发，可达v3,v5 （与其相邻的且还未获得P标号的点），修改其T标号, 并把最小T标号v3,v5改为P标号。（

27、2分）T（V3）=min6, p（V2）+d：3 =niin6,4+1 =5=P（V3）,T（V5）=11。 依此类推，各点的P标号如图所示。（其余各个P标号点各占2分）从 V1 到 V7 的最短路为：Vi f V/f V3-*V5-*V7 或 Vi f巧V6V5V"距离为16。（2分）B =2000 元5-解：由题意有：a =5000元,（2分）SL =50005000 + 2000= 0.714（5分）由表中的累计概率可知:3< 工 (x) = °75A-0（5分）最优决策是订购3箱。获利期望值：（2分）EC(Q) =2000X3X0.05+ (5000-2000

28、X2) X0.1 + (5000X2-2000X 1) X0.25 + 5000X3X0.6= 10800 元。(3分)同理可计算出最小损失期塑值为2950元。linn W=8y】十 12丫三（2分）2比 +2y2 > 2（2分）2y2>l（1分）丫十（2分）Yi 十2% > 6（2分）沪0尸1,2（1分）（3分）6. 解:（1）其对偶问题为:（2）设对偶问题的松驰变量为畑y沙 把* =4?= 1代入对偶问题中的约束方程，知yHO,由互补松驰性有：xi=xz=Oo（5分）又= U均不等于0,由互补松驰性知原问题的两个约束对应的松驰变量Xci=O,fx,+x4 =8甘。，则原问

29、题约束方程可化为：仁2；冃2'解得“4'心。分）即原问题最优解为：X*= （0,0,4,4） T, Z=44o（1分）7. 解：设给每一个地区设置一个销曹点为一个阶段，共三个阶段。（1分）Xk为给第k个地区设置的销售点数。（1分）Sk为第k阶段还剩余的销曹点数，Si=4（1分）状态转移方程为：SzSkXk（1分）dk（Xk）为在第k个地区设置Xk个销售点增加利润。（1分）最优指标函数fk（Sk）为第k阶段把Sk个销售点时分给第k、k+1,-3个销售点获取的最大收益。（1 分）指标函数递推方程：人（SQ = maxyS阳）+心（几忑）, k=2,l（1分）边界方程为：/(S3)

30、= t/3(53,x3)o(1 分)逆推计算如下：k=3 时：S3=x3（4 分）XA （3）= 3（$3，%3）朋）X3012340000110101214142316163417174k=2 时：S3= S2-x2（4 分）Xd2（S2,x2）+fi（S2-x2）人（SJX：01234000010+1012-012120+1412+1017+022130+1612+1417+1021+027240+1712+1617+1421+1022+0312或3k=l 时：Sz= Si-Xi（2 分）XdQ/J + fS-兀）恥）X：0123440 + 3116 + 2725 + 2230+1232

31、+ 0472最优决策方案为：第一个地区设置2个销售点，第二个地区设置1个销售点，第三个地区设置1个销售点, 每月可获总利润为47。（2分）8. 解：问题为求极大型，所有的变量前的价值系数需变为负号，故令兀=1-和，兀=1-兀，模型变为：（2 分）MaxZ = 3 （xj+ + 2可F）（1分）X 3x>'+ X3 5 2（1）（1分）-4x2 '+< 1（1分）s.t. <X|1 2xJ < 1'（1 分）4x2x3 <-l（1分）和,耳农3 =0或1（1分）用目标函数值探索法求最人值：（5分）xrx2，x3是否满足约束方程Z（1）（2）（

32、4）0000X31010JJV2从表中口J以看出,当0, Xj = 1,X3 = 0时具最大目标函数值,即召=1, X2 = 0, = 0 , Zmax=2o（2分）9.解：（1）虎构发点V如图示。（5分）（2）求出网络的最人流如图示，最人流量为55,不满足输电65MW的电力。（15分）（3）在饱和弧v5-v8±增建输送10MW的新线路，使其容量增加到20MW,而把非饱和弧vs-Vj -v4 f V6及vs->v3->v6弧上各增加5MW的流量，V6f V5弧上增加10MW的流量，即可满足输电65MW的电力21需求量。（5分）10解：因为订购与自行生产的物品单价不同，这里

33、的费用必须包含物品本身的费用。（1）若订购，计算一天的总费用（含物品费用）Ch=O. 02 （元/件天人 Co=20 （元/次），R=12 （件/天）f = y2RCoCh = V2 x 12 x 0.02 x 20 = 3.1 （元/ 天）一天的费用：尸=物品本身的费用+总存贮费Fl = 12Xll + 3.1 = 135.1 （元/天）订购批量：e*= 155 （件/次）存贮水平：L =/?匚=12乂8 = 96（件）（2）若自行生产，计算一天的总费用（含物品费用）：Ch=0. 02 （元/件天人 Cp=90 （元/次），R=12 （件/天）2512 x（2x12x90x0.02 = 4.74 （兀/ 天）一天的费用：尸=物品本身的费用+总存贮费F2 = 12 X 9.6+4.74= 119.94