整数规划解法

《整数规划解法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、4.5整数规划的解法分支定界法割平面法匈牙利法14.5.1整数规划解法——分枝定界法步骤：1、寻找替代问题并求解2、分枝与定界3、剪枝21、基本思路：整数规划的最优解不会优于相应的线性规划的最优解。对于极大值问题，相应线性规划的最大值成为整数规划目标函数的上界。maxZ=CXAX=bX0(A)maxZ=CXAX=bX0X为整数(B)(B)为(A)的松弛问题。（1）替代问题的确定3（2）替代问题的求解maxZ=CXAX=bX0(B)采用相应的方法（如图解法）求解出替代问题的最优解，观察其是否满足整数解的要求。如其最优解就为整数，则结束；如含有分数，

2、则需要进行分支定界操作。4（3）分支与定界—增加约束如替代问题的解不符合整数条件，则需要对原问题进行分支。分支方法：假设替代问题的解为[i，i+1]之间的一个数，则分成两支：一支增加约束xj≤i，另一支增加约束xj≥i+1；对上述两个问题进行求解：不考虑整数问题时，求解对应的线性规划问题，观察其最优解是否是整数，如不是，则继续分支定界，直到得到全部整数解为止。X*Xj*i+1i(C)(D)(B)Xji+1(B)Xji5maxZ=40X1+90X29X1+7X2567X1+20X270X1,X20X1,X2为整数例：6解：先解该整数规划对应的松弛

3、问题X*=4.8091.817Z*=355.890，上界Z*选X1分枝问题(2)(1)X14问题(3)(1)X15将[4,5]之间的非整数部分舍去7选(2)继续分枝问题(4)(2)X22问题(5)(2)X23解为X1=4X2=2.1Z=349.0解为X1=5X2=1.571Z=341.39问题2问题38(1)4.8091.817355.890(2)42.1349.0(3)51.571341.39(4)42340(5)1.4283340327.12(6)5.4441340307.76(7)无解X14X15X22X21X22X23分支定界

4、过程94.5.2整数规划解法2——割平面法割平面法的基本思想：在整数规划问题的松弛问题中依次引进线性约束条件(称Gomory约束，高莫雷约束或割平面)，使问题的可行域逐步缩小。但每次切割时，只割去问题的部分非整数解，而不切割任何整数的可行解，直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点，这样就可以用求解线性规划问题的方法找出这个最优解。104.5.3整数规划的解法——匈牙利法应用于分配问题或指派问题分配问题也称指派问题，是一种特殊的整数规划问题。假定有m项任务分配给m个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如

5、何分配使总的效率为最高。111、指派问题一般模型的引出例：有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h)如表所示。问：如何分配任务使效率最高（所需总时间最短）？人工作甲乙丙丁译成英文21097译成日文154148译成德文13141611译成俄文415139从人的角度看从任务角度看12指派问题的一般模型假设：[aij]表示指派问题的效率矩阵xij表示决策变量，决策变量的取值：13指派问题的一般数学模型指派问题的一般模型142、指派问题的求解方法单纯形法表上作业法匈牙利法15

6、（1）指派问题的求解—匈牙利法核心思路：基于这样一个事实：如果效率矩阵的所有元素aij≥0，而其中存在一组位于不同行、不同列的零元素，则只要令对应于这些零元素的xij=1（分配任务），其余的xij=0，则目标函数z必然会取得最小（0）。0149392002320038512140只需令：x11=1，x23=1，x32=1，x44=1，即第一项各种分配给甲，二工作→丙，三→乙，四→丁。总工作时间最少。效率矩阵16问题要求：效率矩阵中存在零元素，同时存在不在同一行、同一列的零元素。实际的效率矩阵中，是不可能存在0元素的，那么如何获得这种特殊的效率矩阵？如何让

7、效率矩阵中产生零元素；如何让产生的零元素位于不同行和不同列。17（2）零元素的产生方法：匈牙利法的基本定理1如果从分配问题效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui(被称为该行的位势)，从每一列分别减去(或加上)一个常数vj(称为该列的位势)，得到一个新的效率矩阵[bij]，若其中则[bij]的最优解等价于[aij]的最优解（说明，经过变换后，有零的新效率矩阵取得最优解时，原效率矩阵也同时取得最优解）18（3）独立零元素的判断方法：匈牙利法的基本定理2若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于

8、不同行、不同列的“0”元素的最大个数。19若矩阵A的元素可分成“0”与非“0”两