运筹学-学习指南

1、精品文档运筹学 -学习指南一、名词解释1 松弛变量为将线性规划问题的数学模型化为标准型而加入的变量。2 可行域满足线性约束条件的解（x,y ）叫做可行解，由所有可行解组成的集合叫做可行域。3 人工变量亦称人造变量.求解线性规划问题时人为加入的变量。用单纯形法求解线性规划问题，都是在具有初始可行基的条件下进行的,但约束方程组的系数矩阵A 中所含的单位向量常常不足m 个，此时可加入若干(至多 m)个新变量，称这些新变量为人工变量。4 对偶理论每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的同时，也给出了另一个问题的解。研究线性规划中原始问题与对偶问题之间关系的理论5 灵敏度分析研究与

2、分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。6 影子价格反映资源配置状况的价格。影子价格是指在其他资源投入不变的情况下,每增加一单位的某种资源的投入所带来的追加收益。即影子价格等于资源投入的边际收益。只有在资源短缺的情况下,每增加一单位的投入才能带来收益的增加7 产销平衡运输一种特殊的线性规划问题。产品的销售过程中，产销平衡是指工厂产品的产量等于市场上的销售量。8 西北角法是运筹学中制定运输问题的初始调运方案（即初始基可行

3、解）的基本方法之一。也就是从运价表的西北角位置开始，依次安排m 个产地和n 个销地之间的运输业务，从而得到一个初始调运方案的方法。9 最优性检验检验当前调运方案是不是最优方案的过程。10 动态规划解决多阶段决策过程优化问题的方法：把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解11 状态转移方程从阶段 K 到 K+1 的状态转移规律的表达式12 逆序求解法在求解时，首先逆序求出各阶段的条件最优目标函数和条件最优决策，然后反向追踪，顺序地求出改多阶段决策问题的最优策略和最优路线。13 最短路问题最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点

4、之间的最短路径。14 最小费用最大流A 到 B ，如何选择路在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从径、分配经过路径的流量，可以达到所用的费用最小的要求。15 排队论排队论 (queueing theory), 或称随机服务系统理论 , 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。.精品文档二、选择题1. 用图解法求解一个关于最大利润的线性规划问题时，若

5、其等利润线与可行解区域相交，但不存在可行解区域最边缘的等利润线，则该线性规划问题(B )。A 、有无穷多个最优解B 、有可行解但无最优解C、有可行解且有最优解D 、无可行解2.若线性规划问题的最优解同时在可行解域的两个顶点处达到，则此线性规划问题的最优解为（B ）A 、两个B 、无穷多个C、零个D 、过这的点直线上的一切点3.用图解法求解一个关于最小成本的线性规划问题时，若其等成本线与可行解区域的某一条边重合，则该线性规划问题(A)。A 有无穷多个最优解B 、有有限个最优解C有唯一的最优解D 无最优解4.在求极小值的线性规划问题中，引入人工变量之后，还必须在目标函数中分别为它们配上系数，这些系

6、数值应为 (A )。A 、很大的正数B、较小的正数C、 1D 、 05.对 LP 问题的标准型：max ZCX,AXb, X0 ，利用单纯形表求解时，每做一次换基迭代，都能保证它相应的目标函数值 Z 必为（B ）A 增大B 不减少C 减少D 不增大6.若 LP 最优解不唯一，则在最优单纯形表上（A）A 非基变量的检验数必有为零者B 非基变量的检验数不必有为零者C 非基变量的检验数必全部为零D 以上均不正确7.求解线性规划模型时，引入人工变量是为了（B）A 使该模型存在可行解B 确定一个初始的基可行解C 使该模型标准化D 以上均不正确11.用大 M 法求解 LP 模型时，若在最终单纯形表上基变量

7、中仍含有非零的人工变量，则原模型（C ）A 有可行解，但无最优解B 有最优解C 无可行解D 以上都不对12.已知 x1(2,4) ， x2(4,8)是某 LP 的两个最优解，则（D ）也是 LP 的最优解。A x(4,4)Bx (1,2)C x (2,3)D 无法判断13、线性规划问题的灵敏度分析研究（BC）A 、对偶单纯形法的计算结果；B 、目标函数中决策变量系数的变化与最优解的关系；C 、资源数量变化与最优解的关系；D 、最优单纯形表中的检验数与影子价格的联系。14、对偶单纯形法迭代中的主元素一定是负元素（A）A 、正确B、错误C、不一定D、无法判断15、对偶单纯形法求解极大化线性规划时，

8、如果不按照最小化比值的方法选取什么变量则在下一个解中至少有一个变量为正（ B ）A 、换出变量B 、换入变量C、非基变量D、基变量16、影子价格是指（D ）A 、检验数B 、对偶问题的基本解C、解答列取值D、对偶问题的最优解17、影子价格的经济解释是（C）A 、判断目标函数是否取得最优解B、价格确定的经济性C、约束条件所付出的代价D、产品的产量是否合理18 、在总运输利润最大的运输方案中，若某方案的空格的改进指数分别为IWB =50 元， I WC =-80 元， I YA =0 元， I XC =20 元，则最好挑选 (A)为调整格。A、WB 格B、WC 格C、 YA格D、XC 格19 、在

9、一个运输方案中，从任一数字格开始，(B)一条闭合回路。A 可以形成至少B不能形成C、可以形成D 有可能形成20、运输问题可以用(B)法求解。A 、定量预测B 、单纯形C、求解线性规划的图解D 、关键线路21、在运输问题的表上作业法选择初始基本可行解时，必须注意（AD）。A 、针对产销平衡的表；B 、位势的个数与基变量个数相同；C、填写的运输量要等于行、列限制中较大的数值；.精品文档D 、填写的运输量要等于行、列限制中较小的数值。22、用增加虚设产地或者虚设销地的方法可将产销不平衡的运输问题化为产销平衡的运输问题（ A ）A 、正确B 、错误C、不一定D 、无法判断23、通过什么方法或者技巧可以

10、把产销不平衡运输问题转化为产销平衡运输问题( C)A 、非线性问题的线性化技巧B 、静态问题的动态处理C、引入虚拟产地或者销地D 、引入人工变量24、动态规划方法不同于线性规划的主要特点是（AD）。A 、动态规划可以解决多阶段决策过程的问题；B 、动态规划问题要考虑决策变量；C、它的目标函数与约束不容易表示；D 、它可以通过时间或空间划分一些问题为多阶段决策过程问题。25、用 DP 方法处理资源分配问题时，通常总是选阶段初资源的拥有量作为决策变量（B ）A 、正确B、错误C、不一定D 、无法判断26、用 DP 方法处理资源分配问题时，每个阶段资源的投放量作为状态变量（B ）A 、正确B、错误C

11、、不一定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 、给出最优策略3

12、2用动态规划解决生产库存的时候，应该特别注意哪些问题？（BC）A 、生产能力B、状态变量的允许取值范围C、决策变量的允许取值范围D、库存容量33. 在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是(C)。A 、降低的B 、不增不减的C、增加的D 、难以估计的34. 最小枝权树算法是从已接接点出发，把(C)的接点连接上A 、最远B 、较远C、最近D 、较近35. 在箭线式网络固中， (D )的说法是错误的。 A 、结点不占用时间也不消耗资源B 、结点表示前接活动的完成和后续活动的开始C、箭线代表活动D 、结点的最早出现时间和最迟出现时间是同一个时间36. 如图所示

13、，在锅炉房与各车间之间铺设暖气管最小的管道总长度是(C)。A 、 1200B、 1400C、 1300D、 170037. 在求最短路线问题中，已知起点到1A ， B， C 三相邻结点的距离分别为 15km ， 20 km25km ，则（ D）。500400A 点B 点A 、最短路线 定通过B 、最短路线一定通过C、最短路线一定通过C 点300D、不能判断最短路线通过哪一点锅炉房( A)338. 在一棵树中，如果在某两点间加上条边，则图一定A 、存在一个圈B、存在两个圈C、存在三个圈700D 、不含圈 60039网络图关键线路的长度( C)工程完工期。A 大于B 小于2C等于D不一定等于40.

14、在计算最大流量时，我们选中的每一条路线(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. 排队系统中状

15、态是指系统中的顾客数（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 问题max

16、zx 2x122 x12 x212x12x28s.t 4 x1164 x212x1, x2 0答案：依题有可得最优解集合为( x1, x2) | ( x1, x2)a(2,3) (1a)(4,2),0a 1也即( x1, x2) | ( x1, x2)(4 2a ,2a ),0 a1最优值为z8（详细求解过程略去）2. 用分枝界定法求解下列线性规划问题max f (x)6x14 x22x14x2132x1x27x1 , x20 且为整数答案：松弛问题的最优解为x12=2.5, x =2, OBJ=23由 x1=2.5得到两个分枝如下：.精品文档max f (x)12max f ( x)6x14

17、x26x4x2x14x21312132x4x2x1x27127和问题2xx问题 IIIx12x13120且为整数x1 , x20且为整数x , x各个分枝问题的松弛解为问题 I问题 IIx123x29/41f(x)2122问题 II的解即原整数问题的最优解3、已知线性规划问题max z5x1 6x27x3x1 5x23x315s.t.5x16x210x320x1x2 x35x1, x20 , x3无约束要求：（ 1）化为标准型式（ 2）列出用两阶段法求解时第一阶段的初始单纯形表解：（ 1）令x1'x;x3x3'x3'',x3'、''0，

18、z z 'x3原模型可以转化为x1 ' x; x3x3 'x3 '', x3 '、，zz 'x3 ''0x1 ' 5x 2 3x3 ' 3x3 '' x4x6 155x1 ' 6x2 10 x3 ' 10 x3 '' x520x1 ' x2x3 ' x3 '' x75x1 ', x2, x3 ', x3 '', x4, x5, x6, x70（ 2）见下表000000-11x1 'x2 &

19、#39;x3 'x3 ''x4 'x5 'x6 'x7 '-1x61515-33-10100x5205-610-100100-1x75111-10001cj-zj26-22-10004、求下列线性规划问题，并写出LP 问题的对偶问题.精品文档max z 3x12 x 2x 12 x 24s.t.3 x12 x 214x1x 23答案：x1, x 20X51315000244max Z4对偶问题：min w4 y114 y23 y3y13y2y33s.t. 2 y12 y2y32y10, y2,305、求出下列问题的对偶问题并分别队原问题及

20、对偶问题求解原问题 : max f ( x)5x13 x26x3x12x2x3182 x1x23x316st.x2x310x1x1 , x20, x3不限答案：对偶问题 : min g ( y)18y116y2 10y3y12 y2y352 y1y2y33s.t3y2y36y1y1 , y20, y3不限用单纯型法求解过程Cj536-600MCBXBbx1x2x'3x" 3x4x5x60x41812111000x51621(3)3010Mx6101111001OBJ=10MMMMM00Mcj - zj5+M3+M6+M-6-M0000x438/31/35/30011/306x

21、'316/32/31/31101/30Mx614/31/3(2/3)0001/31OBJ=32-14M/34-M/32-2M/36602+M/3Mcj - zj1+M/31+2M/3000-2-M/300x411/200011/25/26x'33(1/2)01101/23/23x271/210001/23/2OBJ=399/236603/23/2cj - zj1/200003/2-M-3/20x4400111135x1610220113x24011(1)012OBJ=425377021.精品文档cj- z001102-M+1j0x4801001015x11412000136x&

22、quot; 340111012OBJ=465466013cj- z010001-M 3j对偶问题最优解：y4=0y5=1y6 =0y1=0y2 =1y3 =3原问题最优解： x1=14, x2=0, x3 =-4, x4 =8, x5=0, x6 =0, OBJ=466、 运输问题的数据如下表：B1B2B3B4产量A12237500A24359600A31678300销量300200500400求最优运输方案。答案：最优方案：f * = 6000B 1B 2B 3B4产量A 1100400500A 2200400600A 3300300销量3002005004007、 对于以下运输问题，如何用

23、最小元素法求出初始调运方案？答案：求解过程如下。表中“”内数字为删除线出现的先后顺序。.精品文档8、判断下表中给出的调运方案能否作为表上作业法求解的初始方案？为什么？运销地B1B 2B3B 4B 5产量量产地A12525A2201030A32020A452530销量2020301025105答案：不能作为初始方案。因为数字格只有 6个，而 n m189、某奶牛站希望通过投资来扩大牛群数，开始只有5000 元资金，现在已知可购入A 或者 B 两个品种的奶牛，对于A 种牛每投入 1000元，当年及以后每年可以获得500元和 2头小牛，对B 种牛每投入 1000元，当年及以后每年可以获得200 元和

24、 3头小牛。问：（ 1）在今后的四年内应该如何分配投资使奶牛群最大（ 2）到第四年底奶牛站将有多少头奶牛。答案：状态 Sn 为阶段 n 可利用的资金；决策 dn 为阶段 n 向 A 种牛投入的资金数；Sndn 为阶段 n 向 B 种牛投入的资金数；则转移函数为 Sn 10.2Sn0.3d n递推函数：f n(Sn)r n(d n)f n 1(Sn 1)r nn(3Sn d n );1000r n 表示在阶段 n 出生的小牛数S5000；4第四年末牧场主应拥有的牛的头数为70 头10. 求下面容量网络的最大流，弧边上括号内第一个数为容量，第二个数为流量。（ 1）、根据标号过程找出增广链，确定流量

25、修正量；（ 2）、调整流量，画出最大流图，说明最大流量是多少；（ 3）、根据标号和求解过程确定最小割并算出最小割容量；V 2V 4(3,2)(4,1)V 1(3,1)(1,1)(3,1)V 6(2,0)(2,2)(3,1)(2,2)V 3V 5、解：1.增广链：+V 41 min 2,1,31V 1V 2V 6213（ V,2）（ 3,3）（ V2V,14） （ 4,2）（ -,）1V2（ V4 ,3）（ 3,2）.V 1(1,1)（ 2,0）（ 3,1）V 6精品文档（ 2,2）V3（3,1）V（ 2,2）5(V2,1)图 1（ V2,2）(V4, 2)(V3, 2)2.（ V1 ,1）（ V5 ,1）（ -,）V 2（ 3,3）V 4（ 4,3）（ 3,3）（ V4 ,2）V 1(1,1)（ 2,1） （ 3,0）V 6（ 2,2）V 3（ 3,1）V 5（ 2,2）图 2（ V2 ,2）增广链V 1+V2+V 5-+V 6121V 42 min1,2,1, 21