运筹学基础整数规划课件.ppt

关于运筹学基础整数规划现在学习的是第1页，共41页2 24.1整数规划解决整数规划问题不能仅仅是在线性规划求解中，将解“四舍五入”就行了，因为化整后的解不见得是可行解；即便是可行解，也不一定是优解。注意：注意：注意：注意：在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些具体的问题，常有要求解答必须是整数的情形（称为整数解），解决这样的问题即为整数规划。一、整数规划问题的提出整数规划现在学习的是第2页，共41页3 3【例例1】某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表：问两种货物各托运多少箱，可使利润为最大？建立线性规划模型为：建立线性规划模型为：建立线性规划模型为：建立线性规划模型为：maxZ=20 x1+10 x2 5x1+4x2 24 2x1+5 x2 13x1 0,x2 0利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：x14.8，x20，maxZ96整数规划现在学习的是第3页，共41页4 4讨论：如何调整满足整数解（1 1）四舍五入：）四舍五入：）四舍五入：）四舍五入：x15，x20，Z100但破坏了体积限制条件，因而不是可行解（2 2）舍小数：）舍小数：）舍小数：）舍小数：x14，x20，Z80是可行解，但不是最优解，因 x14，x21，Z90也是可行解C(4.8,0)C(4.8,0)maxZ=20 x1+10 x2 5x1+4x2 24 2x1+5 x2 13x1 0,x2 0 x2x1110 023234567+B(4,1)B(4,1)x14.8，x20，maxZ96非整数解非整数解非整数解非整数解整数规划现在学习的是第4页，共41页5 5二、整数规划的求解方法二、整数规划的求解方法二、整数规划的求解方法二、整数规划的求解方法1、分枝定解法2、割平面法3、利用EXCEL求解整数规划现在学习的是第5页，共41页6 61 1、整数规划之分枝定解法、整数规划之分枝定解法问题问题问题问题A A：maxZ=20 x1+10 x2 5x1+4x2 24 2x1+5 x2 13x1 0,x2 0 x1,x2 整数整数问题问题问题问题B B：maxZ=20 x1+10 x2 5x1+4x2 24 2x1+5 x2 13x1 0,x2 0从问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的上界，记作，（如果是求最小值，即为下界）分枝定界法分枝定界法分枝定界法分枝定界法就是将B的可行域分成子区域的方法，逐步减小减小减小减小和增大增大增大增大，最终逼近Z*。写出整数规划问题整数规划问题整数规划问题整数规划问题A A的伴随线性规划问题为线性规划问题为B 而A的任意可行解任意可行解的目标函数值将是Z*的一个下界，记作，（如果是求最小值，即为上界）Z*整数规划现在学习的是第6页，共41页7 7第一步：寻找替代问题并求解第一步：寻找替代问题并求解第一步：寻找替代问题并求解第一步：寻找替代问题并求解问题问题问题问题B B：maxZ=20 x1+10 x2 5x1+4x2 24 2x1+5 x2 13x1 0,x2 0利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：x14.8，x20，Z96问题问题问题问题B B1 1：maxZ=20 x1+10 x2 5x1+4x2 24 2x1+5 x2 13 x1 4x1 0,x2 0问题问题问题问题B B2 2：maxZ=20 x1+10 x2 5x1+4x2 24 2x1+5 x2 13 x1 5x1 0,x2 0 0 Z*96利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：x14，x21，Z90无解；无解；无解；无解；第二步：分枝与定界第二步：分枝与定界第二步：分枝与定界第二步：分枝与定界x2x1110 023234567+最后得最优解为：最后得最优解为：最后得最优解为：最后得最优解为：x14，x21，Z90整数规划现在学习的是第7页，共41页8 8【例例2】问题问题问题问题A A：maxZ=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1 0,x2 0 x1,x2 整数整数利用单纯形法求解问题利用单纯形法求解问题利用单纯形法求解问题利用单纯形法求解问题B B得最优解为：得最优解为：得最优解为：得最优解为：x14.81，x21.82，Z356问题问题问题问题B B2 2：maxZ=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1 5x1 0,x2 0 0 Z*356利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：x14，x22.1，Z349利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：x15，x21.57，Z341问题问题问题问题B B：maxZ=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1 0,x2 0问题问题问题问题B B1 1：maxZ=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1 4 x1 0,x2 0 0 Z*349第一步：寻找替代问题并求解第一步：寻找替代问题并求解第一步：寻找替代问题并求解第一步：寻找替代问题并求解第二步：分枝与定界第二步：分枝与定界第二步：分枝与定界第二步：分枝与定界整数规划现在学习的是第8页，共41页9 9 分枝定解法求解（续）分枝定解法求解（续）分枝定解法求解（续）分枝定解法求解（续）利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：x14，x22，Z340利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：利用单纯形法求得最优解为：x11.52，x23，Z327问题问题问题问题B B1111：maxZ=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1 4 x2 2 x1 0,x2 0 340 Z*349x14x22.1Z349问题问题问题问题B B1212：maxZ=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1 4 x2 3 x1 0,x2 0问题问题问题问题B B2121：maxZ=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1 5x2 1x1 0,x2 0 x15x21.57Z341x15.44，x21，Z308问题问题问题问题B B2121：maxZ=40 x1+90 x2 9x1+7x2 56 7x1+20 x2 70 x1 5x2 2x1 0,x2 0无可行解无可行解无可行解无可行解整数规划现在学习的是第9页，共41页1010问题Bx14.81x21.82Z356问题B1x14.00 x22.1Z349问题Bx15.00 x21.57Z341问题B11x14.00 x22.00Z340问题B12x11.42x23.00Z327问题B21x15.44x21.00Z308问题B22无可行解无可行解x1 4x1 5x2 2x2 3x2 1x2 2 0 Z*356 0 Z*349 340 Z*349Z*340 分枝定解法求解框图分枝定解法求解框图分枝定解法求解框图分枝定解法求解框图整数规划现在学习的是第10页，共41页1111n分枝为问题1、2后解可能出现如下几种情况序号序号问题问题 1问题问题2说说 明明1无可行解无可行解无可行解无可行解整数规划无可行解整数规划无可行解2无可行解无可行解整数解整数解此整数解即最优解此整数解即最优解3无可行解无可行解非整数解非整数解对问题对问题2继续分枝继续分枝4整数解整数解整数解整数解较优的一个为最优解较优的一个为最优解5整数解，目标函整数解，目标函数优于问题数优于问题2非整数解非整数解问题问题1的解即最优解的解即最优解6整数解整数解非整数解，目标非整数解，目标函数优于问题函数优于问题1问题问题1 1停止分枝停止分枝(剪剪枝枝)，其整数解为界，其整数解为界，对问题对问题2继续分枝继续分枝情况 2,4,5 找到最优解情况 3 在缩减的域上继续分枝定界法情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝所得到的整数解进行比较，结论如情况 4情况 1 无可行解整数规划现在学习的是第11页，共41页1212n分枝定界法的一般步骤如下 第一步第一步，先不考虑原问题的整数限制，求解相应的松弛问题，若求得最优解，检查它是否符合整数约束条件；如符合整数约束条件，即转下一步。第二步第二步，定界。在各分枝问题中，找出目标函数值最大者Z*作为整数规划最优值 的上界，从已符合整数条件的分枝中，找出目标函数值最大者作为下界，即 第三步第三步，分枝。根据对变量重要性的了解，在最优解中选择一个不符合整数条件的xj，令 xj=bj，(bj不为整数)则用下列两个约束条件：第四步第四步，应用对目标函数估界的方法，或对某一分枝重要性的了解，确定出首先要解的某一分枝的后继问题，并解此问题。若所获得的最优解符合整数条件，则就是原问题的解，若不符合整数条件，再回到第二步，并参照第四步终止后继问题。整数规划现在学习的是第12页，共41页1313分枝定界法的分枝定界法的EXCEL演示演示 整数规划现在学习的是第13页，共41页14142、割平面解法割平面法也是求解整数规划问题常用方法之一。【基本思路】如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新增加新的约束条件重新求解的约束条件重新求解。这个新增加的约束条件的作用就是去切割相应松弛问切割相应松弛问题的可行域题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)。而把所有的整数解都保留下来，故称新增加的约束条件为割平面割平面。当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解。即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止。整数规划现在学习的是第14页，共41页1515 n割平面法的具体求解步骤如下：1.对于所求的整数规划问题，先不考虑整数约束条件，求解相应的松弛问题2.如果该问题无可行解无可行解或已取得整数最优解已取得整数最优解，则运算停止；前者表示原问题也无可行解，后者表示已求得整数最优解。如果有一个或更多个变量取值不满足整数条件，则选择某个变量建立割平面。3.增加为割平面的新约束条件，用前面介绍的灵敏分析的方法继续求解，返回1。整数规划现在学习的是第15页，共41页1616【例1】求解下列整数规划问题解：引入松弛变量，写成标准形式（1）+=,0,;2054;62;max432142132121xxxxxxxxxxxxz（2）对上述模型不考虑整数条件，用单纯形法求解相应松弛问题的最终单纯形表为Cj比值CBXBb检验数jx1x2x3x411005/3105/6-1/68/301-2/31/3x1x211-13/300-1/6-1/6最优解为x15/3，x28/3不是整数解不是整数解整数规划现在学习的是第16页，共41页1717 显然，x1=5/3,x2=8/3为非整数解。为求得整数解，想办法在原约束条件的基础下引入一个新的约束条件，以保证一个或几个变量取值为整数。为此，选择分数部分较大的非整数变量分数部分较大的非整数变量，如x2，写出如下表达式：将上式的所有变量的系数及右端常数均改写成一个整数整数整数整数与一个非负真分数非负真分数非负真分数非负真分数之和的形式。上式可以改写成若将带有整数系数带有整数系数带有整数系数带有整数系数的变量留在方程的左边，其余移到方程的右边，则有 由于要求变量取值为正整数正整数，方程的左边必为整数。当然，方程的右边也应为整数。又x30,x40于是，必有x31,x41（3）（4）00此时，也可以选择x2-x3-20，只是因为先分析出方程右端0整数规划现在学习的是第17页，共41页1818 整理后得为了直观地在图形上描述，可将(2)式的两个约束方程代入(5)式即+=且为整数,0,;2054;62;max432142132121xxxxxxxxxxxxz则(5)式成为（5）这就是割平面的方程B(5/3,8/3)x1x2246246-20-4AECO加入新的约束条件，便形成新的线性规划问题，其可行域为新的凸集OAEC。即图中红色直线割去了红色直线以外的ABE部分，其中包括原所求得的非整数最优解点B(5/3,8/3)。三个方程是等价的，三个方程是等价的，任意一个都可增加的任意一个都可增加的新的约束条件新的约束条件整数规划现在学习的是第18页，共41页1919 建立割平面以后，便可以把割平面方程作为新的约束条件加到原整数规划问题(2)式中，在仍然不考虑整数条件的情况下，利用单纯形法或对偶单纯形法继续求解。以选择第一个为例，引入松驰变量x5，代入新增加的约束条件中从上面的推导过程可以看出，新约束对原约束方程起到了这样的作用：对整数规划(1)式所对应的线性规划的可行域，保留了其中的所有整数可行解所有整数可行解，但割掉了一部分非整数解割掉了一部分非整数解。三个约束条件任选其一-1/3x3-1/3x4+x5=-2/3整数规划现在学习的是第19页，共41页2020Cj比值CBXBb检验数jx1x2x3x4x5110005/3105/6-1/608/301-2/31/30-2/300-1/3-1/31x1x2x5110-13/300-1/6-1/60Cj比值CBXBb检验数jx1x2x3x4x5110000100-15/2401 01-2x1x2x6110-400 00-1/220011-3x10，x24为最优解，最优值为Z4整数规划现在学习的是第20页，共41页2121Cj比值CBXBb检验数jx1x2x3x4x5110005/3105/6-1/608/301-2/31/30-2/300-1/3-1/31x1x2x5110-13/300-1/6-1/60Cj比值CBXBb检验数jx1x2x3x4x51100021010-1/2201-10 1x1x2x6110-400 00-1/220011-3x12，x22为最优解，最优值为Z4另一选择现在学习的是第21页，共41页2222分析因为上述的线性规划的最优解已是整数解，所以得整数规划问题（1）的最优解：E(2,2)A(0,4)x1x2246246-20-4x1=0，x2=4。此最优解位于图A点。x1=2，x2=2。此最优解位于图E点。整数规划现在学习的是第22页，共41页2323【例2】求解下列整数规划问题解：引入松弛变量，写成标准形式：（1）（2）第一步：对上述模型不考虑整数条件，用单纯形法求解相应松弛问题的最终单纯形表为Cj比值CBXBb检验数jx1x2x3x432005/2011/2-1/213/410-1/43/4x2x123 -59/400-1/4-5/4最优解为x25/2，x113/4此最优解非整数解此最优解非整数解整数规划现在学习的是第23页，共41页2424 第二步：x1 13/4,x25/2为非整数解，找出非整数解变量中分数部分最大分数部分最大的一个基变量x2，写出这一行的约束：将上式的所有变量的系数及右端常数均改写成一个整数整数整数整数与一个非负真分数非负真分数非负真分数非负真分数之和的形式得：若将带有整数系数的变量整数项留在方程的左边，其余移到方程的右边，则有 由于要求变量取值为正整数正整数，方程的左边必为整数左边必为整数。方程的右边也应右边也应为整数为整数。又由于x30,x40于是，有方程右端小于等于零有方程右端小于等于零。00整数规划现在学习的是第24页，共41页2525 即为了直观地在图形上描述，可将标准式的两个约束方程代入上式，则成为-(14-2x1-3x2)(9-2x1-x2)-1三个方程的任意一个都可做为后面增加的新的约束条件三个方程的任意一个都可做为后面增加的新的约束条件三个方程的任意一个都可做为后面增加的新的约束条件三个方程的任意一个都可做为后面增加的新的约束条件整理后得2x1+2x211这就是割平面的方程整数规划现在学习的是第25页，共41页2626 B(13/4,5/2)A AE EC C2x1+2x211F F加入新的约束条件，便形成新的线性规划问题，其可行域为新的凸集OAEFC。即图中所示的红色直线的下半部分。显然它割去了除红色直线上所有点以外的BEF部分，其中包括原所求得的非整数最优解点B(13/4,5/2)。x1x2246246-20-4OO这就是割平面的方程整数规划现在学习的是第26页，共41页2727 建立割平面以后，便可以把割平面方程作为新的约束条件加到原整数规划问题中，在仍然不考虑整数条件的情况下，利用单纯形法或对偶单纯形法继续求解。将其作为新的约束条件，加入到前面的最终表中，便形成新的线性规划问题。用对偶单纯形法求解。第三步：引入松驰变量x5，代入新增加的约束条件中-1/2x3-1/2x4+x5-1/22x1+2x211任意一个都可做为增加的新的约束条件任意一个都可做为增加的新的约束条件任意一个都可做为增加的新的约束条件任意一个都可做为增加的新的约束条件整数规划现在学习的是第27页，共41页2828Cj比值CBXBb检验数jx1x2x3x4x5320005/2011/2-1/2013/410-1/40-1/200-1/2-1/21x2x1x5230-59/400-1/4-5/40Cj比值CBXBb检验数jx1x2x3x4x5110002010-117/21001 -1/2x2x1x3230-29/200 0-1-1/210011-2x17/2，x22为最优解，最优值为Z29/2，不是整数解现在学习的是第28页，共41页2929 由于仍有非整数解，重复第二步：写出另一行的约束：将上式的所有变量的系数及右端常数均改写成一个整数整数整数整数与一个非负真分数非负真分数非负真分数非负真分数之和的形式得：若将带有整数系数的变量整数项留在方程的左边，其余移到方程的右边，则有此得到新约束：整数规划现在学习的是第29页，共41页3030 2x1+2x211又加入的新约束条件，便形成新的线性规划问题，其可行域又随之改变B(13/4,5/2)A AE EC CF Fx1x2246246-20-4OOx1+x25整数规划现在学习的是第30页，共41页3131 2010-110将其作为新的约束条件，加入到前面的最终表中，便形成新的线性规划问题。用对偶单纯形法求解。第三步：引入松驰变量x6，代入新增加的约束条件中-1/2 x5+x6-1/2Cj比值CBXBb检验数jx1x2x3x4x5x63200007/21001 -1/20 x2x1x3x62300-29/200 0-1-1/2010011-20-1/20000-1/21新增加的约束条件整数规划现在学习的是第31页，共41页3232 Cj比值CBXBb检验数jx1x2x3x4x5x632000041001 0-1x2x1x3x62300-1400 0-10-1300110-41010-102100001-2x14，x21为最优解，最优值为Z14，是整数解整数规划现在学习的是第32页，共41页3333 E(1,4)因为上述的线性规划的最优解已是整数解，所以得整数规划问题的最优解：x1=1，x2=4。maxZ14B(13/4,5/2)A AE EC CF Fx1x2246246-20-4OO整数规划现在学习的是第33页，共41页3434【例3】求解下列整数规划问题解引入松弛变量，写成标准形式：（1）+=,0,;43;1-;max432142132121xxxxxxxxxxxxz（2）对上述模型不考虑整数条件，用单纯形法求解相应松弛问题的最终单纯形表为Cj比值CBXBb检验数jx1x2x3x411003/410-1/41/47/4013/41/4x1x211-5/200-1/2-1/2+=且为整数,0,;43;1-;max21212121xxxxxxxxz最优解为x13/4，x27/4整数规划现在学习的是第34页，共41页3535 显然，x13/4，x27/4 为非整数解。找出非整数解变量中分数部分最大的一个基变量，写出相应的约束：将上式的所有变量的系数及右端常数均改写成一个整数整数整数整数与一个非负真分数非负真分数非负真分数非负真分数之和的形式。据此，上式可以改写成若将带有整数系数的变量整数项留在方程的左边，其余移到方程的右边，则有 ,4/34/14/1431=+-xxx,4/74/14/3432=+xxx,4/30)4/10()4/31()01(431+=+-+xxx,4/31)4/10()4/30()01(432+=+xxx43314/14/34/3xxxx-=-4324/14/34/31xxx-=-整数规划现在学习的是第35页，共41页3636 整理后得为了直观地在图形上描述，可将标准式的两个约束方程代入上式，则成为由于要求变量取值为正整数，方程的左边必为整数。当然，方程的右边也应为整数。又由于x30,x40于是，有,04/14/34/343-xx-3x3-x4-3x2 1+=且为整数,0,;43;1-;max432142132121xxxxxxxxxxxxz-3(1+x1-x2)(4-3x1-x2)-3这就是割平面的方程整数规划现在学习的是第36页，共41页3737 x1x2246246-20-4B(3/4,7/4)+=且为整数,0,;43;1-;max21212121xxxxxxxxz12xOOA AE EC C加入新的约束条件，便形成新的线性规划问题，其可行域为新的凸集OAEC。即图中所示的红色直线的下半部分。显然它割去了除红色直线上所有点以外的ABE部分，其中包括原所求得的非整数最优解点B(3/4,7/4)。整数规划现在学习的是第37页，共41页3838 建立割平面以后，便可以把割平面方程作为新的约束条件加到原整数规划问题中，在仍然不考虑整数条件的情况下，利用单纯形法或对偶单纯形法继续求解。将其作为新的约束条件，加入到前面的最终表中，便形成新的线性规划问题，其可行域为新的凸集OAEC。用对偶单纯形法求解引入松驰变量x5，代入新增加的约束条件中-3x3-x4+x5=-3x1x2246246-20-4OOA AE EC C,04/14/34/343-xx-3x3-x4-3x2 1现在学习的是第38页，共41页3939Cj比值CBXBb检验数jx1x2x3x4x5110003/410-1/41/407/4013/41/40-300-3-11x1x2x5110-5/200-1/2-1/20Cj比值CBXBb检验数jx1x2x3x4x51100011001/3-1/1210100 1/4x1x2x3110-200 0-1/3-1/610011/3-1/3x11，x21为最优解，最优值为Z2整数规划现在学习的是第39页，共41页4040 x1x2246246-20-4+=且为整数,0,;43;1-;max21212121xxxxxxxxz12xE(1,1)因为上述的线性规划的最优解已是整数解，所以得整数规划问题的最优解：x1=1，x2=1。此最优解位于图E点。整数规划现在学习的是第40页，共41页感感谢谢大大家家观观看看现在学习的是第41页，共41页