第五章--整数规划--运筹学

运筹帷幄之中决胜千里之外运筹学课件整数规划第五章DynamicProgramming第一节整数规划数学模型及解的特点一、线性规划的数学模型的表示max（min）z=xj≥0(j=1,2,……,n)st.nj1cjxjnj1aijxj≤(或=,≥)bi(i=1,2,……,m)线性规划问题的特征：（1）目标函数是决策变量的线性函数（2）约束条件是含决策变量的线性等式或不等式第一节整数规划数学模型及解的特点二、整数规划的数学模型的表示max（min）z=xj≥0，xj部分或全部取整数(j=1，2,……,n)st.nj1cjxjnj1aijxj≤(或=,≥)bi(i=1,2,……,m)max..0,cxAxbstxx取整整数规划的矩阵表示：max..0cxAxbstx整数规划的松弛问题：整数规划与其松弛问题最优解和最优值的关系整数规划的可行解一定是其松弛问题的可行解。整数规划的最优值不优于其松弛问题的最优值。三、整数规划数学模型举例解设：xi为服务员在i时段开始上班人数minz=x1+x2+x3+x4+x5+x6+x7+x8约束条件x1≥10st.例1时段（2h）12345678服务员最少数目10891113853要求：服务员要连续工作4个时段目标：人数最少目标x1+x2≥8x1+x2+x3≥9x1+x2+x3+x4≥11x2+x3+x4+x5≥13x4+x5≥5x3+x4+x5≥8x5≥3且xj为整数xj≥0(j=1,2,3,4,5)例2、例3见书P124，125例1时段（2h）12345678服务员最少数目10891113853要求：服务员要连续工作4个时段目标：人数最少四、整数线性规划的数学模型及解的特点max（min）z=xj≥0且取整数(j=1,2,……,n)st.nj1cjxjnj1aijxj≤(或=,≥)bi(i=1,2,……,m)整数线性规划问题与一般线性规划最大区别是：(1)整数规划中决策变量必须为整数(2)设两组可行解X1、X2，(aX1+bX2)不一定是整数规划的解（其中，a，b0且a+b=1）(3)一般线性问题的可行域为一个凸集，而整数规划的可行域是一些离散点取整数全部决策变量都取整数时称全（纯）整数规划部分决策变量取整数时称混合整数规划决策变量只能取0或1时称0-1型整数规划五、整数线性规划的求解方法maxz=x1+4x2例2-2x1+3x2≤3x1+2x2≤8x1,x2≥0且取整数St.x1=18/7x2=19/7Z=94/7x1=3x2=3Z=15x1=2x2=3Z=14x1=2x2=2Z=10x1=3x2=2Z=11X1*=4x2*=2Z*=12一种最简单的方法：枚举法这种思路为：找出所有整数可行解，并分别算出其目标值，通过比较求得问题的最优解第二节整数规划的割平面法红色区域与原区域区别：1.是原区域的一部分2.与原问题有相同的可行解这种方法的思路：把原区域割去不含原问题可行解的那部分区域，从而可以求得原问题的最优解。我们称这种思路为割平面法第一步：先不考虑整数约束，利用单纯形法进行求解割平面法——如何割？1958年，高莫瑞提出一种每次增加一个约束——割平面约束，来割除一些多余的可行域。Cj1400CB基bx1x2x3x400x3x438-23101201δ1400……………….41x2x119/718/7011/72/710-2/73/7δ00-2/7-11/7第二节整数规划的割平面法第二步：考虑非整数解中小数最大的约束，分解成分数约束与整数约束（实践证明这样求解，速度最快）x1=18/7x2=19/7如都是非整数解，而18%7=419%7=5故考虑第一个约束x2+x3/7+2x4/7=19/7（1）x3/7+2x4/7=5/7+（2-x2）（2）因为x3、x4≥0故x3/7+2x4/7≥0而2-x2必定大于等于0的整数故x3/7+2x4/7≥5/7（3）即x3+2x4≥5（3′）综合（3）及原问题的约束，等于增加一个约束x2≤2新增加的约束要求分数约束部分的系数为正第二节整数规划的割平面法第三步：把约束（3）作为新约束加入单纯形法继续求解,如果还不能求出整数最优解，重复直至求出整数最优解为止。Cj14000CB基bx1x2x3x4x5410x2x1x519/718/7-5011/72/7010-2/73/7000-1-21δ00-2/7-11/70410x2x1x324501001/71001-2/70012-1δ000-1-2/7第二节整数规划的割平面法割平面法求解的演示最优解第二节整数规划的割平面法第三节整数规划的分支定界法x1=18/7x2=19/7Z=94/7把原问题非整数约束区域一分为二。我们可以发现原问题可行解没有少-2x1+3x2≤3x1+2x2≤8x1≤2x1,x2≥0且取整数-2x1+3x2≤3x1+2x2≤8x1≥3x1,x2≥0且取整数-2x1+3x2≤3x1+2x2≤8x1,x2≥0且取整数原问题约束我们把这种方法的思路称为分支定界法1）把原区域分成两个分支，这样的分割没有减少可行解，我们可以分别求出各个分支的最优解，看是否为整数解，如果存在分支没有得到整数最优解，按照上述方式继续，直到求出整体最优解为止。2）如果出现某个分支的最优解小于其它存在整数可行解，则该分支没有必要继续求解，这就是定界。分支定界法——把可行域一分为二第一步：先不考虑整数约束，利用单纯形法进行求解Cj1400CB基bx1x2x3x400x3x438-23101201δ1400……………….41x2x119/718/7011/72/710-2/73/7δ00-2/7-11/7第三节整数规划的分支定界法分支定界法——把可行域一分为二第二步：任选不满足整数约束的变量进行分支，把问题分解成两个问题（两个分支）x2=19/7，其整数部分为2如把它分解成两个约束x2≤2和x2≥3故原问题分解成两部分maxz=x1+4x2-2x1+3x2≤3x1+2x2≤8x1,x2≥0且取整数St.x2≤2maxz=x1+4x2-2x1+3x2≤3x1+2x2≤8x1,x2≥0且取整数St.x2≥3和（分支一）（分支二）x1=18/7x2=19/7Z=94/7分支二没有可行域，分支一可以求得最优解为：x1*=4x2*=2z*=12，已经满足整数要求，故为问题得最优解第三节整数规划的分支定界法第三步：把问题的两个分支求出解后，分析各分支的解，解的情况无外乎：1）某个分支无解，则以后不用管理该分支；显然，如果各分支都没有可行解，则原问题也无解2）某个分支有无穷大解，则原问题也应该有无穷大解3）如果某个分支求出整数解，则原问题的解的下界就确定所有求出整数解分支中的最大值，那些已经求得整数解的分支无须继续求解。4）如果某分支的最大值小于问题的下界，则该分支无须继续求解，哪怕还没有求出整数最优解5）否则，选取最大值大的分支再进行分支，直至出现1）～4）的情况分析书上例6P138第三节整数规划的分支定界法第四节0—1型整数规划法一、整数线性规划的数学模型的表示max（min）z=xj≥0且取整数(j=1,2,……,n)st.nj1cjxjnj1aijxj≤(或=,≥)bi(i=1,2,……,m)取整数——xj可以取0、1、2，……在现实生活中，有时xj不仅要取整数，而且只能取0或1称之为0—1规划二、0—1规划的例子设新疆生产建设兵团，拟投资1000万元，计划在P1、P2、P3、P4及P5五个农场修建公路，由于条件不同所需的投资分别为：a1=560、a2=200、a3=540、a4=420及a5=150(万元)。公路建成后，每年所能得到的收益分别为：C1=70、C2=50、C3=90、C4=60及C5=30(万元)。问应如何确定投资地点，使总额不超过1000万元，且建成后每年所获得的总收益最大?解：建立数学模型,设Xj为在Pj农场投资修建公路决策变量Xj=1代表在Pj农场投资修建公路；Xj=0不在Pj农场投资修建公路其中j=1，2，3，4，5560X1+200X2+540X3+420X4+150X5≤1000Xj=0或1(j＝1，2，3，4，5)目标函数：maxZ=70X1+50X2+90X3+60X4+30X5约束条件st.第四节0—1型整数规划法三、0—1型整数线性规划的数学模型的表示max（min）z=xj取0或1(j=1,2,……,n)st.nj1cjxjnj1aijxj≤(或=,≥)bi(i=1,2,……,m)第四节0—1型整数规划法四、0—1规划的求解方法——枚举法一种最简单的方法：枚举法这种思路为：找出所有整数可行解，并分别算出其目标值，通过比较求得问题的最优解。一个0—1规划所有解的个数为：2n技巧：对目标函数进行排序。分析书上例10、11P147第四节0—1型整数规划法第五节指派问题一、指派问题提出解：建立数学模型,设Xij为第i组去装卸第j车其中i,j=1，2，3，4X11+X21+X31+X41=1X12+X22+X32+X42=1X13+X23+X33+X43=1X14+X24+X34+X44=1Xij=0或1（i,j=1，2，3，4）目标函数：minZ=4X11+3X12+4X13+X14+2X21+3X22+6X23+5X24+4X31+3X32+5X33+4X34+3X41+2X42+6X43+5X44约束条件st.P1P2P3P4ⅠⅡⅢⅣ4243333246561545装卸组装卸车要求：每个装卸组装一辆车目标：时间最短二、指派问题求解•匈牙利法————1959库恩利用匈牙利数学家康尼格关于矩阵中独立零元素理论提出的。三、匈牙利法•系数矩阵=4243333246561545第五节指派问题四、匈牙利法步骤42433332465615452.试求最优解-1-2-3-23011210034240313-23011210012020313共减去：1+2+3+2+2=101.对系数矩阵进行变换，使各行各列都出现0元素2100120203133011如果能找出n个独立的0，则为最优解否则继续变换，直到找出n个独立的0第五节指派问题4766689979717121412-1-3共减去：4+7+6+6+6+1+3=33没有找出n个独立的0，怎么办？1514861012107106-4-7-6-6-6000004231331068611720483140000003120207353117204831403.试求最优解00000312020735311720483140-1-10-1-100301020625311610482040110011301020625311610482040共减去：33+1+1-1=34第五节指派问题五、非标准指派问题求解•人多事少与人少事多•一人可以做多件事•最大值问题数学物理化学外语ABCD89879575928890786865858981787296学生科目要求：每个学生只参加一门科目竞赛目的：总成绩最高第五节指派问题•系数矩阵A’=79121数学物理化学外语ABCD89879575928890786865858981787296•系数矩阵A=898795759288907881787296学生科目486182831117151824068658589第五节指派问题89879575