职业规划_整数规划的难度远大于一般线性规划

整数规划 整数规划的难度远大于一般线性规划 2 4 1整数规划简介 要求所有xj的解为整数 称为纯整数规划要求部分xj的解为整数 称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的 最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解 3 4 2整数规划的分枝定解法 4 2 1思路与解题步骤只解松弛问题1 在全部可行性域上解松弛问题若松弛问题最优解为整数解 则其也是整数规划的最优解2 分枝过程若松弛问题最优解中某个xk bk不是整数 令 bk 为bk的整数部分构造两个新的约束条件xk bk 和xk bk 1 分别加于原松弛问题 形成两个新的整数规划3 求解分枝的松弛问题 定界过程设两个分枝的松弛问题分别为问题1和问题2 它们的最优解有如下情况 4 表4 2 1分枝问题解可能出现的情况 情况2 4 5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留 用于以后与问题2的后续分枝所得到的整数解进行比较 结论如情况4 5 4 2 2分枝定界法举例 例4 1 1 解 松弛问题的最优解为x1 2 5 x2 2 OBJ 23由x1 2 5得到两个分枝如下 6 表4 2 3分枝问题的松弛解 问题II的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况 则需要两边同时继续分枝 直到有整数解出现 就可以进行定界过程当有很多变量有整数约束时 分枝即广又深 在最坏情况下相当于组合所有可能的整数解一般整数规划问题属于一类未解决的难题 NP complete 只有少数特殊问题有好的算法 如任务分配问题 匹配问题 7 4 6任务分配问题 例4 6 1有四个熟练工人 他们都是多面手 有四项任务要他们完成 若规定每人必须完成且只完成一项任务 而每人完成每项任务的工时耗费如表4 6 1 问如何分配任务使完成四项任务的总工时耗费最少 8 任务分配问题的数学模型 模型中 xij为第i个工人分配去做第j项任务 aij为第i个工人为完成第j项任务时的工时消耗 aij m m称为效率矩阵 运输问题是任务分配问题的松弛问题任务分配问题不但是整数规划 而且是0 1规划任务分配问题有2m个约束条件 但有且只有m个非零解 是自然高度退化的任务分配是两部图的匹配问题 有著名的匈牙利算法下面介绍一种适合手算的算法 出自清华教科书 9 4 6 1清华算法 定理1如果从效率矩阵 aij m m中每行元素分别减去一个常数ui 从每列元素分别减去一个常数vj 所得新的效率矩阵 bij m m的任务分配问题的最优解等价于原问题的最优解 证明 略定理2若方阵中一部分元素为零 一部分元素非零 则覆盖方阵内所有零元素的最少直线数等于位于不同行 不同列的零元素的最多个数 证明 略清华算法的基本思路 根据定理1变换效率矩阵 使矩阵中有足够多的零 若矩阵中存在m个不同行不同列的零 就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于m条 就尚未找到最优解 设法进一步变换矩阵 增加新的零 10 清华算法的步骤 例4 6 1 第一步 变换效率矩阵 使每行每列至少有一个零行变换 找出每行最小元素 从该行各元素中减去之列变换 找出每列最小元素 从该列各元素中减去之 第二步 检查覆盖所有零元素的直线是否为m条划线规则1 逐行检查 若该行只有一个未标记的零 对其加 标记 将 标记元素同行同列上其它的零打上 标记 若该行有二个以上未标记的零 暂不标记 转下一行检查 直到所有行检查完 11 清华算法的步骤 例4 6 1 2 逐列检查 若该列只有一个未标记的零 对其加 标记 将 标记元素同行同列上其它的零打上 标记 若该列有二个以上未标记的零 暂不标记 转下一列检查 直到所有列检查完 3 重复1 2后 可能出现三种情况 a 每行都有一个 0 显然已找到最优解 令对应 0 位置的xij 1 b 仍有零元素未标记 此时 一定存在某些行和列同时有多个零 称为僵局状态 因为无法采用1 2中的方法继续标记 4 打破僵局 令未标记零对应的同行同列上其它未标记零的个数为该零的指数 选指数最小的先标记 采用这种方法直至所有零都被标记 或出现情况a 或情况c 12 清华算法的步骤 例4 6 1 c 所有零都已标记 但标有 的零的个数少于m 开始划线过程 对没有标记 的行打 对打 行上所有其它零元素对应的列打 再对打 列上有 标记的零元素对应的行打 重复 直至无法继续 对没有打 的行划横线 对所有打 的列划垂线 划线后会出现两种情况 1 标记 的零少于m个 但划有m条直线 说明矩阵中已存在m个不同行不同列的零 但打破僵局时选择不合理 没能找到 回到b重新标记 2 少于m条直线 到第三步 13 清华算法的步骤 例4 6 1 第三步 进一步变换 在未划线的元素中找最小者 设为 对未被直线覆盖的各元素减去 对两条直线交叉点覆盖的元素加上 只有一条直线覆盖的元素保持不变以上步骤实际上仍是利用定理1 第四步 抹除所有标记 回到第二步 重新标记 14 清华算法的步骤 例4 6 1 答 最优分配方案为x13 x21 x34 x42 1 其余为0 即甲 C 乙 A 丙 D 丁 B OBJ 20 15 4 6 2关于清华算法的适用条件 要求所有aij 0若某些aij 0 则利用定理1进行变换 使所有bij 0目标函数为min型对于max型目标函数 将效率矩阵中所有aij反号 则等效于求min型问题 再利用定理1进行变换 使所有bij 0 则可采用清华算法 打破僵局时选择不当的结果 结果仅出现3个标记 但却划出4条线 说明什么 16 线性规划有关的英文词汇 Operational operationsresearch运筹学Linearprogramming线性规划Feasibledomain可行域Convexset凸集Basicfeasiblesolutions基础可行解Simplexalgorithm单纯型法Pivot主元Pivoting主元变换Revised dualsimplexalgorithm修正 对偶单纯型法Relativecost相对成本 机会成本 Shadowprice影子价格Slack Surplus Artificialvariable松弛 剩余 人工变量Unbounded Infeasible Degeneratesolution无界解 无可行解 退化解Duality对偶性Primal dualproblem原问题 对偶问题Compl