运筹学复习总结

交通系统分析复习及习题讲解,龙建成jianchenglong,一、线性规划问题,标准形式线性规划解的概念单纯形法大M法，二阶段法对偶理论对偶单纯形灵敏度分析,一般形式,目标函数,约束条件,非负约束条件,一般形式,价值系数,技术系数,资源数量,2.线性规划标准型及其如何化标准型,1.繁写形式,简写形式,化标准型,maxZ=x12x2+3x3,e.g.minZ=-x1+2x23x3,若目标函数为minZ=CX,令Z=-Z,把目标函数转化为maxZ=-CX。,2.约束条件为不等式1）若左右，左剩余变量=右（剩余变量0）2）若左右，左+松弛变量=右（松弛变量0）,e.g.x1+2x28,x1+2x2+x3=8,e.g.x1-x2+x32,x1-x2+x3-x4=2,3.若存在无约束的变量xk,令xk=xk-xk”，代入其中,xk，xk”0。,minz=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20,x3无约束,s.t.x1+x2+(x3-x3”)+x4=7,x1-x2+(x3-x3”)-x5=2,-3x1+x2+2(x3-x3”)=5,x1,x2,x3,x3”,x4,x50,maxz=x1-2x2+3(x3-x3”)+0 x4+0 x5,4.若某约束变量xr有上下界，xru,令xr=xru,用xr+u取代xrxrv，令xr=vxr,用vxr取代xr(xr0),minz=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20,x33,s.t.x1+x2+(x3+3)+x4=7,x1-x2+(x3+3)-x5=2,-3x1+x2+2(x3+3)=5,x1,x2,x3,x4,x50,maxz=x1-2x2+3(x3+3)+0 x4+0 x5,3.线性规划解的概念及其几何意义,解的基本概念,可行解满足约束条件的解。,最优解使目标函数达到最大值的可行解。,基(Basis)对于线性规划的约束条件AX=bX0设B是A矩阵中的一个非奇异的mm子矩阵（|B|0），则称B为线性规划的一个基。,Pj(1jm)为基向量；其余的为非基向量（n-m个）。,设B是线性规划的一个基，则A可以表示为A=B,N,X也可相应地分成,其中XB为m1向量，称为基变量XN为(n-m)1向量，称为非基变量,约束方程AX=b的分块矩阵表示,若XN取确定的值，则XB有唯一的值与之对应XB=B-1b-B-1NXN特别，取XN=0，这时有XB=B-1b,线性规划的解,基解与基可行解,若其中B-1b0，则称以上的基解为基可行解相应的基B称为可行基若在基解中出现基变量为0的情况，称为退化解,称为线性规划与基B对应的基解,基可行解,线性规划问题的性质,性质1：线性规划的可行域是凸集。性质2：线性规划的基可行解x对应于可行域的顶点。性质3：线性规划的最优解在极点上。,4.线性规划的求解方法,图解法单纯形法,图解法几种情形,(a)可行域有界唯一最优解,(b)可行域有界多个最优解,(c)可行域无界唯一最优解,(d)可行域无界多个最优解,(e)可行域无界目标函数无界,(f)可行域为空集无可行解,O,1,2,3,1,2,3,x,x,2,1,A,B,C,D,x,3,=0,x,4,=0,x,2,=0,x,1,=0,可行域(可行解全体),基可行解(可行域顶点、极点),基解,2.单纯形法,从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解，每次转换要使新的基可行解对应的目标函数比前一次的要优，直到目标函数达到最优解。,基本思想,用单纯形法求解如下线性规划问题：,单纯型法的基本步骤,1.化标准形，找到初始可行基，确定初始可行解，建立初始单纯形表。,对于“”的约束，左边+松弛变量=右边,2.检验各非基变量xj的检验数。若0，则已达到最优，停止。否则转第3步。,4.以alk为主元素进行矩阵的行变换，使Pk变换为第l行的元素为1，其余的为0，并将XB列中的xl换成xk，重复进行2-4步，直到终止。,3.换入变量和换出变量的确定换入变量：maxj0=k,确定xk为换入变量；换出变量：，确定xl为换出变量。,“，”情况,变标准型：对于“”的约束，左边-剩余变量+人工变量=右边对于“=”的约束，左边+人工变量=右边,2两阶段法,第一阶段：不考虑原有问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化,x3换入，x7换出,第二阶段：将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表（通常一步计算结束）,x1换入，x4换出,PP45,1.6题（2）采用两阶段法求解如下线性规划问题：,5.对偶理论,5.对偶单纯形法,检查b列的数字，若至少还有一个负分量，检验数保持非正，则选取最小的b负分量为换出变量。,x1为换入变量,对偶单纯形法的基本思想,1.对偶单纯形法是运用对偶原理来求解原问题的一种方法，而不是求解对偶问题的单纯形法。,2.单纯形法是从一个原始问题的基本可行解转到另一个基本可行解，在迭代过程中保持原问题的可行性，即检验数从有0开始逐步变为为止。,3.对偶单纯形法则是保持对偶问题是基本可行解（所有的检验数），而原问题在非可行解（）的基础上通过逐步迭代达到基本可行解（）。这样，同时达到原问题和对偶问题的最优解。,对偶单纯形法的优点和缺陷,1.初始解可以是非可行解，只要检验数全部非负时就可以进行基变换，不需要引入人工变量。,2.如果原问题约束很多，而变量很少，则可以把原问题变成对偶问题，再用对偶单纯形法求解，减少工作量。,3.灵敏度分析中有时要用到对偶单纯形法，使问题简化。,优点：,缺点：,1.对于大多数的线性规划问题，很难找到对偶问题的一个初始可行基，即很难满足所有的，因此该方法很少单独使用。,资源数量bi的改变目标函数系数cj的改变技术系数aij的改变,灵敏度分析,资源数量bi的改变,目标函数系数cj的改变,1.若cj是非基变量xj的系数，这时它在计算表中所对应的判别数,2.若cr是基变量xr的系数，这时它在计算表中所对应的判别数,6.灵敏度分析,什么是灵敏度分析？,1.当发生变化时，对已求得的线性规划问题的最优解的影响。研究系数在什么样的范围内变化，原最优基仍然是最优的。,2.若原最优基不再是最优的，如何用最简便的方法来找到新的最优解。,3.当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。,在灵敏度分析中可能会遇到的各种情况,小结,作业：pp762.9题现有线性规划问题：先用单纯形法求出最优解，然后分析下列各种条件下，最优解分别有什么变化？（1）约束条件的右端常数由20变为30；（2）约束条件的右端常数由90变为70；（3）目标函数中x3的系数由13变为8；（4）x1的系数列向量由(-1,12)T变为(0,5)T；（5）增加一个约束条件2x1+3x2+5x350；（6）将原约束条件改变为10 x1+5x2+10 x3100。,有m个产地生产某种物资，有n个地区需要该类物资设xij表示产地i运往销地j的物资量，cij表示对应的单位运费,运输问题有mn个决策变量，m+n个约束条件。由于产销平衡条件，只有m+n1个相互独立，因此，运输问题的基变量只有m+n1个。,令a1,a2,am表示各产地产量，b1,b2,bn表示各销地的销量，ai=bj称为产销平衡,二、运输问题,表上作业法,Step1.找到初始基可行解，即在(mn)产销平衡表上给出m+n-1个数字格。,（1）最小元素法确定初始基可行解（2）伏格尔法（Vogel）确定初始基可行解,Step2:求各非基变量的判别数，即在表上计算空格的判别数，判别是否达到最优解，如已达到，停止。否则转向step3。（最优解的判别）,(1)闭回路法(2)位势法,Step3：确定换入和换出变量，找到新的基本可行解，在表上用闭回路法调整。,基本步骤：,2.以xst对应的空格为调入格，以此为出发点作一条除该空格以外的其余顶点均为数字格组成的闭回路，在这条闭回路上对运量做最大可能的调整，令空格的调入量为,1.在所有非基变量对应为负值的检验数中，选择其中最小者（若有两个以上相同，则选取其中一个），作为换入变量。,要求所有xj的解为整数，称为纯整数规划要求部分xj的解为整数，称为混合整数规划如果变量只能取0或1，称为0-1整数规划问题对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解,三、整数规划,已知运输问题的供需关系与单位运价表如下：试用表上作业法求最优解。,运筹学第98页，表3-48,2.分支定界法,基本思路：,先求解整数规划问题A相应的线性规划问题B若B的最优解不符合A的整数条件，则B的最优目标函数值必是A的最优目标函数值的上界，记作,而A的任意可行解的目标函数值是Z*的一个下界Z。,将B的可行域分成子区域，逐步减小和增大Z，最终求到Z*。,分支+定界,解题步骤：,1.解问题B,若B没有可行解，则A也没有可行解，stop。,若B有最优解，且符合A的整数条件，则B的最优解=A的最优解，stop。,若B有最优解，但不符合A的整数条件，则B的最优解记为,问题Bx1=4.81x2=1.82z0=356,问题B1x1=4x2=2.10z0=349,问题B2x1=5x2=1.57z0=341,问题B3x1=4x2=2z0=340,问题B4x1=1.42x2=3z0=327,问题B5x1=5.44x2=1z0=308,问题B6无可行解,各分支的最优目标函数中若有小于Z者，则剪掉这支，以后不再考虑。,5.指派问题,有n个人，去完成n项任务，由于每个人的专长，能力不同，由此产生了指派哪个人去完成哪项任务，使,总效率最高费用最省时间最短,数学模型,1个人只能完成一项任务,一项任务只能由1个人完成,设以给定一个初始的价值系数矩阵,1.使指派问题的系数矩阵经变换，在各行各列中都出现0元素。1）从系数矩阵的每行元素减去该行的最小元素。（2）再从系数矩阵的每列元素减去该列的最小元素。若某行（列）已有0元素，不必再减。,计算步骤：,2.进行试指派，以寻求最优解。（1）若经过第1步后已得到n个独立的0元素，则最优解找到，stop。否则,a)进行行检验：从第一行开始逐行检查，当发现只有一个未标记的0元素的某一行，将该0元素加圈，记为，然后划去该所在列的其它0元素，记作。重复上述行检验，直到每一行都不出现为标记的0元素或至少有两个未标记的0元素为止。,b)进行列检验：从第一列开始逐列检查，当发现只有一个未标记的0元素的某一列时，将该0元素加圈，记为，然后划去该所在行的其它0元素，记作。重复上述列检验，直到每一列都不出现为标记的0元素或至少有两个未标记的0元素为止。,反复进行行检验和列检验。,情况1：每一行均有元素，且个数m=n得到最优解。情况2：存在未标记的0元素，但他们所在的行和列中至少有2个。则可标记元素到任一个0元素，再将其同行、同列的其他0元素标记为。情况3：不存在未标记的0元素，但元素的个数m0)，Pn(t1,t2)在时间区间t1,t2)内(t2t1)系统中有n个(n0)顾客到达的概率,1.无后效性：在不相重叠的时间区间内顾客到达数是相互独立的。,2.平稳性：对充分小的，在区间内有一个顾客达到的概率与t无关，而与区间长成正比，即,3.普通性：对充分小的，在时间区间内有两个或2个以上顾客到达的概率极小，以至可以忽略。,当n=0时，,3.负指数分布,1.无记忆性，马尔柯夫性,2.当输入过程是泊松流时，那么顾客相继达到的间隔时间T必服从负指数分布,有一个顾客到达的概率,没有顾客达到的概率,当有顾客在接受服务时，1个顾客被服务完了离开的概率,没有离开的概率,多于一个顾客到达（离开）的概率,M/M/1排队系统的分析,M/M/1排队系统的分析Pn(t),系统处于稳态时,表示平均到达率与平均服务率之比.,表示一个顾客的服务时间与到达间隔时间之比.,服务强度,在系统中的平均顾客数,在队列中等待的平均顾客数,在系统中顾客的逗留时间W,在系统中顾客逗留时间的期望值,在队列中顾客等待时间的期望值,作业:运筹学，第341页，12.2题,某修理店只有一个修理工人，来修理的顾客达到次数服从泊松分布，平均每小时4人，修理时间服从负指数分布，平均需6分钟。求：（1）修理店空闲时间概率；（2）店内有3个顾客的概率；（3）店内至少有1个顾客的概率；（4）在店内顾客平均数；（5）在店内平均逗留时间；（6）等待服务的顾客平均数；（7）平均等待修理（服务）时间；（8）必须在店内消耗15分钟以上的概率。,七、动态规划的基本概念和基本方程,阶段,把所给的问题分成若干相互联系的阶段，以便能按一定的次序去求解。（时间+空间）阶段变量，用k来表示。,状态,表示每个阶段开始所处的自然状况或客观条件。状态变量，用s(k)来表示。,1,2,3,4,k=1,2,3,4,S(1)=AS(2)=B1,B2,B3S(3)=C1,C2,C3S(4)=D1,D2,阶段,状态,决策,表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而可以确定下一阶段的状态。决策变量，用uk(sk)来表示。允许决策集合用Dk(sk)表示。,策略,是一个按顺序排列的决策组成的集合。由过程的第k个阶段开始到终止状态为止的过程，称为问题的后部子过程（k子过程）。记为,当k=1时，此策略函数序列称为全过程的一个策略。简称策略。,状态转移方程,描述由k阶段到k+1阶段的状态转移规律。,指标函数,用来衡量所实现过程优劣的一种数量指标。定义在全过程和所有后部子过程上确定的数量函数。,常见的指标函数,1.各阶段的指标的和的形式。,2.各阶段的指标的积的形式。,最优值函数,指标函数的最优值。用表示。,动态规划的基本思想,若为最优路径则为最优子路径为最优子路径,三、建立动态规划模型及求解步骤,划分阶段确定状态变量及允许状态集合确定