文档介绍：运筹学5 整数规划
* 用匈牙利法求解: 最优解: 即甲安排做第二项工作、乙做第三项、丙做第四项、丁做第三项。总分为:Z=92+95+90+80=357 * 本章介绍了整数规划的数学模型的特征及其应用; . . . . . 求解方法有:解一般整数规划用分枝定界法、割平面法; 解0-1规划用隐枚举法; 解指派问题用匈牙利法。试一试,下例结论是否正确: * . (分配)问题的效率矩阵每行分别加上一个数后最优解不变. . . (R..)约束是将可行域中一部分非整数解切割掉. . . -1规划时需枚举2的n次幂个可能. The End of Chapter 5 下一章:图与网络 Exit 进入练****第*页* 整数规划 Integer Programming 可分性假设?divisibility assumption 可加性假设?additivity assumption 比例性假设?proportionality assumption 0-1变量 binary variable BIP 0-1整数规划纯整数规划 pure Integer Programming 混合整数规划 mixed Integer Programming LP放宽 LP relaxation 分枝定界法 brabch and bound method 高莫雷 过滤条件 filtering constraint 隐枚举法 implicit enumeration 指派问题 assignment problem 边际收益递减 decreasing marginal returns 第*页* 作业:教材P135 The End of Chapter 5 下一章:图与网络是非决策 yes-or-no decision 二选一约束 either-or-constraints 互斥的选择 mutually exclusive alternative 相依决策 contingent decision * 分枝定界法的步骤: 1. 求整数规划的松弛问题最优解; 2. 若松弛问题的最优解满足整数要求,得到整数规划的最优解,否则转下一步; ,在松弛问题中加上约束xi
≤[[]xi]及xi≥[[]xi]+1组成两个新的松弛问题,称为分枝。新的松弛问题具有特征:当原问题是求最大值时,目标值是分枝问题的上界;当原问题是求最小值时,目标值是分枝问题的下界; 4.? 检查所有分枝的解及目标函数值,若某分枝的解是整数并且目标函数值大于()等于其它分枝的目标值,则将其它分枝剪去不再计算,若还存在非整数解并且目标值大于()整数解的目标值,需要继续分枝,再检查,