您所在位置： &
&nbsp&&nbsp
（精）运筹学指派问题.ppt 19页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
你可能关注的文档：
··········
··········
指派问题（Assignment Problem） 1.
标准指派问题的提法及模型
指派问题的标准形式是：有n个人和n件事，已知第i个人做第j件事的费用为cij（i，j=1，2，…，n），要求确定人和事之间的一一对应的指派方案，使完成这n件事的总费用最小。 数学模型为: 若指派第i个人做第j件事 若不指派第i个人做第j件事 (i,j=1,2,…, n)
设n2个0-1变量
其中矩阵C称为是效率矩阵或系数矩阵。
其解的形式可用0-1矩阵的形式来描述，即 (xij)n?n。
标准的指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题。1955年W. W. Kuhn利用匈牙利数学家D. Konig关于矩阵中独立零元素的定理, 提出了解指派问题的一种算法, 习惯上称之为匈牙利解法。 2.
匈牙利解法
匈牙利解法的关键是指派问题最优解的以下性质：若从指派问题的系数矩阵C=（cij）的某行（或某列）各元素分别减去一个常数k，得到一个新的矩阵C’=（c’ij)，则以C和C’为系数矩阵的两个指派问题有相同的最优解。（这种变化不影响约束方程组，而只是使目标函数值减少了常数k，所以，最优解并不改变。）
对于指派问题，由于系数矩阵均非负，故若能在在系数矩阵中找到n个位于不同行和不同列的零元素（独立的0元素），则对应的指派方案总费用为零，从而一定是最优的。 作变换，其不变性是最优解 匈牙利法的步骤如下：
步1：变换系数矩阵。对系数矩阵中的每行元素分别减去该行的最小元素；再对系数矩阵中的每列元素分别减去该列中的最小元素。若某行或某列已有0元素，就不必再减了（不能出现负元素）。
步2：在变换后的系数矩阵中确定独立0元素（试指派）。若独立0元素已有n个，则已得出最优解；若独立0元素的个数少于n个，转步3。
确定独立0元素的方法：当n较小时，可用观察法、或试探法；当n较大时，可按下列顺序进行
从只有一个0元素的行（列）开始，给这个0元素加圈，记作?，然后划去?所在的列（行）的其它0元素，记作?。 给只有一个0元素的列（行）的0加圈，记作?，然后划去?所在行的0元素，记作?。 反复进行，直到系数矩阵中的所有0元素都被圈去或划去为止。
如遇到行或列中0元素都不只一个（存在0元素的闭回路），可任选其中一个0元素加圈，同时划去同行和同列中的其它0元素。被划圈的0元素即是独立的0元素。 步3：作最少数目的直线，覆盖所有0元素（目的是确定系数矩阵的下一个变换），可按下述方法进行 1） 对没有?的行打“?”号； 2） 在已打“?”号的行中，对? 所在列打“?” 3）在已打“?”号的列中，对?所在的行打“?”号； 4）重复2）3），直到再也找不到可以打“?”号的行或列为止； 5）对没有打“?”的行划一横线，对打“?”的列划一纵线，这样就得到覆盖所有0元素的最少直线数。
步4：继续变换系数矩阵，目的是增加独立0元素的个数。方法是在未被直线覆盖的元素中找出一个最小元素，然后在打“?”行各元素中都减去这一元素，而在打“?”列的各元素都加上这一最小元素，以保持原来0元素不变（为了消除负元素）。得到新的系数矩阵，返回步2。
以例说明匈牙利法的应用。 例1：求解效率矩阵为如下的指派问题的最优指派方案。 解：第一步：系数矩阵的变换（目的是得到某行或列均有0元素） 第二步：确定独立0元素 ?元素的个数m=4，而n=5，进行第三步。 第三步：作最少的直线覆盖所有的0元素，目的是确定系数矩阵的下一个变换。 第四步：对上述矩阵进行变换，目的是增加独立0元素的个数。方法是在未被直线覆盖的元素中找出一个最小元素，然后在打“?”行各元素中都减去这一元素，而在打“?”列的各元素都加上这一最小元素，以保持原来0元素不变（消除负元素）。得到新的系数矩阵。（它的最优解和原问题相同，为什么？） ? ? ? 由解矩阵可得指派方案和最优值为32。
某大型工程有五个工程项目，决定向社会公开招标，有五家建筑能力相当的建筑公司分别获得中标承建。已知建筑公司Ai（I=1，2，3，4，5）的报价cij（百万元）见表，问该部门应该怎样分配建造任务，才能使总的建造费用最小？ 解：第一步：系数矩阵的变换（目的是得到某行或列均有0元素） 第二步：确定独立0元素, 即加圈 ?元素的个数m=4，而n=5，进行第三步。 第三步：作最少的直线覆盖所有的0元素，目的是确定系数矩阵的下一个变换。 第四步：对上述矩阵进行变换，目的是增加独立0元素个数。方法是在未被直线覆盖的元素中找出一个最小元
正在加载中，请稍后...指派问题的数学模型
拟分配n人去干n项工作，每人干且干一项工作，若分配第i人去干第j向工作，需花费cij单位时间，问如何分配工作才能使工人花费的总时间最少？
上述指派问题的可行解可以用一个矩阵表示，其每行每列均有且只有一个元素为1，其余元素均为0；还可以用1，……，n中的一个置换表示。
指派问题的求解可以使用匈牙利算法，或拍卖算法等。
扫码向博主提问
非学，无以致疑；非问，无以广识
擅长领域：
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！Bad Request
Bad Request - Invalid URL
HTTP Error 400. The request URL is invalid.请在APP上操作
打开万方数据APP，点击右上角"扫一扫"，扫描二维码即可将您登录的个人账号与机构账号绑定，绑定后您可在APP上享有机构权限，如需更换机构账号，可到个人中心解绑。
检索详情页
{"words":"$keywords:指派问题+$keywords:O\\-1规划+$keywords:匈牙利解法","themeword":"$keywords","params":"$title:一类指派问题的数学模型及解法"}
&&&一类指派问题的数学模型及解法
一类指派问题的数学模型及解法
本文建立了一类指派问题的O-1规划数学模型,并且建立了推广的匈牙利解法，最后举例演示了该解法的可行性.
摘要： 本文建立了一类指派问题的O-1规划数学模型,并且建立了推广的匈牙利解法，最后举例演示了该解法的可行性.&&
相关论文(与本文研究主题相同或者相近的论文)
同项目论文(和本文同属于一个基金项目成果的论文)
您可以为文献添加知识标签，方便您在书案中进行分类、查找、关联
请输入添加的标签
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）
&北京万方数据股份有限公司 万方数据电子出版社
实名学术社交
个性化订阅推荐
快速查看收藏过的文献当前位置： >>
指派问题(经典运筹学)
一、决策问题与0-1变量决策变量? xi ? ? ?x i ? ? 是否做第i 件事 i ? 1, 2 , ? , n1 0做第i件事 不做第i件事x1 ? x 2 ? ? ? x n ? kn件事中必须做k件并只做k件事 ? n件事中最多做k件事 n件事中至少做k件事? x1 ? x 2 ? ? ? x n ? k ? x1 ? x 2 ? ? ? x n ? kxi ? xj做第i件事的充要条件是做第j件事 ? 做第i件事的充要条件是不做第j件事? xi ? 1 ? x ? xj只在做了第i件事前提下才考虑是否做第j件事j? xi投资项目模型： 例1（投资问题）华美公司有5个项目被列入投资计 划，每个项目的投资额和期望的投资收益见下表： max Z ? 150 x1 ? 210 x2 ? 60 x3 ? 80 x4 ? 180 x5 该公司只有600万资金可用于投资，由于技术上的 ? 210 x1 ? 300 x2 ? 100 x3 ? 130 x4 ? 260 x5 ? 600 原因，投资受到以下约束： ? x1 ? x2 ? x3 ? 1 ? 1、在项目1、2和3中必须有一项被选中 s.t ? x3 ? x4 ? 1 ? x2、项目3和4只能选中一项 ? x1 5 ? x3、项目5被选中的前提是项目1被选中;如何 i ? 1,2,?,5 ? i ? 0,1 在 满足上述条件下选择一个最好的投资 方 案，使投资收益最大解：设 x i 为决策变量（xi ? ? ?0 ?1i ? 1, 2 , ? , 5 )项目 1投资额 投资收益 （万元） （万元） 210 150投资第i个项目23 4 5300100 130 26021060 80 180不投资第i个项目 Z表示投资效益例2（布点问题）某城市共有6个 地 1 2 3 4 5 区，每个区都可以建消防站。 区 1 0 10 16 28 27 市政府希望设置的消防站最少， 2 10 0 24 32 17 但必须满足在城市任何地区发 3 16 24 0 12 27 最优解 生火火警时，消防车要在15分 4 28 32 12 0 15 x2=1, x4=1 钟内赶到现场。据实地测定， 5 27 17 27 15 0 6 20 10 21 25 14 各区之间消防车行驶的时间见 右表。 请为该市制定一个 布点问题模型： min Z ? x ? x ? x ? x ? x 最优值 最节省的计划 x ? x ?1 在第i个地区建站 ? 1Z=2 ? ?1 2 3 46 20 102125 14 05? x6解：x i12? ? ?0 ?不在第i个地区建站i=1,2, …,6Z表示全区消防站总数2 6 ? 1 ? x3 ? x4 ? 1 s.t ? x3 ? x4 ? x5 ? 1 ? x ? x ? x ?1 4 5 6 ? ? x i ? 0 ,1 i ? 1, 2 , ? , 6x ? x ? x?1二、过滤隐枚举法例：求 max Z ? 3 x 1 ? 5 x 2 ? 2 x 3 ? x1 ? 2 x 2 ? x 3 ? 2 ? x ? 4 x 2 ? x 3 ? 42 ? 1 ? s .t ? x 1 ? x 2 ?3 ? 4 x2 ? x3 ? 6 ? ? x 1 , x 2 , x 3 ? 0 或1 ?（适合于变量个数较少的0-1规划）运算次数： 21Z值 约束条件 过滤条件 （1）（2）（3）（4）（x1 x2 x3)（0 （0 （0 （1枚举法： 检验可行解： 32次运算 计算目标 函数值：8次0） 0 1） -2 0） 5 0） 3 （1 0 1） 1 0 0 1 0 （1 1 0） （0 1 1） （1 1 1） 8√ √ √ √√ √√ √Z≥0 Z≥5× √ √ √ √3 6最优解： x 1 ? 1， x 2 ? 1， x 3 ? 1 最优值 Z ? 6三、指派问题与匈牙利法1、指派问题的数学模型设有n个工作，要由 n个人来承 担，每个工作只能由一个人承 担，且每个人只能承担一个工 作。cij表示第i个人做第j件事 的费用,求总费用最低的指派 方案。?1 第i个人做第j 人件事 ? x 解： ij ? ? ? 0 第i个人不做第j 人件事 ?1 1 c 11 2 c 21 …? i c i1 …? n c n1 2c 12 c 22 ? ci2 ? cn2…? ? ? ? ? ?jc1 j c2 j ? c ij ? c nj…? ? ? ? ? ?nc1 n c2n ? c in ? c nn指派问题模型：min Z ???j ic ij x iji=1,2, …,n; j=1,2, …,nZ表示总费用? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 ? i=1,2, …,n ? s .t ? x ? x ? ? ? x ? ? ? x ? 1 1j 2j ij nj ? j=1,2, …,n ? x ? 0 ,1 i ? 1, 2 , ? , j ? 1, 2 , ? , n ?ijmin Z ???cj iijx ij ? c 11 x 11 ? c 12 x 12 ? ? ? c 1 n x 1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? c n 1 x n 1 ? c n 2 x n 2 ? ? ? c nn x nn? x i 1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? s .t ? ? x1 j ? x 2 j ? ? ? x ij ? ? ? x nj ? 1 ? j=1,2, …,n? x 11 ? x 12 ? ? ? x 1 j ? ? ? x 1 n ? 1 ?x ? x ? ? ? x ? ? ? x ? 1 21 22 2j 2n ? ? ? ? x n 1 ? x n 2 ? ? ? x nj ? ? ? x nn ? 1 s .t ? ? x 11 ? x 21 ? ? ? x i1 ? ? ? x n 1 ? 1 ? x 12 ? x 22 ? ? ? x i 2 ? ? ? x n 2 ? 1 ?? ? x 1 n ? x 2 n ? ? ? x in ? ? ? x nn ? 1 ?当n=4时， 有16变量，8个约束方程例：现有4份工作，4个人应聘，由 于各人技术专长不同，他们承担 各项工作所需费用如下表所示， 且规定每人只能做一项工作，每 一项工作只能由一人承担，试求 使总费用最小的分派方案。工作Z表示总费用max Z ? 3 x11 ? 5 x12 ? 4 x13 ? 5 x14 ? 6 x 21 ? 7 x 22 ? 6 x 23 ? 8 x 24 ? 8 x 31 ? 9 x 32 ? 8 x 33 ? 10 x 34 ? 10 x 41 ? 10 x 42 ? 9 x 43 ? 11 x 44? x 11 ? x 12 ? x 13 ? x 14 ? 1 ?x ? x ? x ? x ?1 21 22 23 24 ? x ? x 32 ? x 33 ? x 34 ? 1 ? 31 ? x 41 ? x 42 ? x 43 ? x 44 ? 1 ?x ? x ? x ? x ?1 21 31 41 ? 11 s .t ? x ? x ? x ? x ? 1 12 22 32 42 ? ? x 13 ? x 23 ? x 33 ? x 43 ? 1 ? x 14 ? x 24 ? x 34 ? x 44 ? 1 ? x ? 0 ,1 ij ? i ? 1, 2 , ? , n ? ? j ? 1, 2 , ? , n人 1 2 3 41 3 6 8 102 5 7 9 103 4 4 5 6 8 8 10 9 11解： ? 1 第i人做第j 件事 x ij ? ? ? 0 第i人不做第j 件事i=1,2, 3,4; j=1,2, 3,42、费用矩阵设有n个工作，要由 n个人来承 担，每个工作只能由一个人承 担，且每个人只能承担一个工 作。cij表示第i个人做第j件事 的费用,求总费用最低的指派 方案。? c 11 ? c 取 C ? ? 21 ?? ?c ? n1 c 12 c 22 ? cn2 ? ? ? ? c1n c 2n ? c nn ? ? ? ? ? ?1 1 c 11 2 c 21 …? i c i1 …? n c n1 2c 12 c 22 ? ci2 ? cn2…? ? ? ? ? ?jc1 j c2 j ? c ij ? c nj…? ? ? ? ? ?nc1 n c2n ? c in ? c nn费用矩阵cij表示第i个人做第j件事的费用例：现有4份工作，4个人应聘，由于个人的技术专长不 同，他们承担各项工作所需费用如下表所示，且规定 每人只能做一项工作，每一项工作只能由一个人承担， 试求使总费用最小的分派方案。工作人 1 2 3 4?1 ? ?0 设C ? ?1 ? ?6 ? ?113 6 8 102 2 0 0 3 3 3 0 5 525 7 9 104 5 5 3 73 44 5 6 8 8 10 9 115? ? 6? 6? ? 9? ? 0?费用矩阵? 3 ? ? 6 C ? ? 8 ? ? ? 105 7 9 104 6 8 95 ? ? 8 ? 10 ? ? ? 11 ?对应一个5个人5个工作的指派问题 第2个人做第4个工作的费用 5 第4个人做第2个工作的费用 03、匈牙利法定理：在费用矩阵C=（cij）的任一行（列）中 减去一个常数或加上一个常数不改变本 问题的最优解。? c 11 ? c 21 ?? C ? ? ? c i1 ?? ?c ? n1b ? minc 12 c 22 ? ci2 cn2? ? ? ?c1n ? ? c2n ? ? c in ? ? c nn ? ?-b?c i1 , c i 2 , ? , c in ?? c 11 ? c 21 ? ? C ?? ? c i1 ? b ? ? ? c ? n1c 12 ? c 22 ? ? ci2 ? b ? cn2 ?c1n ? ? c2n ? ? c in ? b ? ? c nn ? ?n个人n个工作 的指派问题1n个人n个工作 的指派问题2? c 11 ? c 21 ?? C ? ? ? c i1 ?? ?c ? n1c 12 c 22 ? ci2 cn2? ? ? ?c1n ? ? c2n ? ? c in ? ? c nn ? ?-b? c 11 ? c 21 ? ? C ?? ? c i1 ? b ? ? ? c ? n1c 12 c 22 ? ci2 ? b cn2? ? ? ?? ? ? ? c in ? b ? ? c nn ? ? c1n c2nmin Z ? c 11 x 11 ? c 12 x 12 ? ? ? c 1 n x 1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? c i 1 x i 1 ? c i 2 x i 2 ? ? ? c in x in ? ? c n 1 x n 1 ? c n 2 x n 2 ? ? ? c nn x nnmin Z ? c 11 x 11 ? c 12 x 12 ? ? ? c 1 n x 1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? ( c i 1 ? b ) x i 1 ? ( c i 2 ? b ) x i 2 ? ? ? ( c in ? b ) x in ?? ? c n 1 x n 1 ? c n 2 x n 2 ? ? ? c nn x nn? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? ? s .t ? x ? x ? ? ? x ? ? ? x ? 1 1j 2j ij nj ? j=1,2, …,n ? x ? 0 ,1 i ? 1, 2 , ? , j ? 1, 2 , ? , n ?ij? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? ? s .t ? x ? x ? ? ? x ? ? ? x ? 1 1j 2j ij nj ? j=1,2, …,n ? x ? 0 ,1 i ? 1, 2 , ? , j ? 1, 2 , ? , n ?ijmin Z? ? ? ? ? ?c 11 x 11 ? c 12 x 12 ? ? ? c 1 n x 1 n c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ? ( c i 1 ? b ) x i 1 ? ( c i 2 ? b ) x i 2 ? ? ? ( c in ? b ) x in ? c n 1 x n 1 ? c n 2 x n 2 ? ? ? c nn x nn? c 11 x 11 ? c 12 x 12 ? ? ? c 1 n x 1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? c i 1 x i 1 ? c i 2 x i 2 ? ? ? c in x in ?? ? c n 1 x n 1 ? c n 2 x n 2 ? ? ? c nn x nn ? b ( x i 1 ? x i 2 ? ? ? x in )? ? ? ? ? ? c 11 x 11 ? c 12 x 12 ? ? ? c 1 n x 1 n c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ? c i 1 x i 1 ? c i 2 x i 2 ? ? ? c in x in ? c n 1 x n 1 ? c n 2 x n 2 ? ? ? c nn x nn ? b? c 11 ? c 21 ?? C ? ? ? c i1 ?? ?c ? n1c 12 c 22 ? ci2 cn2? ? ? ?c1n ? ? c2n ? ? c in ? ? c nn ? ?-b? c 11 ? c 21 ? ? C ?? ? c i1 ? b ? ? ? c ? n1c 12 c 22 ? ci2 ? b cn2? ? ? ?? ? ? ? c in ? b ? ? c nn ? ? c1n c2n? c 11 x 11 ? c 12 x 12 ? ? ? c 1 n x 1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? c i 1 x i 1 ? c i 2 x i 2 ? ? ? c in x in ? ? c n 1 x n 1 ? c n 2 x n 2 ? ? ? c nn x nnmin Z ? Z ? bmin Z ? Z ? b ? c 11 x 11 ? c 12 x 12 ? ? ? c 1 n x 1 n ? c 21 x 21 ? c 22 x 22 ? ? ? c 2 n x 2 n ?? ? c i 1 x i 1 ? c i 2 x i 2 ? ? ? c in x in ?? ? c n 1 x n 1 ? c n 2 x n 2 ? ? ? c nn x nn ? b? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? ? s .t ? x ? x ? ? ? x ? ? ? x ? 1 1j 2j ij nj ? j=1,2, …,n ? x ? 0 ,1 i ? 1, 2 , ? , j ? 1, 2 , ? , n ?ij? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 ? i=1,2, …,n ? s .t ? x ? x ? ? ? x ? ? ? x ? 1 1j 2j ij nj ? j=1,2, …,n ? x ? 0 ,1 i ? 1, 2 , ? , j ? 1, 2 , ? , n ?ij? c 11 ? c 21 ?? C ? ? ? c i1 ? ? ?c ? n1c 12 c 22 ? ci2 cn2? ? ? ?c1n ? ? c2n ? ? c in ? ? c nn ? ?-b? c 11 ? c 21 ? ? C ?? ? c i1 ? b ? ? ? c ? n1c 12 c 22 ? ci2 ? b cn2? ? ? ?? ? ? ? c in ? b ? ? c nn ? ? c1n c2nmin Z? Z ?bmin Z ? Z ? b若 X 0 是 min Z 的最优解 ，则 X 0 也是 min Z 的最优解若 Z 0 是 min Z 的最优值 ，则若 Z0? b 是 min Z 的最优值任务：对C的行和列减去某个常数， 将C化的尽可能简单， 简单到可一眼看出该问题的最优解三、指派问题与匈牙利法1、指派问题的数学模型设有n个工作，要由 n个人来承 担，每个工作只能由一个人承 担，且每个人只能承担一个工 作。cij表示第i个人做第j件事 的费用,求总费用最低的指派 方案。?1 第i个人做第j 人件事 ? x 解： ij ? ? ? 0 第i个人不做第j 人件事 ?1 1 c 11 2 c 21 …? i c i1 …? n c n1 2c 12 c 22 ? ci2 ? cn2…? ? ? ? ? ?jc1 j c2 j ? c ij ? c nj…? ? ? ? ? ?nc1 n c2n ? c in ? c nn指派问题模型：min Z ???j ic ij x iji=1,2, …,n; j=1,2, …,nZ表示总费用? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 ? i=1,2, …,n ? s .t ? x ? x ? ? ? x ? ? ? x ? 1 1j 2j ij nj ? j=1,2, …,n ? x ? 0 ,1 i ? 1, 2 , ? , j ? 1, 2 , ? , n ?ij2、费用矩阵设有n个工作，要由 n个人来承 担，每个工作只能由一个人承 担，且每个人只能承担一个工 作。cij表示第i个人做第j件事 的费用,求总费用最低的指派 方案。? c 11 ? c 取 C ? ? 21 ?? ?c ? n1 c 12 c 22 ? cn2 ? ? ? ? c1n c 2n ? c nn ? ? ? ? 0 ? ? ?1 1 c 11 2 c 21 …? i c i1 …? n c n1 2c 12 c 22 ? ci2 ? cn2…? ? ? ? ? ?jc1 j c2 j ? c ij ? c nj…? ? ? ? ? ?nc1 n c2n ? c in ? c nn费用矩阵cij表示第i个人做第j件事的费用3、匈牙利法定理：在费用矩阵C=（cij）的任一行（列）中 减去一个常数或加上一个常数不改变本 问题的最优解。? c 11 ? c 21 ?? C ? ? ? c i1 ?? ?c ? n1 c 12 c 22 ? ci2 cn2 ? ? ? ? c1n ? ? c2n ? ? c in ? -b ? c nn ? ?? c 11 ? c 21 ? ? C ?? ? c i1 ? b ? ? ? c ? n1c 12 c 22 ? ci2 ? b cn2? ? ? ?c1n ? ? c2n ? ? c in ? b ? ? c nn ? ?b ? min?c i1 , c i 2 , ? , c in ?min Z ? Z ? bmin Z? Z ?b若 X 0 是 min Z 的最优解 ，则 X 0 也是 min Z 的最优解指派问题的最优解：若C中有n 个位于不同行不同列的零元素，则令这些零元素对应的变量取1，其余变量取零，既得指派问题的最优解min Z ?? ?j ?1 i ?144c ij x ij?0?0 ?6 例如： C ? ? 0 ? ?013 0 5 17 6 3 00? 9? 2? ? 0?可行解取 x 14 ? 1， x 22 ? 1,x 31? x i1 ? x i 2 ? x i 3 ? x i 4 ? 1 i=1,2, 3,4 ? ? x ? x ? x ? x ? 1 j=1,2, 3,4 2j 3j 4j s .t ? 1 j ? x ij ? 0 ,1 i ? 1, 2 ,3 , 4 ; j ? 1, 2 ,3 , 4 最 ? ? 优 ? 1, x 43 ? 1 , 其余 x ij ? 0 解总费用 Z ? c 14 x 14 ? c 22 x 22 ? c 31 x 31 ? c 43 x 43 ? 0匈牙利法的基本思路：对费用矩阵C的行和列减去某个常数，将C化成 有n 个位于不同行不同列的零元素，令这些零元 素对应的变量取1，其余变量取零，既得指派问 题的最优解例：有一份说明书要分别译成英、 工作 日、德、俄四种文字，现交给甲、 人 甲 乙丙、丁四个人去完成，每人完 乙 成一种。由于个人的专长不同， 丙 翻译成不同文字所需的时间（小 丁 时数）如右表，问应派哪个人去 完成哪个任务，可使总花费时间 最少？? ? 10 C ? ? 9 ? ? ? 7英 日 德 俄 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9最优方案： 4 ? -2 甲翻译俄文 ，乙翻译日文 ? 2 15 13 ? 0 13 ? 0 13 11 2 ?? 4 14 丙翻译英文 ?6 0 ? ?0 5 14 16 总费用：28小时 ? 0 1 ? 8 11 ?? 15 ? -4 13 ? -9 ? ? 9 ? -7? ? 0 10 11 ? ，丁翻译德文 ?6 ? ?0 ? 5 7 4 ? ? ? ? 1 4 2? ?07 6 3 0-4 -20? ? 9? 2? ? ? 0??最优解x 14 ? 1， 22 ? 1, x 31 ? 1, x 43 ? 1 , 其余 x ij ? 0 x? 2 ? ? 10 C ? ? 9 ? ? ? 715 4 14 813 14 16 114 ? ? 15 ? 13 ? ? ? 9 ?-2 -4-9 -7?0 ? ?6 ? ?0 ? ? ?013 0 5 111 10 7 4-42? ?0 ? ? 11 ? ?6 ? ?0 4? ? ? ? ? 2? ?0? 130 5 17 6 3 0-2??0? ? 9? 2? ? ? 0?最优解的取法： 从含0元素最少的行或列开始，圈出一个0元 素，用 ○表示，然后划去该○所在的行和列 中的其余0元素，用×表示，依次类推，若能 得到n个○，则得最优解X0最优解x x 14 ? 1， 22 ? 1, x 31 ? 1, x 43 ? 1 , 其余 x ij ? 0最优值： Z ???cj ?1 i ?144ijx ij ? c 14 ? c 22 ? c 31 ? c 43 ? 28例：求费用矩阵为右表的 指派问题的最优解工作人A B C 12 8 7 15 4 7 9 17 14 10 9 6 12 6 7D 7 6 14 6 10E 9 6 12 10 6甲 乙 丙 丁 戊? 12 ? ? 8 C ?? 7 ? ? 15 ? ? 47 9 17 14 109 6 12 6 77 6 14 6 109 ? ? 6 ? 12 ? ? 10 ? ? 6 ?-7 ?5 0 ? -6 2 3 ? -7 ? ? 0 10 -6 ?9 8 ? -4 ?0 60 ? 0 0 ?? 2 5 0 3 0 ? 6 7?2? ? 0 ? 5? 4? ? 2?得4个○，且不存在没打×的0修改方法！对n阶费用矩阵C，若C有n 个位于不同行不同列的 零元素，即可得最优解X0。否则，对C进行调整。?5 ? 2 ? ? ?0 ?9 ? ?0 0 3 10 8 0 ? 2 ?? 0 0 ?? 0? 2 5 0 3?7 ? 4 ? ? ?2 ? 11 ? ?0 0 3 10 8 4 2 0 5 0 1 0 0 7 0 4 2? ? 0 ? 5? 4? ? 0??6+2? 6075?-2？4? ? 2 ? -2？?7 ? 4 ? ? ?0 ? 11 ? ?00 3 8 82 0 30 ? 2 ?? 0 0 ? ?? 5 4 4? ? 0? 3??40 ?0 1最优解x x 12 ? 1， 23 ? 1, x 31 ? 1, x 43 ? 1 , x 55 ? 1 , 其余 x ij ? 0最优指派方案：甲做B工作 ，乙做C工作 丙做A工作 ，丁做D工作戊做E工作当C没有n 个位于不同行不同列的零元素时， 对C进行调整。具体步骤： 第一步：做能复盖所有0元素的最小直线集合： 1）对没有○的行打√号?5 0 2）对打√号的行上所有0元 ? ? 2 3 ? 素的列打√号 ? ? 0 10 ?9 8 3）再对打√号的列上所有○的 ? 0 ?? 6 行打√号 √ 4）重复2、3步骤直到得不出新的 打√号为止 5）对没有打√号的行画横线，所有 打√号的列画纵线，所得到的直线 既是复盖所有0元素的最小直线集合 20 ? 2 ?? 0 0 ?? 0 ? 5 0 3 70 ? 4 ??√ 6 2 ?5 ?√第二步：在没有被直线复盖的元素中找出最 小元素，让打√号的列加上这个元 素，打√号的行减去这个元素+2?5 ? 2 ? ? ?0 ?9 ? ?0 0 3 10 8 6 0 ? 2 ?? 0 0 ?? 0√ ? 5 7 5? 0 ? 4? 0 ? 2 3 6 2√ ?√ 第三步：对所得到的矩阵画○，若能得到n个○， 则得最优解，否则重复以上步骤，直至得 到n个○。??7 ? 4 ? ? ? 2 ? 11 ? ? 20 3 10 8 62 0 5 0 30 0 7 0 62? ? 0 ? 5 ? -2? 4? ? 2 ? -2?7 ? 4 ? ?0 ? 11 ? ?00 3 8 8 42 0 30 2 ? 0 ?? 0 ?? ? 5 4 4? ? 0? 3??0 ?0 1例：求费用矩阵为下表的 指派问题的最优解 最优指派方案：甲做B工作 乙做C工作 ,丙做A工作 丁做D工作 ,戊做E工作最优值 Z? 12 ? ?8 C ??7 ? ? 15 ? ?4 7 9 17 14 10工作人A B CDE甲 乙 丙 丁 戊12 8 7 15 47 9 17 14 109 6 12 6 77 6 14 6 109 6 12 10 6=32 ，即总费用为 32 +2 9 7 9 ? -7 0 ?5 0 2 ? 2? ? ? ? 6 6 6 ? -6 2 3 ? 0 0 0 ? ? ? ? -7 ? 12 14 12 ? 0 10 5 7 5 √ -2 ? ? ? 6 6 10 ? -6 ?9 8 0 0 4? ? ? ? ? 0 6 3 6 2 √ -2 7 10 6 ? -4 ?? ?最优解x x 12 ? 1， 23 ? 1, x 31 ? 1, x 44 ? 1 , x 55 ? 1 , 其余 x ij ? 0√?7 ? 4 ? ?0 ? 11 ? ?00 3 8 8 42 0 30 2 ? 0 ?? 0 ?? ? 5 4 4? ? 0? 3??0 ?0 1匈牙利法的具体步骤：第一步：变换指派问题的费用矩阵，使其在各行 各列都出现0元素： 方法：首先每行元素减去该行的最小元素， 然后每列减去该列的最小元素 第二步：进行试指派（画○） 方法：从含0元素最少的行或列开始，圈出一个0 元素，用 ○表示，然后划去该○所在的行 和列中的其余0元素，用×表示，依次类推。 若矩阵中的○的个数等于n，则得最优解 若矩阵中的○的个数&n，则进行第三步第三步：做能复盖所有0元素的最小直线集合： 1）对没有○的行打√号2）对打√号的行上所有0元素的列打√号3）再对打√号的列上所有○的行打√号 4）重复2、3步骤直到得不出新的打√号为止 5）对没有打√号的行画横线，所有打√号的 列画纵线，所得到的直线既是复盖所有0元 素的最小直线集合 第四步：在没有被直线复盖的元素中找出最小元素， 让打√号的列加上这个元素，打√号的行减 去这个元素。转第一步例：现有4份工作，4个人应聘，由于个人的技术专 长不同，他们承担各项工作所需费用如下表所示， 且规定每人只能做一项工作，每一项工作只能由一 个人承担，试求使总费用最小的分派方案。工作人 1 2 3 4最优解1 15 19 26 192 18 23 17 213 4 21 22 16 23 24 18 19 17? 15 ? ? 19 C ? ? 26 ? ? ? 1918 23 17 2121 22 16 2324 ? ? 18 ? 19 ? ? ? 17 ?x x 11 ? 1， 24 ? 1, x 33 ? 1,x 42 ? 1, 其余 x ij ? 0最优方案： 第一个人做第一件事 ； 第二个人做第四件事 ； 第三个人做第三件事 ； 第四个人做第二件事 ；总费用：70? 15 ? ? 19 C ? ? 26 ? ? ? 1918 23 17 2121 22 16 2324 ? ? 18 ? ?? 19 ? ? 17 ?√? 0 ? 1 ? ? 10 ? ? 22 3 0 23 5 1 46 4 0 6? 0 ? 1 ? ? ? 10 ? ? 2? 0 ? 0 ? ? ? 12 ? ? 12 4 0 36 4 0 610 ? ? 1 ?? 4 ? ? 1 ?10 ? ? 0 ? 6 ? ? 0 ??0 ? 0 ? ? 10 ? ?1??6 10 ?√ ?2 ? ? 3 0 √ 2 ? ? ? 0 4? ? 12 ? ? 5 0 ?√ ?3√9? ? 0 ?? 3? ? 0?? 0 ? 1 ? ? 10 ? ? 22 3 0 2√2 4 0 3 6 0 ? 6 4?9? ? 0√ ? 3? ? 0 ?√?6 12 ? ? 3 2 ? 0 6? ? 5 2?0 ?4 ?1 1 0 ?0 0 3最优解x x 11 ? 1， 24 ? 1, x 33 ? 1,x 42 ? 1 , 其余 x ? 0 ij?4、一般的指派问题 (1)求maxZ的指派问题 (2)人数与工作数不等的指派问题 (3)一个人可做几件事的指派问题 (4)某事一定由（不能由）某人做的指派问题(1)求maxZ的指派问题设有n个工作，要由 n个人来 承担，每个工作只能由一个 人承担，且每个人只能承担 一个工作。cij表示第i个人做 第j件事的收益,求总收益最大 的指派方案。?1 第i个人做第j 人件事 ? x 解： ij ? ? ? 0 第i个人不做第j 人件事 ?1 1 c 11 2 c 21 …? i c i1 …? n c n1 2c 12 c 22 ? ci2 ? cn2…? ? ? ? ? ?jc1 j c2 j ? c ij ? c nj…? ? ? ? ? ?nc1 n c2n ? c in ? c nn指派问题模型：max Z ???j ic ij x iji=1,2, …,n; j=1,2, …,nZ表示总收益? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 ? i=1,2, …,n ? s .t ? x ? x ? ? ? x ? ? ? x ? 1 1j 2j ij nj ? j=1,2, …,n ? x ? 0 ,1 i ? 1, 2 , ? , j ? 1, 2 , ? , n ?ij令 M ? max ?c ij ?工作人 1 2 … i … n1c 11 c 21 ? c i1 ? c n12c 12 c 22 ? ci2 ? cn2…? ? ? ? ? ?jc1 j c2 j ? c ij ? c nj…? ? ? ? ? ?nc1 n c2n ? c in ? c nn? M ? c11 ? ? M ? c 21 做C ? ? ? ? ?M ?c n1 ?M ? c12 M ? c 22 ? M ? cn2? ? ? ?M ? c1 n ? ? M ? c2n ? ? ? ? M ? c nn ? ?? 0指派问题最大化的数学模型：max Z ???cj iijx ij用 匈 指派问题最小化的数学模型： 牙 min Z ? ? ? ? ? M ? c ? x 利 法 ? ? ? ? Mx ? c x ?ij ij j i ij ij ij j i? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 ? s .t ? x1 j ? x 2 j ? ? ? x ij ? ? ? x nj ? 1 j=1,2, …,n ? x ij ? 0 ,1 i ? 1, 2 , ? , j ? 1, 2 , ? , n ?i=1,2, …,n???j iMxij???j ic ij x ij? M ?Z? x i1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 i=1,2, …,n ? s .t ? x1 j ? x 2 j ? ? ? x ij ? ? ? x nj ? 1 j=1,2, …,n ? x ij ? 0 ,1 i ? 1, 2 , ? , j ? 1, 2 , ? , n ?M ? max ?c ij ?max Z ?? x i1 ? x i 2 ? ? ? x ? ? ? x in ? 1 i=1,2, …,n i=1,2, …,n ? x i 1 ? x i 2 ? ? ? x ij ? ? ? x in ? 1 ? s .t ? x1 j ? x 2 j ? ? ? x ij ? ? ? x nj ? 1 j=1,2, …,n s .t ? x ? x ? ? ? x ? ? ? x ? 1 j=1,2, …,n ? 1j 2j ij nj ? x ij ? 0 ,1 i ? 1, 2 , ? , j ? 1, 2 , ? , n ? x ? 0 ,1 i ? 1, 2 , ? , j ? 1, 2 , ? , n ? ? ijj ij i??c ij x ijmin Z ? ?? ? ?Mj i? c ij ? x ij ? M ? Z则 X 1， X 2 也是 max Z 的可行解，对应的目标函数值Z1 , Z 2设 X 1， X 2 是 min Z ?的可行解， ? ? 且对应的目标函数值 Z1 ? Z 2? 由 Z 1? ? Z 2? M ? Z1 ? M ? Z 2因此，若X 0 是 min Z ?的最优解? Z1 ? Z 2即 X 0 是 min Z ?的可行解且使 min Z ?取到最小值 Z0 ? Z0则 X 0 也是 max Z 的可行解且使 max Z 取到最大值Z0? ? M ? Z0对maxZ的指派问题令 M ? max工作人 1 2 … i … nM ? c1 n ? ? M ? c2n ? ? ? ? M ? c nn ? ?1c 11 c 21 ? c i1 ? c n12c 12 c 22 ? ci2 ? cn2…? ? ? ? ? ?jc1 j c2 j ? c ij ? c nj…? ? ? ? ? ?nc1 n c2n ? c in ? c nn?c ?ij? M ? c 11 ? ? M ? c 21 做C ? ? ? ? ?M ?c n1 ?M ? c 12 M ? c 22 ? M ? cn2? ? ? ?用匈牙利法求C， 得最优解 X 0 及最优值 Z 0则 X 0 就是 max Z 问题的最优解，, 最优值为M ? Z0例：现有4份工作，4个人应聘，由 于个人的技术专长不同，他们承 担各项工作的效益如下表所示， 且规定每人只能做一项工作，每 一项工作只能由一个人承担，试 求使总效益最大的分派方案。解： M ? 17? 5 ? ? 10 C ? ? 2 ? ? ? 13 10 0 3 7 8 5 11 10 10 ? ? 3 ? 11 ? ? ? 7 ?工作人 1 2 3 41 12 7 15 42 7 17 14 103 4 9 7 12 14 6 6 7 10? 0 ? 10 ? ? ? 0 ? ? 65 0 1 03 5 9 35? ? 3 ?? 9? ? 0?? 0 ? 10 ? ? 0 ? ? 6?5 0 10 2 60 0 ??5? ? 3 ? 9? ? 0?分派方案：第1个人第3项工作 ，第2个人第2项工作 第3个人第1项工作 ，第4个人第4项工作 总效益= 9+17+15+10=51（2）人数与工作数不等的指派问题设有n个工作，要由 m个人来承担，每个工作 只能由一个人承担，且每个人只能承担一个工 作。cij表示第i个人做第j件事的费用,求总费用 最低的指派方案。 用匈牙利法 (a)m&n工作求解1c 11 c 21 ? c i1 ? c m1人 1 2 … i … m2c 12 c 22 ? ci2 ? cm 2…? ? ? ? ? ?jc1 j c2 j ? c ij ? c mj…? ? ? ? ? ?nc1 n c2n ? c in ? c mnn+1 n+2 …m0 0 ? 0 ? 0 0 0 ? 0 ? 0 ? 0 ? 0 ? ? 0 ? ? 0例：现有4份工作，6个人应聘， 由于个人的技术专长不同，他 们承担各项工作所需时间如下 表所示，且规定每人只能做一 项工作，每一项工作只能由一 个人承担，试求使总时间最少 的分派方案。? 12 ? ? 7 ? 15 C ?? ? 4 ? 6 ? ? ? 4 7 17 14 10 5 5 9 12 6 7 5 7 7 14 6 10 8 6 0 0 0 0 0 0 0? ?8 ? ? 0? 3 ? 11 0? ? ? ? ?0 0? ?2 ? 0 ? ? ? ?0 0?工作人 1 2 3 4 5 6112 7 15 4 6 427 17 14 10 5 53 49 12 6 7 5 7 7 14 6 10 8 65 60 0 0 0 0 00 0 0 0 0 02 12 9 5 04 7 1 2 0 21 8 0 4 4 2?? 00 ?? 分派方案： ? 0 ? 第1、2个人没工作 0 ? 0 0 ??? 第3个人第4项工作 0 0 ??? 0 0 ? ?? 第4个人第1项工作 0 0? ? ?? 第5个人第3项工作 第6个人第2项工作 总时间= 6+4+5+5=20 0(b)m&n工作人1c 11 c 21 ? c i1 ? c m10 0 ? 02c 12 c 22 ? ci2 ? cm 20 0 ? 0…? ? ? ? ? ?jc1 j c2 j ? c ij ? c mj…? ? ? ? ? ?? ? ?nc1 n c2n ? c in ? c mn0 01 2 … i … m m+1 m+2 … n? 0 ? 0? 0?0用匈牙利法 求解(3)一个人可做几件事的指派问题设n个人中的第k个人可同时做t件事： 把第k个人视为t个人， 这t个人做同一件事的费用系数都一样 问题化为人数为n-1+t个人的指派问题（4）某人一定不能做某事的指派问题如在minZ问题中，第k个人一定不能做第t件事：取费用系数 c ij 充分大如在maxZ问题中，第k个人一定不能做第t件事，取效率系数 c ij ? 0例：某商业公司计划开办五家新商 每家公司最多可 店。为了尽早建成营业，商业公司 承建两家商店： B1 B2 B3 B4 B5 决定由3家建筑公司分别承建。已 A11 ? 4 8 7 15 12 ? 知第Ai(i=1,2,3)个建筑公司对第 ? ? A 12 4 8 7 15 12 ? ? Bj(j=1,2,3,4,5)家新商店的建造费用 ? 7 9 17 14 10 ? A21 的报价如下表，为保证工程进度， ? 7 9 17 14 10 ? A22 ? 6 9 12 8 7 ? A31 每家建筑公司最多只能承建两个商 ? 6 9 12 8 7 ? A ? ? 32 店，且由于某种原因，第B3家商店 人数≠工作数： 不能由第A1个建筑公司承办，求使 B1 B2 B3 B4 B5 B6 总费用最少的指派方案 A11 50商店建筑公司 A1 A2 A3B1 B2 B3 B4 B5 4 8 7 15 12 7 9 17 14 10 6 9 12 8 7?4 ? 4 ? ?7 ?7 ?6 ? ?68 8 9 9 9 9715 1512 12 10 10 7 77 50 17 17 12 1214 14 8 80? ? 0 A12 ? 0 ?A21 0 ?A22 0 ?A ? 31 0 ?A 32B3不能由A1承办：?4 ? 4 ? 7 C ?? ?7 ?6 ? ?6?2 ? 2 ? 4 ? ? ?4 ?4 ? ?48 50 8 50 9 17 9 17 9 12 9 1215 12 15 12 14 14 8 8 10 10 7 7√ √√ 0 0 ? 0 ? 38 7 5 ? 0 ? 38 7 5 1 √ ? 0? ? ? ? ? 0 0 38 7 5 1 √ 0 ? 0 38 7 5 0 ? ?? ? ? ?3 1 ? 2 ? 4 5 2 0 0 ?√ 5 6 3 0 √ 0? ? ? ? ? ? 0 0? 5 6 3 0 0? ?3 1 ??√ ?? 2 ? 4 5 2 ?√ ? ? 2 1 0 0 ? 1? ?0 ? 0? 2 1 0 0 0 0 ? ? ?? ? ? ? 0 0 ? ? ?2 1 ? 0 ? 1? 0? 0 0 0? ?2 1 ? 0 ? ? √ 0 ??? 0 ??3? ?0 ? ? 3 0 ? ? 2? 2 ? ? ?2 2? ?4 3? ? ? 3? ?42 2 2 2 3 338 38 4 4 0 07 7 5 5 0 05 5 2 2 0 0?0 ? 0 ? 0 ? 3 3 036 36 2 25 5 3 33 3 00 ? 0 0 ? ?0 0 0 ?0 ??1? ? 1 ? 0? 0? 3? ? 3?A11 A12 A21 A22 A31 A32B1 B2 B3 B4 B5 B6指派方案： 1承建B1、B2 ，由A2承建B5 由A 由A3承建B3、B4 总费用=42作业：6个人应聘4份工作，由于个人的技术专长不同，他 们承担各项工作所获得的收益如下表，且规定每人 只能做一项工作，每一项工作只能由一个人承担， 试求使总收益最大的指派方案。 工作 分派方案： 1 2 3 4 人 第1、2个人没工作 1 3 5 4 5 2 6 7 6 8 第3个人第2项工作 3 8 9 8 10 第4个人第3项工作 10 10 9 11 4 第5个人第1项工作 5 12 11 10 12 6 13 12 11 13 第6个人第4项工作第一步：变换费用矩阵，使其在各行各列都出现0元素： 方法：每行减去该行的最小元素，然后每列减去该列的最小元素 第二步：进行试指派（画○） 方法：从含0元素最少的行或列开始，圈出一个0元素，用 ○表 示，然后划去该○所在的行和列中的其余0元素，用×表示，依 次类推。 若矩阵中的○的个数等于n，则得最优解 若矩阵中的○的个数&n，则进行第三步 第三步：做能复盖所有0元素的最小直线集合： 1）对没有○的行打√号 2）对打√号的行上所有0元素的列打√号 3）再对打√号的列上所有○的行打√号 4）重复以上步骤直到得不出新的打√号为止 5）对没有打√号的行画横线，所有打√号的列画纵线， 所得到的直线既是复盖所有0元素的最小直线集合 第四步：在没有被直线复盖的元素中找出最小元素，让打√号 的列加上这个元素，打√号的行减去这个元素。 转第一步
更多搜索：
All rights reserved Powered by
文档资料库内容来自网络，如有侵犯请联系客服。}