运筹学第五章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,主讲教师：,联系电话：,短 号：,E-mail:,清华大学出版社,运筹学教程（第三版）,运筹学基础,胡运权 主编,教材,运 筹 帷 幄 之 中,决 胜 千 里 之 外,运 筹 学 课 件,整 数 规 划,第 五 章,Dynamic Programming,第一节 整数规划数学模型及解的特点,一、线性规划的数学模型的表示,max（min）z=,x,j,0(j=1,2,n),st,.,c,j,x,j,a,ij,x,j,(,或=,),b,i,(i=1,2,m),线性规划问题的,特征,：,（1）目标函数是决策变量的线性函数,（2）约束条件是含决策变量的线性等式或不等式,第一节 整数规划数学模型及解的特点,二、整数规划的数学模型的表示,max（min）z=,x,j,0,，,x,j,部分或全部取整数,(j=1,，,2,n),st,.,c,j,x,j,a,ij,x,j,(,或=,),b,i,(i=1,2,m),整数规划的矩阵表示：,整数规划的,松弛问题,：,整数规划与,其松弛问题最优解和最优值的关系,整数规划的,可行解一定是其松弛问题的可行解。,整数规划的,最优值不优于其松弛问题的最优值。,三、整数规划数学模型举例,解,设：,x,i,为服务员在,i,时段开始上班人数,min z=x,1,+x,2,+x,3,+x,4,+x,5,+,x,6,+x,7,+x,8,约束条件,x,1,10,st,.,例1,时段（2,h）,1,2,3,4,5,6,7,8,服务员最少数目,10,8,9,11,13,8,5,3,要求：服务员要连续工作4个时段 目标：人数最少,目标,x,1,+x,2,8,x,1,+x,2,+x,3,9,x,1,+x,2,+x,3,+x,4,11,x,2,+x,3,+x,4,+x,5,13,x,4,+x,5,5,x,3,+x,4,+x,5,8,x,5,3,且,x,j,为整数,x,j,0,(,j=1,2,3,4,5),例,2,、例,3,见书,P124,，,125,例1,时段（2,h）,1,2,3,4,5,6,7,8,服务员最少数目,10,8,9,11,13,8,5,3,要求：服务员要连续工作4个时段 目标：人数最少,四、整数线性规划的数学模型及解的特点,max（min）z=,x,j,0,且,取整数,(,j=1,2,n),st,.,c,j,x,j,a,ij,x,j,(,或=,),b,i,(i=1,2,m),整数线性规划问题与一般线性规划最大区别是：,(1)整数规划中决策变量必须为整数,(2)设两组可行解,X,1,、X,2,，(aX,1,+bX,2,),不一定是整数规划的解,（其中，,a，b0,且,a+b=1）,(3),一般线性问题的可行域为一个凸集，而整数规划的可行域,是一些离散点。,取整数,全部决策变量都取,整数时称,全（纯）整数规划,部分决策变量取,整数时称,混合整数规划,决策变量只能取,0,或,1,时称,0-1,型整数规划,五、整数线性规划的求解方法,max z=x,1,+4x,2,例2,-2,x,1,+3x,2,3,x,1,+2x,2,8,x,1,x,2,0,且取整数,St.,x,1,=18/7 x,2,=19/7 Z=94/7,x,1,=3 x,2,=3 Z=15,x,1,=2 x,2,=3 Z=14,x,1,=2 x,2,=2 Z=10,x,1,=3 x,2,=2 Z=11,X,1,*,=4 x,2,*,=2 Z*=12,一种最简单的方法：,枚举法,这种思路为：找出所有整数可行解，并分别算出其目标,值,，通过比较求得问题,的,最优解,第二节 整数规划的割平面法,红色区域与原区域区别：,1.是原区域的一部分,2.与原问题有相同的可行解,这种方法的思路：,把原区域割去不含原问题可行解的那部分区域，从而可以求得原问题的最优解。,我们称这种思路为,割平面法,第一步：先不考虑整数约束，利用单纯形法进行求解,割平面法,如何割？,1958年，高莫瑞提出一种每次增加一个约束割平面,约束，来割除一些多余的可行域。,C,j,1 4 0 0,C,B,基,b,x,1,x,2,x,3,x,4,0,0,x,3,x,4,3,8,-2 3 1 0,1 2 0 1,1 4 0 0,.,4,1,x,2,x,1,19/7,18/7,0 1 1/7 2/7,1 0 -2/7 3/7,0 0 -2/7 -11/7,第二节 整数规划的割平面法,第二步：考虑非整数解中小数最大的约束，分解成分数约束与整数约束,（实践证明这样求解，速度最快）,x,1,=,18/7,x,2,=,19/7,如,都是非整数解，而,18%7=4,19%7=5,故考虑第一个约束,x,2,+x,3,/7 +2 x,4,/7=19/7 （1）,x,3,/7 +2 x,4,/7=5/7+（2-x,2,）（2）,因为,x,3,、x,4,0,故,x,3,/7 +2 x,4,/7,0,而2-,x,2,必定大于等于0的整数 故,x,3,/7 +2 x,4,/7,5/7 （3）,即,x,3,+2 x,4,5 （3）,综合（3）及原问题的约束，等于增加一个约束,x,2,2,新增加的约束,要求分数约束部分的系数为正,第二节 整数规划的割平面法,第三步：把约束（3）作为新约束加入单纯形法继续求解,如果还不能求出整数最优解，重复,直至求出整数最优解为止。,C,j,1 4 0 0 0,C,B,基,b,x,1,x,2,x,3,x,4,x,5,4,1,0,x,2,x,1,x,5,19/7,18/7,-5,0 1 1/7 2/7 0,1 0 -2/7 3/7 0,0 0 -1 -2 1,0 0 -2/7 -11/7 0,4,1,0,x2,x1,x3,2,4,5,0 1 0 0 1/7,1 0 0 1 -2/7,0 0 1 2 -1,0 0 0 -1 -2/7,第二节 整数规划的割平面法,割平面法,求解,的演示,最优解,第二节 整数规划的割平面法,第三节 整数规划的分支定界法,x,1,=18/7 x,2,=19/7 Z=94/7,把原,问题非整数约束区域一分为二。我们可以发现原问题可行解没有少,-2,x,1,+3x,2,3,x,1,+2x,2,8,x,1,2,x,1,x,2,0,且取整数,-2,x,1,+3x,2,3,x,1,+2x,2,8,x,1,3,x,1,x,2,0,且取整数,-2,x,1,+3x,2,3,x,1,+2x,2,8,x,1,x,2,0,且取整数,原问题约束,我们把这种方法的思路称为,分支定界法,1）把原区域分成两个分支，这样的分割没有减少可行解，我们可以分别求出各个分支的最优解，看是否为整数解，如果存在分支没有得到整数最优解，按照上述方式继续，直到求出整体最优解为止。,2）如果出现某个分支的最优解小于其它存在整数可行解，则该分支没有必要继续求解，这就是定界。,分支定界法,把,可行域,一分为,二,第一步：先不考虑整数约束，利用单纯形法进行求解,C,j,1 4 0 0,C,B,基,b,x,1,x,2,x,3,x,4,0,0,x,3,x,4,3,8,-2 3 1 0,1 2 0 1,1 4 0 0,.,4,1,x,2,x,1,19/7,18/7,0 1 1/7 2/7,1 0 -2/7 3/7,0 0 -2/7 -11/7,第三节 整数规划的分支定界法,分支定界法,把,可行域,一分为,二,第二步：任选不满足整数约束的变量进行分支，把问题分解成两个问题（两个分支）,x,2,=19/7，,其整数部分为2,如,把它分解成两个约束,x,2,2,和,x,2,3,故原问题分解成两部分,max z=x,1,+4x,2,-2,x,1,+3x,2,3,x,1,+2x,2,8,x,1,x,2,0,且取整数,St.,x,2,2,max z=x,1,+4x,2,-2,x,1,+3x,2,3,x,1,+2x,2,8,x,1,x,2,0,且取整数,St.,x,2,3,和,（分支一）,（分支二）,x,1,=18/7 x,2,=19/7 Z=94/7,分支二 没有可行域，分支一可以求得最优解为：,x,1,*,=4 x,2,*,=2 z*=12，,已经满足整数要求，故为问题得最优解,第三节 整数规划的分支定界法,第三步：把问题的两个分支求出解后，分析各分支的解，解的情况无外乎：,1）某个分支无解，则以后不用管理该分支；显然，如果各分支都没有可行解，则原问题也无解。,2）某个分支有无穷大解，则原问题也应该有无穷大解。,3）如果某个分支求出整数解，则原问题的解的下界就确定，所有求出整数解分支中的最大值，那些已经求得整数解的分支无须继续求解。,4）如果某分支的最大值小于问题的下界，则该分支无须继续求解，哪怕还没有求出整数最优解,5）否则，选取最大值大的分支再进行分支，直至出现1）4）的情况,分析书上例6,P138,第三节 整数规划的分支定界法,第四节,01,型整数规划法,一、整数线性规划的数学模型的表示,max（min）z=,x,j,0,且,取整数,(,j=1,2,n),st,.,c,j,x,j,a,ij,x,j,(,或=,),b,i,(i=1,2,m),取整数,x,j,可以取0、1、2，,在现实生活中，有时,x,j,不仅要取整数，而且只能取0或1,称之为,0 1,规划,二、,01,规划的例子,设新疆生产建设兵团，拟投资1000万元，计划在,P,1,、P,2,、P,3,、P,4,及,P,5,五个农场修建公路，由于条件不同所需的投资分别为：,a,1,=560、a,2,=200、a,3,=540、a,4,=420,及,a,5,=150(,万元)。公路建成后，每年所能得到的收益分别为：,C,1,=70、C,2,=50、C,3,=90、C,4,=60,及,C,5,=30(,万元)。问应如何确定投资地点，使总额不超过1000万元，且建成后每年所获得的总收益最大?,解：建立数学模型,设,X,j,为在,P,j,农场投资修建公路决策变量,X,j,=1,代表在,P,j,农场投资修建公路；,X,j,=0,不在,P,j,农场投资修建公路 其中,j=1，2，3，4，5,560,X,1,+200X,2,+540X,3,+420X,4,+150X,5,1000,X,j,=0,或1(,j1，2，3，4，5,),目标函数：,maxZ=70X,1,+50X,2,+90X,3,+60X,4,+30X,5,约束条件,st,.,第四节,01,型整数规划法,三、,0,1,型整数线性规划的数学模型的表示,max（min）z,=,x,j,取,0,或,1,(,j=1,2,n),st,.,c,j,x,j,a,ij,x,j,(,或=,),b,i,(i=1,2,m),第四节,01,型整数规划法,四、,01,规划的求解方法枚举法,一种最简单的方法：,枚举法,这种思路为：找出所有整数可行解，并分别算出其目标,值,，通过比较求得问题的,最优解。,一个01规划所有解的个数为：,2,n,技巧,：对目标函数进行,排序。,分析书上例10、11,P141,第四节,01,型整数规划法,第四节 指派问题,一、指派问题提出,解：建立数学模型,设,X,ij,为第,i,组去装卸第,j,车 其中,i,j=1，2，3，4,X,11,+X,21,+X,31,+X,41,=1,X,12,+X,22,+X,32,+X,42,=1,X,13,+X,23,+X,33,+X,43,=1,X,14,+X,24,+X,34,+X,44,=1,X,ij,=0,或 1,（,i,j=1，2，3，4）,目标函数：,minZ=4X,11,+3X,12,+4X,13,+X,14,+2X,21,+3X,22,+6X,23,+5X,24,+4X,31,+3X,32,+5X,33,+4X,34,+3X,41,+2X,42,+6X,43,+5X,44,约束条件,st,.,P1,P2,P3,P4,4,2,4,3,3,3,3,2,4,6,5,6,1,5,4,5,装卸组,装卸车,要求：每