运筹学复习题及参考答案运筹学》一、判断题：在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“ T” ,错误者写“F”。

1.T 2. F 3. T 4.T 5.T 6.T 7. F 8. T 9. F10.T 11. F 12. F 13.T 14. T 15. F1.线性规划问题的每一个基本可行解对应可行域的一个顶点。

( T )2.用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数C j-Z j< 0,则问题达到最优。

( F )3.若线性规划的可行域非空有界，则其顶点中必存在最优解。

( T )4.满足线性规划问题所有约束条件的解称为可行解。

( T )5.在线性规划问题的求解过程中，基变量和非机变量的个数是固定的。

( T )6.对偶问题的对偶是原问题。

( T )7.在可行解的状态下，原问题与对偶问题的目标函数值是相等的。

( F )8.运输问题的可行解中基变量的个数不一定遵循m＋n－1 的规则。

( T )9.指派问题的解中基变量的个数为m＋n。

( F )10.网络最短路径是指从网络起点至终点的一条权和最小的路线。

( T )11.网络最大流量是网络起点至终点的一条增流链上的最大流量。

( F)12.工程计划网络中的关键路线上事项的最早时间和最迟时间往往是不相等。

( F )13.在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔时间比订购模型的间隔时间长。

(T )14.单目标决策时，用不同方法确定的最佳方案往往是不一致的。

( T )15.动态规则中运用图解法的顺推方法和网络最短路径的标号法上是一致的。

( F ) 二、单项选择题1.A2.B3.D4.B5.A6.C7.B8.C9. D 10.B11.A 12.D 13.C 14.C 15.B 1、对于线性规划问题标准型：maxZ=CX, AX=b, X> 0,利用单纯形法求解时，每作一次迭代，都能保证它相应的目标函数值Z 必为( A )。

A. 增大B. 不减少C. 减少D. 不增大2、若线性规划问题的最优解不唯一，则在最优单纯形表上( B )。

A.非基变量的检验数都为零B.非基变量检验数必有为零C.非基变量检验数不必有为零者D.非基变量的检验数都小于零3、线性规划问题的数学模型由目标函数、约束条件和(D )三个部分组成。

A.非负条件B.顶点集合C.最优解 D.决策变量4、已知x i= ( 2, 4), X2=(4, 8)是某线性规划问题的两个最优解，则( B )也是该线性规划问题的最优解。

A. (4,4)B. (1,2)C. (2,3)D.无法判断5、下列数学模型中，( A )是线性规划模B.A.2x4x3xMaxZ= 10X I+X2-3X3 MinZ=3x i+X2 2 — 2X2I+5X2 < 15X3 I+3X2-4X121+X2+2X3 A 81-X 2 + 3X3 = 61 A 0,X2 无约束,X3 < 0C =5x i +6x 2+8x 3-9 D. X 4X I +4X 3-X 4=19 ,X 2-5X 3+4X 4 A6、线性规划问题最终解的情形有（ C ）。

A. 可 行 解 、 最 优 解 、 基 本 解 和 无 解B. 可行解、基本可行解、基本解和最优解C. 最 优 解 、 退 化 解 、 多 重 最 优 解 和 无 解D. 最优解、退化解、多重解和无界解7、 若x 是原问题maxZ=CX, AX < b, X > 0的可行解， y 是其对偶问题 MinS=Yb, YA >C, Y >0的可行解， 则有（ B ）。

A. CX > YbB. CXC YbC.CX=Yb D. 无法确定 8、 下面关于运输问题与线性规划问题的关系， （ C ）是正确的。

A. 运输问题和线性规划问题是两类不同的优化问 题；B.运输问题和线性规划问题是两类相同的优化问 题，但不能用相同的方法求解；C.运 输问题是一类特殊的线性规划问题；D.该两类问题的关系无法确定。

MaxZ=x+4x 2-8x 3+2X 4X +4X -X =299、动态规划问题中的状态变量必须具有11、网络计划技术中关键路线法与计划评审技术两 种方法的根本区别在于（ A ）。

A. 工序时间参数的确定B. 计算原理与计算过程C. 关键路线的确定方法D. 最早时间与最迟时间的确定12、下面关于网络图中的虚工序的描述，正确的是 （ D ）。

A. 虚 工序是技术上的等待，因而它不耗费人力、物力，只耗费时间；B. 虚 工序与实工序一样，包括技术上的等待，因而 它既耗费人力、物力，又耗费时间；C. 虚 工序所描述的是一类实际上不存在的工序，只 是为了作图的需要；D.（ D ）性质。

A. 无后 效性C. 可知性和决策性10、 图的组成要素有（A. 点八\、C. D. B. 无后效性和决 策性 D.无后效性和可知性B ）。

B. 点 及 点 之 间 的 连 线点、边和权工序是表示前后两道工序之间的逻辑关系，因而它既不耗费人力、物力，又不耗费时间。

13、决策的三要素是（C ）。

A. 方案、状态和收益B.方案、状态和损失C. 方案集、状态集和损益矩阵D. 方案集、状态集和概率集14、求解风险型决策问题的最大概率准则，一般适用于（C ）。

A. 状态概率为已知的情形B. 状态概率为相等的情形C. 状态概率悬殊较大的情形D.既然作为决策准则，应该适用于任何情形15、针对某一特定的不确定型的决策问题，分别采用五种决策准则（等可能准则、乐观准则、悲观准则、折衷准则和后悔值准则）进行决策，其决策结果（B ）。

A. 相同B. 一般不相同C.绝大多数相同D. 不能确定三、简述题1. 用图解法说明一般线性规划问题的最优解一定在可行域的顶点上达到。

2. 运输问题是特殊的线性规划问题，但为什么不用单纯形法求解。

3. 建立动态规划模型时，应定义状态变量，请说明状态变量的特点四、下列表是三个不同模型的线性规划单纯形表，请根据单纯形法原理和算法，分别在表中括号中填上适当的数字。

1.计算该规划的目标函数值C j f 20 15 20 0 0Ci X B b X i X2 X3 X4 X520x, 2 1 丄02 -1 020X3 1 0 1 1 1/2 00 x 5 3 0 -1 0 0 1z j 20 30 20 -102、确定上表中输入，输出变量五、已知一个线性规划原问题如下，请写出对应的对偶模型S max = 2x i 5x2j兰4x”3x, +x2兰8x-!, x2色0六、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推法求出S至F点的最短路径及最短路长。

B七、自已选用适当的方法，对下图求最小（生成树）。

o九、下图是某一工程施工网络图（统筹图），图中边上的数字为工序时间（天）,请求出各事项的最早时间和最迟时间，求出关键路线，确定计划工期。

十、某企业生产三种产品A i、A2、A3。

每种产品在销售时可能出现销路好（S i），销路一般（S2）和销路差（S3）三种状态，每种产品在不同销售状态的获利情况（效益值）如表1所示，请按乐观法则进行决策，选取生产哪种产品最为合适。

A 18 13 12（表1）十^一、已知运输问题的运价表和发量和收量如表 所示，请用最小元素法求出运输问题的一组解。

十二、下列表3是一个指派问题的效率表(工作时间 表)，其中A i 为工作人员(i=1, 2, 3, 4)、B j 为工作项目(j=1, 2, 3, 4)，请作工作安排，使总的工作时间最小。

B i B 2 B 3 B 4A 1 4 17 4 A 2 2 2 3 5 A 5 6 4 3（表3）化肥，根据市场调查某地区各种化肥每天最少需求 分别为100吨，60吨，130吨。

该厂每天可供的原 料分别为200吨和240吨。

单位成品化肥所耗费的 原料及销售利润如下A 1 2 9 12 7 A 2 1 3 5 2 A 10 4 2 6B i B 2 B 3 B 49 4 5（表2）十三、有一化肥厂用两种原料A,B 生产C,D,E 三种表。

问每天应生产多少各类化肥，使该厂利润最大。

要求建立线性规划模型，不作具体计算。

《运筹学》参考答案四、计算题1.z=602. X 4输入，X 3输出S min = 4y i + 3y 2+4y 3 y i +y 3> 2 y 2+y 3> 5y i , y 2, y 3> 0八、最短路径：V i f V 3f V 5f V 6f V 7 L=10五、 V 3V5六S=26V 6L=13V 6L=13九A 10④②6 5A i 4 ① 7 4 A 2 ② 2 35 A 5 6 4 ③关键线①一③一④一⑥划工期31十、B i B 2 B 3 B 4 A i A 2 2 _ 一⑨6.12-⑦5①31 54②十二、L =B i B 2 B 3 B 4 50 V十三、解：设成品化肥的产量分别为X i、X2、X3吨，则线性规划模型为：MaxZ =10x i 15x211x3X釘00X2 王26X3 >130捲+1.5x2 +4x3兰2002捲+1.2x2 +x3兰240X j -0, j =1,2,3。