v2第5章 整数规划-指派问题.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有 第二步：找出矩阵每列的最小元素，再分别从每列中减去，有 第三步：用最少的直线覆盖所有“0”，得 第四步：这里直线数等于3（等于4时停止运算），要进行下一轮计算． 从矩阵未被直线覆盖的数字中找出一个最小数k并且减去k，矩阵中k＝5． 直线相交处的元素加上k，被直线覆盖而没有相交的元素不变，得到下列矩阵 第四步等价于第1、3行减去5，同时第1列加上5得到的结果 -5 -5 +5 第五步：覆盖所有零最少需要4条直线，表明矩阵中存在4个不同行不同列的零元素．容易看出4个“0”的位置 或 得到两个最优解 有两个最优方案 第一种方案：第一个工厂加工产品1，第二工厂加工产品3，第三个工厂加工产品4，第四个工厂加工产品2； 第二种方案：第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2； 产品总成本 Z＝58＋150＋250＋55＝513 课堂练习 用匈牙利法求解如下效率矩阵的指派问题 课堂练习 11 5 7 6 4 戊 6 9 6 3 7 丁 9 6 4 5 8 丙 9 11 7 12 9 乙 11 8 9 5 7 甲 E D C B A 费 工作 用 人员 直线数等于45 -1 -1 +1 直线数仍然等于45 -1 -1 +1 直线数等于5=5 圈0 此问题有多个最优解 最少费用为28 三。非标准形式的指派问题 在实际应用中，经常遇到非标准形式的指派问题。处理方法： 化标准，再按匈牙利访法求解。 ⒈ 最大化指派问题 例13 有4种机械要分别安装在4个工地，它们在4个工地工作 效率（见下表）不同。问应如何指派安排，才能使4台机械发 挥总的效率最大？ 工地 机器 甲 乙 丙 丁 Ⅰ Ⅱ Ⅲ Ⅳ 30 25 40 32 32 35 30 36 35 40 34 27 28 43 32 38 解：设最大化的指派问题系数矩阵 ，其中最大元 素为m（本例种m=43），令矩阵 本例中 -3 -7 -3 -0 -4 圈0 覆盖 打? ? ? ? -1 -1 +1 圈0 此时m=n=4,因此决策变量矩阵为 即指派机械Ⅰ安装在工地丙，机械Ⅱ安装在工地丁，机械Ⅲ 安装在工地甲，机械Ⅳ安装在工地乙，才能使4台机器发挥总 的效率最大。其总效率为 ⒉ 人数和事数不等的指派问题 若人少事多，则添上一些虚拟的“人”。这些虚拟的“人”做各事 的费用系数可取0，理解为这些费用实际上不会发生。若人多 事少，则添上一些虚拟的“事”。这些虚拟的“事”被各人做的费 用系数同样也取0。 ⒊ 一个人可做几件时的指派问题 若某个人可做几件时，则可将该人化作相同的几个“人”来接受 指派。这几个“人”做同一件时的费用系数当然都一样。 ⒋ 某事一定不能由某人做的指派问题 若某事一定不能由某个人做，则可将相应的费用系数取 作足够大的数M. 例13 对于例12的指派问题，为了保证工程质量，经研究决 定，舍弃建筑公司 和 ，而让技术力量较强的建筑公 司 、 和 来承建。根据实际情况，可以允许每家 建筑公司承建一家或两家商店。求使总费用最少的指派方 案。 反映投标费用的系数矩阵为 由于每家建筑公司最多可承建两家新商店，因此，把每家 建筑公司化作相同的两家建筑公司（ 和 这样，系数矩阵变为： 上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同， 引入一件虚事 ，使之成为标准指派问题的系数矩阵： 再利用匈牙利法求解。 列变换 圈0 ? ? ? -1 -1 +1 再变换 打? 覆盖 圈0 最优解 承建 和 ， 承建 ， 承建 和 。总建筑费用为 最优解 承建 和 ， 承建 ， 承建 和 。总建筑费用为 （万元） * * * * * * * * * 整数规划 整数规划的数学模型及解的特点 解纯整数规划的割平面法* 分支定界法 0-1型整数规