对于限制全部或部分决策变量取离散非负整数值的线性规划, 称之整数线性规划, 简称整数规划. 整数规划的一种特殊情形是 0 − 1 0-1 0−1 整数规划, 它的决策变量仅限于 0 或 1, 简称 0 − 1 0-1 0−1 规划.

指派模型是一种重要的 0 − 1 0-1 0−1 规划模型，指派模型又叫分配模型，指有各种不同的资源将分派给各种不同的用途，以寻求一种最优的分配方案。要求使有限的资源达到最经济的运用，取得最大的经济效果。这里的资源可以是人力，材料、工件、设备等; 用途可以是待用设备、待完成工作、待加工的工件等。资源与用途之间是一一对应的，即当某种资源分配给某种用途之后，这种资源就不能再分配给别的用途了，同样，这种用途也不能再占用别的资源了。

标准指派问题的一般提法是：拟分派 n n n 个人 A 1 , A 2 , ⋯   , A n {A_1},{A_2}, \cdots ,{A_n} A1​,A2​,⋯,An​ 去完成 n n n 项工作 B 1 , B 2 , ⋯   , B n {B_1},{B_2}, \cdots ,{B_n} B1​,B2​,⋯,Bn​，要求每项工作需且仅需一个人去完成，每个人需完成且仅需完成一项工作。已知人 A i {A_i} Ai​ 完成工作 B j {B_j} Bj​ 的时间或费用等成本型指标值为 c i j {c_{ij}} cij​ ，则应如何指派才能使总的工作效率最高？

引入 0 − 1 0-1 0−1 决策变量 x i j = { 1 ,  指派  A i  去完成工作  B j , 0 ,  否则,  i , j = 1 , 2 , ⋯   , n . x_{i j}=\left\{\begin{array}{ll} 1, & \text { 指派 } A_{i} \text { 去完成工作 } B_{j}, \\ 0, & \text { 否则, } \end{array} \quad i, j=1,2, \cdots, n .\right. xij​={1,0,​ 指派 Ai​ 去完成工作 Bj​, 否则, ​i,j=1,2,⋯,n.

则标准指派问题的数学模型为 min ⁡ z = ∑ i = 1 n ∑ j = 1 n c i j x i j , s . t . { ∑ j = 1 n x i j = 1 , i = 1 , 2 , ⋯   , n , ∑ i = 1 n x i j = 1 , j = 1 , 2 , ⋯   , n , x i j = 0  或  1 , i , j = 1 , 2 , ⋯   , n , \begin{gathered} &\min \quad z=\sum_{i=1}^{n} \sum_{j=1}^{n} c_{i j} x_{i j}, \\ & { s.t. }\left\{\begin{array}{l} \sum_{j=1}^{n} x_{i j}=1, \quad i=1,2, \cdots, n, \\ \sum_{i=1}^{n} x_{i j}=1, \quad j=1,2, \cdots, n, \\ x_{i j}=0 \text { 或 } 1, \quad i, j=1,2, \cdots, n, \end{array}\right. \end{gathered} ​minz=i=1∑n​j=1∑n​cij​xij​,s.t.⎩⎨⎧​∑j=1n​xij​=1,i=1,2,⋯,n,∑i=1n​xij​=1,j=1,2,⋯,n,xij​=0 或 1,i,j=1,2,⋯,n,​​

称 C = ( c i j ) n × n {\mathbf{C}} = {({c_{ij}})_{n \times n}} C=(cij​)n×n​ 为效率矩阵，模型的最优解也可以用 n n n 阶方阵 X ∗ {{\mathbf{X}}^*} X∗ 的形式来表示，称之指派问题的最优解方阵。最优解方阵一定是一个置换矩阵，即矩阵的每一行、每一列都恰好有一个“ 1 1 1 ”，其余元素均为 0 0 0。

定理 1 设效率矩阵 C = ( c i j ) n × n {\mathbf{C}} = {({c_{ij}})_{n \times n}} C=(cij​)n×n​ 中任何一行（列）的各元素都减去一个常数 k k k（可正可负）后得到的新矩阵为 B = ( b i j ) n × n {\mathbf{B}} = {({b_{ij}})_{n \times n}} B=(bij​)n×n​，则以 B = ( b i j ) n × n {\mathbf{B}} = {({b_{ij}})_{n \times n}} B=(bij​)n×n​ 为效率矩阵的指派问题与原问题有相同的最优解，但其最优值比原问题的最优值小 k k k

定理 2 (独立零元素定理) 若一方阵中的一部分元素为 0 0 0，一部分元素为非 0 0 0，则覆盖方阵内所有 0 0 0 元素的最少直线数恰好等于那些位于不同行、不同列的 0 0 0 元素的最多个数。

第一步 变换指派问题的系数矩阵 ( c i j ) (c_{ij}) (cij​) 为 ( b i j ) (b_{ij}) (bij​)，使在 ( b i j ) (b_{ij}) (bij​) 的各行各列中都出现 0 0 0 元素

e . g . e.g. e.g.

( C i j ) = [ 12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 9 ] \left(\mathbf{C}_{i j}\right)=\left[\begin{array}{ccccc} 12 & 7 & 9 & 7 & 9 \\ 8 & 9 & 6 & 6 & 6 \\ 7 & 17 & 12 & 14 & 9 \\ 15 & 14 & 6 & 6 & 10 \\ 4 & 10 & 7 & 10 & 9 \end{array}\right] (Cij​)=⎣⎢⎢⎢⎢⎡​1287154​79171410​961267​7614610​969109​⎦⎥⎥⎥⎥⎤​

每行分别 − 7 , − 6 , − 7 , − 6 , − 4 −7, −6, −7, −6, −4 −7,−6,−7,−6,−4 ⟶ \longrightarrow ⟶

[ 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 ] \begin{gathered} \left[\begin{array}{ccccc} 5 & 0 & 2 & 0 & 2 \\ 2 & 3 & 0 & 0 & 0 \\ 0 & 10 & 5 & 7 & 2 \\ 9 & 8 & 0 & 0 & 4 \\ 0 & 6 & 3 & 6 & 5 \end{array}\right]\\ \end{gathered} ⎣⎢⎢⎢⎢⎡​52090​031086​20503​00706​20245​⎦⎥⎥⎥⎥⎤​​

每列都 − 0 -0 −0 ⟶ \longrightarrow ⟶

[ 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 ] \left[\begin{array}{ccccc} 5 & 0 & 2 & 0 & 2 \\ 2 & 3 & 0 & 0 & 0 \\ 0 & 10 & 5 & 7 & 2 \\ 9 & 8 & 0 & 0 & 4 \\ 0 & 6 & 3 & 6 & 5 \end{array}\right] ⎣⎢⎢⎢⎢⎡​52090​031086​20503​00706​20245​⎦⎥⎥⎥⎥⎤​

第二步 进行试指派，以寻求最优解

在 ( b i j ) \left(b_{i j}\right) (bij​) 中找尽可能多的独立 0 元素, 若能找出 n n n 个独立 0 元素, 就以这 n n n 个独立 0 元素对应解矩阵 ( x i j ) \left(x_{i j}\right) (xij​) 中的元素为 1 , 其余为 0 , 这就得到最优解

找独立 0 \mathbf{0} 0 元素:

e . g . e.g. e.g. 续上例

[ 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 ] \left[\begin{array}{ccccc} 5 & 0 & 2 & 0 & 2 \\ 2 & 3 & 0 & 0 & 0 \\ 0 & 10 & 5 & 7 & 2 \\ 9 & 8 & 0 & 0 & 4 \\ 0 & 6 & 3 & 6 & 5 \end{array}\right] ⎣⎢⎢⎢⎢⎡​52090​031086​20503​00706​20245​⎦⎥⎥⎥⎥⎤​

⟶ \longrightarrow ⟶

[ 5 ◎ 2 ∅ 2 2 3 ∅ ∅ ◎ ◎ 10 5 7 2 9 8 ◎ ∅ 4 ∅ 6 3 6 5 ] \left[\begin{array}{ccccc} 5 & ◎ & 2 & \varnothing & 2 \\ 2 & 3 & \varnothing & \varnothing & ◎ \\ ◎ & 10 & 5 & 7 & 2 \\ 9 & 8 & ◎ & \varnothing & 4 \\ \varnothing & 6 & 3 & 6 & 5 \end{array}\right] ⎣⎢⎢⎢⎢⎡​52◎9∅​◎31086​2∅5◎3​∅∅7∅6​2◎245​⎦⎥⎥⎥⎥⎤​

第三步 作最少的直线覆盖所有 0 0 0 元素，以确定该系数矩阵中能找到最多的独立元素数