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

引入 个 变量 :

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

该模型中,式(3)之意是整体救援行动的效益最佳,式(4)之意是第 项任务派且仅派一个人去做,式(5)之意是第 个人做且仅做一项任务,式(6)之意是决策变量仅为0或1对于它的每个可行解,可用解矩阵来表示:

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

2.1.2  模型求解

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

(一)适用条件

基于标准型救援指派问题人数与任务数一一对应和其所求目标为min这两个特点,使用匈牙利解法求解的系数矩阵应为方阶矩阵且其元素均为非负数.

(二)基本原理

定理1  设指派问题的系数矩阵是 ,若把 的各行（或各列）中每个元素都减掉同一或正或负的常数 ,假如得到的变换后的矩阵是 ,那么系数矩阵为 的新问题的最优解跟原来的一样,但其最优值比原最优值少t[5].文献综述

证  已知式(3)到式(6)为原指派问题的模型,现将矩阵 的第 行的每个元素都减去同一常数 ,记新指派问题的目标函数为 ,则有

式（8）倒数第二步运用了等式（3）.因此有

而约束方程从未发生改变,于是它们的最优解必定一样,且其值差常数t.

推论 1  如果把指派问题的系数矩阵中各行及各列都减去每行和每列中的最小元素,那么最优解未变[4].

证  只需反复运用定理1即可得证.

定理2   相等[5].

本定理的证明是由匈牙利数学家狄·康尼格给出的,详细内容本文不作过多叙述.

（三）解题步骤

其求解步骤如下所示.

第一步  对系数矩阵进行变换.先找出各行最小的元素,并逐行减去该元素,再找出各列最小的元素,并逐列减去该元素,从而使系数矩阵的每行每列出现的零元素都不少于一个,且同时没有负元素[1].转第二步.

第二步  试指派,找到独立零元素.

○1 若行（或列）中仅有一个零元素,则对该零元素加圈（可标记成○0),表示人与任务已一 一对应；若每一行和列里的零元素都超过一个,可随意选取一个加圈,并划掉其所在行和列中的其余零元素[1]；

○2 每圈一个,就将其处于一列（或一行）的其余零元素划掉（可标记成Ø）,不然说明重复指派没有意义；

○3 重复○1和○2,一直到矩阵 中的零元素全都被标记才可以结束,最后剩下的○0即是独立零元素.

此时,矩阵会出现两种情况:

第一种情况,若独立零元素的个数恰好等于 ,就能够说明已获得其中一种最佳解决方案.这时,把解矩阵中与独立零元素相对应的元素变成“1”,其余的变成“0”,所得的解矩阵就是最优解矩阵[1].

第二种情况,若独立零元素的个数少于 ,则表示仍需继续求解最佳解决方案.此时,应该作出最少的直线,使其刚好能覆盖全部零元素,方法如下:

1）对没有○0的行打“√”；来!自-优.尔,论:文+网www.youerw.com 匈牙利解法在救援中的应用(2):http://www.youerw.com/shuxue/lunwen_81129.html