word字体下载-冬日暖阳作文

第十一章 整数规划方法

11.1 整数规划的模型

如果一个数学规划的某些决策变量或全部决策变量要求必须取整数，则这样的问题称 为
整数规划问题，其模型称为整数规划模型。
如果整数规划的目标函数和约束都是线 性的，则称此问题为整数线性规划问题。在里我
们只就整数线性规划问题进行讨论，整数线性规划的一般 模型为：
max(min)z

c
j
x
j
j 1
n
（11.1）

n
ax(,)b(i1,2,,m)
i


ijj
s.t.

j1

x0,x为整数(j1, 2,,n)
j

j
对于实际中的某些整数规划问题，我们有时 候可以想到先略去整数约束的条件，即视为
一个线性规划问题，利用单纯形法求解，然后对其最优解进行 取整处理。实际上，这样得到
的解未必是原整数规划问题的最优解，因此，这种方法是不可取的，但可借 鉴于这种思想。
整数规划求解方法总的基本思想是：松弛问题(11.1)中的约束条件（ 譬如去掉整数约束
条件），使构成易于求解的新问题――松弛问题(A)，如果这个问题(A)的最优解 是原问题(11.1)
的可行解，则就是原问题(11.1)的最优解；否则，在保证不改变松弛问题( A)的可行性的条件
下，修正松弛问题(A)的可行域(增加新的约束)，变成新的问题（B），再求问 题(B)的解，重
复这一过程直到修正问题的最优解在原问题(11.1)的可行域内为止，即得到了原 问题的最优
解。
注意到: 如果每个松弛问题的最优解不是原问题的可行解时，则这个解对应 的目标函数
值
z
一定是原问题最优值
z
的上界(最大化问题)，即< br>zz
，或下界(最小化问题)，即
zz
。

*
**
11.2 整数规划的分枝定界法


11.2.1. 分枝定界法的基本思想

将原问题（11.1）中整数约束去掉变 为问题（A），求出问题（A）的最优解，如果它不
是原问题（11.1）的可行解，则通过附加线性不 等式约束（整数），将问题（A）分枝变为若
干子问题
(B
i
)(i1,2 ,,I)
，即对每一个非整变量附加两个互相排斥（不交叉）的整型约束，
就得两个子问 题，继续求解定界，重复下去，直到得到最优解为止。

· ·166

例11.1 用分枝定界法求解下列整数规划问题
maxz40x
1
90x
2
（A）


9x
1
7x
2
56


7x
1
20x
2
70

x,x0,且为整数

12
解（1）去掉
x
1
,x
2
为整数的约束，变为问题
(A
0
)
，求解可得
(A
0)
的最优解为
x
1
4.81,x
2
1.82,z< br>0
356z
，令
z0
，且
0zz
*
z356
。显然不是（A）的
可行解。
（2）分枝：对
x
1
4.81
附加约束条件
x
1
4,x
1
5，将（A）分为两个子问题
(B
1
)
和
(B
2
)
：
maxz40x
1
90x
2

9x1
7x
2
56

(B
2
)

(B
1
)

< br>7x20x70

12

0x4,x0
12

是问题（A）的可行解，取
z349,z0
。
（3）对问题
(B
1
)
，
(B
2
)
分枝：
对问题< br>(B
1
):x
2
2.1
附加约束
x
22,x
2
3
分为问题
(C
1
)
，
(C
2
)

对问题
(B
2
):x
2
1.57
附加约束
x
2
1,x
2
2
分为问 题
(C
3
)
，
(C
4
)

max z40x
1
90x
2

9x
1
7x
2
56


7x
1
20x
2
70< br>
x5,x0
2

1

求解可得
(B< br>1
)
：
x
1
4,x
2
2.1,z
1
349
，
(B
2
)
：
x
1
5,x
2
1.57,z
2
341
。仍不
maxz4 0x
1
90x
2

9x
1
7x
256

(C
2
)

(C
1
)


7x20x70

1 2

0x4,0x2
12

maxz40x
1< br>90x
2

9x
1
7x
2
56


7x20x70

12

0x4,x3< br>12

maxz40x
1
90x
2

9 x
1
7x
2
56
(C
3
)



7x
1
20x
2
70

x5 ,0x1
2

1
分别求解可得：
maxz40x
1
90x
2

(C
4
)



9x
1
7x
2
56

7x
1
20x
2
70
x5,x2
2

1

(C
1
) :x
1
4,x
2
2,z
3
340
； < br>(C
2
):x
1
1.42,x
2
3,z
4
327
；
(C
3
):x
1
5.44,x< br>2
1,z
5
308
；
(C
4
)
：无可行解。
因为
(C
1
)< br>的解为（A）的可行解，故取
z340,z341
，注意到
z
4< br>,z
5
z340
，则
对
(C
2
)
和
(C
3
)
无需再分枝，将其剪掉。由
z340z
*
z341
可知，已得到了问题（A）

·167·

**
的最优解
x
1
4,x
2
2,z
*340
。

11.2.2 分枝定界法的一般步骤

（1 ）将原整数规划问题（11.1）去掉所有的整数约束变为线性规划问题（A），用线性规
划的方法求解 问题（A），则有下列情况：
1） 问题（A）无可行解，则原问题（11.1）也无可行解，停止计算；
2）问题（A）有最优解
X
，并是原问题（11.1）的可行解，则此解就是（A）的最优解，
计算结束；
3） 问题（A）有最优解
X
，但不是原问题（11.1）的可行解，转下一步。 < br>（2）将
X
代入目标函数，其值记为
z
，并用观察法找出原问题（11 .1）的一个可行解
（整数解，不妨可取
x
j
0(j1,2,,n )
），求得目标函数值（下界值），记为
z
，则原问题
（11.1）的最优值 记为
z
，即有
zz
*
z
，转下一步；
（3） 分枝：在问题（A）的最优解中任选一个不满足整数约束的变量
x
j
b
j< br>（非整数），
附加两个整数不等式约束：
x
j
[b
j
]
和
x
j
[b
j
]1
，分别加入到问题（A ）中，构成两个
新的子问题
(B
1
)
和
(B
2)
，仍不考虑整数约束，求问题
(B
1
)
和
(B
2
)
的解。
定界：对每一个子问题的求解结果，找出最优值的最大者为新的上界< br>z
，从所有符合整
数约束条件的分枝中找出目标函数值最大的一个为新的下界
z
。
（4）比较与剪枝：将各分枝问题的最优值同
z
比较，如果其值小于z
，则这个分枝可以
剪掉，以后不再考虑。如果其值大于
z
，且又不是原 问题（11.1）的可行解，则继续分枝，
返回（3），直到最后得到最优解使
z
*< br>z
，即
x
j
(j1,2,,n)
为原问题（11. 1）的最优解。

*
*
*
*
*
11.3 整数规划的割平面法

11.3.1 割平面法的基本思想


首 先把原整数规划问题（11.1）去掉整数约束条件变为线性规划问题（A），然后引入线
性约束条件（ 称为Gomory约束，几何术语割平面）使问题（A）的可行域逐步缩小（即切
割掉一部分），每次切 割掉的是问题的非整数解的一部分，不切掉任何整数解，直到最后使得
目标函数达到最优的整数解（点） 成为可行域的一个顶点为止，这就是原问题（11.1）的最
优解。即利用线性规划的求解方法逐步缩小 可行域，最后找到整数规划的最优解。

例11.2 用割平面法求解下列整数规划问题

· ·168

maxzx
1
x
2



x
1
x
2
1

< br>3x
1
x
2
4

x,x0,且为整数

12
maxzx
1
x
2
将其化为标准型
（A）


x
1
x
2
x< br>3
1


3x
1
x
2
x4
4

x,x,x,x0,且为整数

1234
去 掉整数约束条件，用单纯形法求解相应的线性规划问题，可得非整数的最优解为
x
1

375
,x
2
,x
3
x
4
0,z
，由变量之间的关系可以得到关系式
442
113

xxx


1
4
3
4
4
4




x
3
x
1
x
71
3
234

4444


3

31

xxxx
4

33

1
444

将整数与真分式分开有


31
< br>
x1
3


xx
4

2 3

4

44


因为
x
1
,x
2
,x
3
,x
4
0
，且为整数 ，即左端为整数，右端也必为整数，所以
3

31


< br>x
3
x
4

0
，即
3x
3< br>x
4
3
为所求的切割方程。将其加到问题的约束条件之
4

44

中，构成新的问题（B），求解引入松弛变量
x
5
，则有
3x
3
x
4
x
5
3
， 即求问题
maxzx
1
x
2

x
1
x
2
x
3
1

（B）

3x
1
x
2
x
4
4
< br>

3x
3
x
4
x
5
3


x
1
,x
2
,x
3
,x4
,x
5
0
用单纯形法求解，则可得到问题（B）的最优解为< br>x
1
x
2
x
3
1
，显然是原问题的可
行解，即为所求的最优解，其最优值为
z2
。


·169·

11.3.2 割平面法的计算步骤

设原问 题（11.1）中有
n
个决策变量，
m
个松弛变量，共
nm
个变量，略去整数约束
求解线性规划问题，将最终的求解结果放入如表11-1（称为单纯形表）。其 中
x
i
(i1,2,,m)
表示基变量，
y
j(j1,2,,n)
表示非基变量，则具体计算步骤如下：
(1) 在最优解中 任取一个具有分数值的基变量，不妨就是
x
i
(1im)
，由表11-1 可以
得到关系
x
i


a
j1
n
ij
y
j
b
i
，即
x
i
b
i


a
ij
y
j
j1
n
( 1im)
（11.2）


表11-1：单纯形表

基
x
1
x
ix
m
y
1
y
j
 y
n


b
x
1

x
i

x
m

1 00

010

a
11

a
i1

a
1j




a
ij





a
1n

a
in




b
1

b
i

b
m
-z

001a
m1
a
mj
0 00
a
mn

j



1


j


n

（2）将
b
i
和
a
ij
(1im;j1,2,, n)
（为假分数）分为整数部分和非负的真分数，
即
b
i
Ni
f
i
,a
ij
N
ij
f
ij
(j1,2,,n)

其中
N
i
和
Nij
表示整数，而
f
i
(0f
i
1)
和< br>f
ij
(0f
ij
1)
表示真分数，代入（11.2）式 ，
并将整数放在一边，分数放在一边，即
x
i


Nij
y
j
N
j
f
i


f
ij
y
j
j1j1
nn
(1im)
（11.3）
（3）要使
x
i
和
y
j
都有为整数 ，（11.3）式的左端必为整数 ，右端也是整数，而且由

· ·170

< br>f
ij
0,y
j
是非负整数，故此
f
i


f
ij
y
j
f
i
1
，则必 有
j1
n

f
j1
n
ij
y
j
0
，又因
f
i
0
是真分数，于是有
f
i


f
ij
y
j
0(1 im)
（11.4）
j1
n
这就是所要求的一个切割方程（Gomory约束条件）。
（4）对（11.4）式引入一个松弛变量
S
i
，则（11.4）式变为

S
i


f
j1
n
ij
y
j
f
i
(1i m)

将其代入原问题中去，求解新的线性规划问题。
（5）应用对偶单纯形法求解 ，如果所求解为原问题的可行解（均为整数解），则就是原
问题的最优解，计算结束。否则继续构造Go mory约束条件，直到最优解为整数解为止。
说明：在这里为什么要用对偶单纯形法求解呢？主要是 在Gomory方程
S
i


f
ij
y
j
f
i
中，当非基变量
y
j
0
时，条件变为< br>S
i
f
i
为负数，变为不可行，通
j1
n常的单纯形法无法求解，而用对偶单纯形法从不可行到可行，即可得到最优解。

11.4 0—1整数规划

11.4.1 0—1规划的模型
< br>如果整数线性规划问题的所有决策变量
x
i
仅限于取0或1两个数值，则称此问 题为0—1
线性整数规划，简称为0—1规划。变量
x
i
称为0—1变量，或 二进制变量，其变量取值的约
束可变为
x
i
0
或1，等价于
x
i
1
和
x
i
0
，且为整数，于是0—1规 划的一般模型为
max(min)z

c
j
x
j
j1
n


n
ax(,)b(i1,2,,m)
i


ijj
s.t.

j1

x0或1(j1,2,,n)

j


·171·

例11.3 背包问题（或载货问题）
一个旅行者要在背包里装一些最有用的东西，但限制最多只能带b kg物品，每件物品只
能是整件携带 ，对每件物品都规定了一定的“使用价值”（有用的程度）。如果共有n件物品，
第j件物品重
a
j
kg
，其价值为
c
j
，问题是：在携带的物品总重量不 超过b kg的条件下，携
带哪些物品可使总价值最大？

1,当携带第j种物品时
设决策变量
x
j
:x
j


，则问题的模型为 < br>0,当不携带第j种物品时

maxz

c
j
x< br>j
j1
n


n
axb


jj
s.t.

j1

x0或1

j
例11.4 指派（或分配）问题
在生产管理上，为了 完成某项任务，总
是希望把有关人员最合理地分派，以发挥其
最大工作效率，创造最大的价值。
例如：设某单位有4个人，每个人都有
能力去完成4项科研任务中的任一项，由于
4个 人的能力和经验不同，所需完成各项任
务的时间如表11-2所示。问分配何人去完成
何项任务 使完成所有任务的总时间最少？
设决策变量
x
ij
表示第
i
个人去完成第
j
项任务，即
表11-2
项目

人员
甲
乙
丙
丁
A
2
10
9
7

B
15
4
14
8

C
13
14
16
11

D
4
15
13
9
j项任务时

1,当第i个人去完成第
x
ij


(1i,j4)

j项任务时

0,当第i个人不去完成第
每个人去完成一项任务的约束为 < br>
x
11
x
12
x
13
x
1 4
1

xxxx1

21222324



xxxx1
323334

31
< br>
x
41
x
42
x
43
x
4 4
1
每一项任务必有一人去完成的约束为

· ·172


x
11
x
21
x
31
x
41
1

xxxx1

12223242




x
13
x
23
x
33
x
43
1


x
14
x
2 4
x
34
x
44
1
完成任务的总时间，即目标函数为

minz2x
11
15x
12
13x< br>13
4x
14
10x
21
4x
22
 14x
23
15x
24
9x
31
14x
32
16x
33
13x
34
7x
41
8x42
11x
43
9x
44


21511 4


1041415


，称为效益矩阵，或价值矩阵，
c
ij
表示第
i
个人记系数矩阵为
c
ij



9141613


78119
去完成第
j
项任务时有关的效益（时间、费用、价值等）。故该问题的数学模型为
minz

c
ij
x
ij

i1j 1
44

4


x
ij
1,i1, 2,3,4

j1


4

s.t.


x
ij
1,j1,2,3,4


i1


x
ij
0或1(i,j1,2, 3,4)


一般的指派（或分配）问题：
设某单位有n项任务，正好需要 n个人去完成，由于任务的性质和各人的专长不同，如
果分配每个人仅能完成一项任务，应如何分派使完 成n项任务的总效益（或效率）最高。
设该指派问题有相应的效益矩阵
Cc
ij< br>
nn
，其元素
c
ij
表示分配第
i
个 人去完成第
j
项
任务时的效益（
0
），或者说：以
cij
表示给定的第
i
单位资源分配用于第
j
项活动时的有关效益。
设问题的决策变量为
x
ij
是0—1变量，即

x
ij


其数学模型为

·173·
j项活动时

1,当分配第i个单位资源用于第
(i,j

1,2 ,

,n)

j项活动时

0,当不分配第i个单位资源用 于第

minz

c
ij
x
ij

i1j1
nn

n


x
ij
1,i1,2,,n

j1


n
s.t.


x
ij
1,j1,2,,n
（11.5）

i1

x
ij
0或1(i,j1, 2,,n)




11.4.2 0—1规划的隐枚举法

显枚举法（又称为穷举法）：主要是把问题的所有可能的组合情况（共
2< br>种）列举出来
进行比较，找到所需要的最优解。
隐枚举法：主要是从实际出发，从问题 所有可能的组合取值中利用“过滤条件”排除一
些不可能是最优解的情况，只需考查其中一部分组合就可 得到问题的最优解。因此，隐枚举
法又称为部分枚举法。
隐枚举法不需要更多的理论和知识， 当问题的维数
n
不是特别大时，求解0－1是一种有
效的方法，但对于过滤条件的确定 ，要根据实际问题的具体情况具体分析而定。

n
11.5 指派问题的匈牙利方法

“匈牙利方法”最早是由匈牙利数学家康尼格（D. Konig）用来求矩阵中0元素的个 数
的一种方法，由此他证明了“矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直
线 数”。1955年由库恩（W.W. Kuhn）在求解著名的指派问题时，引用了这一结论，并对具体
算法做了改进，仍然称为“匈牙利方法”。

11.5.1 匈牙利方法的基本思想

由于每个问题都有一个相应的效益矩阵，可以通过初等变换修改效益矩阵的行或列的
元素，使得在每一行或每一列中至少有一个零元素，直到在不同行、不同列中至少有一个零
元素，从而 得到与这些零元素相对应的一个完全分配方案，这个方案是原问题的一个最优分
配方案。
定理11.1（指派问题的最优性） 如果问题（11.5）的效益矩阵
C(c
ij
)
nn
的第
i
行、第
j
列中的每个元素分别减去一个常数 a 、b变为矩阵
D(d
ij
)
nn
，则以新的矩阵
D
为效益

· ·174

矩阵和新的目标函数与原效益矩阵C
和原目标函数求得的最优解相同，最优值只差一个常
数。
证明 只要证明新目标函数和原目标函数值相差一个常数。
事实上：因为
d
ij< br>c
ij
ab
nn
(1i,jn)
，则新的目标函数 为
z



d
ij
x
ij
i 1j1
nn



c
ij
x
ij
a

x
ij
b

x
ij

i1j1
nn
j1i1
nn
< br>
c
ij
x
ij
(ab)z(ab)
i 1j1
故二者相差一个常数a+b，最优解相同。

11.5.2 匈牙利方法的基本步骤

根据指派问题的最优性，“若从效益矩阵
Cc
i j
行（列）的最小元素，得到新矩阵
Dd
ij


n n
的一行（一列）各元素分别减去该
nn
，那么以
D
为效益矩阵 所对应问题的最优解
与原问题的最优解相同”。此时求最优解的问题可转化为求效益矩阵的最大1元素组 的问题。
下面给出一般的匈牙利方法的计算步骤：
第1步：对效益矩阵进行变换，使每行每列都出现有0元素。
（1）从效益矩阵
C
中每一行减去该行的最小元素；
（2）再在所得矩阵中 每一列减去该列的最小元素，所得矩阵记为
Dd
ij

nn
。
第2步：将矩阵
D
中0元素置为1元素，非零元置为0元素，记此矩阵为
E< br>。
第3步：确定独立1元素组。
（1）在矩阵
E
含有1元素的各行 中选择1元素最少的行，比较该行中各1元素所在的
列中1元素的个数，选择1元素的个数最少的一列的 那个1元素；
（2）将所选的1元素所在的行和列清0；
（3）重复第2步和第3步，直到没有1元素为止.，即得到一个独立1元素组。
第4步：判断是否为最大独立1元素组
（1）如果所得独立1元素组是原效益矩阵的最大独立 1元素组（即1元素的个数等于矩
阵的阶数），则已得到最优解，停止计算。
（2）如果所得 独立1元素组还不是原效益矩阵的最大独立1元素组，那么利用寻找可扩
路的方法对其进行扩张，进行下 一步。
第5步：利用寻找可扩路方法确定最大独立1元素组。
（1）做最少的直线覆盖矩阵
D
的所有0元素；
（2）在没有被直线覆盖的 部分找出最小元素，在被直线覆盖的各行减去此最小元素，在
被直线覆盖的各列加上此最小元素，得到一 个新的矩阵，返回第2步。

·175·

说明：上面的算法是按最 小化问题给出的，如果问题是最大化问题，即模型（11.5）中
的目标函数换为
maxz< br>
c
i1j1
nn
ij
x
ij
。此令
Mmax(c
ij
)
和
b
ij
Mc
ij
0
，则效率矩阵
i,j
变为
B(b
ij
)
nn
。于是考虑目标函数为
minz

bx
iji1j1
nn
ij
的问题，仍用上面的方法步骤求
解所得最小解也就 是对应原问题的最大解。
另外，按照匈牙利方法计算步骤，对于这一类问题的求解，我们可以用
Matlab
编程实
现。

11.6 玫瑰有约问题

11.6.1 问题的提出

目前，在许多城市大齡青年的婚姻问题已引起了妇联 、工会和社会团体组织的关注。某
单位现有20对大龄青年男女，每个人的基本条件都不相同，如外貌、 性格、气质、事业、财
富等。每项条件通常可以分为五个等级A、B、C、D、E，如外貌、性格、气质 、事业可分
为很好、好、较好、一般、差；财富可分为很多、多、较多、一般、少。每个人的择偶条件< br>也不尽相同，即对每项基本条件的要求是不同的。该单位拟根据他(她)们的年龄、基本条件
和要 求条件进行牵线搭桥。下面给出20对大龄青年男女的年龄、五项基本条件和要求条件(如
表11-3和 表11-4)。一般认为，男青年至多比女青年大5岁，或女青年至多比男青年大2岁，
并且要至少满足 个人要求5项条件中的2项，才有可能配对成功。该单位希望根据每个人的
情况和要求，建立数学模型解 决下列问题：
(1) 在尽量满足个人要求的条件下，给出一种最佳的配对方案，并使得配对成功率尽可
能的高。
(2) 给出一种20对男女青年可同时配对的最佳方案，使得全部配对成功的可能性最大。

11.6.2 问题的分析

该问题是现实生活中实际问题，主要就是确定合理配 对方案，使得在尽量满足个人要求
的条件下，使配对成功率尽可能高。由于每个人的基本条件和要求都是 给定的，双方彼此是
知道的，而且相互之间有很大的差异，如果完全按照要求条件来组合配对，则其成功 的可能
性是很小的。一对青年男女能否配对成功，主要是取决于相互之间的好感的程度－－“满意
度”，单方面的高满意度也不一定能配对成功。任意一对男女的配对可以看成一个随机事件，
按某一概 率可能配对成功，或不成功。在这里双方的满意度主要反映出了一个人对另一个人
的客观和主观的看法， 因此，满意度的定义成为解决问题的一个关键。
所谓的“成功率”，就是男女双方最终配对成功的概率 。实际上，可以用他们相互之间的
满意度来间接刻画。相互的满意度越高，双方配对成功的概率就越大。
对题目进行分析不难看出，这是一个分派问题，但由于每个人的要求条件和配对所要求

· ·176

的最低条件的限制，这又不是一个标准的分派问题，因为不能保证 每个人都能配对成功。
对问题（1），要使配对成功率尽可能的高，也就是给出一种方案，使得20对 男女的配对后的
满意度之和最高。为此，该问题可以用改进的匈牙利算法求解。

表11-3: 男青年的基本条件和要求条件
男
青
年
基 本 条 件
外性气事财年
貌 格 质 业 富 龄
A C B C A 29
C A B A D 29
B B A B B 28
C A B B D 28
D B C A A 30
C B C B B 28
A B B D C 30
B A B C D 30
A D C E B 28
要 求 条 件
外性气事财
貌 格 质 业 富
A A C B D
B A B B C
B A A B C
C A B C D
C B B B E
B B C D C
C B B D C
A B C C D
A A A C C
A B A D E
A B C D B
B A B B C
A C B B C
A C C D C
A A B C D
A A A E E
女
青
年
表11-4: 女青年的基本条件和要求条件
基 本 条 件
外性气事财年
貌 格 质 业 富 龄
A C C D A 28
B A B A D 25
C B A E A 26
要 求 条 件
外性气事财
貌 格 质 业 富
B A B A D
C B B A B
B A C B C
A A B B A
A B C B B
B A B B C
C B A A C
B A B A B
C B B B A
B B A A C
C B A B C
A A B B E
C A B C C
B A A B D
B A B B B
B A B B A
A A D A C
C A B A C
B B B A A
B B A B B
B
1

B
2

G
1

G
2

B
3

B
4

G
3

G
4

A B B C D 27
B D C E C 25
B
5

B
6

G
5

G
6

G
7

A C B C A 26
D C B A B 30
A B A E C 31
26
B
7

B
8

B
9

B
10

B
11

B
12

G
8

G
9

G
10

G
11

G
12

A A A C E
D B A A A 28
B A C D A 32
A B C A B 29
B A D E C 28
B C D B B 27
A B B C B 28
B E
E
C E A 26
B
13

B
14

B
15

G
13

G
14

G
15

A C B B 26
A A B B D 30
A B B C C 28
D E B A A 30
B B C A A 25
C B A A C 29
B A C D C 28
A E E D A 25
B
16

B
17

B
18

B
19

G
16

G
17

G
18

G
19

G
20

B A B A D 28
A B A C B 31
C D A A A 29
A B C D E 27
B A B B C
B B A C C
A B A E D
A A B B C 28
B A C C E 25
B
20


B C B D B D B A C D 29
注：表中的要求的条件一般是指不低于所给的条件。

11.6.3 模型的假设与符号说明

(1) 模型假设
 题目所给出的男女青年的评价是客观真实的；
 每个人在选择对方时都是理智的；
 五项条件在选择对方时所起的作用是均等的。
(2) 符号约定
B
i
－－第
i(i1,2,,20)
个男青年；

·177·

G
j
－－第
j(j1,2,,20)
个女青年；
x
ij
－－第
i
个男青年与第
j
个女青年配对时取 值1，否则取值0；
(0)
－－第
i
个女青年的第
k
项基本条件的量化指标；
a
ik
(1)
－－第
i
个男青年的第
k
项 基本条件的量化指标；
a
ik
(0)
－－第
i
个女青年的 第
k
项要求条件的量化指标；
b
ik
(1)
－－第
i
个男青年的第
k
项要求条件的量化指标；
b
ik
(0 )
S
ij
(k)
－－第
i
个女青年对第
j
个男青年的第
k
项条件的满意度；
(1)
S
ij
(k)< br>－－第
i
个男青年对第
j
个女青年的第
k
项条件的满 意度；
(0)
－－第
i
个女青年对第
j
个男青年的各项条 件的综合满意度；
S
ij
(1)
－－第
i
个男青年对第< br>j
个女青年的各项条件的综合满意度；
S
ij
SS
ij－－第
i
个男青年与第
j
个女青年的综合相互满意度；
Pij
－－第
i
个男青年与第
j
个女青年配对成功的概率；
P
T
－－所给方案的使配对成功的总概率；
(1)
ASS
ij
(0)
BSS
ij

2020
－－所有男青年 对女青年的满意度矩阵；

2020
－－所有女青年对男青年的满意度矩阵；
d
－－男（女）方的要求条件等级距离最高等级A的档数；
h
－－男（女）方的基本条件等级高出对方所要求条件等级的档数。
其中
i1,2,,20;

j1,2,,20;
k1,2,,5
。
11.6.4 模型的准备

1. 条件的量化处理

对于每个人的外貌、性格、气质、事业和财富五 项条件的5个等级
A、B、C、D
和
E
分别
作量化处理，根据层次分 析中关于条件等级差的度量标准，对
A、B、C、D
、
E
分别赋权为9、< br>7、5、3、1。于是根据表11-3和表11-4可以得到男女青年的基本条件量化矩阵和要求条件量< br>化矩阵（或称权值矩阵）分别为
(1)(1)


Aa
ik


(1)(1)
BB

ik



205
(0)
,A
(0)
a
ik
205,B
(0)



b

205
( 0)
ik
205
（11.6）



· ·178

2. 条件过滤

由于 问题是明确要求“男青年的年龄至多比女青年大5岁，而女青年的年龄至多比男青
年大2岁”，以及“至 少满足个人要求5项条件中的2项”。在20对男女青年中所有可能的配
对中首先应将不满足这些基本条 件的情况过滤掉。由（11.6）式用Matlab编程进行过滤可以过
滤掉58对组合。

3. 满意度的确定

(1) 对单项条件的满意度
要确定
G
j
对
B
i
的第
k(1i,j20,1k5)
项条件的满意度。首先要注意到两个事实：
0)
(1)
其一，如果
B
i
的基本条件
a
ik
比
G
j
的要求条件
b
(
jk
差的越多，则
G
j
对
B
i
的第
k
项条件的满
意度
S
ji
(k)
就越小，反 之亦然。也就是说，如果一方的实际条件比对方期望（要求）的条件
(1)
差距越大，则对方对 另一方失望就越大，即满意度就越小。其二，如果
B
i
的基本条件
a
ik
比
G
j
(0)
0)
的要求条件
b
(< br>jk
高，则
G
j
对
B
i
的第
k项条件的满意度
S
ji
(k)
就会增加，但增加不会太多。即
( 0)
当一方的实际条件高于对方期望（要求）的条件时，则对方对另一方的好感（相对要求条件）
增加不会太大。
根据上面的两个事实，先以女青年
G
j
对男青年
B
i
的第
k
项条件的满意度
S
ji
(k)
为例。
若
B
i
的实际条件比
G
j
的要求差，那么
G
j
对
B
i
该项指标的满意度将迅速减小，减小的速度一< br>般会与
G
j
的要求条件相差的档数有关，二者会成一定的比例关系。当
B
i
的实际条件比
G
j
的
要求条件差得很大（例如，三个档 次以上）时，则认为
G
j
对
B
i
“失去信心”，即满意度 为0。
若
B
i
的实际条件比
G
j
的要求条件还要好 ，那么
G
j
对
B
i
的这项条件的满意度会略有提升，
但提升的不会太大。
根据实 际情况，一般认为如果男青年
B
i
的条件达到女青年
G
j
的 要求条件时，那么，
G
j
会以90%的可能接受
B
i
，此时 即可以认为
G
j
对
B
i
的第
k
项条件的满 意度
S
ji
(k)
=0.9。
下面首先给出
G
j
对
B
i
的第
k
项条件的满意度
S
ji< br>(k)
的定义：
(0)
(0)
(0)
0.1
(1)(0)
0.9h,ab
ikjk

d

(1 )
a

(1)0)0)(1)
S
(
ji
0)
(k)

0.9
(
ik
,a
ik
b
(
jk
且b
(
jk
a
ik
3
0)< br>b
jk


0,a
(1)
b
(0)
且b
(0)
a
(1)
3
ikjkjkik




i,j1,2,

,20



k1,2,

,5


（11.7）

·179·

如果
G
j
的第
k
项条件的要求为
C
，则根据
B
i
的第
k
项条件的不同情况，
G
j
对
B
i
的第
k
项 条件的满意度
S
(
ji
0)
(k)
的取值如图11-1所示 。
(1)
同理定义
B
i
对
G
j
的第k
项条件的满意度
S
ij
(k)
如下：
0.1

(0)(1)
0.9h,ab
jkik

d
0)
a
(
jk

(1)0)(1)(1)0)
S
ij
(k)

0.9
(1)
,a
(
jkb
ik
andb
ik
a
(
jk
3
b
ik


0,a
(0)
b
(1)
a ndb
(i)
a
(0)
3
jkikikjk




S
(
ji
0)
(k)

1
0.9



0)

b
(
jk


i,j1,2,< br>
,20



k1,2,

,5


（11.8）

E D C B A
a
ik

图11-1：
G
j
的要求为
C
时，
G
j
对
B
i
的满意度

(1)
（2） 综合满意度
一对男女青年相互之间的综合满意度主要取决于对对方的 各项条件的满意度
S
ij
(k)
和
(1)
S
(ji
0)
(
k
)(1
i
,
j
20 ;
k
1,2,

,5)
，由假设,可以定义男青年
Bi
对女青年
G
j
的综合满意度为
S
(1)
i j
1
5
(1)


S
ij
(k)
5
k1

i,j1,2,

,20



k1,2,

,5


（11.9）

由（11.6）、（11.8）、（11.9）式计算可得到结果。 同理，定义女青年
G
j
对男青年
B
i
的综合满意度为
S
(0)
ji
1
5
(0)


S
ji
(k)
5
k1

i,j1,2,

,20



k1,2,

,5


（11.10）

由（11.6）、（11.9）、（11.10）式可以计算出结果。

· ·180

（3）相互满意度：
男青年
B
i
与女青年
G
j
的相互满意度定义为
(1)(0)

配对的条件时

S
ij
S
ji
,当B
i
与G
j
满足可能

SS
ij



配对的条件时


0，当B
i
与G
j
不满足可能
经过计算可得到 相互之间的满意度。



11.6.5 模型的建立与求解

问题（1） 根据问题的要求，欲使得在尽量满足个人要求的条件下，使配对成功率尽可 能
的高。事实上，我们可以用20对男女青年的满意度指标
SS
ij
,(i, j1,2,,20)
之和来刻画总
的配对成功的成功率
P
T
,于 是我们将问题归结为所有20 对男女青年如何配对能使得
2020

SS
i1j1
ij
x
ij
有最大值，即问题的模型为
maxz< br>
SS
ij
x
ij
i1j1
2020

20


x
ij
1,j1,2,

,20

i1
（11.11）
20
s.t.


x
ij
1,i1,2,

, 20

j1

x0,或1(i,j1,2,

,20 )

ij

这是一个0-1规划问题，用匈牙利方法求解可得最优配对方案如 表11-5。最优值（总满意
度）为
z16.75132
。

表11-5：问题（1）的最优配对方案
男
女
B
1

G
4

B
2

B
3

G
15

B
4

B
5

G
2

B
6

G
5

B
16

G
19

B
7

G
3

B
17

G
14

B
8

G
13

B
18

G
11

B
9

G
17

B
19

G
8

B
10

G
9

B
20

G
12

G
18

G
20

满意度 0.8499 0.9095 0.8874 0.8016 0.8930 0.7777 0.8349 0.8360 0.6465 0.9327
男
女
B
11

B
12

B
13

G
7

B
14

B
15

G
6

G
16

G
10

G
1

满意度 0.8296 0.8224 0.7568 0.9299 0.8674 0.7796 0.8972 0.9075 0.8784 0.7133

问题（2） 要使20 对男女青年同时配对，使得全部配对成功的可能性最大。记20对男女
青年可同时配对成功的概率为P

P
i,j
ij
，即问题为求

·181·

maxP

P
i,j
ij

由于
Pij
SS
ij
，则问题等价于求一个20对男女青年同时配对的方案使目标函数
maxz

SS
ij
x
ij

i1j1
nn
有最大值，其约束条件与（11.11）式相同。
令< br>C
ij
Log(SS
ij
)
，考虑相应的目标函数

maxZ

C
ij
x
ij

i1j1
nn
约束条件不变，同理求解可得最优的配对方案如表11-6，其最优值为< br>z0.0197
。

表11-6：问题（2）的最优配对方案

男
女
B
1

G
2

B
2

B
3

G
6

B
4

G
14

B
5

G
19

B
15

G
15

B
6

G
5

B
16

G
9

B
7

G
3

B
17

G
16

B
8

G
13

B
18

G
8

B
9

G
11

B
10

G
20

B
20

G
10

G
18

B
12

满意度 0.8812 0.9095 0.8612 0.8699 0.8223 0.7777 0.8349 0.8360 0.7577 0.8506
男
女
B
11

G
1

B
13

G
7

B
14

G
12

B
19

G
4

G
17

满意度 0.8435 0.7339 0.7568 0.8075 0.8379 0.8501 0.8120 0.8398 0.8532 0.7259


· ·182