《-指派问题》课件.ppt

解： 3.用最少的直线覆盖所有0, 最少直线数= 4。 4. 最少直线数= 4 ，表明矩阵中存在4个不同行不同列的零元素(m = 4)。 5.令对应的变量等于1，其余变量等于0，得到最优解。 解： 甲分配到岗位B， 最优分配方案： A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 乙分配到岗位A， 丙分配到岗位D， 丁分配到岗位C， 总成绩=92+95+90+80=357 某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、食品、家具及计算机5个类别。通过评估，家具超市不能放在第3个点，计算机超市不能放在第4个点，不同类别的商品投资到各点的年利润（万元）预测值见下表。该商业集团如何做出投资决策使年利润最大。 例3 表1 地点1 地点2 地点3 地点4 电器 120 300 360 400 服装 80 350 420 260 食品 150 160 380 300 家具 90 200 —— 180 计算机 220 260 270 —— 二.行数与列数不等 这是求最大值、行数与列数不等的综合指派问题。 表1 地点1 地点2 地点3 地点4 电器 120 300 360 400 服装 80 350 420 260 食品 150 160 380 300 家具 90 200 —— 180 计算机 220 260 270 —— 解： 对表1进行以下转换得到效率矩阵： (1)令C43= C54 =0; (3)虚拟一个地点5。 (2)转换成求最小值问题，令M=420,得到效率矩阵; 例3 解： 1.找出每行的最小元素，并从每行中减去； 2.找出每列的最小元素，并从每列中减去； 例3 3.用最少的直线覆盖所有0； (1)在零元素最少的行(列)中任选一个零元素，对这个零元素打上( ), 将该(0)所在的行、列其他零元素全打上记号×。同时对打( )及×的零元素所在的行或列画一条直线。 (2)重复第(1)步。在剩下的没有被直线画去的行、列中再找最少的零元素，打上( ), 打上×及画线。直到所有零元素都被直线画去。 最少直线数= 4。 3.用最少的直线覆盖所有0； 最少直线数= 4。 修改矩阵： (1)从矩阵未被直线覆盖的数字中找出一个最小数40,并且减去40； (2)直线相交处的元素加上40，被直线覆盖而没有相交的元素不变。 重复步骤3，直到最少直线数=5。 3.用最少的直线覆盖所有0； 最少直线数= 5。 (1)在零元素最少的行(列)中任选一个零元素，对这个零元素打上( ), 将该(0)所在的行、列其他零元素全打上记号×。同时对打( )及×的零元素所在的行或列画一条直线。 (2)重复第(1)步。在剩下的没有被直线画去的行、列中再找最少的零元素，打上( ), 打上×及画线。直到所有零元素都被直线画去。 3.用最少的直线覆盖所有0； 最少直线数= 5。 4. 最少直线数= 5 ，表明矩阵中存在5个不同行不同列的零元素(m = 5)。 5.令对应的变量等于1，其余变量等于0，得到最优解。 第二章 对偶理论 2.1 对偶规划 2.2 对偶定理 2.3 对偶单纯形法 2.4 线性规划灵敏度分析 2.5 运输问题 2.6 指派问题 数学模型 匈牙利算法 其他变异的指派问题 第二章 对偶理论 第六节 指派问题 某公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如下表所示。求最优生产配置方案使得单位产品成本总和为最小。 例1 指派问题也称为分配或配置问题。是资源合理配置或最优匹配问题。 指派问题 一. 数学模型 效率表 产品1 产品2 产品3 产品4 工厂1 58 69 180 260 工厂2 75 50 150 230 工厂3 65 70 170 250 工厂4 82 55 200 280 这个问题的求解可以采用枚举法。将所有分配方案求出，总分最小的方案就是最优解。本例的方案有4×3×2×1 = 24 种。 由于方案数是工厂数的阶乘，当工厂数和产品数较多时，计算量非常大。 而用0-1规划描述此类分配问题显得非常简单。下面建立相应的数学模型。 某公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如下表所示。求最优生产配置方案使得单位产品成本总和为最小。 例1 产品1 产品2 产品3 产品4 工厂1 58 69 180 260 工厂2 75 50 150 230 工厂3 65 70 170 250 工厂4 82 55 200 280 解： 设 第i工厂生产第j种产品 第i工厂不生产第j种产品 工厂1 产品1 工厂2 工厂3 工厂4 产品2 产品3 产