第二章--整数规划.pptVIP

? 指派问题 解：设xij 表示第i个施工队去承包第j个项目，且xij 取值为0或1。当第i个施工队去承包第j个项目时，xij＝1，否则xij＝0。 约束条件如下： x11+x12+x13+x14+x15 =1 x21+x22+x23+x24+x25=1 x31+x32+x33+x34+x35 =1 x41+x42+x43+x44+x45 =1 x11+x21+x31+x41+x51=1 x12+x22+x32+x42+x52=1 x13+x23+x33+x43+x53=1 x14+x24+x34+x44+x54=1 x15+x25+x35+x45+x55=1 要使该建筑公司取得最好的经济效益，即取目标函数Z为极大化类型： Max z＝17x11+7x12+9x13+7x14 +9x15+…+6x55 ? 指派问题 标准化方法：完全同于目标函数最大化运输问题的标准化。标准化后的工作效率表如下： 任 务 人 A B C D E 甲 乙 丙 丁 戊 0 9 10 2 13 10 8 0 3 7 8 11 5 11 10 10 11 3 11 7 8 11 5 7 11 表2.2.7 单位：秒 ? 指派问题 例2.2.4 有四个工人，要指派他们分别完成4项工作，每个人做各项工作所消耗的时间如表2.2.8所示。问：指派哪个人去完成哪项工作，可使总消耗时间为最小？A类 ★指派问题的匈牙利解法 表2.2.8 工作 工人 A B C D 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 ? 指派问题 解： （Cij）＝ -15 -18 18 17 -17 -16 19 19 19 21 21 -min 24 23 22 15 18 16 17 26 23 0 0 3 2 1 6 4 9 5 4 0 3 0 1 10 6 -min 0 0 1 0 0 0 3 2 1 6 3 9 4 4 0 2 0 0 10 6 △ △ △ × × ∵m=3n=4, ∴试指派不成 功，转下步 0 0 3 2 1 6 3 9 4 4 0 2 0 0 10 6 △ △ × × △ √ √ √ Min cij＝1 -min -17 -1 -1 +1 ? 指派问题 0 0 4 1 0 6 2 10 3 3 0 2 0 0 10 5 △ × △ √ √ √ Min cij＝2 4－1＝3 △ △ × × √ √ -2 -2 -2 +2 +2 m=3n=4 计算继续 0 0 6 1 0 4 0 10 1 1 0 0 0 0 10 3 × 或 △ 0 0 6 1 0 4 0 10 1 1 0 0 0 0 10 3 × × △ △ △ △ △ △ × × × × × 同行或同列中 有至少两个0， 这时可任选一 行（列）中某 一个0，再划去 同行（列）的其 它0 ? 指派问题 因为m=n=4，所以指派成功，得到以下两个最优解矩阵： 即最优指派方案为： 1）甲－－A，乙－－D，丙－－C，丁－－B； 2）甲－－B，乙－－A，丙－－C，丁－－D。 ? 整数规划问题的求解 例2.3.1 用分枝定界法求解以下模型： * 本节考试不要求 且为整数 解： L0 (仅仅把原问题去掉整数约束) x1=3.25 x2=2.5 z=14.75 z=0, z=14.75 L1 (比L0约束多一个x2≤2) x1=3. 5 x2=2 z=14. 5 x2≤2 x2≥3 L2 (比L0约束多一个x2≥3) x1=3. 5 x2=3 z=13. 5 x1≤3 x1≥4 L3 (比L1约束多一个x1≤3) x1=3 x2=2 z=13 L4 (比L1约束多一个x1 ≥4) x1=4 x2=1 z=14 z=0, z=14. 5 z=14, z=14 ×（无可行解、已得到 整数可行解或不值得分 枝都要剪枝） 增加约束条件不会使 得可行域变大，不会 使目标函数值变大 分解得到整数可 行解的最大目标值 未分解问题各可 行解中目标最大值 14,不 值得分 枝 × × 最优解 分枝使可 行域变小 ? 整数规划问题的求解 例2.3.2