《整数规划的含义》由会员分享，可在线阅读，更多相关《整数规划的含义（58页珍藏版）》请在金锄头文库上搜索。
1、OR3,1,OPERATIONS RESEARCH 运筹学,如何把事情做得最好,OR3,2,第六章 整数规划,本章要求 理解整数规划的含义 掌握分枝定界法的思想和方法 掌握0-1变量的含义和用法 掌握指派问题的算法 微机求解,OR3,3,6.1 整数规划问题的提出,决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数如何解决？四舍五入不行，枚举法太慢 问题分类：纯整数规划、混合整数规划、0-1整数规划 专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法,OR3,4,问题举例,某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润20
2、00元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？ maxZ=2000x1+1000x2 5x1+4x224 2x1+5x2 13 x1.x2 0且为整数 解此LP问题，得：X1=4.8，X2=0 显然不是可行解,OR3,5,整数规划图解法,x2,x1,1 2 3 4 5 6 7,2,3,1,B,A,OR3,6,图解法的启示,A（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解 纯整数规划的可行解就是可行域中的整数点 非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化 IP问题的最优解不优于LP
3、问题的最优解,OR3,7,6.2 分枝定界法,思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解 例1. maxZ=2000x1+1000x2 5x1+4x224 2x1+5x2 13 x1.x2 0且为整数 解：先不考虑整数要求，解相应的LP问题，得：x1=4.8 x2=0 Z=9600 不是可行解 Z=9600是IP问题的上界，记为：Z=9600,OR3,8,分枝定界法（续）,X1=4.8不符合要求，切掉45之间的可行域，可行域变成两块，即原有约束条件再分别附加约束条件x1 4和x1 5 原问题分解为两个 maxZ=2000x1+1000x2 maxZ=2000x1+10
4、00x2 5x1+4x224 5x1+4x224 2x1+5x2 13 ( IP1 ) 2x1+5x2 13 (IP2) x1 4 x1 5 x1.x2 0且为整数 x1.x2 0且为整数,OR3,9,分枝定界法（续）,不考虑整数要求，解相应LP问题。 解IP1得：x1=4 ,x2=1 z=9000 解IP2得：无可行解 此时可以断定IP问题的下界为9000，记为Z=9000 由于目前的分枝末梢最大值是9000，故IP问题的上界便是9000。由于Z=Z，此时已得IP问题的最优解，即x1=4,x2=1,Z=9000,OR3,10,分枝定界法的解题步骤,1、不考虑整数约束，解相应LP问题 2、检查
5、是否符合整数要求，是，则得最优解，完毕。否则，转下步 3、任取一个非整数变量xi=bi，构造两个新的约束条件：xi bi ,xi bi+1,分别加入到上一个LP问题，形成两个新的分枝问题。 4、不考虑整数要求，解分枝问题。若整数解的Z值所有分枝末梢的Z值，则得最优解。否则， 取Z值最大的非整数解，继续分解，Go to 3 （例题2讲解）,OR3,11,6.3 01规划问题,某些特殊问题，只做是非选择，故变量设置简化为0或1，1代表选择，0代表不选择。 例4. 600万元投资5个项目，求利润最大的方案？,OR3,12,求解01规划的隐枚举法,例4解： 0 当项目未被选中 1 当项目被选中 max
6、 Z=160x1+210x2+60x3+80x4+180x5 210x1+300x2+150x3+130x4+260x5 600 X1+x2+x3=1 X3+x4=1 x5 x1 Xj=0或1 j=1，2,5 增加过滤条件：160x1+210x2+60x3+80x4+180x5 240 ,建模：设xj=,OR3,13,用隐枚举法解例4：,(x1,x2,x3,x4,x5）,OR3,14,6.4 指派问题,例8 甲乙丙丁四个人，A、B、D四项任务，不同的人做不同的工作效率不同，如何指派不同的人去做不同的工作使效率最高？,数模： minZ=cijxij xij=1 i=1,n xij=1 j=1,n
7、 Xij=0或1,OR3,15,指派问题解法匈牙利法,解：类似运输问题的最小元素法 第一步 造0各行各列减其最小元素 4 10 7 5 -4 0 6 3 1 6 2 1 Cij= 2 7 6 3 -2 0 5 4 1 0 5 3 1 3 3 4 4 -3 0 0 1 1 0 0 1 4 6 6 3 -3 1 3 3 0 1 3 2 -1 第二步 圈0寻找不同行不同列的0元素，圈之。 所在行和列其它0元素划掉 第三步 打无的行打，打行上0列打 ，打列上行打，打行上0列打 ,OR3,16,指派问题解法匈牙利法（续）,第四步 划线无行、打列划线 第五步 造0直线未覆盖的元素，减去其最小值，交叉点上加
8、最小元素，产生新的0元素，Go to 2 0 6 2 1 -1 5 1 0 0 4 0 Cij= 0 5 3 1 -1 0 4 2 0 3 1 0 0 0 0 1 1 0 1 2 0 2 1 3 2 0 2 3 2 2 2 1 +1 最优解：x13=1,x21=1,x32=1,x44=1 Z=15,OR3,17,相关问题：,非标准型的转化 （1）maxZ= cijxij minZ= (-cij)xij minZ= (M-cij)xij = bijxij M是足够大的常数， 新问题的最优解就是原问题的最优解 （2）整数规划的计算机求解,OR3,18,整数规划习题课,P2226.11,OR3,19
9、,第七章 动态规划（略）,OR3,20,第八章 图与网络分析,引论 哥尼斯堡七桥问题,A,B,D,C,A,B,C,D,简捷表示事物之间的本质联系，归纳事物之间的一般规律,OR3,21,引论 图的用处,A、B、C、D、E 某公司的 五支球队进行循环赛 组织机构设置图,A,B,C,D,E,总公司,分公司,工厂或办事处,OR3,22,8.1 图的基本概念,图是由点和线构成的。 点的集合V表示，V=vi 不带箭头的连线叫做边(edge)，边的集合记为E= ej ，一条边可以用两点 vi,vj 表示,ej= vi,vj . 带箭头的连线叫做弧(arc),弧的集合记为A，A= ak ,一条弧也是用两点表示
10、，ak= vi,vj ,弧有方向：vi为始点，vj为终点,OR3,23,图的基本概念(续),由点和边组成的图叫做无向图，记为G=（V，E） 由点和弧组成的图叫做有向图，记为D=（V，A） 例1.,v1,v2,v3,v4,v1,v2,v3,v4,v5,v6,v7,e1,e2,e3,e4,e5,e6,e7,a1,a2,a8,a4,a3,a5,a6,a9,a7,a10,a11,无向图：点集、边集,有向图：点集、弧集,OR3,24,图的基本概念(续),以点u为端点的边的条数，叫做点u的次 次为1的点叫做悬挂点；次为0的点叫做孤立点；次为奇数则称奇点；次为偶数则称偶点。 点弧交替序列称为链；闭合的链称为
11、圈 首尾相接的链称为路；闭合的路称回路 任意两点之间都有边相连，称为连通图,OR3,25,8.2 树,无圈的连通图称之为树 赋权无向图G=（V，E）的最小基干称为最小支撑树 赋权有向图D=（V，A），从始点到终点的权值最小的路称为最短路,OR3,26,8.3 最短路问题,例6 某交通网络如下图，求v1到v8的最短路线 解：用双标号法,v1,v2,v4,v3,v5,v6,v7,v8,6,3,1,2,2,1,6,10,4,3,10,4,4,6,v1,V2(v3,5),V3(v1,3),V4(v1,1),V5(v2,6),V6(v5,10),V7(v5,9),V8(v5,12),6,3,1,2,2,
12、1,6,10,4,10,4,3,6,4,V2(v1,6）,OR3,27,8.4 最大流问题,引例：如下输水网络，南水北调工程，从vs到vt送水，弧旁数字前者为管道容量，后者为现行流量，如何调整输水最多？,vs,vt,v2,v1,v4,v3,(3,3),(5,1),(1,1),(4,3),(1,1),(2,2),(3,0),(2,1),(5,3),OR3,28,最大流问题的相关概念,网络：给定了弧的容量C（vi,vj）的有向图D=（V，A，C）叫做一个网络。 可行流：各点流入量=流出量，且vs的流出量=vt的流入量，这样的流称之为可行流 截集：分离始点vs和终点vt的弧的集合，叫做截集 截量：截
13、集的容量叫做截量 增广链：一条从到的链，前向弧上可增加，后向弧上可减少，则称此链为增广链,OR3,29,求最大流的方法,方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链。 寻找增广链的标号法：先给vs标号（0，+）,而后依次审查各条弧（vi,vj）：对前向弧，饱和否？不饱和，给vj点标号（vi，l(vj);对后向弧，可否减少？可，给vj标号（-vi, l(vj) ）,直到给vt标上号，就得到了增广链。,OR3,30,解水网最大流问题,.,vs,V2,(0, +),V1,(3,3),(5,1),(1,1),(4,3),(1,1),(2,2),(3,0),(
14、5,3),(2,1),V4,V3,Vt,(vs,4),(-v1,1),(-v2,1),(v3,1),(v2,1),OR3,31,此题最大流图,沿增广链进行调整，前向弧增加l(vj)，后向弧减少l(vj),vs,V2,V1,V3,V4,Vt,(3,3),(5,2),(4,3),(1,0),(1,0),(2,2),(3,0),(5,3),(2,2),(0,+),(vs,3),OR3,32,习题：p3128.4，求最大流,给出任意可行流 找到一条增广链 调整可行流 注：1，#1，$2，*=1,vs,v1,v2,v3,v4,v5,vt,（4,3）,（10,4）$*,（3,2）#,（1,1）,（3,2）,（3,2）*,（4,2）$,（5,3）#
