运筹学-学习指南一、名词解释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 、1D 、05. 对LP 问题的标准型：max ,,0Z CX AX b X ==≥，利用单纯形表求解时，每做一次换基迭代，都能保证它相应的目标函数值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. 已知1(2,4)x=，2(4,8)x=是某LP的两个最优解，则（D ）也是LP的最优解。
A (4,4)x=B (1,2)x=C (2,3)x=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、在总运输利润最大的运输方案中，若某方案的空格的改进指数分别为I WB=50元，I WC=-80元，I YA=0元，I XC=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、1400C、1300D、170037.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 、无法判断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 问题12max 2z x x =+12121212221228 416 ..412 ,0s t x x x x x x x x +≤⎧⎪+≤⎪⎪≤⎨⎪≤⎪≥⎪⎩ 答案：依题有可得最优解集合为1212{(,)|(,)(2,3)(1)(4,2),01}a a a x x x x =+-≤≤ 也即1212{(,)|(,)(42,2),01}a a a x x x x =-+≤≤ 最优值为8z*=（详细求解过程略去）2. 用分枝界定法求解下列线性规划问题12121212max ()6424132 7,0 f x x xx x x x x x =++≤⎧⎪+≤⎨⎪≥⎩且为整数 答案：松弛问题的最优解为 x 1=2.5, x 2=2, OBJ =23由x 1=2.5 得到两个分枝如下：121212112max ()6424132 7I 2,0 f x x x x x x x x x x =++≤⎧⎪+≤⎪⎨≤⎪⎪≥⎩问题且为整数和121212112max ()6424132 7II 3,0 f x x x x x x x x x x =++≤⎧⎪+≤⎪⎨≥⎪⎪≥⎩问题且为整数 问题I 问题II x 1 2 3 x 2 9/4 1 f (x ) 21 223、已知线性规划问题123123123123123max 5675315 561020 5 ,0 ,z s.t.x x x x x x x x x x x x x x x =---⎧-+-≥⎪--+≤⎪⎨--=-⎪⎪≤⎩无约束 要求：（1）化为标准型式（2）列出用两阶段法求解时第一阶段的初始单纯形表 解：（1）令133333';''','''0'x z z x x x x x x =-=-≥-=、，原模型可以转化为133333123346123351233712334567';''','''0''53'3''155'610'10''20'''' 5 ',,','',,,,0 x z z x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x =-=-≥-=+-+-+=⎧⎪-+-+=⎪⎨++-+=⎪⎪≥⎩、，（2）见下表4、求下列线性规划问题，并写出LP 问题的对偶问题1212121212max 322 43214 3 ,0z s.t.x x x x x x x x x x =+⎧-+≥⎪+≤⎪⎨-≤⎪⎪≥⎩ 答案：51315[000]244X *=max 4Z =对偶问题：12312312312,3min 4143332220,0 w s.t.y y yy y y y y y y y =++⎧-++≥⎪⎪+-≥⎨⎪≤≥⎪⎩5、求出下列问题的对偶问题并分别队原问题及对偶问题求解123123123123123: max ()5362182316..10,0,f x x x xx x x x x x s t x x x x x x =++++≤⎧⎪++≤⎪⎨++=⎪⎪≥±⎩原问题不限答案：123123123123123: min ()1816102523..36,0,g y y y yy y y y y y s t y y y y y y =++++≥⎧⎪++≥⎪⎨++=⎪⎪≥±⎩对偶问题不限c j - z j0 -1 0 0 0 -1 -M-3对偶问题最优解：y4=0 y5=1 y6=0 y1=0 y2=1 y3=3原问题最优解：x1=14, x2=0, x3=-4, x4=8, x5=0, x6=0, OBJ=466、运输问题的数据如下表：B1B2B3 B4产量A1 A2 A3 2 2 3 74 35 91 6 7 8500600300销量300 200 500 400求最优运输方案。
