匈牙利解法在救援中的应用

论文总字数：11515字

摘 要

关键词: 指派问题，匈牙利解法，系数矩阵

Abstract: In this paper, we introduced the classification and the solution method of rescue assignment problem on the basis of the Hungarian method,and illustrated the Hungarian method in the application of the problem combining with some examples.

Keywords: assignment problem, the Hungarian method, the matrix of coefficients

目 录

1 引言……………………………………………………………………… 3

2 救援指派问题…………………………………………………………… 3

2.1 标准指派问题………………………………………………………… 3

2.1.1 模型建立…………………………………………………………… 4

2.1.2 模型求解…………………………………………………………… 5

2.1.3 模型举例…………………………………………………………… 7

2.2 非标准指派问题……………………………………………………… 9

2.2.1 最大化指派问题…………………………………………………… 10

2.2.2 人数与任务数不等的指派问题…………………………………… 12

3 二次救援指派问题……………………………………………………… 16

3.1 模型简介……………………………………………………………… 16

3.2 模型建立……………………………………………………………… 16

3.3 模型求解……………………………………………………………… 17

结束语 ……………………………………………………………………… 18

参考文献 …………………………………………………………………… 19

致谢 ………………………………………………………………………… 20

附录 ………………………………………………………………………… 21

1 引言

救援,是当事故与灾难发生后,营救人员为了最大程度减少其对生命与财产的伤害而做出的一系列营救行动.指派问题,其基本条件是,依据实际情况与特定要求指派人员完成不同的任务,使指派方案的总体效果最好^[1].当事故与灾害发生后,救援小组如何在时间紧、地点散、任务多等情形下,根据救援行动的实际需求与目标,快速科学地指派救援人员完成不同的救援任务,使救援行动的总体效益最佳,这就是本文所述的救援指派问题所探讨的范畴.

接下来将从救援指派问题的分类及求解方法进行探究,这里把该问题分成三类:标准型、非标准型以及二次指派问题.对于标准型,因为根据模型得出的系数矩阵的行数与列数相同,所以该矩阵为方阶矩阵,则可直接采用匈牙利解法来确定救援指派的最佳方案.匈牙利数学家狄·康尼格的关于矩阵中独立零元素的定理在1955年被库恩运用并改进,进而提出了匈牙利解法^[1].该法的出发点为:若系数矩阵的全体元素,且矩阵中存在一组既不属于同一行又不属于同一列的零元素,那么该组零元素在解矩阵中对应的,其余的,则

(1)

即为该问题的最优解,且这组位于特殊位置的零元素被叫做独立零元素^[2].对于非标准型,因为其系数矩阵不为方阶矩阵,所以需将矩阵标准化后才可采用匈牙利解法求解.而对于二次指派问题,此文不做过多论述,仅简单介绍.

2 救援指派问题

这里所述的救援指派问题,是在假设已知救援任务的各项需求（如所需救援人员的特征评价指标、救援人员的需求数量等）的前提下,仅从救援人员的自身因素这一个方面确定的具体的救援指派问题.下面根据指派问题的分类以及对匈牙利解法的了解与应用,来确定救援指派问题的最佳解决方案.

2.1 标准指派问题

在某次救援行动中,为了达到总用时最短、资源消耗最低等最小化目标的要求,有项任务需派某个救援小组去做,而这个救援小组刚好有个人.假定每个人完成且只完成一项任务,每项任务能只能被一个人完成,问该如何指派才能使整体救援行动的效益最佳？这类在救援中的总体极小任务分配问题就是标准救援指派问题.

2.1.1 模型建立

由于每个人的技巧、经验或多或少存在差异,每个人完成不同任务的效益（用时、资源消耗、所花费成本等）也会有所不同,于是用表示指派第个人去做第项任务所取得的效益,并假设通常把目标函数的系数写成的矩阵形式,即

(2)

称其为系数矩阵,也称系数矩阵或价值矩阵^[3].

引入个变量:

这样,该问题的数学模型可写为

(3)

(4)

(5)

(6)

该模型中,式(3)之意是整体救援行动的效益最佳,式(4)之意是第项任务派且仅派一个人去做,式(5)之意是第个人做且仅做一项任务,式(6)之意是决策变量仅为0或1^[4].

对于它的每个可行解,可用解矩阵来表示:

(7)

在矩阵的每一行及每一列中的各个元素仅包括一个“1”,其他均为“0”,用来满足式(4)和式(5).每个指派问题都有个可行解.

2.1.2 模型求解

由前文所述模型可知,此类问题是规划的一类特殊问题.匈牙利解法利用这种问题的特点,对系数矩阵进行适当转换,从而找到新的独立零元素,得出解矩阵,以此确定最优指派方案.下面就来详细讲解匈牙利解法.

(一)适用条件

剩余内容已隐藏，请支付后下载全文，论文总字数：11515字