文档详情

整数规划3-指派问题.ppt

发布:2017-11-10约4.31千字共26页下载文档
文本预览下载声明
重庆大学经济与工商管理学院 肖智 运筹学教学介绍 重庆大学经济与工商管理学院 肖智 主讲 制作 THE END *§4.3 指派问题 第三节 指派问题 一、指派问题及其模型 1、指派问题 例4.3.1 指派问题 某企业一部门有A1、A2、A3、A4四个人,该部门有 B1、B2、B3、B4 四项工作需要做,要求每人只能做一 项工作,每项工作只能一人去做。已知:每人做每项工作 的单位消耗如下表 4.3-1 所示。试问:应如何分配工作 使总消耗最少? 表4.3-1 单耗信息表 模型: (4.3-1) 13 7 9 2 A3 12 9 11 5 A4 16 8 12 3 A2 5 1 2 6 A1 B4 B3 B2 B1 单耗 工作 人 2、一般指派问题 有n项任务,有m种资源,要求每种资源只能用于一 项任务,每项任务只能拥有一种资源。已知,第 j项任务 需消耗第 i 种资源Cij。试问:应如何配备资源使总消耗 最少? 3、一般模型: (4.3-2) 4、基本特征: 1)特殊的线性规划; 2)特殊的整数规划; 3)特殊的0-1整数规划; 4)特殊的运输问题; 5、常用求解方法分类 1)线性规划的求解方法; 2)整数规划的求解方法; 3)0-1整数规划的求解方法; 4)运输问题的求解方法; 5)特殊的求解方法——匈牙利算法 二、指派问题的求解方法 1、计算机方法 例4.3.2:以例4.3.1为例。 2、匈牙利算法 1)适用范围:指派问题的标准型问题。 指派问题的标准型问题必须满足以下3个条件: (1)目标要求为极小化(min); (2)效益矩阵(目标系数矩阵)A=(aij)n×n为方阵; (3)A中所有元素均为非负常数(aij≥0,i,j=1,2,…,n) 2)基本理论 (1)定理1:设一个指派问题的效益矩阵为(aij)n 。若 从(aij)n的第 i 行元素中减去一个常数ui (i=1,2,…,n), 从第j 行元素中减去一个常数vj(j=1,2,…,n),得到一 个新的效益矩阵(bij)n,其中每一元素bij=aij-ui-vj,则 (bij)n问题的最优解也是(aij)n问题的最优解。 (2)定理2:若一方阵中的一部分元素为0,一部分元素为非0,则覆盖方阵内所有0元的最少直线数恰好等于那些位于不同行、不同列的0元的最多个数。 3)基本步骤: (1)效益矩阵的初始变换——零元素的获取 ① 行变换:效益矩阵A0的每行减去该行的最小元素得 新效益矩阵A1; ② 列变换:对A1的每列减去该列的最小元素得新效益 矩阵A2; (2)最优性检验: ① 用最少的直线覆盖A2所有的0元素,记其直线数为K, ② 若k=n,则转(4);否则转(3)。 (3)调整: ① 在覆盖有直线的A2中,对线外的所有元素减去这些 元素中的最小a; ② 对线上交叉的元素加上a,得一新的效益矩阵,仍 记为A2;转(2)。 (4)输出最优解: ① 确定位于不同行不同列的0元素; ② 将确定的位于不同行不同列的0元素对应的决策变 量取1,其余决策变量取0,得最优解(方案)。 4)例4.3.3:以例4.3.1为例。 解:(1)效益矩阵的初始变换——零元素的获取 (2)最优性检验 1 3 2 5 0 1 0 4 即有:k=24=n (3)调整: 转(2)最优性检验 即有:k=34=n
显示全部
相似文档