《6运筹学第五章2007》由会员分享，可在线阅读，更多相关《6运筹学第五章2007（28页珍藏版）》请在金锄头文库上搜索。
1、主讲教师：,联系电话： 短 号：,E-mail:,清华大学出版社,运筹学教程（第三版）,运筹学基础,胡运权 主编,教材,运 筹 学 课 件,整 数 规 划,第 五 章,Dynamic Programming,第一节 整数规划数学模型及解的特点,一、线性规划的数学模型的表示,max（min） z =,xj 0 (j=1,2, ,n),st.,cjxj,aijxj (或=,) bi (i=1,2, ,m),线性规划问题的特征 ： （1）目标函数是决策变量的线性函数 （2）约束条件是含决策变量的线性等式或不等式,第一节 整数规划数学模型及解的特点,二、整数规划的数学模型的表示,整数规划的矩阵表示：,
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
3、为整数,例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
4、8,x1 ,x2 0 且取整数,St.,x1=18/7 x2=19/7 Z=94/7,X1*=4 x2*=2 Z*=12,一种最简单的方法：枚举法,这种思路为：找出所有整数可行解，并分别算出其目标值，通过比较求得问题 的最优解,第二节 整数规划的割平面法,红色区域与原区域区别： 1.是原区域的一部分 2.与原问题有相同的可行解,这种方法的思路： 把原区域割去不含原问题可行解的那部分区域，从而可以求得原问题的最优解。,我们称这种思路为割平面法,第一步：先不考虑整数约束，利用单纯形法进行求解,第二节 整数规划的割平面法,第二步：考虑非整数解中小数最大的约束，分解成分数约束与整数约束 （实践证明这样
5、求解，速度最快）,综合（3）及原问题的约束，等于增加一个约束 x2 2,要求分数约束部分的系数为正,第二节 整数规划的割平面法,第三步：把约束（3）作为新约束加入单纯形法继续求解,如果还不能求出整数最优解，重复 直至求出整数最优解为止。,第二节 整数规划的割平面法,割平面法求解的演示,最优解,第二节 整数规划的割平面法,第三节 整数规划的分支定界法,x1=18/7 x2=19/7 Z=94/7,-2x1 + 3x2 3 x1 + 2x2 8 x1 2 x1 ,x2 0 且取整数,-2x1 + 3x2 3 x1 + 2x2 8 x1 3 x1 ,x2 0 且取整数,我们把这种方法的思路称为分支定
6、界法,1）把原区域分成两个分支，这样的分割没有减少可行解，我们可以分别求出各个分支的最优解，看是否为整数解，如果存在分支没有得到整数最优解，按照上述方式继续，直到求出整体最优解为止。 2）如果出现某个分支的最优解小于其它存在整数可行解，则该分支没有必要继续求解，这就是定界。,分支定界法把可行域一分为二,第一步：先不考虑整数约束，利用单纯形法进行求解,第三节 整数规划的分支定界法,分支定界法把可行域一分为二,第二步：任选不满足整数约束的变量进行分支，把问题分解成两个问题（两个分支）,x2 = 19/7，其整数部分为2,如,把它分解成两个约束,x2 2,和,x2 3,x1=18/7 x2=19/7
7、 Z=94/7,分支二 没有可行域，分支一可以求得最优解为： x1*=4 x2*=2 z*=12，已经满足整数要求，故为问题得最优解,第三节 整数规划的分支定界法,第三步：把问题的两个分支求出解后，分析各分支的解，解的情况无外乎： 1）某个分支无解，则以后不用管理该分支；显然，如果各分支都没有可行解，则原问题也无解。 2）某个分支有无穷大解，则原问题也应该有无穷大解。 3）如果某个分支求出整数解，则原问题的解的下界就确定，所有求出整数解分支中的最大值，那些已经求得整数解的分支无须继续求解。 4）如果某分支的最大值小于问题的下界，则该分支无须继续求解，哪怕还没有求出整数最优解 5）否则，选取最大
8、值大的分支再进行分支，直至出现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=
9、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+150X51000 Xj=0或1(j1，2，3，4，5),目标函数：maxZ=70X1+50X2+90X3+60X4+30X5,约束条件 st.,第四节 01 型
10、整数规划法,三、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 +
11、X21 + X31 + X41 = 1 X12 + X22 + X32 + X42 = 1 X13 + X23 + X33 + X43 = 1 X14 + X24 + X34 + X44 = 1 Xij = 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.,装卸组,装卸车,要求：每个装卸组装一辆车 目标：时间最短,二、指派问题求解,匈牙利法, 19
12、59库恩利用匈牙利数学家康尼格关于矩阵中独立零元素理论提出的。,三、匈牙利法,系数矩阵 =,4 2 4 3,3 3 3 2,4 6 5 6,1 5 4 5,第四节 指派问题,四、匈牙利法步骤,4 2 4 3,3 3 3 2,4 6 5 6,1 5 4 5,2. 试求最优解,-1 -2 -3 -2,-2,1. 对系数矩阵进行变换，使各行各列都出现0元素,如果能找出n个独立的0，则为最优解,否则继续变换，直到找出n个独立的0,第四节 指派问题,4 7 6 6 6,8 9 9 7 9,7 17 12 14 12,-1 -3,共减去：,4+7+6+6+6+1+3 = 33,没有找出n个独立的0，怎么办
13、？,15 14 8 6 10,12 10 7 10 6,- 4 - 7 - 6 - 6 - 6,0 0 0 0 0,4 2 3 1 3,3 10 6 8 6,11 7 2 0 4,8 3 1 4 0,0 0 0 0 0,3 1 2 0 2,0 7 3 5 3,11 7 2 0 4,8 3 1 4 0,3. 试求最优解,- 1 - 1,1,第四节 指派问题,五、非标准指派问题求解,人多事少与人少事多,一人可以做多件事,最大值问题,学生,科目,要求：每个学生只参加一门科目竞赛,目的：总成绩最高,第四节 指派问题,系数矩阵A =,7 9 1 21,系数矩阵 A =,89 87 95 75,92 88 90 78,81 78 72 96,学生,科目,4 8 6 18,28 31 11 7,15 18 24 0,68 65 85 89,第四节 指派问题,89 87 95 75,
