人力资源安排的优化问题.pdf

人力资源安排的优化问题 人力资源安排的优化问题 张建方 王 雷 陈 浩 浙江师范大学 浙江金华 321004 摘要 摘要 本文问题是一个有关最优安排分配的问题 首先我们考虑到人员的安排不可能出现小数 故我们 建立了目标函数的最大值的整数线性规划问题的模型 用单纯形法加以计算 得出一个初步的结果 然后 用 What s Best 软件加以求解验证 确定最终结果 关键词 关键词 人力资源安排 整数线性规划 0 1 规划 完美对集 What s Best 分支界定法 文章号 文章号 TS200501004 一 问题的提出 略 二 模型的假设与符号说明 一 问题的提出 略 二 模型的假设与符号说明 1 模型假设 1 模型假设 1 技术人员在工程期间的出勤均正常 2 同职称的员工所带来的工作效益相同 3 工程完成时间足够长 和目标问题不相关 4 每日公司支付给技术人员的工资和每日公司从项目中取得的资金均正常 5 某一技术人员只能在某一项目工作 无兼职情况 2 符号说明 2 符号说明 X 从事各项目的技术人员的人数的最优解 Z 公司的净收益 已经除去公司职员的工资 在 C 项目和 D 项目的管理开支费 Xij 第 i 职称负责第 j 项目的人数 其中 i 1 2 3 4 分别表示高级工程师 工程师 助理工程师 技术人员 j 1 2 3 4 分别表示 A 项目 B 项目 C 项目 D 项目 Yij Yij 1 第 i 个人负责第 j 个项目 否则 Yij 0 C 公司的收益矩阵 1 Cij 第 i 职称人做第 j 个项目时 公司的收益 其中 i 1 2 3 4 分别表示高级工程师 工程师 助理工程师 技术人员 j 1 2 3 4 分别表示 A 项目 B 项目 C 项目 D 项目 D 公司员工的收益矩阵 2 Dij 第 i 个人做第 j 个项目时 公司的收益 规定 i 1 2 3 表示高级工程师 i 4 5 12 表示工程师 i 13 15 表示助理工程师 B 客户要求的项目中人数约束向量值 A 约束条件的系数矩阵 三 问题分析 三 问题分析 本题要求的是 PE 公司怎样分配人员到各项目 才能使每天带来的直接经济效益最 高 因为公司分配出去每一个人员所带来的效益总要大于公司付于该人员的工资 可根据 个人带给公司的收益 个人从具体项目所得利益 该职员的工资 因此我们可确立一个职员 带给公司的一个收益矩阵 A B C D 高级工程师 工程师 助理工程师 750 600 430 1250 600 530 1000 650 480 700 550 480 技术员 390 490 240 340 再加上人员是供不应求 因此我们可以确定人数分配出去越多越好 公司承接的是四个项目 由于公司能分配出去的人员有限 因此我们需要合理的安排 员工 满足各项目的要求 使公司得到的收益最大 首先把这个问题转化成了一个数学规 划模型 又利用图论知识和计算机软件 求得其最优解 四 模型建立 四 模型建立 模型 整数线性规划模型模型 整数线性规划模型 我们要讨论的是人员安排的优化模型 由于人员的个数均为整数 我们把原问题转化 成为一个用求目标函数为最大的整数线性规划求最大解问题 求得其最优解 根据题意 可建立目标函数 max Z 750X11 1250X12 1000X13 700X14 600X21 600X22 650X23 550X24 430X31 530X32 480X33 480X34 390X41 490X42 240X43 340X44 用数学式子表示 符合题中表 3 各项目对专业技术人员结构的所有要求 模型 0 1 规划也属于整数规划模型 0 1 规划也属于整数规划 我们可以用 What s Best 一次性求解出如下结果 A B C D 高级工程师 1 5 2 1 工程师 6 3 6 2 助理工程师 2 5 2 1 技术员 1 3 1 0 从运行结果我们分析 这个整数线性规划在第一步骤用单纯形法求解线性规划是就解 出了我们所要的最优解 但事实上我们在解一般整数线性规划问题时都不能在第一步骤就 能得到整数的结果 而需要用分支界定法或割平面法再从一般线性的最优解中继续寻找整 数最优解 但问题是目前没有专门的整数线性规划的解法 为了便于模型的推广和提高模 型的实用价值 我们提出了一个不涉及非整数解的模型 因为此人员安排问题有很大的特殊性 尽管 X 中有 16 个变量 但我们看到 X13 和 X44 是 已知确定的 又由于 A B C D 客户要求对技术员的最小人数就等于公司所能提供的最 多技术员人数 所以各项目中技术人员的人数 X41 X42 X43 X44也是确定的 为了满足客 户的要求 各项目人员分配首先要满足以下矩阵 1 2 2 1 2 2 2 2 2 2 2 1 1 3 1 0 我们可以发现 41 个人员中只有 15 个人员是未确定的 因此 我们可以定义 否则 个项目个人负责第第 0 1ji Yij j 1 2 3 4 i 1 2 3 15 Yij的系数矩阵 D 为 750 1250 1000 700 750 1250 1000 700 750 1250 1000 700 600 600 650 550 600 600 650 550 600 600 650 550 600 600 650 550 600 600 650 550 600 600 650 550 600 600 650 550 600 600 650 550 600 600 650 550 430 530 480 480 430 530 480 480 430 530 480 480 从而可得 IP max 4 1 4 1ij ijijYa s t 4 1 1 j Yij i 1 2 3 4 15 15 1 41 i Yi 15 1 72 i Yi 15 1 43 i Yi 15 1 144 i Yi3 15 1 4 1 ij Yij 9 12 4 4 1 ij Yij 3 15 13 4 1 ij Yij 模型 遍历模型模型 遍历模型 在模型 模型 中均需要一定高等的数学知识 这对公司人事部人员的素质要求比 较高 所以我们需要一个适合公司人事部人群的可行模型 这个模型只需参数 C 与参数 B 确定 就能直接使用遍历法的程序 用计算机对其进行一个搜索 为了弥补一般遍历模型的耗时性缺点 我们对其进行了一定的修改 在优化后的遍历 模型只需在很短的时间内就能得到题目要求的一个最优解 模型 完美对集模型模型 完美对集模型 该问题本可转化为最优人员指派问题 即找最优对集 定义 1 赋权完全二分图 G U V E 其中 U u1 u2 u3 u4 分别代表 A B C D 四个 项目 V v1 v2 vk 代表 k 个员工 边权 uivj w uivj 表示工人 vj做项目 ui公司所获得 的收益 M E 定义 2 赋权完全二分图 G U V E 中具有最大权的对集 称这种对集为最优对集 定义 3 设 M 是 G 的一个对集 若 G 的每个顶点都是 M 饱和的 顶点与 M 的边关联 则称 M 是 G 的完美对集 定理1 若G为最优对集 则公司收益最大 证明 若 G 为最优对集 则 G 的边权和最大 因为公司的收益即图 G 边权之和 所以 公司收益最大 定理 2 公司收益要最大 则 G 是完美集 证明 因为公司收益最大 则赋权二分图G的边权和最大 G 即最优对集 定理 3 若 G 为最优对集 且 U V 一一对应 即 U V 则 G 为边权和最大的完美对 集 证明 由定义 3 显然成立 从模型 中分析得到 我们只须对 15 个员工进行指派 因为每个项目有员工人数的 限制 满足初始矩阵 1 2 2 1 2 2 2 2 2 2 2 1 1 3 1 0 分析得到还允许分配的项目是 A B C A 项目的上限是 4 个 B 项目的上限是 7 个 C 项目的上限是 4 我们希望人员分配都能达到客户的最上限 这样公司可以赢利最大 那么 15 个员工将分别就职 A B C 中 15 个职位 我们通过作虚拟点 假设 A 项目 4 个 B 项目 7 个 C 项目 4 个 则现在将 3 个项目转化为 15 个项目 U 项工作 u1 u2 u15 V 个员工 v1 v2 v15 W ui vj 为 vj担任 ui获得的效益 对每人分配一件工作 使总公司收益最大 赋权图二分图 G U V E 经过虚拟点的补充 求 G 的最优完美对集 五 模型求解 五 模型求解 模型 的求解模型 的求解 1 单纯形算法 该算法的主要过程可用下图表示 根据其算法通过 What s Best 软件求解得 max Z 27150 所对应的 X 矩阵为 1 5 2 1 6 3 6 2 2 5 2 1 1 3 1 0 2 贪心算法 U15 V15 V 通过对题目中数据的观察 我们发现 X41 1 X42 3 X43 1 X44 0 由 4 1 4 5 j jX 因此我们可确定 X41 1 X42 3 X43 1 X44 0 同理可以由 X11 1 X12 2 X13 2 X14 1 推出 4 1 1 6 j jX 所以我们知道还剩下 3 个高级工程师在满足约束条件下可以自由分派给各项目 同理 可自由分派的工程师为 9 个 助理工程师为 3 个 定义贪心算法的顺序为 在满足条件下 先考虑可自由分派的技术人员数 从小到大 后考虑技术职称 从高到低 最后考虑 C 矩阵中该行元素大小 从大到小 具体算法为 1 先考虑高级工程师 C 矩阵第一行元素从大到小为 C12 C13 C11 C14 在满足 s t 条 件下得出结论 X11 2 X12 5 X13 2 X14 1 2 其次考虑助理工程师 C 矩阵第三行元素从大到小为 C32 C33 C34 C31 在满足 s t 条件下得出结论 X31 2 X32 5 X33 2 X34 1 3 最后考虑工程师 C 矩阵第二行元素从大到小为 C23 C21 C22 C24 在满足 s t 条件 下得出结论 X23 11 2 1 2 6 X21 10 1 2 1 6 X22 16 5 5 3 3 X24 17 6 6 3 2 综上所述我们便可得出 X 最优矩阵 1 5 2 1 6 3 6 2 2 5 2 1 1 3 1 0 代入所求目标函数得结果也为 Z 27150 模型 的求解模型 的求解 该模型在满足初始矩阵 1 2 2 1 条件下 2 2 2 2 2 2 2 1 1 3 1 0 利用 What s Best 软件求得 4 15 的 0 1 矩阵 A B C D 0 1 0 0 0 1 0 0 高级工程师 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 工程师 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 助理工程师 0 1 0 0 因此我们可根据以上的 0 1 矩阵 我们得出最优人员安排矩阵为 1 5 2 1 6 3 6 2 2 5 2 1 1 3 1 0 max Z 27150 显然这与模型 得到的结果一致的 根据题意 经过我们简化后的模型 与模型 是 等价的 在假设 5 中 某职员只能在某一项目中工作 而模型 正是在此假设前提下 建立 这与模型 中 4 15 矩阵中每一行向量之和为 1 是一致的 另外一个方面 模 型 中给出的初始矩阵即为模型 最优解的下限 模型 的求解模型 的求解 对每个 Xij确定的一个下限和上限 根据上限和各个约束条件 以 1 为步长 从上限 开始 遍历搜索 模型 的求解 算法 Kuhn Munkres 可行顶点标号法 求赋权完美二分图的最优对集 定义1 设赋权完美二分图G U V E 的每个顶点u U对应一个实数L u 若满足其中 w ui vj 是边 ui vj 的权 则称 L 为 G 的一个可行顶点标记可行顶点标记 设 L 为可行顶点标记 则称相应的生成子图 G V E 为相等子图为相等子图 这里 El ui vj E L ui L vj w ui vj 定理 设 L 是赋权完美二分图 G U V E 的可行顶点标记 Gl 是相等子图 若 M 是 Gl 的完美对集 则 M 是 G 的最优对集 此定理提供了求最优对集的算法的基本思路和方法 算法基本思路 通过对顶点标记将赋权图转化为非赋权图 在用 Hungarian 算法求最 大对集 若求出的对集为完美对集 则停止 否则 改进顶点标记 重新计算 具体算法步骤 具体算法步骤 设 G U V E U V 每条边 e x y 有权 w e 或记为 w x y L 是一个初始可行 顶点标记 通常取 L x max w x y v V x U L y 0 y V M 是相等 Gl 的对集 具体步骤如下 1 若 U 的 每 个 顶 点 都 是 饱 和 的 否 则 取 M 非 饱 和 点 u U 另 S u T 2 若 NGl S T 则 Gl 没有完美对集 转 3 否则 转 4 3 调整标记 计算 al min L x L y w x y u S yT 由此得到新的可行顶点标记 令 4 去 y NGl S T 若 y 是 M 饱和点 转 5 否则 转 6 5 设 x y M 令 转 2 6 在 Gl 中 u y 交错路是 M 增广路 记为 P 并令转 应用此 Kuhn Munkres 可行顶点标号法算法 我们给出了本题人力资源安排的具体求 解 求解过程如下表所示 根据上表 我们可以得到人力资源安排的最优对集 M x1 y5 x2 y6 x3 y7 x4 y1 x5 y2 x6 y3 x7 y4 x13 y8 x14 y9 x15 y10 x8 y12 x9 y13 x10 y14 x11 y15 x12 y11 我们同样便可得其最优解为 27150 六 模型的灵敏度分析 六 模型的灵敏度分析 定义 灵敏度分析是研究已求得的最优解是怎样随输入系数的变化而变化 从而制订 一个可应付各种偶然情况的全能方法 我们考虑模型的灵敏度 其目标函数的系数和约束条件都是作为输入数据或参数提供 给模型的 单纯形法用这些数据求得最优解 那么改变目标函数的系数和约束条件对最优 解的影响是多少 这些数据在什么变化区间可以使最优解保持稳定性 通过灵敏度的分析 我们可以在最优解不变的情况下预测公司职员工资的调整 也可以得到客户需求变化范 围 在实际应用中有着不可估量的作用 1 对参数 C 作变化 为了便于能直观的看到变化区间 这里只讨论 C 的一项指标 Cij变化而 B 不变的情况 保证最优解不变的情况下确定 C 中元素的上 下限 已知原 C 750 1250 1000 700 600 600 650 550 430 530 480 480 390 390 240 340 经过固定其他值 逐个确定 Cij 的变化范围 C 1250 750 1250 549 550 651 549 600 530 480 580 530 说明 当 Cij C ij 则 C ij 为 Cij 的下限 当 Cij C ij 则 C ij为 Cij的上线 C22的变化范围是 550 651 除 三种情况外 其他 Cij可以在任何变化范围内 2 对参数 B 作变化 我们发现参数 B 的任何一个值发生改变都将影响到最优解 如 我们设当高级工程师再多一个时 因此可得另一个最优解 2 5 2 1 5 3 6 3 2 5 2 1 1 3 1 0 当然最后的效益也将发生改变 七 模型的评价七 模型的评价 模型 所用的整数线性规划方法具有一般性 但求解可能