(7.2.1)--整数规划模型的求解（NO19）.pdf

《(7.2.1)--整数规划模型的求解（NO19）.pdf》由会员分享，可在线阅读，更多相关《(7.2.1)--整数规划模型的求解（NO19）.pdf（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 运运 筹筹 学学 第十九讲第十九讲 整数线性规划模型的求解整数线性规划模型的求解 2 求解求解ILPILP问题方法的思考：问题方法的思考：“舍入取整”法：即先不考虑整数性约束，而去求解其相应的LP问题（称为松驰问题），然后将得到的非整数最优解用“舍入取整”的方法。这样能否得到整数最优解？否！这是因为“舍入取整”的解一般不是原问题的最优解，甚至是非可行解。但在处理个别实际问题时，如果允许目标函数值在某一误差范围内，有时也可采用“舍入取整”得到的整数可行解作为原问题整数最优解的近似。这样可节省求解的人力、物力和财力。整数线性规划模型的求解整数线性规划模型的求解 如对于某个线性规划问题的解X1=

2、1000.8，X2=998.2，虽然取整数后不一定是整数规划问题的最优解，但是从经济成本上考虑，则可以用取整的方法来处理。3 例如：对于线性规划问题 egersareandxxxxxxtsxzint,0,21321.max2121212整数规划的最优解 取整后的整数解，却不是可行解 4 又如，对于下列模型 egersareandxxxxxtsxxzint,0,22010.5max2112121整数规划最优解 松驰LP问题的最优解 取整后的整数解 5 严格地说严格地说，IPIP是个非线性规划问题是个非线性规划问题。这是因为这是因为IPIP的的可行解集是由一些离散的非负整数所组成可行解集是由一些离

3、散的非负整数所组成，不是一个凸集不是一个凸集。迄今为止迄今为止，求解求解IPIP问题尚无统一的有效算法问题尚无统一的有效算法。但常用的有但常用的有求解一般整数规划的分枝定界法求解一般整数规划的分枝定界法、割平面法和求解割平面法和求解0 0-1 1规规划的隐枚举法划的隐枚举法。在这里我们只介绍分枝定界法和隐枚举法在这里我们只介绍分枝定界法和隐枚举法。1 1、整数规划的分枝定界法、整数规划的分枝定界法 分枝定界法可用于解纯整数或混合整数规划问题。在分枝定界法可用于解纯整数或混合整数规划问题。在本世纪六十年代初由本世纪六十年代初由Land DoigLand Doig和和DakinDakin等人提出。

4、由于该等人提出。由于该方法灵活且便于利用计算机求解，所以它是目前求解整数方法灵活且便于利用计算机求解，所以它是目前求解整数规划的重要方法。规划的重要方法。6（1）先不考虑原整数规划问题中的整数性约束，去解其相）先不考虑原整数规划问题中的整数性约束，去解其相应的松弛问题。对于最大化问题，松弛问题的最优值就是应的松弛问题。对于最大化问题，松弛问题的最优值就是原问题最优值的上界。如果松弛问题的最优解满足整数性原问题最优值的上界。如果松弛问题的最优解满足整数性约束，则它就是原问题的最优解。约束，则它就是原问题的最优解。分枝定界法的基本思想分枝定界法的基本思想:iibx 1iibx（2）否则，）否则，就

5、在不满足整数性约束的变量中，任意选一个就在不满足整数性约束的变量中，任意选一个xi（假设其值为（假设其值为bi），将新的约束条件），将新的约束条件 和和 分分别加入原问题中，把原问题分枝为两个子问题，别加入原问题中，把原问题分枝为两个子问题，并分别求解子并分别求解子问题的松弛问题。问题的松弛问题。（3）若子问题的松弛问题的最优解满足整数性约束，则不再分）若子问题的松弛问题的最优解满足整数性约束，则不再分枝，其相应的目标函数值就是原问题目标函数值的一个下界。枝，其相应的目标函数值就是原问题目标函数值的一个下界。对不满足整数性约束的子问题，如果需要的话，继续按上述方对不满足整数性约束的子问题，如果

6、需要的话，继续按上述方法进行新的分枝，并分别求解其对应的松弛问题，直至求得原法进行新的分枝，并分别求解其对应的松弛问题，直至求得原问题的最优解为止。问题的最优解为止。7 且为整数0,1032546.t.s2015zmaxxxxxxxxx21212121解：首先不考虑整数约束，相应的问题称为原问题的松驰解：首先不考虑整数约束，相应的问题称为原问题的松驰问题问题 0,1032546.t.s2015zmaxxxxxxxxx21212121松驰问题（0）用单纯形法求得其最优解为用单纯形法求得其最优解为x x1 1=2.5=2.5，x x2 2=2.5=2.5，z=87.5z=87.5 例题例题1 1：

7、用分枝定界法求解下列整数规划问题：用分枝定界法求解下列整数规划问题：2 1x8 0,1032546.t.s2015zmaxxxxxxxxx21212121松驰问题（0）0210325462015211212121xxxxxxxxx,.t.szmax问题（问题（1 1）3 1x问题（问题（2 2）0310325462015211212121xxxxxxxxx,.t.szmax最优解x1=2，x2=2.67 z=83.3 最优解x1=3，x2=1.75 z=80 且为整数0,1032546.t.s2015zmaxxxxxxxxx212121219 问题（0）x1=2.5，x2=2.5 z=87.5

8、 问题（1）x1=2，x2=2.67 z=83.3 问题（2）x1=3，x2=1.75 z=80 问题（3）x1=2，x2=2 z=70 问题（4）x1=1，x2=3 z=75 问题（5）x1=3.5，x2=1 z=72.5 问题（6）无可行解 2x13x12x23x21x22x2其求解框图如下：其求解框图如下：10 例题例题2 2：用分枝定界法求解下列混合整数规划问题：用分枝定界法求解下列混合整数规划问题 1231232312312313max3324432().323,0,ZxxxxxxxxAstxxxx x xx x并且为整数0,32323442.)(33max3213213232132

9、1xxxxxxxxxxxtsBxxxZ解：去掉整数性约束，变为松驰问题解：去掉整数性约束，变为松驰问题 0,32323442.)(33max32132132321321xxxxxxxxxxxtsBxxxZ11 用单纯形法求得问题（B）的最优解为：29max,310,3,316321Zxxx3161x6511xx和因为因为 为非整数，所以将约束为非整数，所以将约束 分别增加到（分别增加到（B B）中，构成两个分枝问题（）中，构成两个分枝问题（B B1 1）和（）和（B B2 2）。）。0,532323442.)(33max3211321323211321xxxxxxxxxxxxtsBxxxZ0,

10、632323442.)(33max3211321323212321xxxxxxxxxxxxtsBxxxZ15x 16x 1231232312312313max3324432().323,0,ZxxxxxxxxAstxxxx x xx x并且为整数12 51x61x43x33x问题B x1=16/3,x2=3,x3=10/3 z=29 问题B1 x1=5,x2=20/7,x3=23/7 z=194/7 问题B2 无可行解 问题B11 x1=5,x2=11/4,x3=3 z=107/4 问题B12 无可行解 13 分枝定界法应该注意的问题：分枝定界法应该注意的问题：上述两个例题的求解过程遵循了以下

11、分枝定界的原则：上述两个例题的求解过程遵循了以下分枝定界的原则：（1 1）每个松弛问题的最优值均是相应整数规划问题最优）每个松弛问题的最优值均是相应整数规划问题最优值的上界。值的上界。（2 2）在求解子问题的松弛问题时，）在求解子问题的松弛问题时，若松弛问题无可行解，则相应的子问题也无可行解，舍若松弛问题无可行解，则相应的子问题也无可行解，舍弃不再分枝。弃不再分枝。若松弛问题的解满足整数性约束，则此解为相应子问题若松弛问题的解满足整数性约束，则此解为相应子问题的最优解，此时不分枝。如果目标函数值大于目前的下界的最优解，此时不分枝。如果目标函数值大于目前的下界值，则修改下界值。值，则修改下界值。

12、如果松弛问题的解不满足整数性约束，但目标函数值不如果松弛问题的解不满足整数性约束，但目标函数值不大于目前的下界值，则不再分枝。大于目前的下界值，则不再分枝。若松弛问题的解不满足整数性约束，但目标函数值大于若松弛问题的解不满足整数性约束，但目标函数值大于目前的下界值，则对相应的子问题需进一步分枝。目前的下界值，则对相应的子问题需进一步分枝。14 2 2、0 0-1 1整数规划的特殊求解整数规划的特殊求解 对于对于0 0-1 1整数规划，由于决策变量只取整数规划，由于决策变量只取0 0，1 1两个值，两个值，除了能用一般整数规划的求解方法除了能用一般整数规划的求解方法分枝定界法求解外，分枝定界法求

13、解外，还有其特殊的解法。下面介绍求解还有其特殊的解法。下面介绍求解0 0-1 1规划的完全枚举法规划的完全枚举法和隐枚举法。和隐枚举法。一、完全枚举法一、完全枚举法 解解0 0-1 1规划时，一种很自然的想法是检查变量取规划时，一种很自然的想法是检查变量取0 0或或1 1的每一个组合，比较目标函数值的大小以求得最优解。的每一个组合，比较目标函数值的大小以求得最优解。例题例题3 3 用完全枚举法求解0-1规划问题 1231231231223123max3252244.346,01Zxxxxxxxxxstxxxxx xx或1231231231223123max3252244.346,01Zxxxx

14、xxxxxstxxxxx x x或15 解 约束 Z（0，0，0）0 0 0 0 0（0，0，1）-1 1 0 1 5（0，1，0）2 4 1 4-2（0，1，1）1 5*1 5 3（1，0，0）1 1 1 0 3（1，0，1）0 2 1 1 8（1，1，0）3*5*2 4 1（1，1，1）2 6*2 5 6 解：解：123,x x x共有23=8种不同的组合，各种组合下目 标函数及各约束条件左端的值列于下表中 上表中标注“上表中标注“*”的，表示相应的组合不满足该约束条件，”的，表示相应的组合不满足该约束条件，可知相应的可行解为（可知相应的可行解为（0 0，0 0，0 0）、（）、（0 0，

15、0 0，1 1）、（）、（0 0，1 1，0 0）、（）、（1 1、0 0、0 0）、（）、（1 1、0 0、1 1），最优值为），最优值为8 8，最优解为，最优解为（1 1，0 0，1 1）。）。16 0 0-1 1规划的隐枚举法是一种特殊的分枝定界法规划的隐枚举法是一种特殊的分枝定界法，其基本其基本思想是利用变量只能为思想是利用变量只能为0 0或或1 1两个值的特性两个值的特性，进行分枝定界进行分枝定界，以减少枚举而达到求出最优解之目的以减少枚举而达到求出最优解之目的。该法适用于任何该法适用于任何0 0-1 1规划问题的求解规划问题的求解，包括指派问题包括指派问题。二、二、0 0-1 1规

16、划的隐枚举法规划的隐枚举法 隐枚举法首先要将问题化为规范形。隐枚举法首先要将问题化为规范形。（1 1）0 0-1 1规划的规范形为规划的规范形为 )n,.,2,1j(10)m.,2,1i()0(smaxxbxacxcjn1jijijjn1jjj或其中所有的17（2 2）化规范形的方法：）化规范形的方法：1 1）如果目标函数为求极小值，则对目标函数两边乘以）如果目标函数为求极小值，则对目标函数两边乘以-1 1，化为求极大值；化为求极大值；2 2）若目标函数中某变量）若目标函数中某变量x xj j的系数的系数c cj j00，则令，则令x xj j=1=1-y yj j 3 3）如果约束条件是“）

17、如果约束条件是“”形，则可两边乘”形，则可两边乘-1 1，改为“，改为“”形；形；4 4）若某个约束条件为“）若某个约束条件为“=”=”形，则化为两个“形，则化为两个“”的不等”的不等式式,如如 n1jijijn1jijijn1jijijbxabxabxa可化成18（3 3）隐枚举法的基本思想）隐枚举法的基本思想 （1 1）首先令全部变量取）首先令全部变量取0 0（因为目标函数的系数全非正，（因为目标函数的系数全非正，此时，相应的目标函数值此时，相应的目标函数值Z=0Z=0就是上界）。就是上界）。如果此解可行，如果此解可行，则为最优解，计算终止；则为最优解，计算终止；（2 2）否则，有选择地指

18、定某个变为）否则，有选择地指定某个变为0 0或或1 1，并把它们固定下，并把它们固定下来（称为固定变量），将问题分枝成两个子问题。来（称为固定变量），将问题分枝成两个子问题。（3 3）继续分别对它们进行检验，即对未被固定取值的变量）继续分别对它们进行检验，即对未被固定取值的变量（称为自由变量），令其全部为（称为自由变量），令其全部为0 0，检查是否可行。如果可，检查是否可行。如果可行，则它们与固定变量所组成的解就是原问题目前最好的可行，则它们与固定变量所组成的解就是原问题目前最好的可行解（不一定是最优解），不再分枝，其相应的目标函数值行解（不一定是最优解），不再分枝，其相应的目标函数值就是原问

19、题的一个下界；就是原问题的一个下界；（4）否则，在余下的自由变量中，继续上述过程。经过检否则，在余下的自由变量中，继续上述过程。经过检验，或者停止分枝，修改下界，或者有选择地将某个自由验，或者停止分枝，修改下界，或者有选择地将某个自由变量，令其为变量，令其为0 0或或1 1，将子问题再分枝。如此下去，直到所，将子问题再分枝。如此下去，直到所有的子问题停止分枝，或没有自由变量止，并以最大下界有的子问题停止分枝，或没有自由变量止，并以最大下界对应的可行解为最优解。对应的可行解为最优解。)5.,2,1j(105242845723.t.s435211zmaxyyyyyyyyyyyyyyyyj54321

20、5432154321或19 例题例题4 4 用隐枚举法求解下列用隐枚举法求解下列0 0-1 1规划规划 )5.,2,1j(100242645723.t.s4352zmaxxxxxxxxxxxxxxxxxj543215432154321或解：令解：令x x1 1=1=1-y y1 1,x,x3 3=1=1-y y3 3,x,x5 5=1=1-y y5 5,x,x2 2=y=y2 2,x,x4 4=y=y4 4化为规范形得：化为规范形得：20)5.,2,1j(105242845723.t.s435211zmaxyyyyyyyyyyyyyyyyj543215432154321或其求解过程如下图所示：

21、y4=0 y5=1 0 1 2 3 4 5 6 7 8 10 9 11 12 13 14 Z=11 y3=1 y3=0 y4=1 y5=1 y5=0 y2=1 y2=0 y4=0 y4=1 y5=0 y1=0 y1=1 可行解z=3 可行解z=1 可行解z=2 不可行子域 不可行子域 可行解z=6 可行解z=2 不可行子域 由此可知，最优解为由此可知，最优解为x x3 3=x=x4 4=x=x5 5=1,x=1,x1 1=x=x2 2=0,maxz=6=0,maxz=6 21 练习练习1 1：用隐枚举法求解下列：用隐枚举法求解下列0 01 1规划问题：规划问题：1234512345123451

22、2345max567893223220.3201(1,2,3,4,5)jZxxxxxxxxxxxxxxxstxxxxxxj或12345123451234512345max35567893203223.3101(1,2,3,4,5)jZyyyyyyyyyyyyyyystyyyyyyj或解：首先化为规范型：解：首先化为规范型：12345123451234512345max35567893203223.3101(1,2,3,4,5)jZyyyyyyyyyyyyyyystyyyyyyj或05432 yyyy1y22 隐枚举法求解如下：隐枚举法求解如下：最优解为：即 3505432 Zmax,xxxx1x 107325732462562416101732132132132321或,xxxxxxxxxxxx.t.sxxxjmaxZ1 1y23 练习练习2 2：用隐枚举法求解下列：用隐枚举法求解下列0 01 1规划问题：规划问题：化为规范型如下：10332523242250241610174332132132132321或,yyyyyyyyyyyy.t.syyjymaxZ0 Z=43 1 2 0 1yZ=26 1 3y0 3yZ=27 3 0 2y不可行不可行区域区域 不可行不可行区域区域 1 2y最优解为：x1=1,x2=1,x3=0,maxZ=27 24 敬请指教！谢谢！