中南大学《运筹学》程试题及参考答案
一、判断题(在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“√”，错误者写“×”。)
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,树连通，但不存在 。
四、下列表是线性规划单纯形表（求Zmax），请根据单纯形法原理和算法。
1,计算该规划的检验数
2,计算对偶问题的目标函数值
3,确定上表中输入，输出变量
五、已知一个线性规划原问题如下，请写出对应的对偶模型
六、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推法求出S至F点的最短路径及最短路长。
七、自己选用适当的方法，对下图求最小(生成)树。
八、用标号法求下列网络V1→V7的最短路径及路长。
九、下图是某一工程施工网络图(统筹图)，图中边上的数字为工序时间(天)，请求出各事项的最早时间和最迟时间，求出关键路线，确定计划工期。
十、某企业生产三种产品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时即得最优解。
2、运输问题可以用单纯形求解，但由于虚设的变量多，运算复杂，十分不合算，所以不用单纯形法求解，而用简单的表上作业法求解。
3、由于动态规划的求解过程是一个多段决定过程，其状态变量必须满足无后效性和可知性的特征要求。
三、填空题
1.树
2.破圈法和避圈法
3.可行解、退化解、无界解、多重解
4.匈牙利法
5.确定性决策，不确定性决策，风险性决策。
6.圈。
四.
1.
2,Smin=15
3,X4输入，Xi输出。
五、Zmax=-7y1+16y2
六、
S—A1—B1—C1 —F 32
七,
最小树为图中双线所示，最小树长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
十一、
十二、
S=8
(表3)
一、判断题(在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“√”，错误者写“×”。)
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,树连通，但不存在 。
四、下列表是线性规划单纯形表（求Zmax），请根据单纯形法原理和算法。
1,计算该规划的检验数
2,计算对偶问题的目标函数值
3,确定上表中输入，输出变量
五、已知一个线性规划原问题如下，请写出对应的对偶模型
六、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推法求出S至F点的最短路径及最短路长。
七、自己选用适当的方法，对下图求最小(生成)树。
八、用标号法求下列网络V1→V7的最短路径及路长。
九、下图是某一工程施工网络图(统筹图)，图中边上的数字为工序时间(天)，请求出各事项的最早时间和最迟时间，求出关键路线，确定计划工期。
十、某企业生产三种产品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时即得最优解。
2、运输问题可以用单纯形求解，但由于虚设的变量多，运算复杂，十分不合算，所以不用单纯形法求解，而用简单的表上作业法求解。
3、由于动态规划的求解过程是一个多段决定过程，其状态变量必须满足无后效性和可知性的特征要求。
三、填空题
1.树
2.破圈法和避圈法
3.可行解、退化解、无界解、多重解
4.匈牙利法
5.确定性决策，不确定性决策，风险性决策。
6.圈。
四.
1.
2,Smin=15
3,X4输入，Xi输出。
五、Zmax=-7y1+16y2
六、
S—A1—B1—C1 —F 32
七,
最小树为图中双线所示，最小树长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
十一、
十二、
S=8
(表3)
