运筹学[第五章整数规划]山东大学期末考试知识点复习.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。
构造两个约束条件
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°提出变量为整数的条件(当然还有非负条件)，由③式左边看必须是整数，但右边因为0最优解，若(L1)得到的仍为非整数解，则返回步(2)，继续求第二个切割方程。
4．指派问题
(1)指派问题的特点。
把m项工作分派给n个人去做，既发挥各人特长又使效率最高。这是一类特殊0—1规划问题。
(2)求解方法——匈牙利法。
该方法由库思提出，他引用了匈牙利一位数学家的定理。
①指派问题的标准型。
目标为min；系数矩阵为方阵(即人数与工作数相等，或者说每项工作只能由一人来做，每个人只能做一项工作)且其所有元素均为非负。满足这两个条件的指派问题叫做标准型的指派问题。
②标准型指派问题的求解。
5．0—1规划问题
(1)一般形式。
0—1型整数规划是整数规划中的特殊情形，它的变量xi仅取0或1，它和一般整数规划的约束条件形式是一致的。
(2)求解方法——隐枚举法。
0—1规划常用隐枚举法和过滤法，都是利用变量只能取0或l两个值的特性。隐枚举法是一种特殊的分支定界法，它适用任何0—1规划问题的求解。但用隐枚举法要经过一些模型的变换。过滤法实际上就是隐枚举法的一个特殊情况，在计算的过程中确定一个过滤条件，不断地检验，由于0—1的特性，其工作量在维数不大的情况下也是可以很快完成的，但当维数很大时不可取。
要用隐枚举法，首先应将0—1规划化成以下规范形式：

①如果目标函数是求最小值，则对目标函数两边乘以-1，改求最大值。
②如果目标函数中某变量xj的系数cj>0，则令xj=1-yj替换xj，其中yj为0—1变量，于是变量yj在目标函数中的系数变成小于0。
③如果约束条件是“≥”形式，则可两边乘以-1，改为“≤”的形式。
④如果约束条件中含有等式，则可将每个等式化成两个“≤”形式的不等式，例如

0—1规划的隐枚举法的基本思想是：首先令全部变量取0(因为目标函数的系数全非正，此时，相应的目标函数值s=0就是上界)。如果此解可行，则为最优解，计算终止；否则，选择某个变量为0或1，将问题分析成两个子问题，继续分别对它们进行检验，即令没有被选择的变量全部为0，检查是否可行。如此下去，或者再分支，或者使所有的子问题停止分支，并以最大下界值对应的可行解为最优解。