2024年4月15日发(作者：中考数学试卷预测)

实用文案

第五章 整数规划

§1 整数规划的数学模型及特点

要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。

其模型为：

Max(或min)z=

c

j1

n

j

x

j

n

a

ij

x

ij

(,)b

i

i1,2,

m

j1

s.t

x

j

0j1,2,

n

x,x,

x

中部分或全部取整数

12n

若要求决策变量只能取值0或1的整数规划称为0-1型整数线性规划。

§5 指 派 问 题

一． 指派问题的标准形式及数学模型

在现实生活中，有各种性质的指派问题。例如，有若干项工作需要分配给若干人（或部

门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在各教室上

课等等。诸如此类的问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的

总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。

指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j

件事的费用为

c

ij

(i,j

1,2,

n)

，要求确定人和事之间的一一对应的指派方案，是完成这n

件事的总费用最少。

为了建立标准指派问题的数学模型，引入

n

个0-1变量：

2

0

若不指派第i人作第j事

x

ij

1

若指派第i人作第j件事

这样，问题的数学模型可写成

minz

nn

i，j=1,2,…n



c

i1j1

ij

x

ij

（5.1）

n

（5.2）

x

ij

1j1,2,

n

1

i

n

s.t

x

ij

1i1,2,

n

（5.3）

j1

x

ij

0,1i,j1,2,

n

（5.4）

其中，（5.1）表示每件事必优且只有一个人去做，（5.2）表示每个人必做且只做一件

事。

标准文档

实用文案

1

指派问题是产量（

a

）注：○

i

、销量（

b

j

）相等，且

a

i

=

b

j

=1，i，j=1,2,…n的运输

问题。

2

有时也称

c

为第i个人完成第j件工作所需的资源数，○称之为效率系数（或价值系

ij

数）。并称矩阵

c

11

c

C=

(c

ij

)

nn

=

21

c

n1

c

1n

c

22

c

2n

（5.5）



c

n2

c

nn

c

12

为效率矩阵（或价值系数矩阵）。

并称决策变量

x

ij

排成的n×n矩阵

x

11

x

X=

(x

ij

)

nn

=

21

x

n1

x

12

x

22

x

n2

x

1n

x

2n

（5.6）



x

nn

为决策变量矩阵。

(5.6)的特征是它有n个1，其它都是0。这n个1位于不同行、不同列。每一种情况为指派

问题的一个可行解。共n!个解。

其总的费用 z =C⊙X

这里的⊙表示两矩阵对应元素的积，然后相加。

问题是：把这n个1放到X的

n

2

个位置的什么地方可使耗费的总资源最少？（解最优）

例1 已知效率矩阵

5

2

C=

0

4

则

020

300

567

800

100



0



001



0

，

X

=

（2）

1000





0010



100

010

000

001

0

0

X

（1）

=

1

0

都是指派问题的最优解

例12/P-149：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由

5家建筑公司分别承建。已知建筑公司A

i

（i=1，2，…5）对新商店B

j

（1，2，…5）的建造

费用的报价（万元）为

c

ij

（i，j=1,2,…5）,见表5-9。商业公司应当对5家建筑公司怎样

分派建筑任务，才能使总的建筑费用最少？

标准文档


更多推荐

指派,问题,公司,标准,建筑