运筹学复习题及参考答案

中南大学现代远程教育课程考试复习题及参考答案

运筹学

一、判断题：

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. 若线性规划问题具有可行解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解。( )

m

20. 对一个有n个变量，m个约束的标准型线性规划问题，其可行域的顶点数恰好为n个。( ) 21. Dijkstra算法（T、P标号算法）要求边的长度非负。( )

22. 在求网络最大流问题中，最大流的流量是惟一的，但最大流不一定惟一。 ( )

23. 在其他费用不变的情况下，随着单位存贮费用的增加，最优订货批量也相应增大。( ) 24. 状态转移方程为状态变量和决策变量的函数关系。( ) 25. 任何线性规划问题一定有最优解。( )

26. 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字若从单纯形表中删除，将会影响后面的计算结果。( )

27. 影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的两个概念。( )

28. 指派问题效率矩阵的每一行（或每一列）元素分别减去一个常数，将不影响最优指派方案。( ) 29. 任意可行流的流量不超过任意割集的割量。 ( )

30. 当订货数量超过一定的值允许打折扣的情况下，打折扣条件下的订货批量要大于不打折扣时的订货批量。( )

31. 检验数Rj表示非基变量xj增加一个单位时目标函数的改变量。( )

32. 目标函数极大化（MAX型）的指派问题，是将目标函数乘以“－1”化为求最小值，再用匈牙利法求解。( )

33. 动态规划的基本方程是将一个多阶段决策问题转化为一系列具有递推关系的单阶段的决策问题。

C

1

( )

34. 运输问题用闭回路法和用位势法求得的检验数不相同。( )

35. 容量网络中可行流是最大流的充要条件是不存在发点到收点的增广链。 ( )

36. 在其他费用不变的情况下，随着单位缺货费用的增加，最优订货批量也相应减小。( ) 二、线性规划建模题：

1.女子体操团体赛规定：

（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡木、鞍马和自由体操。 （2）每个运动员最多参加3个项目，并且每个项目只能参赛一次。 （3）每个项目至少要有人参赛一次，并且总的参赛人次数等于10。

（4）每个项目采用10分制计分，将10次比赛的得分求和，并排序，分数越高成绩越好。已知代表队5名运动员各单项的预赛成绩如表7所示。

表7

项目 人员 甲 乙 丙 丁 戊 高低杠 8.6 9.2 8.8 8.5 8.0 平衡木 9.7 8.3 8.7 7.8 9.4 鞍马 8.9 8.5 9.3 9.5 8.2 自由体操 9.4 8.1 9.6 7.9 7.7 为安排运动员的参赛项目使团体总分最高，请建立该问题的线性规划模型。

2.某钢厂轧制的薄铜板知卷宽度为100CM，现在要在宽度上进行切割以完成下列订货任务：24cm宽的75卷，40cm的50卷和32cm宽的110卷，长度都是一样的。试求解决切割方案的线性规划模型，使切割剩余的边料最少。 三、填空题：

1.下面为一线性规划模型（Max型）迭代过程中的某一单纯形表，表中CB列表示对应基变量的价值系数。Cj行表示各变量的价值系数。要求： cj （ ） （ ） （ ） （ ） （ ） cB 4 6 -Z

（1）

（2） （3） （4）

xB （ ） （ ） x1 1 0 0 x2 x3 0 1 0 x4 2 -1 -2 x5 -1 1 -2 b 20 30 -260 1 21 2-3 把单纯形表中的空格补充完整。

基本可行解为：X*＝（ ）T 目标函数值为：Z＝（ ）。 当前基本可行解是否是最优解。（ ）[注：填是或不是]

2

2．已知某线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表见下表，请将表中空白处数字填上。 cj CB XB 0 0 0 －Z 0 2 ( ) －Z x4 x1 x2 x4 2 －1 1 0 0 0 x1 x2 x3 x4 x5 x6 3 1 1 1 0 0 b 60 10 20 0 ( ) ( ) ( ) x5 1 －1 2 0 1 0 x6 1 1 －1 0 0 1 2 －1 1 0 0 0 ( ) ( ) 1 ( ) －1 －2 ( ) ( ) 0.5 ( ) 1/2 1/2 ( ) ( ) -1.5 ( ) －1/2 1/2 ( ) ( ) ( ) ( ) （ ） ( ) ( ) 四、简答题：

1.某公司利用三种原料生产五种产品，其有关数据如下表，企业的决策是这五种产品各生产多少使企业获利最大。

产品 原料 甲 乙 丙 万件产品利润（万元） 万件产品所用原料数（千克） A B C D E 0.5 1 0.5 0 0.5 0.5 0 －0.5 1.5 1 0.5 1 1 1 1 4 10 5 10 10.5 资源量（千克） 5 12 10.5 已知该问题建立的线性规划模型的最优单纯形表如下表所示，请回答下述问题： （1） 写出该问题的最优解及目标函数值。

（2） 写出该问题的对偶问题（需指明对偶变量的含义）。 （3） 对偶问题的最优解是多少？

（4） 哪些资源是企业的关键资源？为什么？ cj CB 3 4 0 －Z

4 10 5 10 10.5 0 0 0 XB x1 x2 x3 x4 x5 x6 x7 x8 x5 x7 x4 b 1 2 1 0 1 2 0 0 10 0.25 -0.5 -1.5 0 0 1 1 -1.5 1.25 -0.5 -1 0 1 0 -2 0 1 0.5 -1.5 -1 -5.5 0 0 -1 0 -10 -110 3

五、写出下面线性规划问题的对偶问题。

Min Z = 5x1+4x2 + 3x3?2x1 +7x3 ?8 ? 8x+5x-4x ?15 ?123 ?? 4x2 + 6x3 = 30? x2,x3?0,x1自由变量?六、计算题：

maxz?3x1?5x2?x1?4?1.对于线性规划模型?2x2?12，请先把模型化成标准型，然后用单纯形表迭代求其最优解。 st.??3x1?2x2?18??x1,x2,x3?02.某建筑工地每月需求水泥量为1200吨，每吨定价为1500元，不允许缺货。设每吨每月的存储费为价格

的2％，每次订货费为1800元，需要提前7天订货。试求经济订购批量、每月总费用和再订货点。 3.已知某运输问题的供输关系及单位运价表如下表示：

产地 销地 A1 A2 A3 B1 4 3 1 B2 2 5 3 B3 5 3 2 产量 8 7 4 需求量 4 8 5 1)列出产销平衡表，并用行列差值法给出该运输问题的初始基可行解。 2)用位势法求初始可行解对应的各非基变量的检验数。 3)求出该运输问题的最优解。

4.求下面网络节点1到节点7的最短路径。

v 2 7

4 1 v 1 6 v 3 4 5 2 v 4 5 v5 5 6 v 7 8 1 v6 4

5.某商店拟购进一种应时商品出售。经估算，在未来旺季中每出售一箱可净得利润5000元，如旺季过后则只能削价出售，每箱要赔本2000元。这种商品的需求情况经统计分析，具有以下的分布规律：

需求量（箱） 概率P（R） 0 0.05 1 0.1 2 0.25 3 0.35 4 0.15 5 0.1 现商店经理需作出订购该商品多少箱的决策，其最优决策是订购多少箱？获利期望值为多大？最小损失期望值又是多大？ 6.已知线性规划问题：

max Z=2x1+x2+5x3+6x4?2x1 +x3+x4?8??2x1+2x2+x3+2x4?12?x?0,j=1,2,3,4?j**其对偶问题的最优解为：y1?4,y2?1，要求：

①写出该问题的对偶问题。

②应用对偶规划的性质，求原问题的最优解。

7.某公司打算在三个不同的地区设置4个销售点，根据市场预测部门估计，在不同的地区设置不同数量的销售店，每月可得到的利润如表1所示。试问在各个地区应如何设置销售点，才能使每月获得的总利润最大？其值是多少?

表1 销售店 利润 地区 1 2 3 0 0 0 0 1 16 12 10 2 25 17 14 3 30 21 16 4 32 22 17

8.用隐枚举法求解下面0－1型整数规划问题：

MaxZ?2x1?x2?x3?x1?3x2?x3?2?4x?x?523??s.t.?x1?2x2?x3?2?x?4x?x?423?1??x1,x2,x3?0或1

9.某地的电力公司有三个发电站，它们负责5个城市的供电任务，其输电网络如图4所示。由图可知，城

市8由于经济的发展，要求供应电力65MW，三个发电站在满足城市4、5、6、7的用电需要量后，它们还分别剩余15MW、10MW、40MW，输电网络剩余的输电能力见图4节点上是数字。三个发电站在满足城市4、5、6、7的用电需要量后，剩余发电能力共有65MW，与城市8的用电量刚好相等。问：（1）输电网络的输

5