3.2求解指派问题的匈牙利算法
由于指派问题的特殊性，又存在着由匈牙利数学家Konig提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵C?(cij)一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B?(bij) ，则以C或B为系数矩阵的指派问题具有相同的最优指派。
例8 求解指派问题，其系数矩阵为
?16?17C???24??17?1?0B1???7??1151922?211918??
221817??192216?047?421??
510??360?解 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得
再将第3列元素各减去1，得
?10*37??*?0411? B2??*?7500??*?1350??以B2为系数矩阵的指派问题有最优指派 ?1234???2134?? ??由等价性，它也是例7的最优指派。 有时问题会稍复杂一些。
例9 求解系数矩阵C的指派问题
?127979??89666???C??717121412?
??15146610????4107106??解：先作等价变换如下
?7?6?7?6?4容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n?5，最优指派还无法看出。此时等价变换还可进行下去。步骤如下：
(1) 对未选出0元素的行打?； (2) 对?行中0元素所在列打?；
(3) 对?列中选中的0元素所在行打?； 重复（2）、（3）直到无法再打?为止。
可以证明，若用直线划没有打?的行与打?的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令?行元素减去此数，?列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得
?127979??50*20?89666??2300*????717121412???0*1057???15146610???980*0??36?4107106???06 ?2?0??5??? 4?2????7?4??0??11??00202?3000??8353?
?8004?4140??现在已可看出，最优指派为???12345?。 ???24135?§4 对偶理论与灵敏度分析
4.1原始问题和对偶问题
考虑下列一对线性规划模型：
max和
cTx s.t. Ax?b,x?0 (P) bTys.t. ATy?c,y?0(D)
min称（P）为原始问题，（D）为它的对偶问题。
不太严谨地说，对偶问题可被看作是原始问题的“行列转置”：
（1） 原始问题中的第j列系数与其对偶问题中的第j行的系数相同； （2） 原始目标函数的各个系数行与其对偶问题右侧的各常数列相同； （3） 原始问题右侧的各常数列与其对偶目标函数的各个系数行相同； （4） 在这一对问题中，不等式方向和优化方向相反。 考虑线性规划：
mincTxs.t.Ax?b,x?0
把其中的等式约束变成不等式约束，可得
?A??b?mincx s.t. ??x???,x?0
??A???b?T它的对偶问题是
?y1?maxbs.t. A?A???c
?y2?其中y1和y2分别表示对应于约束Ax?b和?Ax??b的对偶变量组。令y?y1?y2，
?T?y1??b???y2?T??TT?则上式又可写成
maxbTy s.t.