IE案例分析(三).ppt

IE案例分析 王晓光武汉理工大学机电工程学院 案例五 指派问题 问题的提出指派问题 Assignmentproblem 也称分配或配置问题 是资源合理配置或最优匹配问题 其他变异问题对于求最大值 人数与任务数不相等以及不可接受的配置 某个人不能完成某项任务 等特殊指派问题 对于效率矩阵通过适当变换使得满足匈牙利算法的条件再求解 问题的提出某商业集团计划在市内四个点投资四个专业超市 考虑的商品有电器 服装 食品 家具及计算机5个类别 通过评估 家具超市不能放在第3个点 计算机超市不能放在第4个点 不同类别的商品投资到各点的年利润 万元 预测值见下表 该商业集团如何做出投资决策使年利润最大 案例五 指派问题 具体要求 案例五 指派问题 具体要求这是一个求最大值 人数与任务数不相等以及不可接受的配置的一个综合指派问题 案例五 指派问题 具体要求虚拟一个地点5 令C43 C54 0 转换成求最小值问题 令M 420 然后用M分别减去各点的年利润 得到效率表 案例五 指派问题 运用匈牙利算法求最优解 案例五 指派问题 用WinQSB软件求解时不必对效率矩阵进行人工转换 系统会自动转换 1 启动程序 点击开始 程序 WinQSB NetworkModeling 2 建立新问题 选择Assignmentproblem Maximization 输入标题 人数 目标数 为5及任务数 配置数 为4 案例五 指派问题 案例五 指派问题 案例五 指派问题 3 输入数据 4 求解 点击菜单栏SolveandAnalyze 选择SelectInitialSolutionMethod 选择求初始解方法 选项 求初始解有八种方法 选择其中的MatrixMinimum MM 矩阵最小元素法 即最小元素法 案例五 指派问题 案例五 指派问题 5 点击菜单栏SolveandAnalyze 选择SolvetheDisplaySteps Tableau时显示匈牙利算法每一步迭代表 案例五 指派问题 选择Interation中的NextInteration得到进一步的迭代 案例五 指派问题 Excel应用 数学模型如下 xij设为指派i类产品到j超市 i 1 2 3 4 5 j 1 2 3 4 案例五 指派问题 Excel应用 案例五 指派问题 案例五 指派问题 案例五 指派问题 2 给实际指派 实际分配 总成本定义公式 案例五 指派问题 2 给实际指派 实际分配 总成本定义公式 案例五 指派问题 3 选中总收益橙色框 在 工具 菜单中 选择 规划求解 选项 弹出 规划求解参数 对话框 该对话框用来输入所要求解的规划问题的目标函数 决策变量和约束条件 案例五 指派问题 4 在 选项 栏中勾选下面两个选项 案例五 指派问题 5 求解得到结果 案例五 指派问题 最优投资方案为 地点1投资建设计算机超市 地点2投资建设服装超市 地点3投资建设食品超市 地点4投资建设电器超市 年利润总额预测值为1350万元 案例六 公务员招聘与指派 问题的提出某市直属单位因工作需要 拟向社会公开招聘8名公务员 具体的招聘办法和程序如下 公开考试 根据考试总分的高低排序按1 2的比例选择 共16人 进入第二阶段的面试考核 案例六 公务员招聘与指派 问题的提出面试考核 面试考核主要考核应聘人员的知识面 对问题的理解能力 应变能力 表达能力等综合素质 按照一定的标准 面试专家组对每个应聘人员的各个方面都给出一个等级评分 从高到低分成A B C D四个等级 由招聘领导小组综合专家组的意见 笔初试成绩以及各用人部门需求确定录用名单 并分配到各用人部门 案例六 公务员招聘与指派 具体要求该单位拟将录用的8名公务员安排到所属的7个部门 并且要求每个部门至少安排一名公务员 这7个部门按工作性质可分为四类 1 行政管理 2 技术管理 3 行政执法 4 公共事业 案例六 公务员招聘与指派 具体要求招聘领导小组在确定录用名单的过程中 本着公平 公开的原则 同时考虑录用人员的合理分配和使用 有利于发挥个人的特长和能力 招聘领导小组将7个用人单位的基本情况 包括福利待遇 工作条件 劳动强度 晋升机会和学习深造机会等 和四类工作对聘用公务员的具体条件的希望达到的要求都向所有应聘人员公布 每一位参加面试人员都可以申报两个自己的工作类别志愿 案例六 公务员招聘与指派 具体要求现在已知各应聘人员面试成绩 专家测评和用人单位需求的情况下 试根据以下要求探究如何选出适合公务员需求的人员 指派到合适的部门 如果不考虑应聘人员的意愿 择优按需录用 试帮助招聘领导小组设计一种录用分配方案 在考虑应聘人员意愿和用人部门的希望要求的情况下 请你帮助招聘领导小组设计一种分配方案 你的方法对于一般情况 即N个应聘人员M个用人单位时 是否可行 案例六 公务员招聘与指派 表 笔试成绩 专家面试评分及个人志愿 案例六 公务员招聘与指派 表 笔试成绩 专家面试评分及个人志愿 案例六 公务员招聘与指派 表2 用人部门基本情况及对公务员的期望 案例六 公务员招聘与指派 与公务员招聘与指派相类似的问题很多 比如 投资项目的选择 投资场所的选定 工厂的选址 新产品开发方案的确定等等 总之 凡是一些相互排斥的计划 方案的确定问题都可以归结为与公务员招聘与指派类似的规划问题 案例六 公务员招聘与指派 0 1型整数规划是整数规划的特殊情形 它的决策变量仅取0或1这两个值 这时的决策变量也称为0 1变量 在实际问题中 有些问题只需回答 是 或 否 问题就解决了 描述这类问题的变量只需取两个值就可以了 例如是否采纳某个方案 某项任务是否可以交某人承担 集装箱内是否装入某种货物等等 对于这类问题我们可以用逻辑变量来描述 案例六 公务员招聘与指派 具体问题分析和建模求解分析 这是一个人多事少的非标准指派问题 适用0 1整数规划求解 使用0 1整数规划求解的条件分析 人员与任务数目和指派要求明确 在16个人中选8人 分配于7个部门 每个部门至少一个人 这是本案例的绝对约束条件 择优按需 录用 同时考虑录用人员的合理分配和使用 有利于发挥个人的特长和能力 优先考虑考虑应聘者能力与部门需求 择优按需 确定初步分配方案 再结合应聘人员意愿进行方案优化 案例六 公务员招聘与指派 具体问题分析和建模求解用人部门对公务员的期望要求和应聘人员的意愿不是绝对约束 但是要尽量满足 实际上这里没有一个应聘者可以完全满足部门1的能力期许 案例六 公务员招聘与指派 具体问题分析和建模求解系数矩阵应该体现 择优按需 原则 表征每个应聘者能给各个部门带来的效率 在本案例中没有直接给出 需要首先求解出系数矩阵 显见 择优 要求受聘者的总体综合得分尽量地高 按需 指人员合理分配 各部门对公务员特长的期望与受聘人员特长尽量吻合 所以系数矩阵是充分合理地结合应聘者的笔试成绩 面试成绩及用人部门要求给每个应聘者打出的综合评分 案例六 公务员招聘与指派 求解过程数据整理面试环节采用等级评分 不便于分析 给A B C D四个等级分别赋值4 3 2 1同时 用人部门的基本情况主要用于应聘者参考选择申报志愿 在以下求解中可以忽略 重新整理数据得新表格 案例六 公务员招聘与指派 表 笔试成绩 专家面试评分及个人志愿 案例六 公务员招聘与指派 表 笔试成绩 专家面试评分及个人志愿 案例六 公务员招聘与指派 表2 用人部门基本情况及对公务员的期望 案例六 公务员招聘与指派 结合应聘者笔试 面试成绩及各部门的期望确定系数矩阵C 由上表可以得到笔试成绩矩阵ai 面试成绩矩阵bi 用人部门要求矩阵bj 设Cij为矩阵第i行第j列元素 代表第i个公务员对应于第j个部门的综合得分 案例六 公务员招聘与指派 结合应聘者笔试 面试成绩及各部门的期望确定系数矩阵C 结合ai bi bj三个矩阵求解矩阵C 用人部门对应聘者的特长要求在笔试部分无法体现 Cij的值应该包括考虑用人部门要求影响的面试成绩与笔试成绩两部分 j部门k项能力的期望分越高代表这项能力在该部门越被看重 所以将bj看成bi矩阵的权重矩阵 取面试成绩矩阵与用人部门要求矩阵相乘所得矩阵 笔试成绩矩阵分别乘以各自的权重在相加所得矩阵作为系数矩阵 案例六 公务员招聘与指派 结合应聘者笔试 面试成绩及各部门的期望确定系数矩阵C 即令有 k 1 2 3 4 u1 u2 0为根据实际情况设定的权数 这里暂取u1 0 1 u2 1 可以得到系数矩阵如下 案例六 公务员招聘与指派 案例六 公务员招聘与指派 案例六 公务员招聘与指派 用xij i 1 2 16 j 1 2 7 表示决策变量 依题意可建立0 1整数规划模型 案例六 公务员招聘与指派 问题就转化为求下面的优化模型 案例六 公务员招聘与指派 增设虚部门8 取Ci8 min Ci1 Ci2 Ci7 得 案例六 公务员招聘与指派 增设虚部门8 取Ci8 min Ci1 Ci2 Ci7 得 案例六 公务员招聘与指派 利用WinSQB求解 NetworkModeling AssignmentProblem 案例六 公务员招聘与指派 将上表系数录入NetworkModeling AssignmentProblem 模型中 案例六 公务员招聘与指派 求解如下 案例六 公务员招聘与指派 因为部门8为虚部门 所以第8个应聘者应该调整工作部门 根据第8个应聘者的能力特长 将其安排在部门1工作 即的最优分配方案为 案例六 公务员招聘与指派 考虑应聘者意愿和用人部门的希望要求的情况下进行分配只需在上述模型上增加照顾应聘者意愿的约束即可 选择或放弃某个部门对于应聘者而言是个相互排斥的问题 故可采用0 1整数规划 引入应聘者意愿决策变量 对上述模型进行变化得到新模型 案例六 公务员招聘与指派 设 案例六 公务员招聘与指派 案例六 公务员招聘与指派 Cijyij代替Cij组成新系数矩阵 同上 增设虚部门8 得系数矩阵如下表 案例六 公务员招聘与指派 Cijyij代替Cij组成新系数矩阵 同上 增设虚部门8 得系数矩阵如下表 案例六 公务员招聘与指派 利用WinSQB求解 NetworkModeling AssignmentProblem 案例六 公务员招聘与指派