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