指派问题——匈牙利法_第1页
指派问题——匈牙利法_第2页
指派问题——匈牙利法_第3页
指派问题——匈牙利法_第4页
指派问题——匈牙利法_第5页
已阅读5页,还剩27页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、指派问题的求解方法指派问题的求解方法匈牙利法匈牙利法 指派问题的求解方法指派问题的求解方法2指派问题及求解方法指派问题及求解方法1 、指派问题的提出、指派问题的提出有有 n 项不同的任务,恰好分派给项不同的任务,恰好分派给n 个人分别承担,个人分别承担,由于每人完成各项任务的效率情况不同。现假设必须由于每人完成各项任务的效率情况不同。现假设必须指派每个人去完成一项任务,需考虑怎样把指派每个人去完成一项任务,需考虑怎样把 n 项任务项任务指派给指派给 n 个人,使得完成个人,使得完成 n 项任务的总的效率最高,项任务的总的效率最高,这就是指派问题。这就是指派问题。例有例有4个工人,要分别指派他们

2、完成个工人,要分别指派他们完成4项不同的工作,项不同的工作,每人做各项工作所消耗的时间如下表所示,问应如何每人做各项工作所消耗的时间如下表所示,问应如何指派工作,才能使总的消耗时间为最少。指派工作,才能使总的消耗时间为最少。3解:解:令令 xij = 1(第第 i人完成第人完成第j项工作项工作)或或0(第(第 i人不进行人不进行第第j项工作项工作)于是得到一个于是得到一个0-1整数规划问题:整数规划问题:Min z=15x11+18x12+21x13+24x14+19x21+23x22 +22x23+18x24+26x31+17x32+16x33+19x34 +19x41 +21x42+23x

3、43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作只能一人干)

4、x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干) xij 为为0-1变量变量,i,j = 1,2,3,42、指派问题的一般形式指派问题的一般形式 设有设有 n 个资源(人或机器等)个资源(人或机器等)A1, A2, , An,分配做,分配做 n 件事件事B1, B2, Bn,要求每件事必须使用要求每件事必须使用1个资源,且不同个资源,且不同事件由不同资源完成。已知事件由不同资源完成。已知 Ai 做做 Bj的效的效率(如劳动工时、成本、创造价值等)率(如劳动工时、成本、创造价值等)为为cij 。问如何进行指派可使总工作效率。问如何进行指派可使总工作效率最佳?最佳?

5、指派问题的一般形式指派问题的一般形式定义变量:设指派问题变量为定义变量:设指派问题变量为 xij, ,则共有,则共有n2 个变量,且变量取值为:个变量,且变量取值为: xij=1或或0 ( xij =1 表示表示 Ai 做做 Bj,否则取值为,否则取值为 0 )由由cij ( 0)组成的方阵组成的方阵 称为效率矩阵,模型为:称为效率矩阵,模型为: 10),2,1(1),2,1(1.1111orxnjxnixtsxczMinijniijnjijninjijij3、指派指派问题的匈牙利解法问题的匈牙利解法 1955年,库恩(年,库恩(W.W.Kuhn)利用匈牙利数学)利用匈牙利数学家康尼格(家康尼

6、格(D.Knig)关于矩阵中独立零元素)关于矩阵中独立零元素定理,提出了一种指派问题算法,被称为匈定理,提出了一种指派问题算法,被称为匈牙利解法。牙利解法。 指派问题的任何可行解由指派问题的任何可行解由 n2个满足约束条件个满足约束条件的数的数 xij 组成组成。这些这些 xij中,有中,有 n个为个为1,其余,其余均为均为0,且此,且此 n个个1必位于损益表中不同行不必位于损益表中不同行不同列中,由此同列中,由此 n个个xij=1 确定了确定了n 个相应的个相应的cij 也位于效率矩阵中的不同行不同列上,相应也位于效率矩阵中的不同行不同列上,相应的可行解的可行解 的目标函数值由此的目标函数值

7、由此 n个个cij 之和确定。之和确定。指派问题的匈牙利解法指派问题的匈牙利解法定理定理6.1:设:设 C=(cij)是一个效率矩阵,若可行是一个效率矩阵,若可行解解x*=(xij)的的 n个个1所对应的所对应的 n个个 C=(cij)均为均为0,则则x* 是最优解。是最优解。定理定理6.2:设给定了以:设给定了以 C=(cij)为效率矩阵的指为效率矩阵的指派问题派问题 G,现将,现将 C的元素的元素cij 改变为:改变为: cij=cij- i- j,其中:其中: i, j 为常数。为常数。 则以则以C=(cij) 为效率矩阵的指派问题为效率矩阵的指派问题G 与与 G有相同的最优解。有相同的

8、最优解。 约化矩阵约化矩阵:效率矩阵通过行或列同时加上:效率矩阵通过行或列同时加上(减去)一个常数得到的矩阵。(减去)一个常数得到的矩阵。指派问题的性质定理的证明指派问题的性质定理的证明定理定理6.2:对于指派问题,效率矩阵的任一行:对于指派问题,效率矩阵的任一行(或列或列)减去减去(或加上或加上)一个相同的数得到的新指一个相同的数得到的新指派问题与原问题同解。派问题与原问题同解。s)( s)(xcxc xs)(xcxc s)x(cxc=z n1jkjkjnki1in1jijijn1jkjn1jkjkjnki1in1jijijn1jkjkjnki1in1jijijz指派问题的匈牙利解法指派问题

9、的匈牙利解法 根据此定理,可以对根据此定理,可以对 做如下改变,目的是做如下改变,目的是找出找出C 中的中的 n个不同行不同列的个不同行不同列的0元素元素: 将将 C的每一行减去该行中的最小元素,得的每一行减去该行中的最小元素,得到到C矩阵矩阵 ,则,则C 的每行中均至少出现一个的每行中均至少出现一个0元素,且所有元素,且所有cij 0 。同样,对。同样,对C 的列亦进的列亦进行如此计算,由此,我们完全可以从原效行如此计算,由此,我们完全可以从原效率矩阵率矩阵 出发,得到一个新的效率矩阵出发,得到一个新的效率矩阵 ,使,使 C的的每行每列中均至少存在一个每行每列中均至少存在一个0元素元素,而,

10、而不改变问题的最优解。不改变问题的最优解。指派问题的匈牙利解法指派问题的匈牙利解法约化矩阵性质应用约化矩阵性质应用347100320460315310),2(),5(),2(),2(43219322875982537532列减列减,再对第,再对第得到得到行分别加行分别加,第第例:例: C约化矩阵性质应用(续)约化矩阵性质应用(续)注:不同行不同列的注:不同行不同列的0 0元素,称为元素,称为独立独立0 0元素元素, ,当矩阵中含有当矩阵中含有n个独立个独立0 0元素时即得解。元素时即得解。142822141)0(0)0(2043)0(31231)0(52342311 fxxxx相应最小费用相应

11、最小费用是一组最优解,是一组最优解,显然,显然,得到得到 6072395006024310指派问题的匈牙利解法指派问题的匈牙利解法定理定理6.3 6.3 设矩阵设矩阵C C中含有中含有0 0元素,那么划去元素,那么划去C C中中所有所有0 0元素所需的最少直线数等于元素所需的最少直线数等于C C中独立中独立0 0元素的个数。元素的个数。例例 下列矩阵中,最少下列矩阵中,最少3 3条直线覆盖了所有条直线覆盖了所有0 0元元素,因此可判定矩阵有素,因此可判定矩阵有3 3个独立个独立0 0元素。元素。13指派问题的匈牙利解法指派问题的匈牙利解法步骤步骤Step 1. 每行减去该行的最小数每行减去该行

12、的最小数, 每列减去该每列减去该列的最小数,使矩阵每行每列均有列的最小数,使矩阵每行每列均有0元素;元素;Step 2. 寻找独立寻找独立0元素元素 从从单单个个0元素的行元素的行(列列)开始,给开始,给0加圈,记作加圈,记作,然后划去所在列然后划去所在列(行行)的其它的其它0元素,记为元素,记为;重复;重复进行,直到处理完所有列进行,直到处理完所有列(行行)的的单个单个0元素;元素; 若若还还存在没有画圈的存在没有画圈的0元素元素(同行或同列中的同行或同列中的0元素元素多于多于1个个),则从剩余的,则从剩余的0元素最少的行元素最少的行(列列)开始,开始,选选0元素画圈,然后划掉同行同列的其它

13、元素画圈,然后划掉同行同列的其它0元素,元素,反复进行,直到所有反复进行,直到所有0元素均被圈出或划掉为止;元素均被圈出或划掉为止;若若元素的数目元素的数目m=n,则该指派问题的最优,则该指派问题的最优解已经得到,否则转入解已经得到,否则转入Step 3;指派问题的匈牙利解法指派问题的匈牙利解法步骤(续)步骤(续)Step 3. 设有设有 mn 个个, 找最少覆盖所有找最少覆盖所有0的直线的直线1) 对没有的行打对没有的行打2) 对已打对已打行中含行中含所在列打所在列打3) 对已打对已打列中含所在行打列中含所在行打4) 重复重复2)3), 直至没有要打直至没有要打的行和列为止的行和列为止5)

14、对没有打对没有打的行划横线的行划横线, 对打对打的列划竖线的列划竖线得到最少覆盖所有得到最少覆盖所有0的直线数的直线数l。 若若l0充分大充分大)非标准形式的指派问题非标准形式的指派问题例例任务与人员数不等的情况任务与人员数不等的情况 分配甲、乙、丙、丁分配甲、乙、丙、丁 4 人去完成人去完成 5项任务,每人完成各项任务的时间如项任务,每人完成各项任务的时间如下表。由于任务多,规定其中有一人下表。由于任务多,规定其中有一人可兼完成两项任务,试确定总花费时可兼完成两项任务,试确定总花费时间最少的分派方案。间最少的分派方案。非标准形式的指派问题非标准形式的指派问题例例各人完成不同任务的效率情况各人

15、完成不同任务的效率情况 任务任务人人 A B C D E甲甲59112217乙乙242311518丙丙14782012丁丁42216325非标准形式的指派问题非标准形式的指派问题例例解:增加一人,其完成各项任务时间为该任解:增加一人,其完成各项任务时间为该任务完成的最少时间:务完成的最少时间: 任务任务人人 A B C D E甲甲59112217乙乙242311518丙丙14782012丁丁42216325戊戊4丁丁7丙丙8丙丙3丁丁12丙丙非标准形式的指派问题非标准形式的指派问题例例人多任务少,允许某人空闲人多任务少,允许某人空闲 从甲、乙、丙、丁、戊从甲、乙、丙、丁、戊5人中选人中选 4 人去完成人去完成 4 项任务,每人完成各项项任务,每人完成各项任务的时间如下表。规定每人只能完任务的时间如下表。规定每人只能完成一项任务。由于某种原因,甲必须成一项任务。由于某种原因,甲必须被分配一项任务,丁不承担第被分配一项任务,丁不承担第 4 项任项任务,试确定总花费时间最少的分派方务,试确定总花费时间最少的分派方案。案。 非标准形式的指

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论