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

第五章 整数规划 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。 构造两个约束条件 xj≤[bj] ① 和 xj≥[bj]+1 ② 其中[bj]为不超过bj的最大整数。 将这两个约束条件分别加入问题B，求两个后继规划问题B1和B2。不考虑整数约束条件求解这两个后继问题。 定界，以每个后继问题为一分支标明求解的结果。 第一步：先不考虑整数约束，变成一般的线性规划问题，用图解法或单纯形法求其最优解，记为 ) ； 第二步：若求得的最优解 ，刚好就是整数解，则该整数就是原整数规划的最优解，否则转下步； 第三步：对原问题进行分支寻求整数最优解。 第四步：对上面两个子问题按照线性规划方法求最优解。若某个子问题的解是整数解，则停止该子问题的分支，并且把它的目标值与上一步求出的最优整数解相比较以决定取舍；否则，对该子问题继续进行分支。 第五步：重复第三、四步直至获得原问题最优整数解为止。 2)割平面法 割平面法既可以求解纯整数规划，也可以用于求解混合整数规划。其基本思路与分支定界法类似，它也是在求解整数规划(Ⅰ)的相应的线性规划(L)的基础上，不断增加新的约束，通过求解一系列线性规划问题，最终得到原问题(I)的整数最优解。但在此方法中，新约束的求法与分支定界法中不同，此外新增加的约束叫做割平面或切割方程，它使得由原可行域中切割掉一部分，此部分只包含非整数解，但不切割掉任何整数可行解。 割平面法求解整数规划的求解步骤： (1)先不考虑整数条件，求解(Ⅰ)相对应的线性规划问题(L)，与分支定界法步骤(1)一样，同样可得到三种结果之一。 (2)求一个切割方程：切割方程可由单纯形表的最终表中的任一个含有非整数基变量的等式约束演变而来，因此，切割方程不唯一。 1°令xi为相应的线性规划(L)的最优解中为分数值的一个基变量，由单纯形的最终表得到： 其中i∈Q(Q表示构成基变量号码的集合)，k∈K(K表示构成非基变量号码的集合)。 2°将bi和aik都分解成整数部分N和非负真分数f之和，即 而N为不超过b的最大整数，即N=[b]。并将①代入②，得 3°提出变量为整数的条件(当然还有非负条件)，由③式左边看必须是整数，但右边因为0fi1，所以不能为正，故得切割方程 (3)在(L)的基础上，增加第一个切割方程，即构成线性规划问题(L1)，用单纯形法或对偶单纯形法求最优解，若(L1)得到的仍为非整数解，则返回步(2)，继续求第二个切割方程。 4．指派问题 (1)指派问题的特点。 把m项工作分派给n个人去做，既发挥各人特长又使效率最高。这是一类特殊0—1规划问题。 (2)求解方法——匈牙利法。 该方法由库思提出，他引用了匈牙利一位数学家的定理。 ①指派问题的标准型。 目标为min；系数矩阵为方阵(即人数与工作数相等，或者说每项工作只能由一人来做，每个人只能做一项工作)且其所有元素均为非负。满足这两个条件的指派问题叫做标准型的指派问题。 ②标