教学材料《运筹学》-第4章

4.2整数规划求解方法4.2.1舍入化整与穷举整数舍入化整法采用类似“四舍五入”的方法对整数规划问题进行求解。对于【例4-1】的模型，可以用舍入化整法进行求解，步骤如下:(1)求出对应松弛问题的最优解。所谓松弛问题是指整数规划决策变量解除整数限制后的线性规划问题(某一整数规划对应的线性规划问题称为松弛问题，即不考虑决策变量整数限制的整数规划问题)。因只有两个变量，故可采用图解法进行求解，结果如图4-1所示。(2)对松弛问题的最优解做“四舍五入”处理。(3)依次对变量取值。下一页返回4.2整数规划求解方法从数学模型上看，整数规划是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解。但实际上两者却有很大的不同，通过舍入得到的整数解也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。因此，舍入化整法并不是对整数规划问题对应松弛问题的最优解进行“四舍五入”就可以获得。穷举整数法是找出松弛问题所有的整数解并通过比较函数值获得最优解的方法。4.2.2分枝定界法分枝(支)定界法(BranchandBound)是求解整数规划问题的常用方法。上一页下一页返回4.2整数规划求解方法这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。分枝定界法用于求解整数规划问题的基本思路是:在松弛问题的可行域中寻找使目标函数值达到最优的整数解，这种思路的依据是下面定理。定理:对于某一求max(或min)的整数规划问题，其目标函数最优值不超过(低于)其松弛问题的目标函数最优值。4.2.3割平面法割平面法是1958年由美国学者高莫利(R.E.GoMory)提出的求解全整数规划的一种比较简单的方法，其基本思想和分枝定界法大致相同，即先不考虑变量的取整约束，用单纯形法求解相应的线性规划。上一页下一页返回4.2整数规划求解方法如果所得的最优解为整数解，则停止计算。如果最优解不是整数解，那么分枝定界法是任取一个取分数值的变量()将原整数规划分成两枝，其实质是用两个垂直于坐标轴的平行平面和将原可行域R分成两个可行域R1和R2，并将两个平行平面之间的不含有整数解的那一部分可行域去掉，以缩小可行域。而割平面法是用一张平面(不一定垂直于某个坐标轴)，将含有最优解的点但不含任何整数可行解的那一部分可行域切割掉，通过在原整数规划基础上增加适当的线性不等式约束来实现，该线性不等式约束称之为切割不等式，当切割不等式取等号时，叫作割平面。上一页下一页返回4.2整数规划求解方法然后继续求解这个新的整数规划问题，在这个新的整数规划的基础上增加适当的线性不等式约束，直至求得最优整数解为止。也就是说，通过构造一系列平面来切割不含有任何整数可行解的部分，最终获得一个具有整数坐标的顶点的可行域，而该顶点恰好是原整数规划的最优解。割平面法求解全整数规划问题的关键在于，如何构造切割不等式，使增加该约束后能达到真正的切割?而且没有切割掉任何整数可行解。割平面法的基本步骤如下:

(1)先不考虑变量的整数限制，用单纯形法求解相应的松弛问题，如果该问题没有可行解或最优解已是整数，则停止，否则进行下一步骤。上一页下一页返回4.2整数规划求解方法在求解松弛问题时，首先要将原问题的数学模型标准化，然后将整数规划中所有非整数系数全部转换成整数，构造“切割不等式”(割平面约束)。(2)在松弛问题的约束条件中添加“切割不等式”，即对上述线性规划问题的可行域进行“切割”，然后返回步骤(1)，直至获得最优整数解。割平面法求解步骤总结:(1)用单纯形法求解松弛问题;(2)在松弛问题最终单纯形表中任选一约束条件，来构造新的约束条件(割平面约束);上一页下一页返回4.2整数规划求解方法(3)将新的约束条件加入最终单纯形表中，直至求得最优整数解。4.2.4隐枚举法在线性规划问题的模型中，当变量的取值只能是“0”或“1”时，称之为“0-1整数规划问题，’(或0-1规划问题)。对于0-1整数规划问题，有一种极其简单的解法，就是将变量取值为0或1的所有组合列出，然后分别代入目标函数，选出其中能使目标函数最优化的组合，即为最优解。如果变量较少时(如不超过3个)，是不难枚举的，但是当变量较多时，可能解将呈指数剧增，靠经验枚举求解难以做到快捷有效。上一页下一页返回4.2整数规划求解方法为解决0-1规划的求解问题，BalasE在196年提出了隐枚举法，目前隐枚举法(ImplicitEnumerationAlgorithm)已经成为求解“0-1整数规划问题”的常见方法，其基本思想是通过增加“过滤约束”舍弃一定不是最优解的解组合以求得最优解。“隐”的含义是指在检验可能解的可行性和非劣性过程中，增加一个过滤条件，以加快筛选过程，其应用前提是要枚举出所有可能解的集合。对具有n个变量的0-1整数规划问题来说，可能解的个数为2n。4.2.5匈牙利法1955年，库恩(W.W.Kuhn)根据匈牙利数学家康尼格(D.Koumlnig)得出的结论，提出了求解指派问题的方法一匈牙利法(HungarianMethod)，用于求解目标函数最小化的指派问题。上一页下一页返回4.2整数规划求解方法其理论依据为:若指派问题的系数矩阵的某行(或某列)各元素分别加上一个常数k，得到一个新的矩阵，则这两个矩阵所对应的指派问题的最优解相同。在求解时遵循康尼格定理:矩阵中独立。元素的最多个数等于能覆盖所有。元素的最少直线数。根据这个定理，对于n阶效率矩阵，匈牙利法求解指派问题的步骤为:(1)首先让效率矩阵中的每行(列)都出现零元素。若效率矩阵某行(列)中没有零元素，则该行(列)所有元素都减去该行(列)中的最小元素。

(2)寻找独立零元素。独立零元素有狭义和广义之分。上一页下一页返回4.2整数规划求解方法狭义的独立零元素是指:若某行(列)中只有一个零，那么这个“零”就是独立零元素，而且各个独立零元素应分别位于不同的行或列中，即每行(列)中只有一个独立零元素。当独立零元素的数量等于n时，计算停止，此时将效率矩阵中独立零元素变为“1”，其他元素变为“0”，则获得最优解。若独立零元素的数量小于n，则重复第(3)步，直至找到n个独立零元素为止。(3)继续寻找独立零元素。若独立零元素的数量小于n，说明在进行第(2)步时，同列(行)不同行(列)都出现了独立零元素，此时只能选择某一行(列)的“0”作为独立零元素，因而放弃选择其他行(列)的独立零元素，因此，应以这两行(列)为对象做进一步的处理。上一页下一页返回4.2整数规划求解方法将这两行(列)中的元素都减去除“0”