整 数 规 划
(Integer Programming)
第一节.整数规划问题的提出
一、整数规划的一般形式
1、实例：
例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5－1：
13
24
托运限制
20
10
2
5
5
4
甲
乙
利润
每箱（百元）
重量
每箱（百斤）
体积
每箱（米3）
货物
问两种货物各托运多少箱，可使获得的利润为最大？
2、整数规划一般形式
解：设托运甲、乙两种货物x1，x2箱，用数学式可表示为：
整数规划的数学模型
一般形式
依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、0－1整数规划。
纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。
全整数规划：除了所有决策变量要求取非负整数外，系数aij和常数bi也要求取整数（这时引进的松弛变量和剩余变量也必须是 整数）。
混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。
0－1整数规划：所有决策变量只能取 0 或 1 两个整数。
整数规划与线性规划的关系
从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。
举例说明。
例：设整数规划问题如下
首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。
图
用 解法求出最优解
x1＝3/2, x2 = 10/3
且有Z = 29/6
x1
x2
⑴
⑵
3
3
(3/2,10/3)
现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3) (2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。
按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。
因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。
如上例：其中（2，2）（3，1）点为最大值，Z=4。
目前，常用的求解整数规划的方法有：
分支定界法和割平面法；
对于特别的0－1规划问题采用隐枚举法和匈牙利法。
在20世纪60年代初 Land Doig 和 Dakin 等人提出了分枝定界法.由于该方法灵活且便于用计算机求解,所以目前已成为解整数规划的重要方法之一.分枝定界法既可用来解纯整数规划,也可用来解混合整数规划.
分枝定界法的主要思路是首先求解整数规划的伴随规划（整数规划的松弛问题） ,如果求得的最优解不符合整数条件,则增加新约束——缩小可行域;将原整数规划问题分枝——分为两个子规划,再解子规划的伴随规划……通过求解一系列子规划的伴随规划及不断地定界 .最后得到原整数规划问题的整数最优解 .
分枝定界法
基本思路
考虑纯整数问题：
整数问题的松弛问题：
例
某公司计划建筑两种类型的宿舍.甲种每幢占地 ×103m2, 乙种每幢地×103m2.该公司拥有土地3×103m2. 计划甲种宿舍不超过 8 幢,乙种宿舍不超过4幢.甲种宿舍每幢利润为10万元，乙种宿舍利润为每幢20万元.问该公司应计划甲、乙两种类型宿舍各建多少幢时,能使公司获利最大 ?
解 设计划甲种宿舍建 幢,乙种宿舍建 幢,则本题数学模型为 :
这是一个纯整数规划问题,称为问题 。将(1)中约束条件
的系数全化为整数,改为：
（1）
然后去掉整数条件,得到问题 的伴随规划 (2), 称之为
问题
（2）
用单纯形法求解问题 , 得到最优解及最优值：
1. 计算原问题 目标函数值的初始上界
因为问题 的最优解不满足整数条件,因此 不是问题
的最优解,又因为 的可行域 问题 的可行域 ,
故问题 的最优值不会超过问题 的最优值. 即有
因此可令 作为 的初始上界
即
一般说来,若问题 无可行解,则问题 也无可行解,停止计
算。若问题 的最优解 满足问题 的整数
条件,则 也是问题 的最优解,停止计算.
2. 计算原问题 目标函数值的初始下界
若能从问题 的约束条件中观察到一个整数可行解,则可将
其目标函数值作为问题 目标函数值的初始下界,否则可令
初始下界Z=-∞.给定下界的目的,是希望在求解过程中寻找
比当前 更好的原问题的目标函数值 .
对于本例,很容易得到一个明显的可行解X=(0,0)T,Z=0. 问
题 的最优目标函数值决不会比它小,故可令 =0.
3. 增加约束条件将原问题分枝
当问题 的最优解 不满足整数条件时,在 中任选一个
不符合整数条件的变量.如本例选 显然问题 的
整数最优解只能是 或 ,而绝不会在5与6之间.
因此当将可行域 切去 部分时,并没有切去 的
整数可行解.可以用分别增加约束条件 及 来达
到在 切去 部分的目的. 切去 后就分
为 及 两部分,即问题 分为问题 及问题 两枝子
规划.
问题
问题
作出问题 的伴随规划 则问题 的可行
域为 见图2(b). 以下我们将由同一问题分解出的两
个分枝问题称为"一对分枝".
4. 分别求解一对分枝
在一般情况下,对某个分枝问题(伴随规划)求解时,可能出现
以下几种可能:
(a)
(a)
(b)
图2
(1 ) 无可行解
若无可行解,说明该枝情况己查明,不需要由此分枝再继续
分枝,称该分枝为 “树叶”，剪枝。
(2) 得到整数最优解
若求得整数最优解，则该枝情况己查明,不需要再对此继续
分枝，该分枝也是 "树叶".
(3) 得到非整数最优解
若求得某个分枝问题得到的是不满足整数条件的最优解，
①该最优解的目标函数值Z小于当前的下界 ，则该
枝内不可能含有原问题的整数最优解，称为“枯枝”，需
剪掉。
②该最优解的目标函数值Z大于当前的下界 ，则仍需对该枝继续分枝，以查明该分枝内是否有目标函数值比当前的 更好的整数最优解。
本例中问题 及问题 的模型及求解结果如下：
还要区分两种情况：
问题
问题
解为:
解为:
问题 的解 是整数最优解,它当然也是问题
的整数可行解,故 的整数最优解
即此时可将 修改为:
同时问题 也被查清, 成为“树叶”。
因为 ,不满足整数条件, 故问题 分别增加约
束条件： 及 。分为 与 两枝, 建立相应的
伴随规划——问题 与
问题
问题
它们的可行域分别为
见图3。
图3
因为 ，问题
无可行解，此问题已
是"树叶", 已被查清.
求解问题 , 得到最优解
5. 修改上、下界 与
(l) 修改下界
修改下界的时机是:每求出一个整数可行解时,都要作修改
下界 的工作.
修改下界 的原则:在至今所有计算出的整数可行解中,选
目标函数值最大的那个作为最新下界 。
因此在用分枝定界法的求解全过程中,下界 是不断增大的.
(2) 修改上界
上界 的修改时机是:每求解完一对分枝,都要考虑修改上界
修改上界 的原则是:挑选在迄今为止所有未被分枝的问题的
目标函数值中最大的一个作为新的上界.新的上界 应该小于
原来的上界 .
在分枝定界法的整个求解过程中,上界的值在不断减小.
问题
问题
解为:
因为此时 的解为整数解,因此修改下界为 =130, 而此
时所有未被分枝的问题( )的目标函数值中最大的
为 , 故修改上界 =130.
6. 结束准则
当所有分枝均已查明(或无可行解——“树叶”, 或为整数可
行解——“树叶”,或其目标函数值不大于下界 ——”枯枝”）
且此时 ，则已得到了原问题的整数最优
解，即目标函数值为下界 的那个整数解 .
在本例中,当解完一对分枝 后, 得到
又 是"树叶", 为"枯枝", 因此所有分枝( )
均已查明.故已得到问题 的最优解:
或
故该公司应建甲种宿舍7幢乙种宿舍3幢; 或甲种5幢、乙
种4幢时,获利最大.获利为130万元.
可将本例的求解过程与结果用图5 来描述.
问题
问题
问题
问题
问题
问题
问题
不可行
分枝规则
情况 2, 4, 5 找到最优解
情况 3 在缩减的域上继续分枝定界法
情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4 或 5
下面将分枝定界法求解混合型整数规划的计算步骤归纳如下:
第1步:将原整数线性规划问题称为问题 .去掉问题
的整数条件,得到伴随规划问题 ·
第2步:求解问题 , 有以下几种可能:
(l) 没有可行解, 则 也没有可行解, 停止计算。
(2) 得到 的最优解, 且满足问题 的整数条件, 则 的
最优解也是 的最优解, 停止计算.
(3) 得到不满足问题 的整数条件的 的最优解,记它的
目标函数值为 , 这时需要对问题 (从而对问题 ) 进行分枝, 转下一步。
(3) 得到不满足问题 的整数条件的 的最优解, 记它的目
标函数值为 , 这时需要对问题 ( 从而对问题 ) 进行分
枝 , 转下一步 .
第3步:确定初始上下界 与 .
以 作为上界 . 观察出问题 的一个整数可行解,将其
目标函数值记为下界 . 若观察不到,则可记 = -∞.转
下一步.
第4步: 将问题 分枝.
在 的最优解 中,任选一个不符合整数条件的变量 ,
其值为 , 以 表示小于 的最大整数.构造两
个约束条件:
将这两个约束条件分别加到问题 的约束条件集中,得到
的两个分枝:问题 与 ·
对每个分枝问题求解,得到以下几种可能:
(1) 分枝无可行解——该分枝是 " 树叶 ".
(2) 求得该分枝的最优解, 且满足 的整数条件. 将该最
优解的目标函数值作为新的下界 , 该分枝也是"树叶".
(3) 求得该分枝的最优解,且不满足 的整数条件,但其目标函数不大于当前下界 , 则该分枝是“枯枝”需要剪枝.
(4) 求得不满足 整数条件的该分枝的最优解,且其目标
函数值大于当前下界 ,则该分枝需要继续进行分枝.
若得到的是前三种情形之一,表明该分枝情况已探明,不需要
继续分枝.
若求解一对分枝的结果表明这一对分枝都需要继续分枝,则
可先对目标函数值大的那个分校进行分枝计算,且沿着该分
枝一直继续进行下去,直到全部探明情况为止.再返过来求解目标函数值较小的那个分枝.
第6步:修改上、下界.
修改下界 ：每求出一次符合整数条件的可行解时,
都要考虑修改下界 , 选择迄今为止最好的整数可行解
相应的目标函数值作下界
(2) 修改上界 ：每求解完一对分枝,都要考虑修改上界
上界的值应是迄今为止所有未被分枝的问题的目标函数值
中最大的一个.
在每解完一对分枝、修改完上、下界 和 后,若已有
此时所有分枝均已查明,即得到了问题 的最优值
求解结束.
若仍有 ,则说明仍有分枝没查明,需要继续分枝, 回到第4步
运算步骤
解松弛问题
满足要求?
结束
分枝
Y
N
选一分支写出并求解松弛问题
判定是否
为整数解
初始分支为可行解集，初始界为无穷
判定是否
分支集空
Y停止
当前最好解为最优解
N
Y
判定最优值是否
优于当前界
判定最优值是否
优于当前界
按非整数变量分支并加入分支集
以最优解替代当前最好解最优值替代当前界
Y
Y
N
剪枝
N
N
求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。
可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程
当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解
一般整数规划问题属于一类未解决的难题，只有少数特殊问题有好的算法。
练习：用分枝定界法求解整数规划问题
LP1
x1=1, x2=7/3
Z(1) ＝10/3
LP
x1=3/2, x2=10/3
Z(0) ＝29/6
LP2
x1=2, x2=23/9
Z(2) ＝41/9
x1≤1
x1≥2
LP5
x1=1, x2=2
Z(5) ＝3
LP6
无可
行解
＃
＃
x2≤2
x2≥3
LP3
x1=33/14, x2=2
Z(3) ＝61/14
LP4
无可
行解
x2≤2
x2≥3
＃
LP7
x1=2, x2=2
Z(7) ＝4
LP8
x1=3, x2=1
Z(8) ＝4
x1≤2
x1≥3
＃
＃
例：用割平面法求解整数规划问题
解：增加松弛变量x3和x4 ，得到(LP)的初始单纯形表和最优单纯形表：
0
1
0
x4
0
0
1
0
0
－Z
0
2
-3
0
x4
0
1
2
3
6
x3
0
x3
x2
x1
b
XB
CB
0
1
0
Cj
-1/4
1/4
-1/6
x4
0
-1/4
0
0
-3/2
－Z
1/4
1
0
3/2
x2
1
1/6
0
1
1
x1
0
x3
x2
x1
b
XB
CB
0
1
0
Cj
此题的最优解为：X＊ =(1 , 3/2) Z = 3/2 但不是整数最优解。看x2所在行。
将系数和常数项分解
由于x2，x3，x4为非负整数，等式右端为整数，（）内为正，左端必为负数。所以，有：
这就得出了一个切割方程，将它作为增加约束条件。
0
1/4
1/4
1
0
3/2
x2
1
-1/4
-1/4
-1/6
x4
0
0
1
0
s1
0
-1/4
0
0
-3/2
－Z
-1/4
0
0
-1/2
s1
0
1/6
0
1
1
x1
0
x3
x2
x1
b
XB
CB
0
1
0
Cj
现将生成的割平面条件加入松弛变量，然后加到表中：
1
0
0
1
0
1
x2
1
0
1
-1/3
x4
-1
-4
2/3
s1
0
0
0
-1
－Z
1
0
0
2
x3
0
0
0
1
2/3
x1
0
x3
x2
x1
b
XB
CB
此时，X1 ＝(2/3, 1), Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：
将生成的割平面条件加入松弛变量，然后加到表中：
0
2/3
-1/3
0
0
1
2/3
x1
0
0
1
0
0
1
0
1
x2
1
0
-4
1
1
0
0
2
x3
0
-1
-2/3
s1
0
-2/3
x4
0
1
s2
0
0
0
-1
－Z
0
0
0
-2/3
s2
0
x3
x2
x1
b
XB
CB
1
0
-1
0
0
1
0
x1
0
3/2
0
-1
0
1
0
0
x2
1
-6
0
5
1
0
0
6
x3
0
0
1
s1
1
1
x4
-3/2
-3/2
s2
0
0
0
0
－Z
0
0
0
1
s1
0
x3
x2
x1
b
XB
CB
-1/2
1
0
0
0
1
1
x1
0
0
1
0
0
1
0
1
x2
1
3/2
-5
0
1
0
0
1
x3
0
-1
1
s1
0
1
x4
0
-3/2
s2
0
0
0
-1
－Z
0
0
0
1
x4
0
x3
x2
x1
b
XB
CB
至此得到最优表，其最优解为 X＊= (1 , 1) , Z = 1, 这也是原问题的最优解。
有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。
把(2)(3)代入(1)并移项得：
例 写出下列问题的切割方程
-8/3
-1/3
0
0
-23
2/3
-1/6
0
1
5/2
x1
6
-1/3
1/3
1
0
2
x2
4
x4
x3
x2
x1
b
xB
CB
0
0
4
6
Cj
解：
例：用割平面法求解数规划问题
1
0
5
4
20
x4
0
0
0
x4
0
0
1
1
－Z
1
1
2
6
x3
0
x3
x2
x1
b
XB
CB
0
1
1
Cj
1/3
－2/3
1
0
8/3
x2
1
－1/6
－1/6
x4
－1/6
0
0
-13/3
－Z
5/6
0
1
5/3
x1
1
x3
x2
x1
b
XB
CB
初
始
表
最优表
在松弛问题最优解中，x1, x2 均为非整数解，由上表有：
将系数和常数都分解成整数和非负真分数之和
以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：
引入松弛变量s1 后得到下式，将此约束条件加到上表中，继续求解。
0
1/3
－2/3
1
0
8/3
x2
1
1
－1/3
－1/3
0
0
－2/3
s1
0
－1/6
－1/6
x4
0
0
0
s1
0
－1/6
0
0
－13/3
－Z
5/6
0
1
5/3
x1
1
x3
x2
x1
b
XB
CB
0
1
1
Cj
－2
1
0
1
0
4
x2
1
－3
1
1
0
0
2
x3
0
0
－1
x4
0
－1/2
0
s1
0
0
0
0
－4
－Z
0
0
1
0
x1
1
x3
x2
x1
b
XB
CB
0
1
1
Cj
﹡
得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解： X＊= (0, 4), Z = 4, 或 X＊= (2, 2), Z = 4。
0-1整数规划
一、问题的提出
1、实例
例 某公司拟在市东、西-南三区建立门市部。拟议中有7个位置（点）Ai供选择。规定
在东区，由A1,A2,A3三个点中至多选两个；
在西区，由A4,A5两个点中至少选一个；
在南区，由A6,A7两个点中至少选一个。
如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择那几个点可使年利润为最大？
则0-1规划模型为：
2、0-1整数规划的一般形式
0－1 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法
例：求解下列0－1 规划问题
解：对于0－1 规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。
×
2 6
( 1. 1. 1 )
×
3
( 1. 1. 0 )
8
∨
0 2 1 1
( 1. 0. 1 )
×
1 5
( 0. 1. 1 )
3
∨
1 1 1 0
( 1. 0. 0 )
－2
∨
2 4 1 4
( 0. 1. 0 )
5
∨
－1 1 0 1
( 0. 0. 1 )
0
∨
0 0 0 0
( 0. 0. 0 )
是∨ 否×
(1) (2) (3) (4)
Z 值
满足条件
约束条件
x1 . x2. x3
由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 )
由上表可知： x1 =0 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将3 x1－2 x2＋5 x3 ≥5 作为一个约束，凡是目标函数值小于5 的组合不必讨论，如下表。
×
4
( 1. 1. 1 )
×
1
( 1. 1. 0 )
8
∨
8 0 2 1 1
( 1. 0. 1 )
×
3
( 1. 0. 0 )
×
3
( 0. 1. 1 )
×
-2
( 0. 1. 0 )
5
∨
5 －1 1 0 1
( 0. 0. 1 )
0
∨
0 0 0 0 0
( 0. 0. 0 )
是∨ 否×
(0) (1) (2) (3) (4)
Z 值
满足条件
约束条件
x1 . x2. x3
隐枚举法求解0-1整数规划的思路
3、不断更换过滤条件
1、把目标函数的系数按升序排列[max]，约束条件做相应调整；
2、把所有的整解x按一定的次序排列
例： 用隐枚举法求解下列0-1规划问题
解：
目标函数的系数按升序排列
通过试探可行解(x1,x2,x3)=(1,0,0)
引入下列过滤条件：
0
5
否
是
1
0
1
-1
0
5
(0,0,0)
(0,0,1)
(4)
(3)
(2)
(1)
(0)
Z值
是否满足条件
条 件
点
(x2,x1,x3)
改进过滤条件：
8
否
是
1
1
2
0
3
8
(0,1,0)
(0,1,1)
(4)
(3)
(2)
(1)
(0‘)
Z值
是否满足条件
条 件
点
(x2,x1,x3)
改进过滤条件：
否
否
否
否
-2
3
1
6
(1,0,0)
(1,0,1)
(1,1,0)
(1,1,1)
(4)
(3)
(2)
(1)
(0‘)
Z值
是否满足条件
条 件
点
(x2,x1,x3)
为了选修课程门数最少，应学习哪些课程 ？
选课策略
要求至少选两门数学课、三门运筹学课和两门计算机课
课号
课名
学分
所属类别
先修课要求
1
微积分
5
数学
2
线性代数
4
数学
3
最优化方法
4
数学；运筹学
微积分；线性代数
4
数据结构
3
数学；计算机
计算机编程
5
应用统计
4
数学；运筹学
微积分；线性代数
6
计算机模拟
3
计算机；运筹学
计算机编程
7
计算机编程
2
计算机
8
预测理论
2
运筹学
应用统计
9
数学实验
3
运筹学；计算机
微积分；线性代数
0-1规划模型
决策变量
目标函数
xi=1 ~选修课号i 的课程（xi=0 ~不选）
选修课程总数最少
约束条件
最少2门数学课，3门运筹学课，
2门计算机课。
课号
课名
所属类别
1
微积分
数学
2
线性代数
数学
3
最优化方法
数学；运筹学
4
数据结构
数学；计算机
5
应用统计
数学；运筹学
6
计算机模拟
计算机；运筹学
7
计算机编程
计算机
8
预测理论
运筹学
9
数学实验
运筹学；计算机
练习：用隐枚举法求解0—1规划问题
（0 . 1 . 1 . 0 . 0）
指派问题
一、问题的提出
1、实例
有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如下表所示，问如何分配任务使完成四项任务的总工时耗费最少？
解：设
则此指派问题的模型为
第一个约束说明第i个人只能完成一个任务。
第二个约束说明第j项任务只能由一人完成。
在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。
（一）、指派问题的数学模型
设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第I 个人去做第j 件工作的的效率（ 时间或费用）为Cij(i=…n;j=…n)并假设Cij ≥0。问应如何分配才能使总效率（ 时间或费用）最高？
设决策变量 1 分配第i 个人去做第j 件工作
xij =
0 相反 ( I,j=. …n )
其数学模型为：
二、求解指派问题的理论依据
指派问题的一般形式
1、指派问题是一个特殊的运输问题
2、Koing定理：在原指派问题的效益矩阵中同行同列加上某一常数，所得指派问题与原问题同解。
证明：
（二）、解题步骤：
指派问题是0-1 规划的特例，也是运输问题的特例，当然可用整数规划，0-1 规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。
第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即
(1) 从（cij）的每行元素都减去该行的最小元素；
(2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。
第二步：进行试指派，以寻求最优解。
在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素(不同行不同列的零元素），就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：
(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎ 。然后划去◎ 所在列(行)的其它0元素，记作Ø ；这表示这列所代表的任务已指派完,不必再考虑别人了。
(2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎ 所在行的0元素，记作Ø .
(3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。
(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。
（5）若◎ 元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m < n, 则转入下一步。
第三步：作最少的直线覆盖所有0元素。
(1)对没有◎的行打√号；
(2)对已打√号的行中所有含Ø元素的列打√号；
(3)再对打有√号的列中含◎ 元素的行打√号；
(4)重复(2)，(3)直到得不出新的打√号的行、列为止；
(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。l 应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若 l＝m < n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。
第四步：变换矩阵(bij)以增加0元素。
在没有被直线覆盖的所有元素中找出最小元素，然后打√各行都减去这最小元素；打√各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。
例一：
任务
人员
A
B
C
D
甲
2
15
13
4
乙
10
4
14
15
丙
9
14
16
13
丁
7
8
11
9
2
4
9
7
4
2
◎
Ø
◎
Ø
Ø
◎
◎
例二、
有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？
任务
人员
A
B
C
D
甲
6
7
11
2
乙
4
5
9
8
丙
3
1
10
4
丁
5
9
8
2
求解过程如下：
第一步，变换系数矩阵：
－5
第二步，试指派：
◎
◎
◎
Ø
Ø
找到 3 个独立零元素
但 m = 3 < n = 4
第三步，作最少的直线覆盖所有0元素：
◎
◎
◎
Ø
Ø
√
√
√
独立零元素的个数m等于最少直线数l，即l＝m=3<n=4；
第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：
0
0
0
0
0
0
得到4个独立零元素， 所以最优解矩阵为：
◎
◎
◎
Ø
Ø
√
√
√
◎
◎
◎
Ø
Ø
15
◎
◎
◎
Ø
Ø
◎
练习：
11
5
7
6
4
戊
6
9
6
3
7
丁
8
6
4
5
8
丙
9
11
7
12
9
乙
11
8
9
5
7
甲
E
D
C
B
A
费 工作
用
人员
-1
-2
◎
Ø
◎
◎
◎
Ø
Ø
◎
Ø
◎
◎
◎
Ø
Ø
√
√
√
l =m=4 < n=5
◎
Ø
◎
◎
◎
Ø
Ø
◎
Ø
◎
Ø
◎
Ø
◎
Ø
√
√
√
√
√
√
√
◎
Ø
◎
Ø
◎
Ø
◎
Ø
√
√
√
√
√
√
√
l =m=4 < n=5
◎
Ø
◎
Ø
◎
Ø
◎
Ø
√
√
√
√
√
√
√
◎
Ø
Ø
◎
Ø
Ø
◎
Ø
◎
Ø
◎
此问题有多个最优解
28
◎
Ø
Ø
◎
Ø
Ø
◎
Ø
◎
Ø
◎
◎
Ø
Ø
◎
Ø
Ø
◎
Ø
◎
Ø
◎
用匈牙利法求解下列指派问题，已知效率矩阵分别如下：
