《运筹学——怎样把事情做到最好（三）》由会员分享，可在线阅读，更多相关《运筹学——怎样把事情做到最好（三）（58页珍藏版）》请在金锄头文库上搜索。
1、OPERATIONS RESEARCH 运筹学如何把事情做得最好OR3 1第六章 整数规划本章要求理解整数规划的含义掌握分枝定界法的思想和方法掌握0-1变量的含义和用法掌握指派问题的算法微机求解OR3 26.1 整数规划问题的提出决策问题中经常有整数要求，如人数、 件数、机器台数、货物箱数如何解决 ？四舍五入不行，枚举法太慢问题分类：纯整数规划、混合整数规划 、0-1整数规划专门方法：分枝定界法、割平面法、隐 枚举法、匈牙利法OR3 3问题举例某集装箱运输公司，箱型标准体积24m3，重量 13T,现有两种货物可以装运，甲货物体积5m3、 重量2T、每件利润2000元；乙货物体积4m3、重 量5
2、T、每件利润1000元，如何装运获利最多？maxZ=2000x1+1000x25x1+4x2242x1+5x2 13x1.x2 0且为整数解此LP问题，得：X1=4.8，X2=0显然不是可行解OR3 4整数规划图解法x2x11 2 3 4 5 6 7 231BAOR3 5图解法的启示A（4.8，0）点是LP问题的可行解，不 是IP问题的可行解，B（4，1）才是IP的最 优解纯整数规划的可行解就是可行域中的整 数点非整数点不是可行解，对于求解没有意 义，故切割掉可行域中的非可行解，不妨 碍整数规划问题的优化IP问题的最优解不优于LP问题的最优解OR3 66.2 分枝定界法思路：切割可行域，去掉非
3、整数点。一次分枝 变成两个可行域，分别求最优解例1. maxZ=2000x1+1000x25x1+4x224 2x1+5x2 13x1.x2 0且为整数 解：先不考虑整数要求，解相应的LP问题，得： x1=4.8 x2=0 Z=9600 不是可行解Z=9600是IP问题的上界，记为：Z=9600OR3 7分枝定界法（续）X1=4.8不符合要求，切掉45之间的可行域， 可行域变成两块，即原有约束条件再分别附加约 束条件x1 4和x1 5原问题分解为两个maxZ=2000x1+1000x2 maxZ=2000x1+1000x25x1+4x224 5x1+4x2242x1+5x2 13 ( IP1
4、) 2x1+5x2 13 (IP2)x1 4 x1 5x1.x2 0且为整数 x1.x2 0且为整数OR3 8分枝定界法（续）不考虑整数要求，解相应LP问题。解IP1得：x1=4 ,x2=1 z=9000解IP2得：无可行解此时可以断定IP问题的下界为9000，记 为Z=9000 由于目前的分枝末梢最大值是9000，故 IP问题的上界便是9000。由于Z=Z，此时 已得IP问题的最优解，即 x1=4,x2=1,Z=9000OR3 9分枝定界法的解题步骤1、不考虑整数约束，解相应LP问题2、检查是否符合整数要求，是，则得最 优解，完毕。否则，转下步3、任取一个非整数变量xi=bi，构造两个 新的
5、约束条件：xi bi ,xi bi+1,分别加 入到上一个LP问题，形成两个新的分枝问 题。4、不考虑整数要求，解分枝问题。若整 数解的Z值所有分枝末梢的Z值，则得最 优解。否则， 取Z值最大的非整数解，继 续分解，Go to 3 （例题2讲解）OR3 106.3 01规划问题某些特殊问题，只做是非选择，故变量设置简 化为0或1，1代表选择，0代表不选择。例4. 600万元投资5个项目，求利润最大的方案 ？项 目投资 额项目收益约束条件210160 中选1项 300210 之中选1项 15060选必先选 13080 260180OR3 11求解01规划的隐枚举法例4解： 0 当项目未被选中1
6、当项目被选中 max Z=160x1+210x2+60x3+80x4+180x5210x1+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 12用隐枚举法解例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
7、，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） 420OR3 136.4 指派问题例8 甲乙丙丁四个人，A、B、D四项任 务，不同的人做不同的工作效率不同，如 何指派不同的人去做不同的工作使效率最 高？任务 人 时间A B C D甲乙丙丁4 10 7 52 7 6 33 3 4 44 6 6 3数模：minZ=cijxij xij=1 i=1,nxij=1 j=1,nXij=0或1OR3 14指派问题解法匈牙利法解：类似运输问题的最小元素法第一步 造0各行各列减其最小元素4 10 7 5 -4 0 6 3 1 6 2 1 Ci
8、j= 2 7 6 3 -2 0 5 4 1 0 5 3 1 3 3 4 4 -3 0 0 1 1 0 0 14 6 6 3 -3 1 3 3 0 1 3 2 -1 第二步 圈0寻找不同行不同列的0元素， 圈之。 所在行和列其它0元素划掉 第三步 打无的行打，打行上0列打 ，打列上行打，打行上0列打 OR3 15指派问题解法匈牙利法（续 ）第四步 划线无行、打列划线第五步 造0直线未覆盖的元素，减 去其最小值，交叉点上加最小元素，产生 新的0元素，Go to 20 6 2 1 -1 5 1 0 0 4 0Cij= 0 5 3 1 -1 0 4 2 0 3 1 00 0 0 1 1 0 1 2 0
9、 21 3 2 0 2 3 2 2 2 1 +1 最优解：x13=1,x21=1,x32=1,x44=1 Z=15OR3 16相关问题：非标准型的转化（1）maxZ= cijxij minZ= (-cij)xij minZ= (M-cij)xij = bijxij M是足够大的常数， 新问题的最优解 就是原问题的最优解 （2）整数规划的计算机求解OR3 17整数规划习题课P2226.11 ABCBD 1121314151OR3 18第七章 动态规划（略）OR3 19第八章 图与网络分析引论 哥尼斯堡七桥问题ABDCABCD简捷表示事物之间的 本质联系，归纳事物 之间的一般规律OR3 20引论
10、图的用处A、B、C、D、E 某公司的 五支球队进行循环赛 组织机构设置图ABCDE总公司分公司工厂或 办事处OR3 218.1 图的基本概念图是由点和线构成的。点的集合V表示，V=vi不带箭头的连线叫做边(edge)，边的集 合记为E= ej ，一条边可以用两点 vi,vj 表示,ej= vi,vj .带箭头的连线叫做弧(arc),弧的集合记为 A，A= ak ,一条弧也是用两点表示，ak= vi,vj ,弧有方向：vi为始点，vj为终点OR3 22图的基本概念(续)由点和边组成的图叫做无向图，记为G=（V，E）由点和弧组成的图叫做有向图，记为D=（V，A）例1.v1v2v3v4v1v2v3v4v5v6v7e1 e2e3e4e5e6e7a1a2a8a4a3a5a6a9a7a10 a11无向图：点集、边集有向图：点集、弧集OR3 23图的基本概念(续)以点u为端点的边的条数，叫做点u的次次为1的点叫做悬挂点；次为0的点叫做 孤立点；次为奇数则称奇点；次为偶数则 称偶点。点弧交替序列称为链；闭合的链称为圈首尾相接的链称为路；闭合的路称回路任意两点之间都有边相连，称为连通图OR3 248.2 树无圈的连通图称之为树赋权无向图G=（V，E）的最小基干称为 最小支撑树赋权有向图D=（V，A），从始点到终点 的权值最小的路称为最短路OR3
