《《运筹学》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《运筹学》PPT课件.ppt（122页珍藏版）》请在三一文库上搜索。
1、运筹学课件,LOGO,目 录,第一章 线性规划 第二章 整数规划 第三章 动态规划 第四章 图与网络 第五章 决 策 论 第六章 矩阵对策,第一章 线性规划,数学模型 图解法 可行域的性质 单纯形法 单纯形表 单纯形法的矩阵描述 对偶规划 运输问题,数学模型,线性规划模型的结构 目标函数：max，min max z(min f)=cjxj 约束条件：,=, aijxj (=, ) bi (i=1,2, n) 变量符号：0,unr,0 xj 0 (j=1,2, n) 线性规划的标准形式 目标函数：max max z=cjxj 约束条件 ：= aijxj = bi (i=1,2, n) 变量符号
2、：0 xj 0 (j=1,2, n),典型问题： 合理下料问题,典型问题： 合理下料问题 运输问题,典型问题： 合理下料问题 运输问题 生产的组织与计划问题,典型问题： 合理下料问题 运输问题 生产的组织与计划问题 投资证券组合问题,典型问题： 合理下料问题 运输问题 生产的组织与计划问题 投资证券组合问题 分派问题,典型问题： 合理下料问题 运输问题 生产的组织与计划问题 投资证券组合问题 分派问题 生产工艺优化问题,线性规划的图解,x1,x2,目标函数等值线,可行域,最优解,6,6,-8,4,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域的
3、性质,线性规划的最优解在极点上 线性规划的可行域是凸集,极点,凸集,不是凸集,凸集,二个重要结论： 满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。,二个重要结论： 满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。 最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。,解的讨论： 最优解是唯一解；,解的讨论： 最优解是唯一解； 无穷多组最优解： 例： max z=40x1+30x2 s.t. 4x1+3x2 120 2x1+x2 50 x1,x2 0,x2,50,40,30,20,10,10,20,30,40,x1,
4、可行域,目标函数是同约束条件：4x1+3x2 120平行的直线,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当z的值增加时，目标函数与约束条件：4x1+3x2 120 重合，Q1与Q2之间都是最优解。,Q1（25，0）,Q2（15，20）,解的讨论： 无界解： 例：max z=x1+x2 s.t. -2x1+x2 40 x1-x2 20 x1,x2 0,x2,50,40,30,20,10,10,20,30,40,x1,该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。,解的讨论： 无可行解： 例：max S=2x1+3x2 s.t. x1+2x
5、2 8 x1 4 x2 3 -2x1+x2 4 x1,x2 0,该问题可行域为空集，即无可行解，也不存在最优解。,解的情况： 有可行解 有唯一最优解 有无穷最优解 无最优解 无可行解,单纯形法的引例,例： max z=31x1+22x2 s.t. 6x1+ 2x2180 4x1+10x2400 3x1+5x2210 x1,x20,写成标准型为： max z=31x1+22x2 6x1+2xx+x3 =180 4x1+10x2 +x4 =400 3x1+5x2 +x5=210 xj0 (j=1,2,5),max z=31x1+22x2 6 x1+ 2 x2 + x3 =180 4 x1+10 x
6、2 + x4 =400 3 x1+ 5 x2 + x5=210 xj0 (j=1,2,5),基变量XB=(x3 , x4 , x5)T,非基变量XN=(x1 , x2)T,令所有非基变量为0，则得初始可行解为X(0)=(0,0,180,400,210)T,对应z(0)=0 取目标函数最大正系数对应的非基变量为入基变量；取最小比值所对应方程的基变量为出基变量。本例中，取 x1为入基变量， x3为出基变量。,x1+ 1/3x2 +1/6x3 = 30 26/3x2 -2/3x3 +x4 =280 4x2 -1/2x3 +x5 =120,令非基变量x2=x3=0,z(1)=930,相应的基可行解为x
7、(1)=(30,0,0,280,120)T,为使目标函数中不出现基变量，消去x1，得 z=31(30-1/3x2-1/6x3)+22x2=930+35/3x2-31/6x3 由于非基变量x2的系数为正，故将x2作为入基变量，z值仍可变大，即X(1)还不是最优解。再次迭代得，,x1 +5/24x3 1/12x5=20 5/12x3 +x4 13/6x5 =20 x2 1/8x3 +1/4x5 =30,同理，为使目标函数中不出现基变量，消去x2，得 z = 93035/3(301/8x31/4x5)31/6x3 = 128089/24x335/12x5 （*）,令非基变量x3=x5=0,得z(2)
8、=1280,相应的基可行解为X(2)=(20,30,0,20,0)T.,由于（*）式中，非基变量x3,x5的系数皆为负，故若将其作为入基变量，均只能使z值减小而非增大。由此，X（2）已是最优解X*,z(2)为对应的最优值z*.,单纯形表,写出单纯形表,max z=31x1+22x2 6 x1+ 2 x2 + x3 =180 4 x1+10 x2 + x4 =400 3 x1+ 5 x2 + x5=210 xj0 (j=1,2,5),作旋转变幻的新单纯形表,得新基可行解X(1)=(30,0,0,280,120)T.因唯有2=35/30，x2为入基变量，又因比值最小在第三行，故x5为出基变量。合之
9、，知主元为4。作旋转变化得下表,因所有检验数j0(j=1,2,5),故当前基可行解X(2)=(20,30,0,20,0)T即为最优解X*,最优值为z*=1280.,单纯形法的矩阵描述,其矩阵形式为：,max z=CBXBCNXN s.t. BXBNXN=b XB ,XN0,矩阵描述之初始单纯形表,先取初始单位阵I作为初始基阵B，得 初始单纯形表：,矩阵描述之迭代单纯形表,再选某一基阵B进行迭代，得 迭代单纯形表：,对偶规划,DUAL,定义：,设有原规划： max z = CX AXb X0,其对偶规划为： min f =Yb YAC Y0,原规划与对偶规划的线性关系,运输问题,运输问题的表示
10、网络图、线性规划模型、运输表 初始基础可行解 最小元素法、差值法 判别最优方案 位势法,2,3,2,1,3,4,1,运输问题网络图,s2=27,s3=19,d1=22,d2=13,d3=12,d4=13,s1=14,供应量,供应地,运价,需求量,需求地,6,7,5,3,8,4,2,7,5,9,10,6,运输问题线性规划模型,供应地约束,需求地约束,运输问题的表格表示,最小元素法（1）,最小元素法（2）,最小元素法（3）,最小元素法（4）,最小元素法（5）,最小元素法（6）,表上作业法差值法(1),计算各行各列中最小两个运价之差值,差值法(2),除第二列外重新计算差值,差值法(3),差值法(4)
11、,差值法(5),差值法(6),差值法(7),判别最优方案位势法,本例中，每个含格所对应的ij=cij-ui-vj均为非负，故所得方案已是最优方案,位势法(2),例：已知初始方案如下表所示，检验并改 进至最优方案。,位势法(3),1,2,5,4,3,6,位势法(4),1,2,3,4,位势法(5),第二章 整数规划,分枝定界法 0-1型整数规划 分配问题,例1：讨论纯整数规划 max z=x1+2x2 s.t. 2x1+5x215 2x12x25 x1 , x20且为整数,分枝定界法,不考虑x1,x2为整数的限制条件，得规划（0）对应的最优解与最优值为,R0,z,2x15x2=15,3,2.5,分
12、枝定界法(1),考察X的某一分量，不妨选x2= ,因为1x22,为了使x2整数化,剔除1x22对应的可行域.为此,增加约束条件x21及x22,于是可行域R0可分解成两个小可行域R1和R2.原规划(0)分解成规划(1)与规划(2):,(1) （2） max z=x1+2x2 max z=x1+2x2 s.t. 2x1+5x215 s.t. 2x1+5x215 2x1-2x25 2x1-2x25 x21 x22 x1,x20且为整数 x1,x20且为整数,分枝定界法（2）,仿上求解，得规划（1）、（2）对应的最优解与最优值为：,R2,R1,分枝定界法(3),考察(1)、(2)，因规划（2）的z值优
13、于规划（1）的z值，故先分解规划（2）。仿上，R2分解成R3与R4=。规划（2）分解成规划（3）与规划（4）：,分枝定界法(4),(1) （2） max z=x1+2x2 max z=x1+2x2 s.t. 2x1+5x215 s.t. 2x1+5x215 2x1-2x25 2x1-2x25 x22 x22 x1 2 x1 3 x1,x20且为整数 x1,x20且为整数,分枝定界法(5),仿上求解，得规划（1）、（2）对应的最优解与最优值为：,无可行解, 剪枝,考察(1)、(3)，因规划（3）的z值优于规划（1）的z值，故先分解规划（3）。仿上，R3分解成R5与R6。规划（3）分解成规划（5）
14、与规划（6）：,分枝定界法(6),(5) （6） max z=x1+2x2 max z=x1+2x2 s.t. 2x1+5x215 s.t. 2x1+5x215 2x1-2x25 2x1-2x25 x22 x22 x1 2 x1 2 x22 x23 x1,x20且为整数 x1,x20且为整数,分枝定界法(7),仿上求解，得规划（1）、（2）对应的最优解与最优值为：,R1,R5,01型整数规划(1),显枚举法： 例：求解下列01规划 max z=3x12x25x3 s.t. x12x2x32 x14x2x34 x13x2 3 4x23x36,01型整数规划(2),按二进位制穷举01变量xj（j=
15、1，2，3）构成的解X=(x1,x2,x3)T,共有8种可能组合。先检查哪些是可行解，再从中选最优解。,01型整数规划(3),分析上述求解过程，对显枚举法作相应的改进后，其计算见表如下，此即为隐枚举法：,分配问题,一般最小分配问题的数学模型为: min f=cijxij s.t. xij=1 (i=1,2,n) xij=1 (j=1,2,n) xij=0或1 (i,j=1,2,n) 目标函数最大的分配问题可化为目标函数最小的分配问题来求解。可取一个比所有cij都大的整数k，令 cij=kcij即可。以cij为价值系数求最大分配就等价于以cij为价值系数求最小分配。,1、缩减矩阵,分配问题解法匈
16、牙利法,-2.0 -1.0 -1.8 -1.8,-0.1,2、初始分配,匈牙利法（2）,3、行列标号,匈牙利法（3）,s,4,3,4、继续缩减,匈牙利法（4）,=0.3,s,4,4,2,3,3,5、调整分配,而今 0 已满4个，故得最优分配，最优解为：,匈牙利法（5）,X*=,第三章 动态规划(DP),不定阶段最短路线问题 资源分配问题 排序问题,求如图所示交通图中点i =1,2,3,4到点5的最短路线及路长。,一、不定阶段最短路线问题,1、迭代运算,*,f(1)=d() =2,*,f(4)=d()=3,*,f(3)=d() +f(4)=1+3=4,f(2)=d()+f(3)=0.5+4=4.
17、5,*,2、最优方案,例：工厂有五台设备分配给编号为j=1，2，3的三个车间。各种可能的分配台数xi及其对应的经济收益gi(xi)(万元)数据如下表所示： 问：应如何分配给车间设备的台数，才能使总收益最大？,二、资源分配问题,）阶段变量k表示把当前留存的设备以某一台数分配给k号车间（k=1,2,3）。 ）状态变量yk表示第k阶段开始时留存的设备台数。 ）决策变量xk表示把当前留存的设备分配给k号车间的台数，对应的决策集合为： xk|xk=0,1,yk k=1,2 Dk(yk)= x3|x3=y3 k=3 )转移方程 yk+1=ykxk )目标函数 Vk3=gj(xj) (k=1,2,3) )基
18、本方程 fk(yk)=maxgk(xk)+fk+1(ykxk) f4(y4)=0 (k=3,2,1),1、动态规划模型,2、逆序计算表,3、最优策略 有两个最优策略 P13*=0,2,3或2,2,1,4、最优方案,最优排序方法： 求mina1, a2, a3,an;b1,b2, ,bn，此值记作m 当m=ai时，则把工件i排在首位，并从初始工件集w中去掉工件i。工件i不唯一时，可任选一个。 当m=bi时，则把工件i排在末位。并从初始工件集w中去掉工件i，工件i不唯一时，可任选一个。 4、对新得的工件集wi重复步骤1、2、3，直至w成为空集，停止,三、排序问题,例：设有2*5排序问题，数据如下表
19、所示，求最优顺序。,解：按最优排序规则，可得如下最优顺序：, 2,15,第四章 图与网络,图的基本概念 树的性质 中国邮递员问题 有向图与最短路问题 最大流问题,图的基本概念,非空点集V与连接点的某个线集E之二元组合称为图 ，记作G=(V,E).,点与有向边 每一条边和两个邻点关联，一条边可以用两个邻点的标号表示（i，j）,路径（Path） 前后相继并且方向相同的边序列 P=(1,2),(2,3),(3,4),4,3,1,2,链（Chain） 前后相继并且方向不一定相同的边序列称为链 C=(1,2),(3,2),(3,4),4,1,3,2,回路（Circuit） 起点和终点重合的路径称为回路
20、=(1,2),(2,4),(4,1) 回路中各条边方向相同,2,3,1,4,圈(Cycle) 起点和终点重合的链称为圈 =(1,2),(2,4),(3,4),(1,3) 圈中各条边方向不一定相同,4,2,1,3,连通图 任意两个节点之间至少有一条链的图称为连通图,树(Tree) 无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点,2,4,3,5,1,树的性质,任何树至少有一个悬挂点,p个顶点的树T含p1条边,树T中任意两点之间存在唯一 的一条链,树T中不相邻两点之间连一条边，则形成唯一的圈,2,4,3,5,1,2,4,3,5,1,2,4,3,5,1,当连通图G=(V,E)的部分子图为树T
21、，则称T为G得支撑树，记作T=(V,E),其中E包含于E,图的支撑树,定理 设连通非负赋权图，R为蕴含E的圈。R有最小总数的充分必要条件为 （1）每边最多重复一次； （2）在G的每个圈上，重复边总权不超过圈总权之半。,中国邮递员问题,如图所示之G是一幅街道图，点v6表示邮局。求最优投递路线。,1,4,5,2,1,3,2,2,6,3,2,v1,G含两个奇点v2, v4。,取链v2, v6, v5, v4,作重复边，得Euler图G(0),有Euler圈R(0)，总权是40,R(0)满足条件1,检验条件2。取圈v1, v5, v4, v1调整的G(1),有R(1),总权是39。,取圈v2, v3,
22、 v5, v2，调整得G(2),有R(2)，总权是37。,逐圈检验。得G(2) =G*,其上任一个Euler圈皆为R*.例如可取R*= v6, v2, v3, v4 v1, v2, v3, v5 v1, v6, v3, v5 v1, v4, v5, v6,有向图与最短路问题,1、顺序标号法 例：如图是一个单项道路系统。大批物资集中在出发地S，要求用车尽快运输到目的地T。A,B,C,D,E是中间站。图中数字为相邻两站间的路程。,0,2,4,4,8,7,13,由此而得两条从v1到v7的最短路R7* : v1, v2, v3, v6, v7与v1, v2, v3, v5, v6, v7,2、递推标号
23、法,求如图所示D的从v1到v8的最短路R8*及 路长ri*,v1,v2,v4,v3,v5,v6,v7,v8,6,-1,-2,8,3,-1,2,1,-1,2,-3,7,-5,-3,-5,1,1,得一条最短路 R8*=v1, v3, v4, v7, v8 路长为r8* =-10,无向图求最短路算法,求如图所示之G的从v1到v8的最短路R8*及路长r8*.,*,*,*,*,*,*,表中空格对应的值为+，固定标号加上方括弧，短横线格是同一行固定标号重复书写之简化。得一条最短路R8* v1,v3,v5,v2,v6,v8 路长为r8* =11,最大流问题,网络与流,弧的容量和流量 容量cij，流量fij,
24、可行流 满足以下条件的流称为可行流： 1、每一个节点流量平衡 2、0fij cij,饱和弧、非饱和弧,1、如果fij=cij，则 aij称为饱和弧；,(1,2)是饱和的,2、如果fijcij，则aij称为非饱和弧；,（1，2）是不饱和的 间隙为12=c12-f12=5-3=2,增广链,若简单链L上各弧的流满足： 1、0fijcij aijL+ 2、0 fijcij aijL- 则L成为关于F的一条增广链。,求如图说示网络D上的最大流F*,弧上的数组(cij, fij(0)。,既取初始可行流为0,(0,+),(S,2),(S,9),(S,3),(1,2),lt=2,2),2),(1,2),(2,
25、6),(0,+),(S,3),(S,9),(2,4),(1,6),8),lt=6,6),6),(0,+),(S,3),(S,3),(2,3),(3,3),lt=3,9),3),3),(0,+),(S,3),(3,2),(-3,3),lt=2,2),5),图中弧上的数组即是(cij , fij*),第五章 决 策 论,决策树法：,决策点,决策枝 （方案）,状态点,(期望值）,概率枝,（概率）,结果点 （收益或 损失值）,某服装加工厂的生产方案及市场状态资料如表所示。试用决策树法确定决策策略。,解 图为决策过程的决策树。经过第一次决策，在单品种大批量生产（方案s1 ）情况下，做两用衫为应选方案。再
26、进行第二决策，与多品种小批量生产（方案s2 ）比较。因s1的利润期望值高于s1 ，故决策者应选策略s2，,1,2,3,4,5,6,e1 0.6,e2 0.4,e1 0.8,e2 0.2,e1 0.5,e2 0.5,e1 0.4,e2 0.6,e1 0.75,e2 0.25,e1 0.9,e1 0.1,1,2,0,20302,20435,20435,第六章 矩阵对策,当局中人I、II和策略集S1、S2及局中人I的赢得矩阵A=(aij)mn确定后，一个矩阵对策就可确定。矩阵对策的数学模型表示为： G=I,II;S1,S2;A 简记作：G=S1,S2;A,2n和m2矩阵对策的图解法,例：求解矩阵对策
27、G=S1,S2;A,其中S1=1,2, S2=1,2,3,A为 1 7 13 9 0 -2,解：显然，G无鞍点且无优超关系. 设局中人I的混合策略为X=x1,x2T=(x,1-x)T,则按“理智行为”，I期望的赢得为 v1=maxminx9(1x),7x,13x2(1x) =maxmin-8x9,7x,15x2 =maxf(x) (0x1),在Oxv平面直角坐标系中， 取x0,1,画直线段，如图所示： l1 v=-8x9 l2 v=7x l3 v=15x2,x*,求解矩阵对策G=S1,S2;A,其中, S1=1,2,3,4, S2 =1,2,A为,1 -5 -4 4 -2 3 0 -5,易知G无鞍点，又因为14,所以x4*=0,A简化为 1 -5 -4 4 -2 3,设局中人II的混合策略为Y=y1y2T=(y,1-y)T,则按“理智行为”，II期望的支付为 v1=minmaxx9(1x),7x,13x2(1x) =minmax-8x9,7x,15x2 =ming(y) (0y1),在Oyv平面直角坐标系中，取y0,1,画直线段，如图所示： l1 v=6y5 l2 v=-8y4 l3 v=-5y3,y*,