胡云权运筹学课件3

OR31OPERATIONSRESEARCH运筹学Ⅲ——如何把事情做得最好郝英奇OR32第六章整数规划本章要求理解整数规划的含义掌握分枝定界法的思想和方法掌握0-1变量的含义和用法掌握指派问题的算法微机求解OR336.1整数规划问题的提出决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数……如何解决？四舍五入不行，枚举法太慢问题分类：纯整数规划、混合整数规划、0-1整数规划专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法OR34问题举例某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？maxZ=2000x1+1000x25x1+4x2≤242x1+5x2≤13x1.x2≥0且为整数解此LP问题，得：X1=4.8，X2=0显然不是可行解OR35整数规划图解法x2x11234567231BAOR36图解法的启示A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解纯整数规划的可行解就是可行域中的整数点非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化IP问题的最优解不优于LP问题的最优解OR376.2分枝定界法思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解例1.maxZ=2000x1+1000x25x1+4x2≤242x1+5x2≤13x1.x2≥0且为整数解：先不考虑整数要求，解相应的LP问题，得：x1=4.8x2=0Z=9600不是可行解Z=9600是IP问题的上界，记为：Z=9600OR38分枝定界法（续）X1=4.8不符合要求，切掉4—5之间的可行域，可行域变成两块，即原有约束条件再分别附加约束条件x1≤4和x1≥5原问题分解为两个maxZ=2000x1+1000x2maxZ=2000x1+1000x25x1+4x2≤245x1+4x2≤242x1+5x2≤13(IP1)2x1+5x2≤13(IP2)x1≤4x1≥5x1.x2≥0且为整数x1.x2≥0且为整数OR39分枝定界法（续）不考虑整数要求，解相应LP问题。解IP1得：x1=4,x2=1z=9000解IP2得：无可行解此时可以断定IP问题的下界为9000，记为Z=9000٭由于目前的分枝末梢最大值是9000，故IP问题的上界便是9000。由于Z=Z，此时已得IP问题的最优解，即x1=4,x2=1,Z=9000OR310分枝定界法的解题步骤1、不考虑整数约束，解相应LP问题2、检查是否符合整数要求，是，则得最优解，完毕。否则，转下步3、任取一个非整数变量xi=bi，构造两个新的约束条件：xi≤[bi],xi≥[bi]+1,分别加入到上一个LP问题，形成两个新的分枝问题。4、不考虑整数要求，解分枝问题。若整数解的Z值所有分枝末梢的Z值，则得最优解。否则，取Z值最大的非整数解，继续分解，Goto3（例题2讲解）OR3116.30—1规划问题某些特殊问题，只做是非选择，故变量设置简化为0或1，1代表选择，0代表不选择。例4.600万元投资5个项目，求利润最大的方案？项目投资额项目收益约束条件210160中选1项300210之中选1项15060选必先选13080260180OR312求解0—1规划的隐枚举法例4解：0当项目未被选中1当项目被选中maxZ=160x1+210x2+60x3+80x4+180x5210x1+300x2+150x3+130x4+260x5≤600X1+x2+x3=1X3+x4=1x5≤x1Xj=0或1j=1，2,…,5增加过滤条件：160x1+210x2+60x3+80x4+180x5≥240建模：设xj=OR313用隐枚举法解例4：(x1,x2,x3,x4,x5）Z值（1，0，0，1，0）240（1，1，1，1，1）X（1，1，1，1，0）X（1，1，1，0，1）X（1，1，1，0，0）X（1，1，0，1，1）X（1，1，0，1，0）X（1，1，0，0，1）X（1，1，0，0，0）X（1，0，1，1，1）X（1，0，1，1，0）X（1，0，0，1，1）420………..OR3146.4指派问题例8甲乙丙丁四个人，A、B、D四项任务，不同的人做不同的工作效率不同，如何指派不同的人去做不同的工作使效率最高？任务人时间ABCD甲乙丙丁41075276333444663数模：minZ=ΣΣcijxijΣxij=1i=1,…,nΣxij=1j=1,…,nXij=0或1OR315指派问题解法—匈牙利法解：类似运输问题的最小元素法第一步造0——各行各列减其最小元素41075-40631621Cij=2763-2054105313344-300110014663-31330132-1第二步圈0——寻找不同行不同列的0元素，圈之。所在行和列其它0元素划掉第三步打——无的行打，打行上0列打，打列上行打，打行上0列打…OR316指派问题解法—匈牙利法（续）第四步划线——无行、打列划线第五步造0——直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的0元素，Goto20621-1510040Cij=0531-1042031000011012021320232221+1最优解：x13=1,x21=1,x32=1,x44=1Z=15OR317相关问题：非标准型的转化（1）maxZ=ΣΣcijxijminZ’=ΣΣ(-cij)xijminZ’’=ΣΣ(M-cij)xij=ΣΣbijxijM是足够大的常数，新问题的最优解就是原问题的最优解（2）整数规划的计算机求解OR318整数规划习题课P222——6.11ABCBD1121314151OR319第七章动态规划（略）OR320第八章图与网络分析引论哥尼斯堡七桥问题ABDCABCD简捷表示事物之间的本质联系，归纳事物之间的一般规律OR321引论图的用处A、B、C、D、E某公司的五支球队进行循环赛组织机构设置图ABCDE总公司分公司工厂或办事处OR3228.1图的基本概念图是由点和线构成的。点的集合V表示，V={vi}不带箭头的连线叫做边(edge)，边的集合记为E={ej}，一条边可以用两点[vi,vj]表示,ej=[vi,vj].带箭头的连线叫做弧(arc),弧的集合记为A，A={ak},一条弧也是用两点表示，ak=[vi,vj],弧有方向：vi为始点，vj为终点OR323图的基本概念(续)由点和边组成的图叫做无向图，记为G=（V，E）由点和弧组成的图叫做有向图，记为D=（V，A）例1.v1v2v3v4v1v2v3v4v5v6v7e1e2e3e4e5e6e7a1a2a8a4a3a5a6a9a7a10a11无向图：点集、边集有向图：点集、弧集OR324图的基本概念(续)以点u为端点的边的条数，叫做点u的次次为1的点叫做悬挂点；次为0的点叫做孤立点；次为奇数则称奇点；次为偶数则称偶点。点弧交替序列称为链；闭合的链称为圈首尾相接的链称为路；闭合的路称回路任意两点之间都有边相连，称为连通图OR3258.2树无圈的连通图称之为树赋权无向图G=（V，E）的最小基干称为最小支撑树赋权有向图D=（V，A），从始点到终点的权值最小的路称为最短路OR3268.3最短路问题例6某交通网络如下图，求v1到v8的最短路线解：用双标号法v1v2v4v3v5v6v7v86312216104310446v1V2(v3,5)V3(v1,3)V4(v1,1)V5(v2,6)V6(v5,10)V7(v5,9)V8(v5,12)6312216104104364V2(v1,6）OR3278.4最大流问题引例：如下输水网络，南水北调工程，从vs到vt送水，弧旁数字前者为管道容量，后者为现行流量，如何调整输水最多？vsvtv2v1v4v3(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)OR328最大流问题的相关概念网络：给定了弧的容量C（vi,vj）的有向图D=（V，A，C）叫做一个网络。可行流：各点流入量=流出量，且vs的流出量=vt的流入量，这样的流称之为可行流截集：分离始点vs和终点vt的弧的集合，叫做截集截量：截集的容量叫做截量增广链：一条从到的链，前向弧上可增加，后向弧上可减少，则称此链为增广链OR329求最大流的方法方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链。寻找增广链的标号法：先给vs标号（0，+∞）,而后依次审查各条弧（vi,vj）：对前向弧，饱和否？不饱和，给vj点标号（vi，l(vj));对后向弧，可否减少？可，给vj标号（-vi,l(vj)）,直到给vt标上号，就得到了增广链。OR330解水网最大流问题.vsV2(0,+∞)V1(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(5,3)(2,1)V4V3Vt(vs,4)(-v1,1)(-v2,1)(v3,1)(v2,1)OR331此题最大流图沿增广链进行调整，前向弧增加l(vj)，后向弧减少l(vj)vsV2V1V3V4Vt(3,3)(5,2)(4,3)(1,0)(1,0)(2,2)(3,0)(5,3)(2,2)(0,+∞)(vs,3)OR332习题：p312－8.4，求最大流给出任意可行流找到一条增广链调整可行流注：’＝1，#＝1，$＝2，*=1vsv1v2v3v4v5vt（4,3）’（10,4）$*（3,2）#（1,1）（3,2）’（3,2）*（4,2）$（5,3）#*（4,3）’（2,2）（7,6）’（8,3）#$*(0,+∞)(vs,3)OR333第九章网络计划9.1基本概念～是用网络分析的方法编制的计划杜邦公司—关键路线法CPM确定型美国海军武器局—计划评审技术PERT网络图（有向赋权图）的构成结点，也称事项，一道工序的开始或结束工序（弧），相对独立的活动，消耗资源虚工序，只表示衔接关系，不消耗资源工序时间（权），完成工序的时间消耗OR3349.2.网络规则1、避免循环、不留缺口2、一一对应：一道工序用两个事项表示3、从左向右依次展开例：工序ABCDEFGHI紧前工序----ABBC、DC、DE、FG工序时间466759748A,4B,6C,6D,7E,5G,7F,9H,4I,8OR3359.3关键路线法－－CPM9.3.1时间参数运算什么是关键路线？1、作业时间t（i，j），经验数据、统计数据2、事项最早时间TE(j)＝max{TE(i)+t（i，j）}到齐上课，最后到者决定最早开课时间3、事项最迟时间TL(i)＝min{TL(j)-t（i，j）}保证12点吃饭，路最远者决定最迟下课时间4、工序最早可能开工时间TES(i,j)＝TE(i)=max{TES(h,i)+t（h,i）}5、工序最早可能完工时间TEF(i,j)＝TES(i,j)+t（i，j）hijOR336.6、工序最迟必须开工时间TLS（i,j)＝TL(j)－t（i,j)＝min{TLs(j,k)-t（i，j）}7、工序最迟必须完工时间TLF（i,j)＝TL(j)＝TLS（i,j)+t（i,j)8、工序总时差：在不影响其紧后工序最迟必须开工时间的前提下，本工序可以推迟的时间R（i,j）＝TLS(i,j)－TES(i,j)＝TLF(i,j)－TEF(i,j)＝min{TLS(j,k)}–TEF（i,j）9、工序单时差：在不影响其紧后工序最早可能开工时间的前提下，本工序可以推迟的时间r（i,j）＝min{TES(j,k)}–TEF（i,j