文档介绍：第五章整数计划
§1 整数计划数学模型及特点
要求一部分或全部决议变量必需取整数值得计划问题称为整数计划。
其模型为：
Max(或min)z=
中部分或全部取整数

若要求决议变量只能取值0或1整数计划称为0-1型整数线性计划。
§5 指派问题
指派问题标准形式及数学模型
在现实生活中，有多种性质指派问题。比如，有若干项工作需要分配给若干人（或部门）来完成；有若干项协议需要选择若干个投标者来承包；有若干班级需要安排在各教室上课等等。诸如这类问题，它们基础要求是在满足特定指派要求条件下，使指派方案总体效果最好。因为指派问题多样性，有必需定义指派问题标准形式。
指派问题标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j件事费用为，要求确定人和事之间一一对应指派方案，是完成这n件事总费用最少。
为了建立标准指派问题数学模型，引入个0-1变量：
若指派第i人作第j件事
若不指派第i人作第j事
i，j=1,2,…n

这么，问题数学模型可写成
（）
（）
（）
（）
其中，（）表示每件事必优且只有一个人去做，（）表示每个人必做且只做一件事。
注：指派问题是产量（）、销量（）相等，且==1，i，j=1,2,…n运输问题。
有时也称为第i个人完成第j件工作所需资源数，称之为效率系数（或价值系数）。并称矩阵
C= = （）
为效率矩阵（或价值系数矩阵）。
并称决议变量排成n×n矩阵
X== （）
为决议变量矩阵。
()特征是它有n个1，其它全部是0。这n个1在不一样行、不一样列。每一个情况为指派问题一个可行解。共n!个解。
其总费用 z =C⊙X
这里⊙表示两矩阵对应元素积，然后相加。
问题是：把这n个1放到X个位置什么地方可使花费总资源最少？（解最优）
例1 已知效率矩阵
C=
则
X（1）= ， X（2）=
全部是指派问题最优解
例12/P-149：某商业企业计划创办五家新商店。为了尽早建成营业，商业企业决定由5家建筑企业分别承建。已知建筑企业Ai（i=1，2，…5）对新商店Bj（1，2，…5）建造费用报价（万元）为（i，j=1,2,…5）,见表5-9。商业企业应该对5家建筑企业怎样分配建筑任务，才能使总建筑费用最少？
表5-9
B1
B2
B3
B4
B5
A1
4
8
7
15
12
A2
7
9
17
14
10
A3
6
9
12
8
7
A4
6
7
14
6
10
A5
6
9
12
10
6
解：这是一标准指派问题。若设0-1变量
i,j=1,2,…5
当Ai不承建Bj时
当Ai承建Bj时
=
则问题数学模型为
Min z=4+8+…+10+6

若看成运输问题，且如上所述，则表5-9为
商店
企业
B1
B2
B3
B4
B5
任务
A1
（4）
（8）
（7）
（15）
（12）
1
A2
（7）
(9)
(17)
(14)
(10)
1
A3
(6)
(9)
(12)
(8)
(7)
1
A4
(6)
(7)
(14)
(6)
(10)
1
A5
(6)
(9)
(12)
(10)
(6)
1
所选企业数
1
1
1
1
1
5
当然，第一行1应放在（1，1）位置，此位置同时是第一列费用最小。但通常情况下没有这么好。需找一适合通常方法。
匈牙利解法原理：
即使指派问题是一类特殊整数计划问题，又是特殊0-1计划问题和特殊运输问题，所以，它能够用多个对应解法来求解。不过，这些解法全部没有充足利用指派问题特殊性质，有效地降低计算量。1955年，库恩（）提出了匈牙利法。
定理1：设指派问题效率矩阵为C= ，若将该矩阵某一行（或某一列）各个元素全部减去统一常数t（t可正可负），得到新效率矩阵，则认为效率矩阵新指派问题和原指派问题最优解相同。但其最优解比原最优解之降