第四章第四章 整数规划与分配问题整数规划与分配问题数学模型割平面法分枝定界法0-1整数规划分配问题整数规划整数规划Integer Linear ProgrammingInteger Linear Programming简述简述LP虽然用途广泛，但经常地，客观上要求 L.P.最优解中不能含有非整数值（如股票的购买之解答），整数规划就是专门用来求解这类问题的有效工具重重点点掌掌握握：0-1 规划灵活应用、分枝定界法。提出问题提出问题某厂生产A1，A2两种品牌电视，用B1，B2两种原料，具体数据如下，求如何安排生产使利润最大整数规划整数规划数学模型数学模型若所有若所有 xj 的解为整数，称为纯整数规划的解为整数，称为纯整数规划pure integer linear programming若部分若部分 xj 的解为整数，称为混合整数规划的解为整数，称为混合整数规划mixed integer linear programming若若xj 只取只取0或或1，成为，成为0-1整数规划整数规划zero-one integer linear programming松弛问题松弛问题整数规划整数规划整数规划的最优解不会优于其松弛问题的最优解整数规划的最优解不会优于其松弛问题的最优解注 释最优解不一定在顶点上达到最优解不一定在顶点上达到最优解不一定是松弛问题最优解的邻近整最优解不一定是松弛问题最优解的邻近整数解数解整数可行解远多于顶点，枚举法不可取整数可行解远多于顶点，枚举法不可取整数规划问题的求解方法整数规划问题的求解方法整数规划问题的求解方法整数规划问题的求解方法分枝定界法分枝定界法branch and bound method 分枝定界法是一种隐枚举方法（分枝定界法是一种隐枚举方法（implicit enumeration）或部分或部分枚举方法，是枚举方法基础上的改进，几乎所有的计算机计算都用枚举方法，是枚举方法基础上的改进，几乎所有的计算机计算都用此算法。其关键是分支和定界。此算法。其关键是分支和定界。例例 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0 X1 ， X2 取整数取整数.6分支定界法分支定界法思路与解题步骤思路与解题步骤只解松弛问题只解松弛问题1、在全部可行域上解松弛问题、在全部可行域上解松弛问题若松弛问题最优解为整数解，则其也是整数规划的最若松弛问题最优解为整数解，则其也是整数规划的最优解优解2、分枝过程、分枝过程若松弛问题最优解中某个若松弛问题最优解中某个 xk=bk 不是整数，令不是整数，令 bk 为为 bk 的整数部分的整数部分构造两个新的约束条件构造两个新的约束条件 xk bk 和和 xk bk +1，分别分别加于原松弛问题，形成两个新的整数规划加于原松弛问题，形成两个新的整数规划3、求解分枝的松弛问题、求解分枝的松弛问题 定界过程定界过程设两个分枝的松弛问题分别为问题设两个分枝的松弛问题分别为问题 1 和问题和问题 2 ，它们，它们的最优解有如下情况的最优解有如下情况 整数规划整数规划分支问题解可能出现的情况分支问题解可能出现的情况情况情况 2, 4, 5 找到最优解找到最优解情况情况 3 在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况 6 问题问题 1 的整数解作为的整数解作为界界被保留，用于以后与问题被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况的后续分枝所得到的解进行比较，结论如情况 4或或5整数规划整数规划分支定界法图解整数规划分支定界法图解整数规划分支定界法图解整数规划分支定界法图解整数规划 松弛问题松弛问题 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0该整数规划松弛问题的解为：该整数规划松弛问题的解为：（X1 ，X2 ）=（3/2 ,10/3）Z1 = 29/614X1 + 9X2 51- 6X1 + 3X2 151/141/39整数规划整数规划 Integer ProgrammingInteger Programming（IPIP）分支定界法图解整数规划分支定界法图解整数规划松弛问题松弛问题 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0（3/2 ，10/3）Z1 = 29/6B1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0B2 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 1 X1 ， X2 0B2：解解（1,7/3 ）Z21 = 17/3B1：解解（2,23/9 ）Z11 = 41/912B1B210整数规划整数规划 Integer ProgrammingInteger Programming（IPIP）整数规划问题的求解方法整数规划问题的求解方法分支定界法图解整数规划分支定界法图解整数规划（3/2 ,10/3）Z1 = 29/6B1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0B2：解解（1,7/3 ）Z21 = 17/3B1：解解（2,23/9 ）Z11 = 41/9B11 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 3 X1 ， X2 0B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0B12：解解（33/14,2 ）Z12 = 61/141 2X=2X=311整数规划整数规划 Integer ProgrammingInteger Programming（IPIP）整数规划问题的求解方法整数规划问题的求解方法分支定界法图解整数规划分支定界法图解整数规划（3/2 ，10/3）Z1 = 29/6B2：解解（1,7/3 ）Z21 = 17/3B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0B12：解解（33/14,2 ）Z12 = 61/14B121 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 3 X2 2 X1 ， X2 0B122 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0B121：解解（3，1 ）Z121 = 4B122：解解（2，2 ）Z122 = 4B1：解解（2，23/9 ）Z11 = 41/9 1 2 312割平面法割平面法割平面法割平面法cutting plane approachcutting plane approach割平面法求解整数规划问题时，若其松驰问题的最优解割平面法求解整数规划问题时，若其松驰问题的最优解 X* 不满足不满足整数要求时，则从整数要求时，则从 X* 的非整分量中选取一个，用以构造一个线性的非整分量中选取一个，用以构造一个线性约束条件（约束条件（Gomory 割平面），将其加入原松驰问题中，形成一个割平面），将其加入原松驰问题中，形成一个新的线性规划，然后求解之。其关键在于新增加的这个线性约束条新的线性规划，然后求解之。其关键在于新增加的这个线性约束条件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切割掉了，而割掉了，而不会切割掉问题的任何整数解不会切割掉问题的任何整数解。13整数规划整数规划 Integer ProgrammingInteger Programming（IPIP）整数规划问题的求解方法整数规划问题的求解方法割平面法割平面法cutting plane approach 构造切割方程的步骤：构造切割方程的步骤：1、令、令 xi 是相应松驰问题的最优解中为非整数值的一个基变量，由是相应松驰问题的最优解中为非整数值的一个基变量，由单纯形表最终表得：单纯形表最终表得： xi + aik xk = bi （1 式）式）其中其中 i Q （Q 指基变量下标集）指基变量下标集） k K （K 指非基变量下标集）指非基变量下标集）14整数规划整数规划 Integer ProgrammingInteger Programming（IPIP）整数规划问题的求解方法整数规划问题的求解方法割平面法割平面法cutting plane approach 构造切割方程的步骤：构造切割方程的步骤：2、将、将 bi 和和 aik 都分解成整数部分都分解成整数部分 N （不超过不超过 b 的最大整数）与非负的最大整数）与非负真分数部分真分数部分 f 之和，即：之和，即： bi = Ni + fi ， 其中其中 0 fi 1 （2 式）式） aik = Nik + fik ，其中其中 0 fik 1例如：若例如：若 b = 2.35 ，则则 N = 2 ，f = 0.35； 若若 b = -1.45 ，则则 15整数规划整数规划 Integer ProgrammingInteger Programming（IPIP）割平面法割平面法cutting plane approach 构造切割方程的步骤：构造切割方程的步骤：2、将（、将（2 式）代入（式）代入（1 式）得：式）得： xi + Nik xk - Ni = fi - fik xk （3 式）式）3、提出变量为整（当然含非负）的条件：、提出变量为整（当然含非负）的条件：由于（由于（3 式）中等式左边需整，而式）中等式左边需整，而 0 fi 1 ，故有故有 fi - fik xk 0 （4 式）式）此即为所需切割方程。此即为所需切割方程。16整数规划整数规划 Integer ProgrammingInteger Programming（IPIP）割平面法割平面法cutting plane approach 构造切割方程的步骤：构造切割方程的步骤：（1）切割方程）切割方程 fi - fik xk 0 真正进行了切割，至少把非整数最优真正进行了切割，至少把非整数最优解这一点切割掉了。解这一点切割掉了。证明：（反证法）假设松驰问题的最优解证明：（反证法）假设松驰问题的最优解 X* 未被切割掉，则由未被切割掉，则由 fi - fik x*k 0， 又因为又因为 x*k = 0，（，（因因 x*k 为非基变量）为非基变量） 有有 fi 0 ，这与这与 fi 0 矛盾。矛盾。（2）不会切割掉任何整数解，因为切割方程是由变量为整的条件提）不会切割掉任何整数解，因为切割方程是由变量为整的条件提出的。出的。17整数规划整数规划 Integer ProgrammingInteger Programming（IPIP）割平面法割平面法cutting plane approach例例求解求解IP Max Z = X1 + X2 - X1 + X2 1 3X1 + X2 4 X1 ，X2 0 X1 ，X2 整数整数LP Max Z = X1 + X2 - X1 + X2 1 3X1 + X2 4 X1 ，X2 0181、求解、求解 LP 得到非整数最优解：得到非整数最优解： X =（3/4，7/4，0，0），），Max Z = 5/2求解步骤：求解步骤：19整数规划整数规划 Integer ProgrammingInteger Programming（IPIP）求解步骤求解步骤：2、构造切割方程：、构造切割方程： 由由 B 表表中的第中的第 2 个方程个方程 X2 + 3/4 X3 + 1/4 X4 = 7/4 有有 b2 = 7/4 = 1 + 3/4 a23 = 3/4 = 0 + 3/4 ， a24 =