运筹学期末复习

1,运筹学总复习,2,第八章 排队论,3,s 系统中并联服务台的数目； 平均到达率（单位时间到达的顾客数）；1/ 平均到达间隔（相继到达顾客的平均间隔 时间）。 平均服务率（单位时间服务的顾客数）；1/ 平均服务时间（为顾客服务的平均时间）。 服务强度，即每个服务台单位时间内的 平均服务时间； 一般有 s ；,稳态排队系统的参数,4,Pn=PN=n：稳态系统任一时刻状态为n（系统中恰好有n个顾客）的概率； 特别当 n = 0 时，Pn即P0，为稳态系统所有服务台全部空闲的概率。,稳态下系统的基本数量指标,5,到达的顾客不一定全部进入系统接受服务，设系统中有n个顾客时，每单位时间进入系统的顾客平均数为n，每单位时间离开系统的顾客平均数为n。我们引入：e 有效平均到达率，即每单位时间实际进入系统的平均顾客数（期望值）， e=npn 对等待制的排队系统，有 e ,6,平均有效离去率 : e = n pn 从平稳系统中均值的意义看，容易理解应有平均有效离去率等于平均有效到达率，即 e = e,7,L , Lq, e ,W , Wq 之间的关系： L = e W, Lq = e Wq几何解释：稳态时，一个顾客，进入系统后，每单位时间平均到达e顾客。,队长L由时间段内W个e组成的,L=eW,5) Little公式,8,同理：Lq= eWq又 W=Wq+（1/）-W与Wq只相差一段平均服务时间1/ L=Lq+(e /),5) Little公式,以上公式对一般泊松输入指数排队模型成立。,9,对于平均队长和平均队列长，可用下列公式计算 因此，只要知道 ，则 或 就可由以上两公式求得，从而再由上面四公式就能求得四项主要工作指标。,10,排队论求解的主要数量指标,P0 、Pn 、L 、 Lq 、W 、Wq,11,单服务台无限源系统M/M/1/FCFSM/M/1/N/FCFS,12,M/M/1/FCFS系统: 参数 ，问题的一般提法： 泊松输入/负指数分布/单服务台/系统无限制/顾客源无限制求解： (1)系统状态P0 、Pn (2)系统运行指标：L 、 Lq 、W 、Wq,13,M/M/1/FCFS排队系统模型的主要指标,1、系统中无顾客的概率：P0 =1 2、系统中有n个顾客的概率： Pn =n .(1 )3、系统中的平均顾客数：L= /(1 )4、顾客在系统中的平均逗留时间：W = L /5、顾客花在排队上的平均等待时间：Wq = W-1 /u6、平均排队的顾客数： Lq= Wq,14,1、例子 P216 某医院急诊室同时只能诊治1个病人，诊治时间服从指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。求该排队系统的主要数量指标。,15,由题意知：该题是M/M/1/FCFS排队系统,(人小时)，,60154(人小时),故服务强度为,其中，p0是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。,16,此模型的平均有效到达率，即是到达率 ,病人在急诊室内外平均逗留时间：,病人平均等候时间：,(小时)45(分钟),急诊室内外的病人平均数：,（人）,（小时）,急诊室外排队等待的病人平均数：,(人),17,2、 某医院手术室只能同时诊治一个病人，病人到达服从泊松分布，每小时病人平均到达率为2.1(人/小时)。每次手术平均时间0.4(小时/人)，服从负指数分布求：(1) 病房中病人的平均数(L)；(2) 排队等待手术病人的平均数(Lq )；(3) 病人在病房中平均逗留时间(W)(4) 病人排队等待时间(Wq)。,18,19,3、某医院急诊室每小时到达一个病人，输入为最简单流，急诊室仅有一名医生，病人接受紧急护理平均需20分钟，服务时间为负指数分布，试求： （1） 稳态情况下：a)没有病人的概率；b)有两个病人的概率；c)急诊室里病人的平均数；d)排队中病人的平均数；e)病人在急诊室中的平均时间 （2）为了保证病人急诊所花费的平均时间少于25分钟，那么平均紧急护理时间必须降至多少分钟?,20,21,22,第七章 动态规划,23,动态规划的基本概念,1) 阶段和阶段变量 阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量阶段数等于多阶段决策过程从开始到结束所需作出决策的数目。,24,2）状态、状态变量和可能状态集 描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。,25,每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1。通常定义阶段的状态即指其初始状态。,26,一般状态变量的取值有一定的范围或允许集合，称为可能状态集，可能状态集用相应阶段状态sk的大写字母Sk表示，skSk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定,27,3）决策、决策变量和允许决策集合 决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。,28,用以描述决策变化的量称之决策变量。决策变量的值可以用数，向量、其它量，也可以是状态变量的函数. 记uk= uk(sk)，表示于阶段 k 状态为 sk 时的决策变量。,29,决策变量的取值往往也有一定的允许范围，称之允许决策集合。决策变量uk(sk)的允许决策集用Uk(sk)表示, uk(sk) Uk(sk) 允许决策集合实际是决策的约束条件。,30,4）策略和允许策略集合 策略(Policy)也叫决策序列策略有全过程策略和k部子策略之分，全过程策略是指由依次进行的n个阶段决策构成的决策序列，简称策略，表示为 p1,nu1,u2,un。,31,从 k 阶段到第 n 阶段，依次进行的阶段决策构成的决策序列称为 k 部子策略, 表示为pk,n uk, uk+1, , un ，显然当 k = 1 时的 k 部子策略就是全过程策略。,32,在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P1,n ，从允许策略集中，找出具有最优效果的策略称为最优策略。,33,5）状态转移方程 系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1 。,34,系统状态的这种转移，用数学公式描述即有：通常称上式为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。,35,6)指标函数 用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用等等。,36,阶段指标函数（阶段效应） 用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk,37,过程指标函数（目标函数）,用Rk(sk,uk)表示k子过程的指标函数。Rk(sk,uk) 不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:,38,7) 最优解 用fk(sk)表示第k子过程指标函数 ，在状态sk下的最优值,即 称 fk(sk) 为第 k 子过程上的最优指标函数；,39,相应的子策略称为sk状态下的最优子策略，记为pk*(sk) ；而构成该子策赂的各段决策称为该过程上的最优决策，记为有 简记为,40,特别， 当 k = 1 且 s1 取值唯一时，f1(s1)就是问题的最优值，而p1* 就是最优策略。,41,最优策略即为s1=s1*状态下的最优策略： 我们把最优策略和最优值统称为问题的最优解。,42,8) 多阶段决策问题的数学模型 适于动态规划方法求解的一类多阶段决策问题，即具有无后效性的多阶段决策问题的数学模型:,43,常用求最小的加法计算公式：,（边界条件）,阶段指标,44,动态规划方法的基本步骤,用函数基本方程逆推求解是常用的方法：首先要有效地建立动态规划模型,然后再递推求解基本方程,最后回溯求得最优策略。合理、有效地建立一个动态规划模型,是解决问题的关键。,45,（一）动态规划建模要点, 将实际问题恰当地分割成n个子问题(n个阶段) 通常是根据时间或空间而划分，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n。,46,动态规划建模要点, 正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性。 在动态规划模型中，一般状态变量要选取那种可以进行累计的量。,47,动态规划建模要点,正确地定义决策变量及各阶段的允许决策集合Uk(sk)。 一般将问题中待求的量选作动态规划模型中的决策变量。,48,动态规划建模要点,正确地写出状态转移方程 要能正确反映状态转移规律。如果给定第 k 阶段状态变量 sk 的值，则该段的决策变量 uk 一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有 sk+1 = Tk ( sk , uk ),49,动态规划建模要点,正确地写出目标函数 目标函数由递推关系构成，因此，它应满足下列性质：函数可分性：阶段指标相对独立；要满足递推关系；过程函数严格单调。,50,动态规划基本方程 fn+1(sn+1) = 0 (边界条件) fk(sk) = opt ugk ( sk , uk ) + fk+1(sk+1) k = n , n-1, , 1,51,（二）逆序求解动态规划基本方程,常见三种情况：一种是对于特殊的网络求最优路径，可以直接在网络图上，直观地使用标号法（见下一节）求解；对于离散型的动态规划问题，常使用列表格（递推方程）的方法求解。当阶段指标与递推公式可表示为解析显函数时，对于规模较大，特别是连续型的动态规划问题，常直接使用函数求优的方法。,52,（三）回溯求得最优策略,从k=1开始，逐步向后归纳出前一环节各步所选择的决策，得到决策序列，即最优策略。,53,1、例子 P176用递推方程求解最短路径问题,54,（一）建模,如图划分成 5 个阶段；状态变量sk表示第k阶段开始的位置；决策变量uk定义为到达下一站所选择的路径；状态转移：决策确定了下一阶段的状态；阶段指标：图中线段上所标的数值；,55, 最优指标函数 fk(sk) ：表示从目前状态到E的最短路径。终端条件为 f5 ( s5 ) = f5 ( E ) = 0其含义是从E到E的最短路径为0。,56,（二）逆推求解第4阶段的递推方程为,从 f5 ( s5 ) 到 f4 ( s4 ) 的递推过程用下表表示,57,第3阶段的递推方程为：,从 f4(s4) 到f3(s3) 的递推过程用表格表示如下表：,58,第2阶段的递推方程为,从f3(s3) 到f2(s2) 的递推过程用表格表示如下,59,60,第1阶段的递推方程为：,61,由此得到 f1(s1) =21 , 即从 A 到 E的最短路径长度为21。（三）回溯求最优策略： 由 f1(s1) 向 f4(s4) 回溯，得到最短路径为：S A1 B1 C1 ES A3 B1 C1 ES A3 B2 C1 E,62,2、见以下有向图，图中数字为两点间距离 要求：用表格（递推方程）计算。（1）求出AD的最短路径以及最短长度；（2）用双箭头在图上注明。,63,参考答案,A到D的最短路径：AB3 C1 D最短长度：21,64,第四章 运输问题,65,1. 求初始基本可行解 （西北角法、最小元素法）2. 求检验数（位势法）3. 换基（闭回路）,表上作业法：,66,1、初始基本可行解的确定 （1）西北角法：从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。,67,（2）最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。,68,注:应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0。,69,由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。,2、基本可行解的最优性检验,70,位势法 位势：设对应基变量xij 的 m +n -1 个 ij ，存在ui ,vj 满足 ui+vj=cij ，i=1,2 ,m ; j=1,2 ,n . 称这些 ui , vj 为该基本可行解对应的位势。,71,由于有m + n 个变量（ ui , vj ）， m + n - 1 个方程（基变量个数）， 故有一个自由变量，位势不唯一。,利用位势求非基变量xij的检验数： ij = cij - ui - vj i = 1, , m ; j = 1, , n,72,位势法求检验数：step 1 从任意基变量对应的 cij 开始,任取 ui 或 vj ，然后利用公式 cij = ui + vj 依次找出 m + n 个 ui , vj step 2 计算非基变量的检验数 ij = cij - ui - vj ；填入圆圈内,73,当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，这一过程通常称为换基(或主元变换)过程（闭回路法）。,3、求新的基本可行解,74,74,（1）选负检验数中最小者 rk，那么 xrk 为主元，作为进基变量（上页图中 x24 ）; （2）以 xrk 为起点找一条闭回路，除 xrk 外其余顶点必须为基变量格（上页图中的回路）;,在运输问题的表上作业法中，换基的过程是如下进行：,75,75,（3）为闭回路的每一个顶点标号， xrk 为 1号，沿一个方向（顺时针或逆时针）依次给各顶点标号；（4）求 =Minxijxij对应闭回路上的偶数标号格= xpq 那么确定 xpq为出基变量，为调整量；,76,76,（5）对闭回路的各奇标号顶点调整为：xij + ，对各偶标号顶点 调整为：xij - ，特别 xpq - = 0， xpq变为非基变量。 重复(2)、(3)步，直到所有检验数均非负，得到最优解。,77,注意： （1）构造闭回路进行换基时，只有一个基变量出基，一个非基变量进基； （2）如果偶标号格中两个变量减去调整量后都变为零，则取其中一个为出基变量，另一个填上运量0。,77,78,1、例子 P99,79,80,81,所有ij 0，得到最优解 x13 = 5,x14 = 2,x21 = 3,x24 = 1, x32 = 6, x34 = 3, 其余 xij = 0 ; 最优值： f* = 35+102+13+81+46+53 = 85,82,2、用表上作业法求解下列运输问题,83,84,第三章 线性规划对偶与灵敏度分析,85,对偶规划的形式 有对称形式和非对称形式。 对称形式的对偶规划之间具有下面的对应关系： (1) 若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即 “max，” 和 “min，” 相对应。,86,(2) 从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3) 从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4) 两个规划模型中的变量皆非负。,87,对称形式： 互为对偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”,88,非对称形式的对偶规划:对非对称形式，可以按照下面的对应关系直接给出其对偶规划(1) 将模型统一为“max，”或“min，” 的形式，对于其中的等式约束按下面(2)、(3)中的方法处理；(2) 若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；(3) 若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。,89,1、例子 P67 写出下面线性规划的对偶规划模型,90,解 先将约束条件变形为“”形式,91,根据非对称形式的对应关系，直接写出对偶规划,92,2、写出下面线性规划的对偶规划模型,93,94,94,理解最优单纯形表的含义考虑问题 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . . am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0,灵敏度分析,95,95,设最优单纯形表,其中：,96,96,灵敏度分析,ci 单个变化保持最优解不变的允许范围bj 单个变化对解的可行性的影响线性规划增加一个变量线性规划增加一个约束,97,97,若ck是非基变量的系数：设ck变化为 ck + ck k= k+ ck只要 k 0 ,即 ck - k ，则最优解不变；否则，将最优单纯形表中的检验数 k 用 k取代，继续单纯形法的表格计算。,98,98,例 Max z = -2x1 - 3x2 - 4x3 S.t. -x1 -2x2 - x3 +x4 = - 3 -2x1 + x2 -3x3 +x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0,99,99,例：最优单纯形表,从表中看到3= c3+c3-(c2a13+c1a23 ) 可得到c3 9/5 时，原最优解不变。,100,100,设 cl 变化为 cl + cl ，那么 j=j - cl alj 只要对所有非基变量j0，即jclalj ，则最优解不变；否则，将最优单纯形表中的检验数j 用 j取代，继续单纯形法的表格计算。,2、若 cl 是基变量的系数,101,101,Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0,例,b,增加变量,增加约束,102,102,下表为最优单纯形表,考虑基变量系数c2发生变化,由j=cj-(c1a1j+c5a5j+(c2+c2)a2j) j=3,4可得到 -3c21时，原最优解不变。,103,103,设分量 br 变化为 br + br ，只要保持 B-1(b + b)0 ，则最优基不变，即对偶价格不变；否则，需要利用对偶单纯形法继续计算。,3、 右端常数的变化,104,104,上例最优单纯形表如下,例,105,105,0 0.25 0 这里 B-1 = -2 0.5 1 0.5 -0.125 0,各列分别对应 b1、b2、b3 的单一变化因此，设 b1 增加 4，则 x1 , x5 , x2分别变为：4+04=4, 4+(-2)4=-40, 2+0.54=4用对偶单纯形法进一步求解，可得：,106,106,于是，x* = ( 4, 3, 2, 0, 0 )T f* = 17,107,107,讨论保持最优基不变的前提下，b2的允许变化范围 4 + b2 0.25 0 b2 -16 4 + b2 0.5 0 b2 -8 2 + b2 (- 0.125) 0 b2 16于是 -8 b2 16,108,108,增加变量 xn+1, 相应有pn+1, cn+1 。 可计算出 B-1pn+1, n+1=cn+1-cri ari n+1 填入最优单纯形表：若 n+1 0 则 最优解不变；否则，进一步用单纯形法求解。,4、 增加新变量,109,109,例,对前例，增加x6 , p6=( 2, 6, 3 )T, c6=5,用单纯形法进一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5,110,110,首先，应把最优解代入新的约束 若满足，则最优解不变，停止； 否则，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），填入最优单纯形表作为新的一行，并通过矩阵行变换把对应基中的列向量变为单位向量。 进一步用对偶单纯形法求解。,5、增加一个约束条件,111,111,例 上例增加 3x1+ 2x215，原最优解不满足这个约束。于是,对表中新的一行利用矩阵初等行变换进行处理，可得新的对偶单纯形表：,112,112,经对偶单纯形法一步，可得最优解为（3.5, 2.25, 0, 0, 3, 2 )T，最优值为 13. 75,113,113,灵敏度分析 1,114,114,115,参考答案,115,116,116,灵敏度分析 2,117,118,参考答案,118,119,第二章 单 纯 形 法,120,标准形式目标函数：Max z = c1x1 + c2x2 + + cnxn,约束条件：a11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0,121,线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。 对于各种非标准形式的线性规划问题，转换成标准形式进行求解。,122,1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + + cnxn 则可以令z-f ，该极小化问题与下面的极大化问题有相同的最优解，即 Max z = -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f - Max z,123,2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s =bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi,124,当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时，类似地令 s =(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi,125,为了使约束由不等式成为等式而引进的变量 s 称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。,126,3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj = xj- xj”其中 xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。,127,4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1 + a22 x2 + + a