中南大学《运筹学》程试题及参考答案 判断题(在下列各题中,你认为题中描述的内容为正确者,在题尾括号 内写“√”,错误者写“×”。) 1.图解法提供了求解线性规划问题的通用方法。 2.用单纯形法求解一般线性规划时,当目标函数求最小值时,若所有的检验数GZ ≥0,则问题达到最优。 3.在单纯形表中,基变量对应的系数矩阵往往为单位矩阵 4.满足线性规划问题所有约束条件的解称为基本可行解。 5.在线性规划问题的求解过程中,基变量和非基变量的个数是固定的。() 6.对偶问题的目标函数总是与原问题目标函数相等 7.原问题与对偶问题是一一对应的 8.运输问题的可行解中基变量的个数一定遵循m+n-1的规则 9.指派问题的解中基变量的个数为m+n 10.网络最短路径是指从网络起点至终点的一条权和最小的路线 11网络最大流量是网络起点至终点的一条增流链上的最大流量。 12.工程计划网络中的关键路线上事项的最早时间和最迟时间往往不相等。() 13.在确定性存贮模型中不许缺货的条件下,当费用项目相同时,生产模型的间隔 时间比订购模型的间隔时间长。 4.单目标决策时,用不同方法确定的最佳方案往往是一致的。 15.动态规划中运用图解法的顺推方法和网络最短路径的标号法上是一致的。 简述题 1.用图解法说明线性规划问题单纯形法的解题思想。 2.运输问题是特殊的线性规划问题,但为什么不用单纯形法求解。 3.建立动态规划模型时,应定义状态变量,请说明状态变量的特点。 填空题 1.图的组成要素 2.求最小树的方法有
中南大学《运筹学》程试题及参考答案 一、判断题(在下列各题中，你认为题中描述的内容为正确者，在题尾括号 内写“√”，错误者写“×”。) 1. 图解法提供了求解线性规划问题的通用方法。 ( ) 2. 用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数 Cj-Zj ≥0，则问题达到最优。 ( ) 3. 在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。 ( ) 4. 满足线性规划问题所有约束条件的解称为基本可行解。 ( ) 5. 在线性规划问题的求解过程中，基变量和非基变量的个数是固定的。 ( ) 6. 对偶问题的目标函数总是与原问题目标函数相等。 ( ) 7. 原问题与对偶问题是一一对应的。 ( ) 8. 运输问题的可行解中基变量的个数一定遵循 m＋n－1 的规则。 ( ) 9. 指派问题的解中基变量的个数为 m＋n。 ( ) 10. 网络最短路径是指从网络起点至终点的一条权和最小的路线。 ( ) 11. 网络最大流量是网络起点至终点的一条增流链上的最大流量。 ( ) 12. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往不相等。 ( ) 13. 在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔 时间比订购模型的间隔时间长。 ( ) 14. 单目标决策时，用不同方法确定的最佳方案往往是一致的。 ( ) 15. 动态规划中运用图解法的顺推方法和网络最短路径的标号法上是一致的。 ( ) 二、简述题 1. 用图解法说明线性规划问题单纯形法的解题思想。 2. 运输问题是特殊的线性规划问题，但为什么不用单纯形法求解。 3. 建立动态规划模型时，应定义状态变量，请说明状态变量的特点。 三、填空题 1. 图的组成要素 ； 。 2. 求最小树的方法有 、
3.线性规划解的情形有 4.求解指派问题的方法是 5.按决策环境分类,将决策问题分为 6.树连通,但不存在 四、下列表是线性规划单纯形表(求Zmnx),请根据单纯形法原理和算法。 1.计算该规划的检验数 0-10 2.计算对偶问题的目标函数值 3.确定上表中输入,输出变量 五、已知一个线性规划原问题如下,请写出对应的对偶模型 x1+x2≤7 2x1+3x,≥16 x1,x2≥0
3. 线性规划解的情形有 、 、 、 。 4. 求解指派问题的方法是 。 5. 按决策环境分类，将决策问题分为 、 、 。 6. 树连通，但不存在 。 四、下列表是线性规划单纯形表（求 Zmax），请根据单纯形法原理和算法。 1. 计算该规划的检验数 2. 计算对偶问题的目标函数值 3. 确定上表中输入，输出变量 五、已知一个线性规划原问题如下，请写出对应的对偶模型 max 6 1 2 S = x + x + + , 0 2 3 16 7 1 2 1 2 1 2 x x x x x x Cj → 3 2 0 0 0 Ci xB b x1 x2 x3 x4 x5 3 x1 3 1 1 2 0 -1 0 2 x3 4 0 1 1 1/2 0 z j 3 3.5 2 -2 0 c j－z j
六、下图为动态规划的一个图示模型,边上的数字为两点间的距离,请用逆推 法求出S至F点的最短路径及最短路长。 7 七、自己选用适当的方法,对下图求最小(生成树 八、用标号法求下列网络Ⅴ1→V的最短路径及路长 Va 九、下图是某一工程施工网络图(统筹图),图中边上的数字为工序时间天), 请求出各事项的最早时间和最迟时间,求出关键路线,确定计划工期
A1 11 B2 六、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推 法求出 S 至 F 点的最短路径及最短路长。 七、自己选用适当的方法，对下图求最小(生成)树。 八、用标号法求下列网络 V1→V7的最短路径及路长。 九、下图是某一工程施工网络图(统筹图)，图中边上的数字为工序时间(天)， 请求出各事项的最早时间和最迟时间，求出关键路线，确定计划工期。 B1 S A2 7 10 B3 9 C2 13 F C1 10 10 7 5 12 14 6 6 10 5 6 8 V1 V7 V5 V6 V4 V3 V2 5 4 3 5 3 1 7 6 1 7 3 1 V1 2 3 3 5 2 3 3 5 6 V3 V2 V4 V5 V6 2 3 1 4 5 6 5 12 4 9 10 5 0 9 4
十、某企业生产三种产品A、A2、A3每种产品在销售时可能出现销路 好(S1)销路一般(S2)和销路差S3)三种状态,每种产品在不同销售状态的获利情 况效益值如表1所示,请按乐观法则进行决策,选取生产哪种产品最为合适。 犬态 效益值 S? A 10 A 20129 151312 (表 十一、已知运输问题的运价表和发量和收量如表2所示,请用最小元素法求出 运输问题的一组可解释。 BI B, B3 B4 A 2 表2) 十二、下列表3是一个指派问题的效率表工作时间表)其中A为工作人员(=1 2,3,4)B为工作项目〔=1,2,3,4),请作工作安排,使总的工作时间最小。 B B A 5643 6 参考答案 判断题 (1)×(2)√(3)√(4)×(5)√(6)×(7)√(8)√(9)×(10) (11)×(12)×(13)√(14)×(15) 二、简述题 1、在可行域内先确定一个基本可行解,然后通过迭代计算,逐步使目标函数增大(求Zmx), 求出新解,计算出方案机会成本后,得出相应检验数,当所有的C-2≤0时即得最优解
十、某企业生产三种产品 A1 、A2、A3。每种产品在销售时可能出现销路 好(S1)，销路一般(S2)和销路差(S3)三种状态，每种产品在不同销售状态的获利情 况(效益值)如表 1 所示，请按乐观法则进行决策，选取生产哪种产品最为合适。 (表 1) 十一、已知运输问题的运价表和发量和收量如表 2 所示，请用最小元素法求出 运输问题的一组可解释。 (表 2) 十二、下列表 3 是一个指派问题的效率表(工作时间表)，其中 A i为工作人员(i=1, 2, 3, 4)、Bj 为工作项目(j=1, 2, 3, 4)，请作工作安排，使总的工作时间最小。 参考答案 一、判断题 (1)× (2)√ (3)√ (4)× (5)√ (6)× (7)√ (8)√ (9)× (10)√ (11)× (12) × (13)√ (14)× (15) × 二、简述题 1、在可行域内先确定一个基本可行解，然后通过迭代计算，逐步使目标函数增大（求 Zmax）， 求出新解，计算出方案机会成本后，得出相应检验数，当所有的 Cj–Zj≤0 时即得最优解。 状态 效益值 产品 S1 S2 S3 A1 30 10 -6 A2 20 12 9 A3 15 13 12 B1 B2 B3 B4 A1 2 9 12 7 9 A2 1 3 5 2 4 A3 10 4 2 6 5 3 5 4 6 B1 B2 B3 B4 A1 4 1 7 4 A2 2 2 3 5 A3 5 6 4 3 A4 6 3 2 4
2、运输问题可以用单纯形求解,但由于虚设的变量多,运算复杂,十分不合算,所以不用 单纯形法求解,而用简单的表上作业法求解。 3、由于动态规划的求解过程是一个多段决定过程,其状态变量必须满足无后效性和可知性 的特征要求 三、填空题 1.树 2.破圈法和避圈法 3.可行解、退化解、无界解、多重解 4匈牙利法 5.确定性决策,不确定性决策,风险性决策。 6圈 320000 C Xo b XX X4 X5 (3)X13 (2)X24|0 l1/2-1 2. Smin=15 3.X4输入,X输出。 五、Za=7y1+16y2 2y2≤6 B28 (32) (26)
2、运输问题可以用单纯形求解，但由于虚设的变量多，运算复杂，十分不合算，所以不用 单纯形法求解，而用简单的表上作业法求解。 3、由于动态规划的求解过程是一个多段决定过程，其状态变量必须满足无后效性和可知性 的特征要求。 三、填空题 1.树 2.破圈法和避圈法 3.可行解、退化解、无界解、多重解 4.匈牙利法 5.确定性决策，不确定性决策，风险性决策。 6.圈。 四. 1. 2. Smin=15 3. X4 输入，Xi 输出。 五、Zmax=-7y1+16y2 − + − + , 0 3 1 2 6 1 2 1 2 1 2 y y y y y y 六、 S—A1—B1—C1—F 32 B1 S A2 7 10 B3 9 C2 13 F C1 10 7 A1 10 5 11 12 14 9 B28 6 10 5 6 8 (32) (27) (17) (10) (0) (13) (16) (26) (18) cj → 3 2 0 0 0 0 Ci X0 b X1 X2 X3 X4 X5 X6 (3) X1 3 1 0 1/2 -1 0 1/2 (2) X2 4 0 1 1 1/2 -1 0 Zj 3 2 7/2 -2 -2 3/2 Cj–Zj 0 0 (-7/2) (2) 2 -3/2
七 V6 最小树为图 中双线所示,最小树长14 (V1.4) 八、 最短路径:1→v3→vs→V6→vL=10 20△N d△ △o -630 20 12 A 选方案A1
七、 最小树为图 中双线所示，最小树长 14 八、 最短路径：v1→v3→v5→v6→v7 L=10 九、 十、 S1 S2 S3 max A1 30 10 -6 30 A2 20 12 9 20 A3 15 13 12 15 选方案 A1 5 2 V1 V2 V4 4 3 5 3 V3 V5 V6 4 2 4 V2 V5 V7 V6 V2 V4 V1 (v1, 0) (v1, 4) (v1, 6) (v1, 13) (v6, 10) (v3, 9) (v5, 7) (v1, 3) (v1, 5) 4 3 5 1 7 3 1 7 5 6 3 1 ① ② ④ ⑥ ③ ⑤ 4 0 12 5 10 9 9 4 5 5 0 10 20 31 20 0 10 27 31 6 20
Al A 965 B A 7 A2② 263 表 3
十一、 十二、 S=8 (表 3) B1 B2 B3 B4 A1 4 ① 7 4 A2 ② 2 3 5 A3 5 6 4 ③ A4 6 3 ② 4 B1 B2 B3 B4 3 … 0 … 6 … 3 | | | | | | | 0 … 0 … 1 … 3 | | | | | | | 2 … 3 … 1 … 0 | | | | | | | 4 … 1 … 0 … 2 B1 B2 B3 B4 ai A1 2 ⑨ 12 ⑦ 9 A2 ① 3 5 ② 6 A3 10 ④ ② 6 5 bj 3 7 4 6 … … … … … … … … … | | | | | | | | | | | | | | | | 3 3 4 3 6