整数规划的含义

1、OPERATIONS RESEARCH运筹学如何把事情做得最好OR3 1第六章 整数规划本章要求本章要求理解整数规划的含义掌握分枝定界法的思想和方法掌握0-1变量的含义和用法掌握指派问题的算法微机求解OR3 26.1 整数规划问题的提出决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数如何解决？四舍五入不行，枚举法太慢问题分类：纯整数规划、混合整数规划、0-1整数规划专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法OR3 3问题举例某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件

2、利润1000元，如何装运获利最多？maxZ=2000 x1+1000 x2 5x1+4x224 2x1+5x2 13 x1.x2 0且为整数解此LP问题，得：X1=4.8，X2=0显然不是可行解OR3 4整数规划图解法x2x1 1 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=2000 x1+1000 x2 5x1+4x224 2x1+5x2 13 x1.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=2000 x1+1000 x2 maxZ=2000 x1+1000 x2 5x1+4x224 5x1+4x224 2x1+5x2 13 (

4、IP1 ) 2x1+5x2 13 (IP2) x1 4 x1 5 x1.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选必先R3 11求解01规划的隐枚举法例4解： 0 当项目未被选中 1 当项目被选

6、中 max Z=160 x1+210 x2+60 x3+80 x4+180 x5 210 x1+300 x2+150 x3+130 x4+260 x5 600 X1+x2+x3=1 X3+x4=1 x5 x1 Xj=0或1 j=1，2,5增加过滤条件：160 x1+210 x2+60 x3+80 x4+180 x5 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，

7、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 .OR3 136.4 指派问题例8 甲乙丙丁四个人，A、B、D四项任务，不同的人做不同的工作效率不同，如何指派不同的人去做不同的工作使效率最高？ 任务人 时间 A B C D 甲 乙 丙 丁 4 10 7 5 2 7 6 3 3 3 4 4 4 6 6 3数数模模：minZ=cijxij xij=1 i=1,n xij=1 j=1,n Xij=0或1OR3 14指派问题解法匈牙利法解：类似运输问题的最小元素法第一步 造造0各行各列减其最小元素 4 10 7 5 -4

8、 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 15指派问题解法匈牙利法（续）第四步 划线划线无行、打列划线第五步 造造0直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的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

9、 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=15OR3 16相关问题：非标准型的转化（1）maxZ= cijxij minZ= (-cij)xij minZ= (M-cij)xij = bijxij M是足够大的常数， 新问题的最优解就是原问题的最优解（2）整数规划的计算机求解OR3 17整数规划习题课P2226.11ABCBD1121314151OR3 18第七章 动态规划（略）OR3 19第八章 图与网络分析引论 哥尼斯堡七桥问题ABD CABCD简捷表示事物之间的本质联系，归纳

10、事物之间的一般规律OR3 20引论 图的用处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.v

11、1v2v3v4v1v2v3v4v5v6v7e1e2e3e4e5e6e7a1a2a8a4a3a5a6a9a7a10a11无向图：点集、边集有向图：点集、弧集OR3 23图的基本概念(续)以点u为端点的边的条数，叫做点u的次 次为1的点叫做悬挂点；次为0的点叫做孤立点；次为奇数则称奇点；次为偶数则称偶点。点弧交替序列称为链；闭合的链称为圈首尾相接的链称为路；闭合的路称回路任意两点之间都有边相连，称为连通图OR3 248.2 树无圈的连通图称之为树赋权无向图G=（V，E）的最小基干称为最小支撑树赋权有向图D=（V，A），从始点到终点的权值最小的路称为最短路OR3 258.3 最短路问题例6 某交通网

12、络如下图，求v1到v8的最短路线解：用双标号法v1v2v4v3v5v6v7v86312216104310446v1V2(v3,5)V3(v1,3)V4(v1,1)V5(v2,6)V6(v5,10)V7(v5,9)V8(v5,12)6312216104 104364V2(v1,6）OR3 268.4 最大流问题引例：如下输水网络，南水北调工程，从vs到vt送水，弧旁数字前者为管道容量，后者为现行流量，如何调整输水最多？vsvtv2v1v4v3(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)OR3 27最大流问题的相关概念网络：给定了弧的容量C（vi,vj

13、）的有向图D=（V，A，C）叫做一个网络。可行流：各点流入量=流出量，且vs的流出量=vt的流入量，这样的流称之为可行流截集：分离始点vs和终点vt的弧的集合，叫做截集截量：截集的容量叫做截量增广链：一条从到的链，前向弧上可增加，后向弧上可减少，则称此链为增广链OR3 28求最大流的方法方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链。寻找增广链的标号法：先给vs标号（0，+）,而后依次审查各条弧（vi,vj）：对前向弧，饱和否？不饱和，给vj点标号（vi，l(vj);对后向弧，可否减少？可，给vj标号（-vi, l(vj) ）,直到给vt标上号，就得到

14、了增广链。OR3 29解水网最大流问题.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)OR3 30此题最大流图沿增广链进行调整，前向弧增加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)OR3 31习题：p3128.4，求最大流给出任意可行流找到一条增广链调整可行流 注：1，#1，$2，*=1vsv1v2v3v4v5vt（4,3）（1

15、0,4）$*（3,2）#（1,1）（3,2）（3,2）*（4,2）$（5,3）#*（4,3）（2,2）（7,6）（8,3）#$*(0,+)(vs,3)OR3 32第九章 网络计划9.1基本概念是用网络分析的方法编制的计划杜邦公司关键路线法CPM 确定型美国海军武器局计划评审技术PERT网络图（有向赋权图）的构成结点，也称事项，一道工序的开始或结束工序（弧），相对独立的活动，消耗资源虚工序，只表示衔接关系，不消耗资源工序时间（权），完成工序的时间消耗OR3 33 9.2.网络规则1、避免循环、不留缺口2、一一对应：一道工序用两个事项表示3 、从左向右依次展开例：工 序ABCDEFGHI紧前工序-

16、ABBC、D C、D E、F G工序时间466759748A,4B,6C,6D,7E,5G,7F,9H,4I,8OR3 349.3 关键路线法 CPM9.3.1时间参数运算 什么是关键路线？1、作业时间t（i，j），经验数据、统计数据2、事项最早时间TE(j)maxTE(i)+ t（i，j） 到齐上课，最后到者决定最早开课时间3、事项最迟时间TL(i)minTL(j)- t（i，j） 保证12点吃饭，路最远者决定最迟下课时间4、工序最早可能开工时间 TES(i,j) TE(i) = maxTES(h,i)+ t（h,i ）5、工序最早可能完工时间 TEF(i,j)TES(i,j)+ t（i，j

17、）hijOR3 35.6、工序最迟必须开工时间 TLS（i,j) TL(j) t（i,j) minTLs(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) minTLS(j,k) TEF（i,j）9、工序单时差：在不影响其紧后工序最早可能开工时间的前提下，本工序可以推迟的时间 r （i,j） minTES(j,k) TEF（i,j） KkkOR3 369.3.2时间参

18、数图解.解上例：计算事项 时间参数 TESTLSTEFTLFTESTLSTEFTLSr(i,j)R（i,j）A4B6C6G7D7E5F9H4I 80047613222028282024136关键路线：由总时差为零的工序构成 B D G It（i,j)t（j,k)OR3 37. 解上例 计算工序时间参数 工序ijt(i,j) ESEFLSLFRrA4043730B6060600C641071333D761361300E561119241311F91322152420G71320132000H42226242822I82028202800OR3 389.4计划评审技术PERTPERT的产生 关键路

19、线法中，工序时间是确定值，而对研究性的工序来说， t（i，j）是随机的。1958年美国海军武器局研制北极星导弹时提出，重点在于计划的评审。PERT的时间估计 采用三种时间估计法a最乐观时间，b最悲观时间，m最可能时间，则 工序期望时间 te 方差 e2（ ）2a+4m+b 6ba6OR3 39PERT的计算方法网络图的绘制与关键路线法相同参数计算与关键路线法体系不同 工程期望工期 TE tek 期望工期方差 2 ek2 计划工期 TK业主要求的工期 预期完工概率： 查正态分布表 一定概率的完工期 TK TE + TK TEOR3 40PERT应用举例P346例6 关键工序：C D F/G I

20、J期望工期： TE10.50+10.17+20.33+5.17+12.8359 121.36+0.25+4.00+0.25+14.6920.55 22 1.36+0.25+1.00+0.25+14.6917.55完工概率：1（60-59）20.550.22 查表得 P（ 1）58.7 2（60-59）17.550.244 查表得 P（ 2）59.5若要有90的把握，计划工期应定多长 TK TE + 59+4.531.2964.84OR3 419.5 网络优化CPM与PERT主要目标是控制工期网络优化在上述基础上，寻求时间更短、资源更省、成本更低的方案9.5.1时间资源优化 （资源的均衡配置）原

21、则：关键优先、利用时差 P331例题4方法：绘制资源负荷图，排定关键工序，游移非关键工序60 80 110 135d20天g30天k25天58人H15天 39人42人26人F18天 22人OR3 429.5.2 时间费用优化时间和费用双目标优化，一般来讲二者是矛盾的。通过仔细分析，寻找既省时又省钱的方案，即最低成本日程。费用：直接费用和间接费用直接费用：建造工程本身所需材料、人工间接费用：工程所需管理费用、设备租金ct间接费用总费用直接费用赶工：直接费用增加，间接费用减少。间接费用是常量直接费用简化为常量处理。则：赶工直接费用率费用差时间差OR3 43例题5 P337资料：P325图9-8，关

22、键工序A、D、G、K、L P337表9-7提供赶工费用资料。赶工选择关键工序才有意义；赶工费用率不高于间接费用率才有价值；赶工时间既取决于极限工期，又取决于次长路线。A 60B 45C 10D 20E 40G 30K 25F 18H 15L 35首选K赶工10天再选G赶工10天已赶工20天，此时出现两条关键路线OR3 44第十章 决策论10.1决策的分类按层次分：战略决策，战术决策按频率分：程序性决策，非程序性决策按状态信息分：确定型决策，不确定型决策，风险型决策决策的三要素：方案、状态、损益矩阵决策的程序OR3 4510.2不确定型决策悲观准则乐观准则折衷准则等可能准则后悔值准则OR3 46

23、10.3风险型决策10.3.1决策准则例1：1、最大可能准则 取A 3方案，收益30 2、期望值准则 取A 1方案，收益34 EMV（Expected Maximum Value）P(j)aij10.220.530.240.1E（Ai）A1A2A3-20-1015202030403830605030343228.5jOR3 47.3、期望值与标准差准则（Ai)P（ j ）aij- E（Ai）2（A1）22，（A2）17，（A3）4.5设常数K代表风险厌恶因子，则期望值与标准差的综合值为：ED(Ai)E(Ai)K（Ai)设K=1，则 ED(A1)342212 ED(A2)321715 ED(A3

24、)28.54.524OR3 48.4、生存风险度决策法生存风险度最大损失/致命损失例2：某企业有200万元资产，火灾概率0.0001，保险费每年500元。按照期望值法决策： 20000000.0001200500按照生存风险度法决策：投保：风险度50020/200万元0.5不投保：风险度200万元/200万元100OR3 4910.3.2 决策树法把决策问题结构化例3.某研究所可投标一项70万元的新产品开发项目。若投标，预研费用2万元，中标概率60，若中标用老工艺花费28万元，成功概率80，用新工艺花费18万元，成功概率50，研制失败赔偿15万元，投标还是不投标？中标后用什么工艺？OR3 50

25、.解：计算：状态节点 700.8+（-15）0.253状态节点 700.5+（-15）0.527.5决策节点 max53-28，27.5-1825状态节点250.6+00.415状态节点010决策节点 max15，015 投标，中标用老工艺123456不投标投标中标不中老工艺新工艺成功失败成功失败70-157050.80.20.50.50.60.425-28-1815-213肯定不中标 1OR3 5110.3.3 贝叶斯决策1、完全信息价值 EVPI Expected Value in perfect Information是指决策人为获取完全准确的信息，所能支付的信息费的上限。10.120.230.540.2E（Ai）A1A2A3-20-1015202030403830605030343228.5EVPI P(j)maxaijEMV0.115+0.230+0.540+0.