运筹学复习资料.docx

1、运筹学复习资料我们老师付雅琴说：计算题来源于上课的例题（书本上的），以及让我们做过的课后习题。最近考试较多，希望大家做好考前复习，最后主大家考试顺利！试题结构：1、判断题（102） 2、单选题（102） 3、多选题（5 2） 4、计算题（510）（第三、五、七、十一、十三章有计算题）第一张 ： 绪论1.定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为管理者提供有依据的最优方案，以实现最有效的管理。2.研究内容：线性规划、整数线性规划、目标规划、图与网络模型、存储论、排队论、对策论、排序与统筹方法、决策分析、动态规划、预测3.运用运筹学解决问题的一

2、般过程 （课件答案） （课本答案） 规定目标和明确问题 认清问题收集数据和建立模型 找出一些可供选择的方案求解模型和优化方案 确定目标或评估方案的标准检验模型和评价方案 评估各个方案方案实施和不断改进 选出一个最优的方案 执行此方案 进行最后评估：问题是否得到圆满解决第二章 ：线性规划的图解方法1.怎样辨别一个模型是线性模型？其特征是： （1）问题的目标函数是多个决策变量的 线性 函数，通常是求最大值或最小值； （2）问题的约束条件是一组多个决策变量的 线性 不等式或等式。2.线性规划三个要素建模步骤决策变量、目标函数、约束条件3.LP问题的标准型特点：(1) 目标函数求最大值 (2) 约束条

3、件都为等式方程，且右端常数项bi都大于或等于零 (3) 决策变量xj为非负。一般形式 目标函数： max （min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 标准形式目标函数： max z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn

4、 = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0，bi 04.线性问题的性质与判断（1 ）线性规划可行域为凸集（2）最优解在凸集上某一顶点达到（特殊情况下为凸集的某条边）（3 ）可行域有界，则一定有最优解5.图解法与解的状况（1）图解法使用范围：仅有两个决策变量的LP（2）基本步骤：a.建立平面直角坐标系；b.将约束条件图解，求得满足约束条件的解的集合；c.作出目标函数的等值线，并根据优化要求，平移目标函数等值线，求出最优解。 （3）解的状况：唯一最优解；无穷多最优解；无界解

5、；无可行解（4）重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；a.无穷多个最优解。若将例1中的目标函数变为max z=50x1+50x2，则线段BC上的所有点都代表了最优解；b.无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；c.无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。6.通过图解法了解LP解的四种形式 唯一最优解；无穷多最优解；无界解；无可行解可行域的类型解的类型非空有界有唯一最优解有无穷多最优解无界有

6、无界解空集无可行解7.灵敏度分析建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci , aij , bj 变化时，对最优解产生的影响。 8.规划问题：生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。第三章：线性规划问题的计算机求解1.百分之一百法则（一道计算题）当前 LP问题 的最优解（或：对偶价格）不变允许增加量：系数在上限范围内的最大增加量= 上限 现在值允许减少量：系数在下线范围内的最大减少量= 现在值 下限 2. 百分之一百法则的注意事项（1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允

7、许增加（减少）百分比均看作零（2）百分之一百法则是充分条件，但非必要条件；也就是说超过100%并不一定引起变化；（3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只有重新求解。第四章：线性规划在工商管理中的应用1.怎样根据实际问题建模2.三要素：决策变量、目标函数、约束条件第五章：单纯形变（概念、计算题）1.单纯形变的优势2.凸集、可行基解、最优解（三个定理）定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。定理2：线性规划问题的 基可行解 对应可行域(凸集)的顶点。定理3：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得

8、3.基、基向量、基变量、非基变量（1）基：设A为约束条件的mn阶系数矩阵(m0且aik（i=1，2,m）则线性规划具有无界解。4）无可行解的判别：当用大M单纯形法计算得到最优解并且人工变量依然为基变量时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。第六章：单纯形变法的灵敏度与对偶1.怎样把LP问题转化为对偶问题（1）目标函数由 MAX 变为 MIN（2）原问题有多少约束行，对偶问题的目标函数就有多少变量（3）原问题目标函数有多少变量，对偶问题就有多少约束行（4）原问题的价值系数 C 变为对偶问题右端常数项 B（5）原问题的右端常数 B 变为对偶问题目标函数的价值

9、系数 C（6）原问题的系数矩阵 A 转置后变为对偶问题的系数矩阵操作表格如下：原问题（或对偶题）对偶问题（或原问题）约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项目标函数 max目标函数 min约束条件m个m个变量00=无约束变量n个n个约束条件00无约束=第七章：运输问题（有一道计算题）1.何为产销平衡？产大于销？销大于产？2.运输规划问题建模 3.表上作业法步骤描述方法第一步求初始基行可行解（初始调运方案）西北角法最小元素法第二步求检验数并判断是否得到最优解：当非基变量的检验数ij全都非负时得到最优解，若存在检验数ij 0，说明还没有达到最优，转第三步。闭回路法位势法第三

10、步调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步4.初始可行解（最小元素法、基变量的个数）（1）最小元素法在表上找到单位运价最小的x21，并使x21取尽可能大的值，即x21=min(4,3)=3，把A2的产量改为1，B1的销量改为0，并把B1列划去。在剩下的33矩阵中再找最小运价，同理可得其他的基本可行解。一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。（2）基变量的个数（略）5.非基变量的检验数（闭回路、位势法） （1） 闭回路法对于代表非基变量的空格（其调运量为零），

11、把它的调运量调整为1，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。（2）位势法（略）6.进基、出基（闭回路调整法）（1）选取所有负检验数中最小值对应的非基变量xij作为入基变量，以求尽快实现最优。（2）在以xij为出发点的闭回路中，找出所有偶数的顶点的调运量,以其中的最小的变量为出基变量（3）将该闭回路上所有的奇数顶点的调运量增加这一数值，所有的偶数顶点的调运量减少这一数值。 7.多个最优解？退化解？（1）如何寻找多个

12、最优方案？识别是否有多个最优解的方法和单纯形表法一样，只需看最优方案中是否存在非基变量的检验数为零。如在本题中给出的最优运输方案中x11的检验数为0，可知此运输问题有多个最优解。只要把x11作为入基变量，调整运输方案，就可得到另一个最优方案第八章：整数规划1.整数规划？纯整数规划？0-1规划？（1）一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。（2）纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。（3）0-1型整数线性规划：决策变量只

13、能取值0或1的整数线性规划。2.整数规划的解VS对应的LP问题的解3.整数规划问题的建模第十章：动态规划1.多阶段决策、最优性定理（1）在实际生产经营活动中，常常可以将一个较复杂的决策过程划分为若干个相互联系的阶段，而每个阶段都需要做出决策，并且某个阶段的决策确定之后，将影响其后的下一个阶段的决策。（2）最优化原理：作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。也就是说，最优策略的任意子策略都是最优的。对最短路问题来说，从“最短路”上的任一点到终点的那部分道路（最短路上的子路），也一定是从该点到终点的最短路

14、（最短子路）。2.阶段、状态、决策、状态转移、阶段指标、策略、过程指标（1）阶段k：首先将问题的全过程适当地分成若干个互相联系的阶段，一般是根据时间与空间的自然特征去划分阶段；k是表示决策顺序的离散的量（2）状态：是指每个阶段开始时所处的自然状况或客观条件。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的（3）状态转移：状态转移方程：第阶段的状态，是由第阶段的状态、和第阶段的决策所决定的，用方程的形式表示这种关系为，称之为状态转移方程；其中函数关系因问题的不同而不同。（4）决策：决策是某一阶段内的抉择，第k阶段的决策与第k个阶段的状态有关，通常用表示第k阶段处于状态时的决策变

15、量，而这个决策又决定了第 阶段的状态（5）策略：由所有各阶段的决策组成的决策函数序列 称为“全过程策略”，记为，从第k阶段开始到最后第n阶段的决策函数序列，称“k子策略”，记为（6）阶段指标函数：从状态出发，选择决策所产生的第阶段决策效用指标 （7）过程指标函数 动态规划要求过程指标具有可分离性指标具有可加性： 指标具有可乘性： 3.解最短路问题4.解资源分配问题第十一章：图与网络模型（有一道计算题）1. 图论中的图VS几何中的图 图论：图是由点和边构成，可以反映一些对象之间的关系。图G区别于几何学中的图。这里只关心图中有多少个点、以及哪些点之间有连线。图论：图是由点和边构成，可以反映一些对象

16、之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。2. 图、有向图、边、弧、连通图、赋权图、网络、树（1） 图：图是由点和边构成，可以反映一些对象之间的关系。（2） 树：无圈的连通图即为树（3） 3. 求解最短路的双标号法双标号法 的步骤（1）给出 点Vs 以标号 ( 0, s )（2）找出已标号的点的集合 I，没标号的点的集合 J，以及弧的集合 （3）如果 B是空集，则计算结束。 如果Vt已标号 ( Lt, Kt )，则 Vs到Vt的距离为Lt，而从 Vs到Vt的最短路径，则可以从Vt 反向追踪到起点Vs （根据 Kt 的记录）而得到。

17、 如果Vt 未标号，则可以断言不存在从 Vs到Vt的路。如果上述的弧(B)的集合不是空集，则转下一步。（4）对B中的每一条弧，计算 Sij = Li + Cij 。在所有的 Sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（Scd , c），返回步骤2。4.图的最小生成树（破圈法、最小生成树的权重）性质1：任何树中必存在次为1的点。性质2：n 个顶点的树必有n-1 条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。（2）最小生成树问题：在一个赋权的、连

18、通的、无向图 G 中找出一个生成树，并使得这个生成树的所有边的权数之和为最小（3）求解最小生成树的破圈算法 a.在给定的赋权的连通图上任找一个圈 b.在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。c.如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。（4）最大流问题的网络图论解法 基本算法步骤： （1）找出一条从发点到收点的路，在这条路上的每一条弧 顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的 最小的顺流的容量pf，从而通过这条路增加网络的流量pf。（3）在这条路上，减

19、少每一条弧的顺流容量pf ，同时增加这些弧的逆流容量pf，返回步骤（1）。 * 为了使算法更快捷有效，我们一般在步骤（1）中尽量选择包含弧数最少的路。第十三章：存储论（有一道计算题）1. 经济定购批量模型一年的总费用 TC(Q)求极值，得使总费用最小的订购批量为一年的存贮费用= 一年的订货费用=一年的总费用=两次订货间隔时间 2. 经济生产批量模型设每次生产量为 Q ，生产率是 p，则每次的生产时间 t 为Q/ p ，于是最高库存量为 (p-d) Q/ p。到 T 时刻存贮量为0，则0到T时间内的平均存贮量为 (p-d) Q/2p 。故单位时间的存贮费为： 另一方面，设D为产品在考察期内的总需

20、求量，则考察期内的生产准备费为 c3 D /Q ，进而，考察期内的总费用TC为： 使TC达最小值的最佳生产量一年的最低总费用生产量为Q时的最大存贮量为每个周期所需时间为显然，时，经济生产批量模型趋于经济订购批量模型。3.年总费用、存储费、订货费、年订货次数、订货时间间隔、在订货点4.允许缺货的经济订购、生产模型（概念） （1）概念：所谓允许缺货是指企业在存贮量降至0时，不急于补充、等一段时间，然后订货。顾客遇到缺货也不受损失或损失很小，并假设顾客会耐心等待，直到新的补充到来。当新的补充一到，企业立即将所缺的货物交付给这些顾客，即缺货部分不进入库存。（2）模型： 设每次订货量为 Q ，由于最大缺

21、货量为S，则最高库存量为 Q- S，故不缺货时期内的平均存贮量为(Q- S)/2，于是，周期T 内的平均存贮量= (Q- S)t1/2T。由于t1 = (Q- S)/d，T= Q/d， 则周期T 内的平均存贮量= (Q- S)2/2Q。又周期T内的平均缺货量= (S t2 ) /2T。由于t2 = S/d，T= Q/d，故周期T内的平均缺货量= S2/2Q。故单位时间的总费用TC为： 使TC达最小值的最佳订购量订购量为Q时的最大缺货量一年的最低总费用订购量为Q时的最大存贮量为每个周期T所需时间 显然，时，允许缺货订购模型趋于经济订购批量模型。 5.经济订购批量折扣模型6.需求为随机变量的单一周

22、期存储模型7.（Q，R）策略，（T，S）策略（Q，R）策略下面我们给出求（Q，R）策略最优解的近似方法，而精确的数学公式太复杂，这里不作介绍。具体求解步骤如下： 1. 设全年的需求量近似为D，利用经济订货批量存贮模型求出（每次的）最优订货量Q。 2. 根据具体情况制定出服务水平，即制定在m天里出现缺货的概率，也即不出现缺货的概率为1。利用下式求出 r P( m 天里需求量 r ) = 1，其中 r 为再订货点，即当库存量下降到r 时订货， m 天后到货第十四章：排队论1.排队系统要素2.排队系统符号表示一个排队系统的特征可以用五个参数表示，形式为：ABCDE其中：a 顾客到达的概率分布，可取M

23、、 D、G 等；b 服务时间的概率分布，可取M、D、 G 等；c 服务台个数，取正整数；d 排队系统的最大容量，可取正整数或；e 顾客源的最大容量，可取正整数或。例如 M / M / 1 / / 表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。单位时间顾客平均到达数 ，单位时间平均服务顾客数 ( ) 数量指标公式: a、系统中无顾客的概率 P0 =1 / b、平均排队的顾客数 Lq =2/( ) c、系统中的平均顾客数 Ls = Lq + / d、顾客花在排队上的平均等待时间 Wq = Lq / e、顾客在系统中的平均逗留时间 Ws = Wq+ 1/ f、顾客得不到及时服务必须排队等待的概率 Pw = / g、系统中恰好有 n 个顾客的概率 Pn =( /)n P03.泊松到达、负指数时间、服务强度4.M/M/1效率指标、M/M/2与M/M/15.排队系统的经济分析第十五章：对策论1.对策模型三要素2.矩阵对策3.如何判断最优纯策略？怎样求解矩阵对策小的值？4.如何判断矩阵对策论存在最优