华东交大运筹学综合复习题
一、单项选择题（共20分，每题2分）
1、如果决策变量数相等的两个线规划的最优解相同，则两个线性规划（）
A、约束条件相同
B、目标函数相同
C、最优目标函数值相同
D、以上结论都不对
2、对偶单纯形法的最小比值规则是为了保证（）
A、使原问题保持可行
B、使对偶问题保持可行
C、逐步消除原问题不可行性
D、逐步消除对偶问题不可行性（）
3、X1要求是非负整数，它的来源行是X1-5/3 X4+7/3 X5=8/3, 高莫雷方程是（）
A、-1/3 X4-1/3 X5<= 2/3
B、X4- X5<= -2
C、X4+ X5+S=2
D、-1/3 X4-1/3 X5+S= -2/3
4、下列说法正确的有（）
A 、运输问题的运价表第r行每个cij 同时加上一个非0常数k，其最优调运方案变化。
B、运输问题的运价表的所有cij同时乘以一个非0常数k，其最优调运方案不变。
C、运输问题的运价表第p列每个cij同时乘以一个非0常数k，其最优调运方案不变。
D、运输问题的运价表的所有cij同时乘以一个非0常数k，其最优调运方案变化。
5、要求不超过第一目标值，恰好完成第二目标值，目标函数是（）
A、minZ=P1d1-+P2(d2-+d2+)
B、minZ= P1d1++P2(d2-+d2+)
C、minZ=P1(d1-+d1+)+P2(d2-+d2-)
D、minZ=P1(d1-+d1+)+ P2d2-
6、下列说法正确的是（）
A、分支定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相
应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问
题通过分支迭代求出最优解。
B、用割平面法求解整数规划问题，构造的解割平面有可能切去一些不属于最优解的整
数解。
C、用分支定界发求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任
取其中一个作为下界，再进行比较剪支。
D、整数规划问题的最优值优于其相应的线性规划问题的最优值。
7、对运输问题的描述，下列说法正确的是（）
A、若变量B组包含有闭回路，则B中的变量对应的列向量线性无关。
B、运输问题的对偶问题不一定存在最优解。
C、第i行的位势u i是第i个对偶变量。
D、运输问题的对偶问题的约束条件为大于等于约束。
8、工序（i,j）的最早开工时间T ES（i,j）等于（）
A、T E（i）
B、max{ T Es（k）+ t ki }
C、T L（i）
D、min{ T L（j）- t ij }
9、以下哪项是决策结果的方法程序（）
A、收集信息-确定目标-提出方案-方案优化-决策
B、确定目标-收集信息-决策-提出方案-优化方案
C、确定目标-收集信息-提出方案-方案优化-决策
D、确定目标-提出方案-收集信息-方案优化-决策
10、对动态规划问题的描述，下列错误的结论是（）
A、给定某一阶段的状态，则在这一阶段以后过程的发展不受这一阶段以前的各个阶
段状态的影响，而只与当前状态有关，与过程过去的历史无关。
B、动态规划问题数学模型由阶段、状态、决策与策略、状态转移方程及指标函数5
个要素组成。
C、动态规划是求解多阶段决策问题的一种算法策略，当然也是一种算法。
D、动态规划是一种将问题分解为更小的，相似的子问题，并存储子问题的解而避免
计算重复的子问题，以解决最优化问题的算法策略。
二、判断题，正确打√，错误打×, 并将修改建议简写在对应题号下的改错栏。
（20分，每题2分）
1、按最小元素法给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭
回路。
（）
2、当最优解中存在为0的基变量时，则线形规划具有多重最优解。
（）
3、检验数λj表示非基变量Xj增加一个单位时目标函数值的改变量。
（）
4、图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
（）
5、线性规划模型中增加一个约束条件，可行区域的范围一般将缩小，减少一个约束条件，
可行域的范围一般将扩大。
（）
6、在折衷主义准则中，乐观系数α的确定与决策者对风险的偏好有关。
( )
7、对于一个m行n列的运输问题，其初始可行解中基变量个数为m+n个。
（）
8、在目标规划模型中，正偏差变量应取正值，负偏差变量应取负值。
（）
9、在任一图G中，当点集V确定后，树图是G中边数最少的连通图。
（）
10、用动态规划求解一般线性规划问题是将约束条件数作为阶段数，变量作为状态。
（）
三、简答题（12分，每题3分）
1. 什么是线性规划问题的基础可行解？（3分）
2. 在对偶单纯形法中使用最小比值定理的作用是什么？（3分）
3. 如何理解动态规划问题中的“状态”的概念？（3分）
4.决策分析的基本原则是什么？（3分）
四、（20分）某运输问题的供需平衡表与单位运价表如下，求出使总的运费最小的最优运输
方案以及最小运输费用。
五、（15分）已知项目各工序的三种估计时间如下表所示
1、绘制网络图并计算各工序的期望时间；（5分）
2、计算关键工序和关键路线。
（5分）
3、项目完工时间的期望值。
（5分）
六、（13分）某公司为经营业务的需要，决定要在现有生产条件不变的情况下，生产一种新产品，现可供开发生产的产品有I、II、III、IV四种不同产品，对应的方案为A1,A2,A3,A4．由于缺乏相关资料背景，对产品的市场需求只能估计为大中小三种状态，而且对于每种状态出
求：（1）用悲观主义准则求解的决策方案（4分）
（2）用乐观主义准则求解的决策方案（4分）
（3）用最小机会损失准则求解的决策方案（5分）
参考答案及评分标准
一、单项选择题（20分，每题2分）
判断及改错题答题表
三、简答题（12分）
1. 什么是线性规划问题的基本可行解？（3分）
答：对应基β，令所有的非基变量为零，求解约束方程组AX=b，可惟一得出基变量的一组值，这样得到的N个变量的一组解成为一个“基本解”或“基解”。
如果一个基本解中的所有变量都大于或等于0，则称这个基本解为“基本可行解”或“基可行解”。
2. 在对偶单纯形法中使用最小比值定理的作用是什么？（3分）
答：在对偶单纯形法中，当求解进基变量是采用最小比值定理，是为了不改变对偶问题的可行性。
3. 如何理解动态规划问题中的“状态”的概念？（3分）
答：状态（State）是描述决策过程当前特征并且具有无后效性的量。
状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。
每一状态可以取不同值，状态变量记为sk。
各阶段所有状态组成的集合称为状态集。
4.决策分析的基本原则是什么？（3分）
答:最优化（满意）原则; 系统原则;可行性原则;.信息对称、准全原则
四、（20分）某运输问题的供需平衡表与单位运价表如下，求出使总的运费最小的最优运输
方案以及最小运输费用。
minz=25 元
五、（15分）已知项目各工序的三种估计时间如下表所示
1、 绘制网络图并计算各工序的期望时间；（5分）
2、 计算关键工序和关键路线。
（5分）
3、 项目完工时间的期望值。
（5分） 【解】（1）网络图
(2)关键工序：
(3) 项目完工时间的期望值：10.17+14.83+17.17+11.83＝54(小时)
六、（13分） 解：（1）小中取大法（悲观主义准则） (4分) 策略值为 {}
100
min ,,min ,min max min max 421==⎭
⎬⎫
⎩⎨⎧=j j j j j j i
ij i a a a a v
则对应的A4方案为决策方案，即生产产品IV （2）大中取大法（乐观主义准则） (4分) 策略值为
则对应的A1方案为决策方案，即生产产品I ． （3）最小机会损失准则 (5分)
编制机会损失表, 找出每个方案的最大机会损失, 选择最小的机会损失值, 对应的方案
即为所决策方案
则应选对应的A2方案为决策方案，即生产产品Ⅱ{}
800max ,,max ,max max max max 421==⎭⎬⎫
⎩⎨⎧=j j
j j j j j ij i a a a a v。