运筹学[第五章整数规划]山东大学期末考试知识点复习.doc

山东大学 期末考试 知识点复习第五章 整数规划 1整数规划的特点 (1)整数规划：决策变量要求取整数的线性规划。 (2)整数规划可分为纯整数规划和混合整数规划。 (3)整数规划的可行域为离散点集。 2整数规划的建模步骤 整数规划模型的建立几乎与线性规划模型的建立完全一致，只是变量的部分或全体必须限制为整数。 3求解整数规划的常用方法 1)分支定界法 没有最大化的整数规划问题A，与它相应的线性规划问题为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作 ，而A的任意可行解的目标函数值将是z*的一个下界 ，分支定界法就是将B的可行域分成子区域的方法，逐步减小 和增大 ，最终求得z*。 将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。 (1)解与整数规划问题A相应的线性规划问题B，可能得到以下几种情况之一： B没有可行解，A也没有可行解，停止计算。 B有最优解，并符合问题A的整数条件，则此最优解即为A的最优解，停止计算。 B有最优解，但不符合A的整数条件，记它的目标函数值为 。(2)用观察法找问题A的一个整数可行解，求得其目标函数值，并记作 。以z*表示问题A的最优目标数值，则 z* 。 下面进行迭代。 分支，在B的最优解中任选一个不符合整数条件的变量xi，其值为bi。 构造两个约束条件 xjbj 和 xjbj+1 其中bj为不超过bj的最大整数。 将这两个约束条件分别加入问题B，求两个后继规划问题B1和B2。不考虑整数约束条件求解这两个后继问题。定界，以每个后继问题为一分支标明求解的结果。 第一步：先不考虑整数约束，变成一般的线性规划问题，用图解法或单纯形法求其最优解，记为 ) ； 第二步：若求得的最优解 ，刚好就是整数解，则该整数就是原整数规划的最优解，否则转下步；第三步：对原问题进行分支寻求整数最优解。 第四步：对上面两个子问题按照线性规划方法求最优解。若某个子问题的解是整数解，则停止该子问题的分支，并且把它的目标值与上一步求出的最优整数解相比较以决定取舍；否则，对该子问题继续进行分支。 第五步：重复第三、四步直至获得原问题最优整数解为止。2)割平面法 割平面法既可以求解纯整数规划，也可以用于求解混合整数规划。其基本思路与分支定界法类似，它也是在求解整数规划()的相应的线性规划(L)的基础上，不断增加新的约束，通过求解一系列线性规划问题，最终得到原问题(I)的整数最优解。但在此方法中，新约束的求法与分支定界法中不同，此外新增加的约束叫做割平面或切割方程，它使得由原可行域中切割掉一部分，此部分只包含非整数解，但不切割掉任何整数可行解。割平面法求解整数规划的求解步骤： (1)先不考虑整数条件，求解()相对应的线性规划问题(L)，与分支定界法步骤(1)一样，同样可得到三种结果之一。 (2)求一个切割方程：切割方程可由单纯形表的最终表中的任一个含有非整数基变量的等式约束演变而来，因此，切割方程不唯一。1令xi为相应的线性规划(L)的最优解中为分数值的一个基变量，由单纯形的最终表得到：其中iQ(Q表示构成基变量号码的集合)，kK(K表示构成非基变量号码的集合)。2将bi和aik都分解成整数部分N和非负真分数f之和，即而N为不超过b的最大整数，即N=b。并将代入，得3提出变量为整数的条件(当然还有非负条件)，由式左边看必须是整数，但右边因为0fi0，则令xj=1-yj替换xj，其中yj为01变量，于是变量yj在目标函数中的系数变成小于0。 如果约束条件是“”形式，则可两边乘以-1，改为“”的形式。如果约束条件中含有等式，则可将每个等式化成两个“”形式的不等式，例如 01规划的隐枚举法的基本思想是：首先令全部变量取0(因为目标函数的系数全非正，此时，相应的目标函数值s=0就是上界)。如果此解可行，则为最优解，计算终止；否则，选择某个变量为0或1，将问题