第4章整数规划与分配问题--研究生

1、第第4章章 整数规划整数规划1 整数规划的特点及作用整数规划的特点及作用 2 分枝界定法分枝界定法 3 割平面法割平面法2纯整数规划：纯整数规划：在整数规划中，如果所有的变量都为非负整在整数规划中，如果所有的变量都为非负整 数，则称为数，则称为纯整数规划问题纯整数规划问题；混合整数规划：混合整数规划：如果有一部分变量为非负整数，则称之为如果有一部分变量为非负整数，则称之为 混合整数规划问题混合整数规划问题。0-10-1变量：变量：在整数规划中，如果变量的取值只限于在整数规划中，如果变量的取值只限于0 0和和1 1，这，这 样的变量我们称之为样的变量我们称之为0-10-1变量变量。0-10-1规

2、划：规划：在整数规划问题中，如果所有的变量都为在整数规划问题中，如果所有的变量都为0-10-1变变 量，则称之为量，则称之为0-10-1规划规划。1 整数规划的有关概念及特点整数规划的有关概念及特点一、一、 概念概念整数规划：整数规划： 要求决策变量取整数值的规划问题。要求决策变量取整数值的规划问题。 （线性整数规划、非线性整数规划等）（线性整数规划、非线性整数规划等）3求整数解的线性规划问题，不是用求整数解的线性规划问题，不是用四舍五入四舍五入法或法或去尾法去尾法对对性规划的非整数解加以处理就能解决的，用性规划的非整数解加以处理就能解决的，用枚举法枚举法又往往又往往会计算量太大，所以要用整数

3、规划的特定方法加以解决。会计算量太大，所以要用整数规划的特定方法加以解决。例：例： 求解下列整数规划：求解下列整数规划：二、二、 整数规划的求解特点整数规划的求解特点并取整数, 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz1 整数规划的有关概念及特点整数规划的有关概念及特点41x2x143221 xx5 . 45 . 021xx2123xxz)5 . 2,25. 3(分析：分析： 若当作一般线性规划求若当作一般线性规划求解，图解法的结果如下。解，图解法的结果如下。1、非整数规划、非整数规划最优解最优解 显然不是整数规划的可行解。显然不是整数规划的可行解。2

4、、四舍五入后的结果四舍五入后的结果 也不是整数规划的可行解。也不是整数规划的可行解。)5 . 2,25. 3()3, 3(3、可行解是阴影区可行解是阴影区域交叉点，可比较这域交叉点，可比较这些点对应的函数值，些点对应的函数值，找出最优。找出最优。) 1, 4(1 整数规划的有关概念及特点整数规划的有关概念及特点第第4章章 整数规划整数规划1 整数规划的特点及作用整数规划的特点及作用 2 分枝界定法分枝界定法 3 割平面法割平面法6分枝定界法分枝定界法是求解整数规划的一种常用的有效的方法，它是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问既能解决纯整数规

5、划的问题，又能解决混合整数规划的问题。题。 大多数求解整数规划的商用软件就是基于分枝定界法编大多数求解整数规划的商用软件就是基于分枝定界法编制而成的。制而成的。下面举例来说明分枝定界法的思想和步骤。下面举例来说明分枝定界法的思想和步骤。2 分枝定界法分枝定界法7性质性质 求求MAXMAX的问题的问题：整数规划的最优目标函数值整数规划的最优目标函数值小于或小于或等于等于相应的线性规划的最优目标函数值；相应的线性规划的最优目标函数值； 求求MINMIN的问题：的问题：整数规划的最优目标函数值整数规划的最优目标函数值大于或大于或等于等于相应的线性规划的最优目标函数值。相应的线性规划的最优目标函数值。

6、1、求解整数规划相应的一般线性规划问题（即先去掉整数、求解整数规划相应的一般线性规划问题（即先去掉整数约束）。约束）。 易知：易知：整数规划的可行域（小）包含于线性规划的可行整数规划的可行域（小）包含于线性规划的可行域域 (大）。大）。 若线性规划的最优解恰是整数解，则其就是整数规划的若线性规划的最优解恰是整数解，则其就是整数规划的最优解。否则该最优解，是整数规划最优解的上界或下界。最优解。否则该最优解，是整数规划最优解的上界或下界。2 分枝定界法分枝定界法8例：例： 求解下列整数规划：求解下列整数规划：并取整数, 0 x,x5 . 4x5 . 0 x14x3x2t . sx2x3zmax21

7、2121210,5 . 45 . 01432.23max21212121xxxxxxtsxxz解：解：1 1、解对应的线性规划：、解对应的线性规划：其最优解为其最优解为 ，显然不是整数规划的可行显然不是整数规划的可行解。解。)5 . 2,25. 3(L0：75.140z2 分枝定界法分枝定界法92 2、分枝与定界：分枝与定界： 将对应的线性规划问题分解成几个子问题，每个子问将对应的线性规划问题分解成几个子问题，每个子问题就是一分枝，而所有子问题的解集之和要包含原整数规题就是一分枝，而所有子问题的解集之和要包含原整数规划的解集。划的解集。 求解每一分枝子问题：求解每一分枝子问题： 若其最优解满足

8、整数约束，则它就是原问题的一个可行若其最优解满足整数约束，则它就是原问题的一个可行解（不一定是最优）；否则，就是该枝的上界或下界。解（不一定是最优）；否则，就是该枝的上界或下界。 若所有分支的最优解都不满足整数条件（即不是原问题若所有分支的最优解都不满足整数条件（即不是原问题的可行解），则选取一个边界值最优的分支继续分解，直的可行解），则选取一个边界值最优的分支继续分解，直至找到一个原问题的可行解。至找到一个原问题的可行解。 若在同一级分枝中同时出现两个以上的原问题可行解，若在同一级分枝中同时出现两个以上的原问题可行解，则保留目标值最优的一个，其余不再考虑。则保留目标值最优的一个，其余不再考虑

9、。从各分枝中找原问题可行解的目的是为下一步的比较与剪枝。从各分枝中找原问题可行解的目的是为下一步的比较与剪枝。2 分枝定界法分枝定界法10将上述线性规划问题分为两枝，并求解。将上述线性规划问题分为两枝，并求解。5 .14, 2, 5 . 3121zxx解得5 .13, 3, 5 . 2221zxx解得L1：L2：0,25 . 45 . 01432.23max212212121xxxxxxxtsxxz0,35 . 45 . 01432.23max212212121xxxxxxxtsxxz显然两个分枝均非整数可行解，选边界值较大的显然两个分枝均非整数可行解，选边界值较大的L L1 1继续分继续分枝

10、。枝。 2 分枝定界法分枝定界法11将将L1分为两枝，并求解。分为两枝，并求解。13, 2, 3121zxx解得14, 1, 4221zxx解得L11：L12：0,325 . 45 . 01432.23max2112212121xxxxxxxxtsxxz两个分枝均是整数可行解，保留目标值较大的两个分枝均是整数可行解，保留目标值较大的L L1212。 0,425 . 45 . 01432.23max2112212121xxxxxxxxtsxxz2 分枝定界法分枝定界法123 3、比较与剪枝比较与剪枝 将各子问题的边界值与保留下的整数可行解对应的目将各子问题的边界值与保留下的整数可行解对应的目标值

11、比较，将边界值劣于可行解的分支减剪去。标值比较，将边界值劣于可行解的分支减剪去。 若比较剪枝后，只剩下所保留的整数可行解，则该解若比较剪枝后，只剩下所保留的整数可行解，则该解就是原整数规划的最优解；否则选取边界值最大的一个分就是原整数规划的最优解；否则选取边界值最大的一个分枝继续分解，在其后的过程中出现新的整数可行解时，则枝继续分解，在其后的过程中出现新的整数可行解时，则与原可行解比较，保留较优的一个，重复第三步。与原可行解比较，保留较优的一个，重复第三步。2 分枝定界法分枝定界法13L0：X22X23X13X14用图表示上例的求解过程与求解结果用图表示上例的求解过程与求解结果75.14, 5

12、 . 2,25. 3121zxx5 .14, 2, 5 . 3121zxx5 .13, 3, 5 . 2221zxx13, 2, 3121zxx14, 1, 4221zxx2 分枝定界法分枝定界法第第4章章 整数规划整数规划1 整数规划的特点及作用整数规划的特点及作用 2 分枝界定法分枝界定法 3 割平面法割平面法15一、一、 基本思想基本思想 在整数规划的松弛问题中，依次引进新的约束条件在整数规划的松弛问题中，依次引进新的约束条件（割平面），使问题的可行域逐步减小，但每次割去（割平面），使问题的可行域逐步减小，但每次割去的只是部分非整数解，直到使问题的目标函数值达到的只是部分非整数解，直到使

13、问题的目标函数值达到最优的整数点成为缩小后的可行域的一个顶点，这样最优的整数点成为缩小后的可行域的一个顶点，这样就可以用线性规划的方法求得整数最优解。就可以用线性规划的方法求得整数最优解。3 割平面法割平面法16例：例： 求解下列整数规划：求解下列整数规划：并取整数, 0,5 . 45 . 01432.23max21212121xxxxxxtsxxz0,921432.23max2142132121xxxxxxxxtsxxz解：解：1 1、解对应的线性规划（松弛问题），并将约束条件的系解对应的线性规划（松弛问题），并将约束条件的系数均化为整数：数均化为整数：3 割平面法割平面法17加入松弛变量后

14、求解，得最终单纯形表：加入松弛变量后求解，得最终单纯形表：25/2011/2-1/2313/410-1/43/400-1/4-5/41x4x3x1x2x2xj如果上述求解结果是整数解，则结束；否则转下一步；如果上述求解结果是整数解，则结束；否则转下一步；2 2、找出非整数解中分数部分最大的一个基变量，并将该行找出非整数解中分数部分最大的一个基变量，并将该行对应的约束方程所有常数（系数及常数项）分解成一个整数对应的约束方程所有常数（系数及常数项）分解成一个整数与一个正分数之和；将所有分式项移到等式右端。与一个正分数之和；将所有分式项移到等式右端。例如上例，取第一行约束例如上例，取第一行约束 3

15、割平面法割平面法1843424324322121212212)211(21252121xxxxxxxxxx易知，左端为整数，要是等式成立，右端也必为整数，且易知，左端为整数，要是等式成立，右端也必为整数，且02121211212121214343xxxx将将 代入上式，得代入上式，得214213293214xxxxxx112221 xx3 割平面法割平面法191x2x143221 xx5 . 45 . 021xx2123xxz)5 . 2,25. 3() 1, 4(112221 xx这就是一个割平面。将这就是一个割平面。将其添加到原约束中，得其添加到原约束中，得到新的可行域如图所示。到新的可行

16、域如图所示。割去的只是部分非整数割去的只是部分非整数解。解。112221 xx3 割平面法割平面法203 3、将新的约束添加到原问题中，得到一个新的线性规划问将新的约束添加到原问题中，得到一个新的线性规划问题，求解此问题，可用灵敏度分析的方法。题，求解此问题，可用灵敏度分析的方法。4 4、重复上述的重复上述的1-31-3步，直至求出整数最优解。步，直至求出整数最优解。25/2011/2-1/20313/410-1/43/400-1/200-1/2-1/2100-1/4-5/40212121021212154343xxxxx将将 反应到最终表中，得反应到最终表中，得1x4x3x1x2x2xj5x5x3 割平面法割平面法21运用对偶单纯形法，解得运用对偶单纯形法，解得22010-11/231001-1/2010011-2000-1-1/21x4x3x1x2x2xj3x5x213此解仍非整数解，将基变量此解仍非整数解，将基变量 对应的约束分解为：对应的约束分解为： 1x55415412121321321xxxxxxx得到新的约束得到新的约束 212102121655xxx3 割平面法割平面法2222010-11/2031001-1/2