文档介绍：. .
-优选
第五章整数规划
§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