下载文档原格式
第四讲 指派模型及匈牙利方法§ 4.1 引言将不同的任务分派给若干人去完成，由于任务有难易，人员素质有高低，因此各人去完成不同的任务的效率就有差异。
我们的问题是：应分派何人去完成哪种任务使得总效率最高（或所花费的时间最少，或所需的费用最低）？这一类问题称为指派问题或分配问题。
指派问题的一般提法是：用最佳方法按照一对一的原则把“任务”指派给“人”。
具体地就是：设有n 个人A 1，A 2，…，A n ，被分派去完成n 项工作B 1，B 2，…，B n ，要求每项工作需且仅需一个人去完成，每个人需完成且仅需完成一项工作。
已知A i 完成B j 工作的效率（如工时、成本或价值等）为c ij 。
问应如何指派，才能使总的工作效率最好？指派问题本质上是0—1规划问题。
设X ij 表示A i 完成B j 工作，并令⎪⎩⎪⎨⎧=工作去完成当不指派工作去完成当指派j i j i ij B A B A X 0 1，则指派模型的标准形式为), ,2 ,1,( }1 ,0{ ) , ,2 ,1( 1 ), ,2 ,1( 1s.t.)0( min 1111n j i X n j X n i Xc X c Z ij n i ij nj ijij ni nj ij ij ΛΛΛ=∈====≥=∑∑∑∑====由c ij 组成的方阵C = (c ij )n ⨯n 称为效率矩阵。
只要效率矩阵C 给定，指派问题也就相应确定。
若0ij x 为指派模型的最优解，则n 阶方阵X = (0ij x ) 称为指派模型的最优解方阵。
事实上，方阵X 为一置换方阵，即该矩阵中的每一行、每一列只有一个“1”。
显然，指派问题是运输问题的特例。
§ 4.2 匈牙利方法除了求解0—1规划外，解决指派问题还有其特殊的方法，它是由匈牙利数学家柯尼格（D. Köngig ）提出的，因此得名匈牙利方法（The Hungarian Method of Assignment ）。
130基于空缺链和匈牙利算法的资源分配问题杨 子 马 硕 贾 隆 哈尔滨工业大学（威海）摘 要：对于寄居蟹，壳是它们生命的保障，寄居蟹要很慎重地思考并且评估壳资源，才会交换他们的壳，同时它们也能着眼于未来，所以它们有着最好的蟹类的平均主义思想。
而我们人类从中看出空屋链模型和匈牙利算法对于社会资源分配的启示，例如职位招聘，房屋流动等。
关键词：空屋链 匈牙利算法 资源分配一、引言为了说明让每个人都受益的交换策略的起源，有以下背景。
寄居蟹，一种在美国非常流行的宠物类型，依靠其它生物的壳作为保护。
当蟹遇到了新壳，会立即从住所出来，试穿新住所，这是典型的寄居蟹式作风。
但如果这个新壳有些偏大，它可不会失望的走掉，相反，它会站在这个新壳附近一直等待着，直到其它的蟹出现，那些新来的都会试试这个新壳。
但如果这个新壳对于新来的来说也很大的话，那么它们会一起等待，有时，一个新壳旁边的寄居蟹甚至20组之多。
但这些蟹不是随机的，相反，它们按个头从大到小排成整齐一排。
一旦有一个蟹能够适应这个新壳，队伍中的所有蟹都将会迅速交换它们的壳。
队伍前最大的的蟹将会遗弃它自己的壳，然后那第二大的寄居蟹将会使用那个被最大的寄居蟹遗弃的壳。
然后一直这样传递下去。
由此，这个连续的交换资源使得队伍每一个个体都能得到好处的方式（经济学家称为“空缺链”）启示我们发现更优秀的资源分配方式。
二、模型1.基本模型。
空缺链最初出现在住宅市场，对家庭的初始迁移，包含新家庭或家庭搬走留下的住房市场。
当这个初始空屋单位是第一个房子，当全家搬到了另一个空房子，这个空缺链将继续。
户主的家庭没有搬或当以家庭为单位的房屋拆迁，空置链停止。
我们以职位为社会资源为例，探讨社会资源的更有利分配。
1.1定义和符号。
V i：在i区的空位数 N：区域同质化数 r ij ：从i到j地区空置转让转换率 V i r i ：1.从i到的空缺j的地区总流面积2.家庭总迁移从i流动到j区面积 F i ：i区空置损失率 G i ：i区空置生成率 q ij ：从i空缺转移到j区概率 Σj m：从i区住宅总面积中被选择的机会 1.2假设。
