整数规划问题的求解分析

经济管理学院《运筹学》结课论文整数规划问题的求解分析整数规划问题的求解分析摘要：整数规划是NP困难]1[的经典问题之一，本文讨论了整数规划问题中分支定界法与割平面法的基本原理和求解过程以及算法思想，当在决策变量和约束条件很多时,用常规的求解法效率很低，针对此种缺陷,提出了遗传算法，实现了快速解决整数规划的问题。关键词：整数规划；分支定界法；割平面法；遗传算法1引言整数规划(IP)]2[是运筹学领域里的一个重要分支,是规划论中研究决策变量取整数的一类较新、较特殊的线性规划，且大多数的组合优化问题都可以写成一个IP，如背包、旅行商、最短路、选址、分配和生产与存储计划问题等要求决策变量的取值为整数它的求解方法，目前来讲主要有割平面法、分枝定界法以及逐步完善的遗传算法。下面就它们的解法和差异加以讨论。2割平面法2.1割平面方法思想割平面法是由高莫瑞(REGomory)1958年提出的，故又称为Gomory的割平面法。它的基本思想是：不断增加线性约束条件(几何术语称为割平面)将原规划问题的可行域切割掉一部分，使其切割掉的部分只包含非整数解，没有切割掉任何整数可行解，直到切割后得到的可行域有一个整数坐标的极点恰好是问题的最优解为止。]3[2.2割平面方法步骤(1)先不考虑变量的取整约束，用单纯形法求解相应的线性规划问题，如果该问题没有可行解或最优解已是整数则停止，否则转下步。在求解相应的线性规划时，首先要将原问题的数学模型进行标准化。这里的“标准化”有两个含义：第一是将所有的不等式约束全部转化成等式约束，这是因为要采用单纯形表进行计算的缘故。第二是将整数规划中所有非整数系数全部转换成整数，这是出于构造“切割不等式”的需要。]4[(2)求一个“切割不等式”及添加到整数规划的约束条件中去，即对上述线性规划问题的可行域进行“切割”，然后返回步骤1。3分支定界法3.1分支定界法思想分枝定界法可用于解纯整数或混合的整数规划问题，由于这方法灵活且便于计算机求解,所以现在它已是解整数规划的重要方法。]5[设有最大化的整数规划问题A，与他相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的上界，记作Z；而A的任意可行解的目标函数值将是Z*的一个下界Z_。分枝定界法就是将B的可行域分成子区域(称为分枝)的方法。逐步减小Z和增大Z_,最终求到z*。3.2分支定界法步骤]5[第一步：先不考虑整数约束,变成一般线性规划问题，求出最优解，记为X*(0)；第二步：若X*(0)刚好是整数解，则该整数解就是原整数规划的最优解；否则，转入下一步；第三步：对原问题进行分枝寻求整数最优解。选取非整数解X*(0)的一个非整数分量x*i=bi，以该非整数分量的相邻整数[bi]和[bi]+1为边界将原问题分枝为两个子问题，并抛弃这两个整数之间的非整数区域：（1）在原线性规划模型中添加分枝约束xi≤[bi]，构成第一个子问题；（2）在原线性规划模型中添加分枝约束xi≥[bi]+1，构成第二个子问题；第四步：对上面两个子问题求出最优解。若某个子问题的解是整数解，则停止该子问题的分枝，并且把它的目标函数值与上一步求得的最优整数解对应的目标函数值比较以决定取舍；否则，对该子问题继续进行分枝。第五步：重复第三、第四步直至获得原问题最优整数解为止。其缺点为必须在每个节点解一个完整的线性规划。在大型问题中这将很费时，但在目前来讲，它在解决实践问题上还是最有效的，但不是说每个整数规划都能用它来解。请看下面的例子。求:“分枝”为整数规划最优解的出现创造条件，而“定界”则提高了搜索的效率。经验表明，优先选择较小的、不符合整数要求的变量进行分枝；并在可能的情况下，根据对实际问题的了解,事先选择一个合理的“界限”，可以更好地发挥分枝定界法的优点。此例具体解题过程如下图所示：4割平面法与分枝定界法比较综合前面所述,我们从它面的实质、解题步骤、适用对象解题算法等方面作了介绍，我们不能泛泛而谈谁优谁劣，各有千秋。4.1割平面法与分枝定界法思想]6[割平面法与分枝定界法它们的相同点都是对可行域进行切割，舍去一部分非整数解域，使剩下的子域包含原整数规划的所有可行域；所不同的是，割平面法剩下的子域仍然为一个，而分枝定界法剩下的是两枝。4.2割平面法与分支定界法对问题的结构割平面法对问题的结构以及求解结果都有较高要求，即要区分纯整数和混合整数问题，不同的类有不同的切割方程，而分枝定界法它可以对纯整数和混合整数问题直接使用。割平面法在添加相应割平面后要改变计算方法———用对偶单纯形法求解，而分枝定界法不需改变计算方法，便于计算机编程计算。割平面法在作切割后剩下的仍为一个子域，后继计算为一个较小子域上的整数规划，而分枝定界法在作切割后形成了两个分枝，后继计算便为两个较小子域上的整数规划，随着分枝增多，计算量较大。因此，当我们遇到一个较复杂的整数规划时，常常将两种方法结合起来使用，效果更好。5整数规划的遗传算法]7[5.1染色体编码方式基本遗传算法采用二进制编码方法。对于一般函数优化问题,由于其定义域一般为实数域,因此常采用如下形式的染色体编码方式:染色体(个体)X=(X1,X2,…,Xn)→对于整数规划问题，一部分变量定义域为数，一部分变量定义域为整数。对整数变量而言，较为合理的编码方式应采用二进制编码。染色体(个体)X=(X1，X2,…,Xr，Xr+1，…Xn)→X1X2…XnX1X2…XrBr+1…Bn其中X1，…，Xr为实数编码方式，而Bi(i=r+1，…，n)为对应于整数Xi(i=r+1，…，n)的二进制串编码。下面介绍一种整数的二进制串编码方法。设整数Xk(k=r+1，…，n)∈[0，Mk]，按如下算法对Mi进行分解：N0=0；X=Mk；p=0dop=p+1；Np=int[log2(x+1)]；x=x-2NP+1whilex0；显然,按上述算法产生的p个整数NJ(j=1,2,…,p)满足Mk=(2n1-1)+(2n2-1)+…+(2np-1)。即Mk可由p个位数分别为Nj(j=1,2，…，p)的二进制数相加而得到。因此,Xk可由(n1+n2+…+Np)个二进制串Bk表示。5.2适应值的定义及比例变换对问题(1)，采用如下的罚函数将其转换为无约束最优化问题：MinF(X)=f(x)+11))(,0max(miixg+α)(11xhmii其中α为大的正数目标函数对应的适应值采用如下的形式:Fitness=Fmax-Fij其中，Fij为第i代中第j个个体的目标函数值,Fmax为第i代中目标函数的最大值。5.3遗传算法的控制参数和变量5.3.1复制算子每当一个个体被选择杂交，它的期望拷贝数就减0.5，而当一个串被选择复制，它的期望拷贝数就减少；当一个个体的期望拷贝数降到0以下，这个个体就失却了被选择的机会。为保证算法的收敛性，采用最优选择的方法将父代中适应值最大的个体强制性地复制给子代。5.3.2杂交算子杂交算子采用线性组合与一点杂交相结合的方式,即如果个体Xs、Xt被选择杂交,则产生子代个体。5.3.3变异算子变异率Pm的大小与群体规模及染色体长度有关,根据笔者经验,一般取不超过10/N*L(其中N为群体规模,L为串长)为宜。变异算子采用非一致变异算子与单点变异相结合的变异方式。6总结算法对于只有部分变量取整数的混合整数规划问题,只需修改相应变量的整数限制即可求解，用现代进化算法求解传统的优化问题具有其独到的优势,遗传算法以其适应性广,无需背景知识,搜索能力强等优点被广泛应用于各类优化问题中并基于适应值来选择染色体,这就使得该算法不受搜索空间的限制性假设的约束,不必要求诸如连续、可导和凸性等假设,因而使得它在求解各类最优化问题时具有广泛的适应性。参考文献[1]马振华,陈景良,刘坤林,等.现代应用数学手册,运筹学与最优化理论卷[M].北京:清华大学出版社,1999.[2]宁伟华,陈绍顺.求解整数规划的混合遗传算法[J].空军工程大学学报,2004,12(06):80-83.[3]刘勇，康立山，陈毓屏.非数值并行算法——遗传算法[M].北京:科学出版社,1997.[4]熊义杰.解ILP的割平面法的收敛性问题[J].运筹与管理，2003,12（02）：36-38.[5]苟格.整数规划中的割平面法与分枝定界法比较[J].达县师范高等专科学校学报，2005,03（02）：18-21.[6]连海峰.整数规划中的割平面法与分枝定界法研究[J].数学的实践与认识，2011,06（11）：81-90.[7]陈永忠.整数规划的遗传算法[J].交通部上海船舶运输科学研究所学报，2000,06（23）:42-26.