运筹学-学习指南
一、名词解释
1松弛变量
为将线性规划问题的数学模型化为标准型而加入的变量。
2可行域
满足线性约束条件的解（x,y）叫做可行解，由所有可行解组成的集合叫做可行域。
3人工变量
亦称人造变量.求解线性规划问题时人为加入的变量。用单纯形法求解线性规划问题，都是在具有初始可行基的条件下进行的,但约束方程组的系数矩阵A中所含的单位向量常常不足m个，此时可加入若干(至多m)个新变量，称这些新变量为人工变量。
4对偶理论
每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的同时，也给出了另一个问题的解。研究线性规划中原始问题与对偶问题之间关系的理论
5灵敏度分析
研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。
6影子价格
反映资源配置状况的价格。影子价格是指在其他资源投入不变的情况下,每增加一单位的某种资源的投入所带来的追加收益。即影子价格等于资源投入的边际收益。只有在资源短缺的情况下,每增加一单位的投入才能带来收益的增加
7产销平衡运输
一种特殊的线性规划问题。产品的销售过程中，产销平衡是指工厂产品的产量等于市场上的销售量。
8西北角法
是运筹学中制定运输问题的初始调运方案（即初始基可行解）的基本方法之一。也就是从运价表的西北角位置开始，依次安排m个产地和n个销地之间的运输业务，从而得到一个初始调运方案的方法。 9最优性检验
检验当前调运方案是不是最优方案的过程。
10动态规划
解决多阶段决策过程优化问题的方法：把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解
11状态转移方程
从阶段K到K+1的状态转移规律的表达式
12逆序求解法
在求解时，首先逆序求出各阶段的条件最优目标函数和条件最优决策，然后反向追踪，顺序地求出改多阶段决策问题的最优策略和最优路线。
13最短路问题
最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
14最小费用最大流
在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。
15排队论
排队论(queueing theory), 或称随机服务系统理论, 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。
二、选择题
1. 用图解法求解一个关于最大利润的线性规划问题时，若其等利润线与可行解区域相交，但不存在可行解区域最边缘的等利润线，则该线性规划问题( B )。
A、有无穷多个最优解 B、有可行解但无最优解 C、有可行解且有最优解 D、无可行解
2. 若线性规划问题的最优解同时在可行解域的两个顶点处达到，则此线性规划问题的最优解为（ B ）
A、两个 B、无穷多个
C、零个 D、过这的点直线上的一切点
3. 用图解法求解一个关于最小成本的线性规划问题时，若其等成本线与可行解区域的某一条边重合，则该线性规划问题( A )。
A．有无穷多个最优解 B、有有限个最优解 C．有唯一的最优解 D．无最优解
4. 在求极小值的线性规划问题中，引入人工变量之后，还必须在目标函数中分别为它们配上系数，这些系数值应为( A )。
A、很大的正数 B、较小的正数 C、1 D、0
5. 对LP问题的标准型：maxZ?CX,AX?b,X?0，利用单纯形表求解时，每做一次换基迭代，都能保证它相应的目标函数值Z必为（ B ）
A 增大 B 不减少 C 减少 D 不增大 6. 若LP最优解不唯一，则在最优单纯形表上（ A ）
A 非基变量的检验数必有为零者 B 非基变量的检验数不必有为零者 C 非基变量的检验数必全部为零 D 以上均不正确 7. 求解线性规划模型时，引入人工变量是为了（ B ）
A 使该模型存在可行解 B 确定一个初始的基可行解 C 使该模型标准化 D 以上均不正确
11. 用大M法求解LP模型时，若在最终单纯形表上基变量中仍含有非零的人工变量，则原模型（ C ）
A 有可行解，但无最优解 B 有最优解 C 无可行解 D 以上都不对 12. 已知
x1?(2,4)，x2?(4,8)是某LP的两个最优解，则（ D ）也是LP的最优解。
A x?(4,4) B x?(1,2) C x?(2,3) D 无法判断
13、线性规划问题的灵敏度分析研究（ BC ） A、对偶单纯形法的计算结果；
B、目标函数中决策变量系数的变化与最优解的关系； C、资源数量变化与最优解的关系；
D、最优单纯形表中的检验数与影子价格的联系。
14、对偶单纯形法迭代中的主元素一定是负元素（ A ）
A、正确 B、错误 C、不一定 D、无法判断
15、对偶单纯形法求解极大化线性规划时，如果不按照最小化比值的方法选取什么变量则在下一个解中至少有一个变量为正（ B ）
A、换出变量 B、换入变量 C、非基变量 D、基变量 16、影子价格是指（D）
A、检验数 B、对偶问题的基本解 C、解答列取值 D、对偶问题的最优解 17、影子价格的经济解释是（ C ）
A、判断目标函数是否取得最优解 B、价格确定的经济性 C、约束条件所付出的代价 D、产品的产量是否合理
18、在总运输利润最大的运输方案中，若某方案的空格的改进指数分别为IWB=50元，IWC=-80元，IYA=0元，IXC=20元，则
最好挑选( A )为调整格。
A、WB格 B、WC格 C、YA格 D、XC格 19、在一个运输方案中，从任一数字格开始，( B )一条闭合回路。
A．可以形成至少 B．不能形成 C、可以形成 D．有可能形成 20、运输问题可以用( B )法求解。
A、定量预测 B、单纯形 C、求解线性规划的图解 D、关键线路 21、在运输问题的表上作业法选择初始基本可行解时，必须注意（ AD ）。 A、针对产销平衡的表；
B、位势的个数与基变量个数相同；
C、填写的运输量要等于行、列限制中较大的数值； D、填写的运输量要等于行、列限制中较小的数值。
22、用增加虚设产地或者虚设销地的方法可将产销不平衡的运输问题化为产销平衡的运输问题
（ A ）
A、正确 B、错误 C、不一定 D、无法判断 23、通过什么方法或者技巧可以把产销不平衡运输问题转化为产销平衡运输问题( C )
A、非线性问题的线性化技巧 B、静态问题的动态处理 C、引入虚拟产地或者销地 D、引入人工变量 24、动态规划方法不同于线性规划的主要特点是（ AD ）。
A、动态规划可以解决多阶段决策过程的问题； B、动态规划问题要考虑决策变量；
C、它的目标函数与约束不容易表示； D、它可以通过时间或空间划分一些问题为多阶段决策过程问题。
25、用DP方法处理资源分配问题时，通常总是选阶段初资源的拥有量作为决策变量（ B ）
A、正确 B、错误 C、不一定 D、无法判断
26、用DP方法处理资源分配问题时，每个阶段资源的投放量作为状态变量（ B ）
A、正确 B、错误 C、不一定 D、无法判断 27、．动态规划最优化原理的含义是：最优策略中的任意一个K-子策略也是最优的（ A ）
A、正确 B、错误 C、不一定 D、无法判断
28．动态规划的核心是什么原理的应用（ A ）
A、最优化原理 B、逆向求解原理 C、最大流最小割原理 D、网络分析原理
29．动态规划求解的一般方法是什么？（ C ）
A、图解法 B、单纯形法 C、逆序求解 D、标号法
30．用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（ B ）
A、任意网络 B、无回路有向网络 C、混合网络 D、容量网络
31．动态规划的求解的要求是什么（ ACD ）
A、给出最优状态序列 B、给出动态过程 C、给出目标函数值 D、给出最优策略
32．用动态规划解决生产库存的时候，应该特别注意哪些问题？（ BC ）
A、生产能力 B、状态变量的允许取值范围 C、决策变量的允许取值范围 D、库存容量
33. 在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( C )。
A、降低的 B、不增不减的 C、增加的 D、难以估计的
34. 最小枝权树算法是从已接接点出发，把( C )的接点连接上
A、最远 B、较远 C、最近 D、较近 35. 在箭线式网络固中，( D )的说法是错误的。
A、结点不占用时间也不消耗资源
B、结点表示前接活动的完成和后续活动的开始 C、箭线代表活动
D、结点的最早出现时间和最迟出现时间是同一个时间
36. 如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( C )。
A 、1200 B、1400 C、1300 D、1700
1 400 锅炉房 700 2
37. 在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20 km
25km，则（ D ）。
A、最短路线—定通过A点 B、最短路线一定通过B点
C、最短路线一定通过C点 D、不能判断最短路线通过哪一点
38. 在一棵树中，如果在某两点间加上条边，则图一定( A )
A、存在一个圈 B、存在两个圈
C、存在三个圈 D、不含圈
39 网络图关键线路的长度( C )工程完工期。
A．大于 B．小于 C．等于 D．不一定等于 40. 在计算最大流量时，我们选中的每一条路线( C )。
A、一定是一条最短的路线 B、一定不是一条最短的路线
C、是使某一条支线流量饱和的路线 D、是任一条支路流量都不饱和的路线
41. 从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（ C ） A、树的逐步生成法 B、求最小技校树法
C、求最短路线法 D、求最大流量法
42. 为了在各住宅之间安装一个供水管道．若要求用材料最省，则应使用( B )。
A、求最短路法 B、求最小技校树法 C、求最大流量法 D、树的逐步生成法 43．排队系统状态转移速度矩阵中，每一列的元素之和等于0。（ B ）
A、正确 B、错误 C、不一定 D、无法判断
44. 排队系统中状态是指系统中的顾客数（ A ）
A、正确 B、错误 C、不一定 D、无法判断
500 300 3 600 45．排队系统的组成部分有（ ABC ）
A、输入过程 B、排队规则 C、服务机构 D、服务时间
46．排队系统中，若系统输入为泊松流，则相继到达的顾客间隔时间服从什么分布（ D ）
A、正态分布 B、爱尔朗分布 C、泊松流 D、负指数分布
47．研究排队模型及数量指标的思路是首先明确系统的意义，然后（ ABC ）
A、写出状态概率方程 B、写出状态转移速度矩阵 C、画出状态转移速度图 D、写出相应的微分方程
48．排队系统的状态转移速度矩阵中（ B ）元素之和等于零。
A、每一列 B、每一行 C、对角线 D、次对角线
三、计算题
1..用图解法求解下列LP问题
maxz?x1?2x2
?2x1?2x2?12??x1?2x2?8 ?s..t?4x1?16 ?4?12 ?x2??x1,x2?0 答案：依题有
可得最优解集合为
{(x1,x2)|(x1,x2)?a(2,3)?(1?a)(4,2),0?a?1} 也即
{(x1,x2)|(x1,x2)?(4?2a,2?a),0?a?1} 最优值为
z??8（详细求解过程略去）
122. 用分枝界定法求解下列线性规划问题
maxf(x)?6x?4x12?2x?4x?13 ?2x ?x? 7??x,x?0 且为整数?1212答案：松弛问题的最优解为 x1=2.5, x2=2, OBJ=23
由x1=2.5 得到两个分枝如下：
maxf(x)?6x?4x1122maxf(x)?6x?4x12?2x1?4x2?13?2x?4x?13?2x ?x? 7 ?2x ?x? 7 和
??12问题II?问题I?? x1?3? x?2???x1,x2?0 且为整数?x,x?0 且为整数12112各个分枝问题的松弛解为 x1 x2 f(x) 问题II的解即原整数问题的最优解
问题I 2 9/4 21 问题II 3 1 22 3、已知线性规划问题
maxz??5x1?6x2?7x3??x1?5x2?3x3?15 ???5x1?6x2?10x3?20 s.t.??x1?x2?x3??5 ?,?0 , 无约束 x3?x1x2要求：（1）化为标准型式
（2）列出用两阶段法求解时第一阶段的初始单纯形表 解：（1）令
x'??x;x?x'?x'',x'、x133333''?0，?z?z'
原模型可以转化为
?z?z'x'??x;x?x'?x'',x'、x''?0，?x'?5x?3x'?3x''?x?x?15? ?5x'?6x?10x'?10x''?x?20??x'?x?x'?x''?x?5 ?x',x,x',x'',x,x,x,x?0 ?133333123346123351233712334567（2）见下表 -1 0 -1 0 10 20 0 30 40 -1 1 x' x 15 20 5 1 5 1 2 ' x3' x'' x3 -10 -1 2 ' x5' x6' x7' xxxj65 -6 1 6 -3 10 1 -2 -1 0 0 -1 0 1 0 0 1 0 0 0 0 0 1 0 57c-zj 4、求下列线性规划问题，并写出LP问题的对偶问题
maxz?3x1?2x2
??x1?2x2?4 ??3x1?2x2?14 s.t.??x1?x2?3 ??x1,x2?0 0150] 4答案：
X?[240maxZ?4
?513 对偶问题：
minw?4y?14y?3y123??y?3y?y?3 23?1? s.t.?2y?2y?y?2123??y1?0,y2,3?0 ?
5、求出下列问题的对偶问题并分别队原问题及对偶问题求解