运筹学第五章.ppt
主讲教师：,联系电话：短 号：,E-mail:,清华大学出版社,运筹学教程（第三版）,运筹学基础,胡运权 主编,教材,运 筹 学 课 件,整 数 规 划,第 五 章,Dynamic Programming,第一节 整数规划数学模型及解的特点,一、线性规划的数学模型的表示,max（min）z=,xj 0(j=1,2,n),st.,cjxj,aijxj(或=,)bi(i=1,2,m),线性规划问题的特征：（1）目标函数是决策变量的线性函数（2）约束条件是含决策变量的线性等式或不等式,第一节 整数规划数学模型及解的特点,二、整数规划的数学模型的表示,整数规划的矩阵表示：,整数规划的松弛问题：,整数规划与其松弛问题最优解和最优值的关系,整数规划的可行解一定是其松弛问题的可行解。,整数规划的最优值不优于其松弛问题的最优值。,三、整数规划数学模型举例,解 设：xi 为服务员在 i 时段开始上班人数,min z=x1+x2+x3+x4+x5+x6+x7+x8,约束条件,x110,st.,要求：服务员要连续工作4个时段 目标：人数最少,目标,x1+x2 8,x1+x2+x3 9,x1+x2+x3+x4 11,x2+x3+x4+x5 13,x4+x5 5,x3+x4+x5 8,x5 3,且xj为整数,例2、例3见书P124，125,四、整数线性规划的数学模型及解的特点,max（min）z=,xj 0 且 取整数(j=1,2,n),st.,cjxj,aijxj(或=,)bi(i=1,2,m),整数线性规划问题与一般线性规划最大区别是：(1)整数规划中决策变量必须为整数(2)设两组可行解X1、X2，(aX1+bX2)不一定是整数规划的解（其中，a，b0 且 a+b=1）(3)一般线性问题的可行域为一个凸集，而整数规划的可行域 是一些离散点。,五、整数线性规划的求解方法,max z=x1+4x2,例2,-2x1+3x2 3,x1+2x2 8,x1,x2 0 且取整数,St.,x1=18/7 x2=19/7 Z=94/7,X1*=4 x2*=2 Z*=12,一种最简单的方法：枚举法,这种思路为：找出所有整数可行解，并分别算出其目标值，通过比较求得问题的最优解,第二节 整数规划的割平面法,红色区域与原区域区别：1.是原区域的一部分2.与原问题有相同的可行解,这种方法的思路：把原区域割去不含原问题可行解的那部分区域，从而可以求得原问题的最优解。,我们称这种思路为割平面法,第一步：先不考虑整数约束，利用单纯形法进行求解,第二节 整数规划的割平面法,第二步：考虑非整数解中小数最大的约束，分解成分数约束与整数约束（实践证明这样求解，速度最快）,综合（3）及原问题的约束，等于增加一个约束 x2 2,要求分数约束部分的系数为正,第二节 整数规划的割平面法,第三步：把约束（3）作为新约束加入单纯形法继续求解,如果还不能求出整数最优解，重复 直至求出整数最优解为止。,第二节 整数规划的割平面法,割平面法求解的演示,最优解,第二节 整数规划的割平面法,第三节 整数规划的分支定界法,x1=18/7 x2=19/7 Z=94/7,-2x1+3x2 3x1+2x2 8 x1 2x1,x2 0 且取整数,-2x1+3x2 3x1+2x2 8 x1 3x1,x2 0 且取整数,我们把这种方法的思路称为分支定界法,1）把原区域分成两个分支，这样的分割没有减少可行解，我们可以分别求出各个分支的最优解，看是否为整数解，如果存在分支没有得到整数最优解，按照上述方式继续，直到求出整体最优解为止。2）如果出现某个分支的最优解小于其它存在整数可行解，则该分支没有必要继续求解，这就是定界。,分支定界法把可行域一分为二,第一步：先不考虑整数约束，利用单纯形法进行求解,第三节 整数规划的分支定界法,分支定界法把可行域一分为二,第二步：任选不满足整数约束的变量进行分支，把问题分解成两个问题（两个分支）,x2=19/7，其整数部分为2,如,把它分解成两个约束,x2 2,和,x2 3,x1=18/7 x2=19/7 Z=94/7,分支二 没有可行域，分支一可以求得最优解为：x1*=4 x2*=2 z*=12，已经满足整数要求，故为问题得最优解,第三节 整数规划的分支定界法,第三步：把问题的两个分支求出解后，分析各分支的解，解的情况无外乎：1）某个分支无解，则以后不用管理该分支；显然，如果各分支都没有可行解，则原问题也无解。2）某个分支有无穷大解，则原问题也应该有无穷大解。3）如果某个分支求出整数解，则原问题的解的下界就确定，所有求出整数解分支中的最大值，那些已经求得整数解的分支无须继续求解。4）如果某分支的最大值小于问题的下界，则该分支无须继续求解，哪怕还没有求出整数最优解 5）否则，选取最大值大的分支再进行分支，直至出现1）4）的情况,分析书上例6 P138,第三节 整数规划的分支定界法,第四节 01 型整数规划法,一、整数线性规划的数学模型的表示,max（min）z=,xj 0 且取整数(j=1,2,n),st.,cjxj,aijxj(或=,)bi(i=1,2,m),取整数xj 可以取0、1、2，,在现实生活中，有时xj不仅要取整数，而且只能取0或1称之为0 1 规划,二、01规划的例子,设新疆生产建设兵团，拟投资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，5,560X1+200X2+540X3+420X4+150X51000Xj=0或1(j1，2，3，4，5),目标函数：maxZ=70X1+50X2+90X3+60X4+30X5,约束条件 st.,第四节 01 型整数规划法,三、01型整数线性规划的数学模型的表示,max（min）z=,xj 取 0或1(j=1,2,n),st.,cjxj,aijxj(或=,)bi(i=1,2,m),第四节 01 型整数规划法,四、01规划的求解方法枚举法,一种最简单的方法：枚举法,这种思路为：找出所有整数可行解，并分别算出其目标值，通过比较求得问题的最优解。,一个01规划所有解的个数为：2n,技巧：对目标函数进行排序。,分析书上例10、11 P141,第四节 01 型整数规划法,第四节 指派问题,一、指派问题提出,解：建立数学模型,设Xij为第i组去装卸第j车 其中i,j=1，2，3，4,X11+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.,装卸组,装卸车,要求：每个装卸组装一辆车 目标：时间最短,二、指派问题求解,匈牙利法,1959库恩利用匈牙利数学家康尼格关于矩阵中独立零元素理论提出的。,三、匈牙利法,系数矩阵=,4243,3332,4656,1545,第四节 指派问题,四、匈牙利法步骤,4243,3332,4656,1545,2.试求最优解,-1-2-3-2,-2,1.对系数矩阵进行变换，使各行各列都出现0元素,如果能找出n个独立的0，则为最优解,否则继续变换，直到找出n个独立的0,第四节 指派问题,47666,89979,717121412,-1-3,共减去：,4+7+6+6+6+1+3=33,没有找出n个独立的0，怎么办？,15148610,12107106,-4-7-6-6-6,00000,42313,310686,117204,83140,00000,31202,07353,117204,83140,3.试求最优解,-1-1,1,第四节 指派问题,五、非标准指派问题求解,人多事少与人少事多,一人可以做多件事,最大值问题,学生,科目,要求：每个学生只参加一门科目竞赛,目的：总成绩最高,第四节 指派问题,系数矩阵A=,79121,系数矩阵 A=,89879575,92889078,81787296,学生,科目,48618,2831117,1518240,68 65 85 89,第四节 指派问题,89879575,
