第五章 多目标规划
§ 1．问题的提出与目标规划的数学模型
§ 2．目标规划的图解分析法
§ 3．用单纯形法求解目标规划
§ 4．求解目标规划的层次算法
§ 5．应用举例
§ 1．问题的提出与
目标规划的数学模型
线性规划、整数规划和后面将要学习的动态规划都是
解决单个目标函数在一组约束条件下的极值问题。但在许
多实际问题中，在一组约束条件下，往往要求实现多个目
标。例如，在企业安排生产问题中，既要利润高，又要消
耗低，还要考虑市场需求，等等。这些目标的重要性各不
相同，目标规划正是为了解决这类多目标规划问题而产生
的，它能把决策者的意愿反映到数学模型中去。
线性规划问题的局限性,
1,要求问题的解必须满足全部约束条件，但实际问
题中并非所有约束都需严格满足；
2,只能处理单目标的优化问题，因此线性规划模型
认为地将一些次要目标转为约束。而实际问题中，目标和
约束可以互相转化，处理时不一定严格区分；
3,线性规划中各个约束条件都处于同等重要的地位，
但实际问题中，各目标的重要性是有差别的；
4,线性规划寻求最优解，但很多实际问题中只需找
出满意解就可以了。
最佳生产计划问题
某工厂计划生产甲、乙两种产品，这两种产品的有关
数据如下表所示。
工厂在作决策时，要实现如下的目标,
目标 1,根据市场信息，产品甲的销售量有下降的趋
势，故考虑产品甲的产量不大于产品乙；
一、问题的提出
目标 2,超过计划供应的原料时，需要高价采购，使
成本增加，因而只采购计划供应的原料；
目标 3,应尽可能利用现有设备，但不希望加班；
目标 4,应尽可能达到并超过计划利润指标 (56元 )。
这样，在考虑产品生产决策时，不再是单纯追求利润
最大，而是同时要考虑多个目标，这样的问题一般的线性
规划方法已无法解决，需引入一种新的数学模型 ——目
标规划 。
二、目标规划模型的建立
1,偏差变量
用来表示实际值与目标值之间的差异。
d + —— 超出目标的差值，称为 正偏差变量 。
d - —— 未达到目标的差值，称为 负偏差变量 。
因实际决策值不可能既超过目标值又低于目标值，故
最终结果中恒有 d + · d - =0 (即两者至少有一个为 0)。
目标规划中，一般有多个目标值，每个目标值都相应
有一对偏差变量 。
2,绝对约束和目标约束
绝对约束 是指必须严格满足的等式约束或不等式
约束；如线性规划问题的所有约束条件，不能满足这些条
件的解称为非可行解，所以绝对约束是 硬约束 。
目标约束 是目标规划所特有的一种约束，它把要
追求的目标值作为右端常数项，在追求此目标值时允许发
生正偏差和负偏差。因此，目标约束是由决策变量，正、
负偏差变量和要追求的目标值组成的 软约束 。
目标约束不会不满足，但可能偏差过大 。
绝对约束,问题中的目标 2，在原料供应受严格限制
的基础上考虑，可写成绝对约束为
112 21 ?? xx
假设问题中甲、乙两产品的产量分别为 x1 和 x2 。
目标约束,问题中的目标 4 可写成目标约束为
?? ???? 1121 56108 ddxx
化为标准形式是,56108
1121 ???? ?? ddxx
线性目标约束的一般形式是,? ?
iiii bddXf ???
??
? ? ? ? ?
?
??
n
i
jiji
T
n xCXfxxxX
1
21,,,,?
其中,
3,优先因子和权系数
目标规划中，当决策者要求实现多个目标时，这些目
标之间是有主次区别的。
凡要求第一位达到的目标，赋于 优先因子 p1，要求第
二位达到的目标，赋于优先因子 p2 … 并规定 pk+1∝ pk，表
示 pk 比 pk+1 有绝对优先权。因此，不同的优先因子代表
着不同的优先等级。
若要区别具有相同优先因子的多个目标，可分别赋予
它们不同的 权系数 ?k 。越重要的目标，其权系数的值越
大。
在实现多个目标时，首先保证 p1 级目标的实现，这
时可不考虑其它级目标，而 p2 级目标是在保证 p1 级目标
值不变的前提下考虑的，以此类推。
4,目标函数
目标规划的目标函数是由各目标约束的正、负偏差变
量及相应的优先因子、权系数构成的，其中不含决策变量。
因为决策者的愿望总是尽可能缩小偏差，实现目标。故总
是将目标函数极小化，其基本形式有三种。
对于第 i 个目标, ? ?
iiii bddXf ??? ??
(1) 若要求 决策值超过目标值,则相应的负偏差变量
要尽可能地小，而对正偏差变量不加限制，目标函数的形
式为,
?
idm in
(2) 允许 达不到目标值,就是相应的正偏差变量要尽
可能地小,目标函数的形式为,
?idm in
(3) 恰好达到目标,则相应的正、负偏差变量都要尽
可能地小,目标函数的形式为,
? ??? ? ii ddm i n
加入优先因子和权系数后，建立目标函数，其一般形
式为,
? ???
?
????
?
??
L
l
lkllkl
K
k
k ddpz
11
m in ??
前述问题的目标规划模型可以写为,
? ? ???? ???? 3322211m i n dpddpdpz
?
?
?
?
?
?
?
?
?
??
????
????
????
??
??
??
??
??
。
，
，
，
，
3,2,1,0,,,
56108
102
0
112
s, t,
21
3321
2221
1121
21
iddxx
ddxx
ddxx
ddxx
xx
ii
目标规划的一般数学模型，见教材 135~136页。
§ 2．目标规划的图解分析法
对于只有两个决策变量的线性目标规划的数学模型，
可以用图解法来分析求解。传统的线性规划一般只是寻求
一个点，在这个点上得到单目标的最优值，目标规划一般
是寻求一个区域，这个区域提供了相互矛盾的目标集的折
衷方案。
步骤 1 建立直角坐标
系，令各偏差变量为 0，作
出所有的约束直线 。满足
所有绝对约束条件的区域，
用阴影标出。
步骤 2 作图表示差变量增减对约束直线的影响
在所有目标约束直线旁标上 d +,d -,如图所示。这
表明目标约束直线可以沿 d +,d -,所示的方向平移。
步骤 3 根据目标函数中的优先因子次序，逐步分析求
解。
根据目标函数中的优先因子次序，首先考虑具有优先
因子 p1 的目标的实现。目标函数要求实现 min d1+，从图
中可见，可以满足 d1+=0,这时，只能在三角形 OBC的区
域上取值；
考察具有优先因子 p2的
目标，此时可在线段 ED 上
取值；
考察优先因子 p3 的目标，
这就使取值范围缩小到线段
GD 上，该线段上所有点的
坐标，都是问题的解。
多目标规划问题的另一类表示方法
买糖问题
设商店有甲、乙、丙三种糖果，单价分别为 4元 /kg,
2.80元 /kg 和 2.40元 /kg。今要筹办一次节日茶话会，要求
用于买糖的钱数不超过 20元，糖的总量不少于 6kg,甲、
乙两种糖的总和不少于 3kg,问应如何确定最好的买糖方
案。
解,设购买甲,乙,丙三种糖果的斤数分别为 x1,x2,x3
用于买糖所花的钱数为 y1,所买糖的总斤数为 y2 。
我们希望 y1 取最小值,y2 取最大值。
m a x
m i n4.28.24
3212
3211
????
????
xxxy
xxxy
约束条件可以写为,
0,,
3
6
204.28.24
321
21
321
321
?
??
???
???
xxx
xx
xxx
xxx
这是含有两个目标的线性规划问题，这里可以将求 y2
的最大值转化为求（ - y2 ）的最小值，这时目标函数可以
写为,
? ? ? ?? ?TxfxfV 21,m i n?
其中,
Txxxxyxfyxf ),,(,)(,)( 3212211 ????
§ 3．用单纯形法求解目标规划
目标规划的数学模型与线性规划的数学模型基本相同，
因此利用单纯形法求解步骤也基本相同，但是需要尤其注
意它们之间的区别。
线性规划的单纯形法求解过程,
1,建立初始单纯形表，计算出所有变量的检验数。
2,在非基变量检验数中找到最大的正数 σj，它所对
应的变量 xj 作为换入基的变量。
3,对于所有 aij> 0 计算 bi /aij,其中最小的元素 θ 所
对应的基变量 xi 作为换出基的变量。
4,建立新单纯形表，重复上述步骤 2,3，直到所有
检验数都小于等于零。
由于目标规划的目标函数都是求极小化问题，而线性
规划问题的标准型中目标函数都是求极大化问题，因此在
用单纯形法求解时要注意一些重要的的差别。
? ?
?
?
?
?
?
?
?
??
????
????
???
???
??
??
??
??
???
)3,2,1( 0,,,
10023
40 2
10
m i n
21
3321
2221
111
32211
iddxx
ddxx
ddxx
ddx
dPddPz
ii
用单纯形法求解下述目标规划问题,
第一步,列出初始单纯形表，并计算检验数。
将表格中最后一行检验数按优先级改写为,
（这是与线性规划单纯形法的 第一个差别 ）
对两行检验数需分别进行处理。
第二步,确定换入基的变量。
在负检验数中，选择最小的一个 σj 所对应的变量 xj
作为换入基的变量。在这个问题中第一优先级 P1 所的检
验数中 – 1 是最小的，因此 x1 为换入基的变量。
这是与线性规划单纯形法的 第二个差别,在线性规划
中是将大于零的检验数中较大的一个对应的变量换入基。
这是仅仅因为目标函数取值有极大和极小的差别，对于目
标函数取极小的线性规划问题也可以同样进行处理。
第三步,确定换出基的变量。
对于所有 aij> 0 计算 bi /aij,其中最小的元素 θ 所对应
的基变量 xi 作为换出基的变量。（这与线性规划相同）
在这个问题中 min{bi /aij }=10，因此 d1- 为换出变量。
换入、换出基的变量确定过程如下表,
第四步,用换入变量替换换出变量，进行单纯形法迭
代运算，直至优先级 P1 所对应的检验数全为非负。
本例中，第一优先级计算后得,
由于优先级 P2 的检验数仍然有负值，因此可以继续
优化，重复上述步骤 2~4 。
确定换入、换出变量,
第一点说明,
目标函数按优先级顺序进行优化，当 P1 行所有检验
数非负时，说明第一级已经优化，可以转入下一级，考察
P2 行检验数，依此类推。
第二点说明,
从考察 P2 行检验数开始，注意应包括更高级别的优
先因子在内。如上述问题的进一步单纯形表如下,
对应的检验数为
P1 + (–3/2)P2 >0
对应的检验数为
P1 – P2 >0
对应的检验数为
P1 – 2P2 >0
因此上述三种情况都
不能选为换入基的变量，
这其实与线性规划相同。
判别迭代计算停止的准则,
(1) 检验数 P1,P2,…,Pk 行的所有值均
为非负；
(2) 若 P1,P2,…,Pi 行的所有检验数为
非负，而 Pi+1 行存在负检验数，但在负检验
数所在列的上面行中有正检验数（不一定是
相邻行，只要在起上方即可）。
§ 4．求解目标规划的层次算法
求解目标规划是从高优先级到低优先级逐层优化的，
求解目标规划的层次算法就是根据这样的思想构造的。
层次算法步骤,
第一步,对目标函数中的 P1 层次进行优化，建立第
一层次的线性规划模型 LP1 并求解。 LP1的目标函数为
? ??
?
???? ??
L
l
ll dwdwz
1
11111m in
LP1的约束条件含原目标规划的所有约束。
第二步,对 P2 层次进行优化。
由于下一层次的优化应在前面各层次优化的基础上进
行,若第一层次目标函数最优值为 z1*,则构建的 P2 层次
的线性规划模型 LP2,其目标函数为
? ??
?
???? ??
L
l
ll dwdwz
1
22222m in
约束条件除含有原目标规划的所有约束条件之外，由
于这一步优化是在前一步优化的基础上进行的，所以前一
步优化的结果应成为一个新的约束条件，即约束条件增加
了一个式子,
? ? *1
1
1111 zdwdw
L
i
ll ???
?
????
小于等于使得上一步的最优值在计算后不会发生改变
第三步,依此类推得到第 Ps( s ≥2) 层次进行优化时建
立的线性规划模型 LPs 为,
? ??
?
???? ??
L
l
sslssls dwdwz
1
m in
?
?
?
?
?
?
?
?
?
?
?
????
????
????
????
??
??
?
?
????
?
?
),,1( 0,,),,1( 0
),,1(
),,1(),(
)1,,1(
,.
1
1j
*
Llddnjx
Llgddxc
mi bxa
srzdwdw
ts
llj
lll
n
j
jlj
i
n
jij
rrrlrrl
??
?
?
?
当进行到 s=K 时，对 Pk 层次建立的线性规划模型
LPk 的最优解即为目标规划问题的满意解。 K是某一步。
例, 用层次算法求解下述目标规划。
? ? ? ?
?
?
?
?
?
?
?
?
?
?
?
??
???
???
????
????
??
??????
??
??
??
??
??
??????
)4,,1( 0,,,
155
16 4
0 2
1532
1222
.,
3m in
21
442
331
2221
1121
21
4333322211
?iddxx
ddx
ddx
ddxx
ddxx
xx
ts
dPddPddPdPz
ii
解,第一层次的优化模型 LP1为,
?
?
?
?
?
?
?
?
?
?
?
??
???
???
????
????
??
?
??
??
??
??
??
?
)4,,1( 0,,,
155
16 4
0 2
1532
1222
.,
m in,LP
21
442
331
2221
1121
21
111
?iddxx
ddx
ddx
ddxx
ddxx
xx
ts
dz
ii
利用线性规划的单纯形法对其求解，得,
0,75.3,5.8
,0,75.3,875.1
*
143
431121
???
??????
??
????
zdd
ddddxx
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
???
???
????
????
??
??
??
?
??
??
??
??
??
)4,,1( 0,,,
0
155
16 4
0 2
1532
1222
.,
m i n,LP
21
1
442
331
2221
1121
21
2122
?iddxx
d
ddx
ddx
ddxx
ddxx
xx
ts
ddz
ii
因为 z1*=0,因此在第二层次的优化模型中加上约束
条件 =0 (因为 最小就只能是 0，因此不用写小于号 ),?
1d ?1d
求解后所得最优值与最优解与 LP1 相同，即 z2*=0 。
由于 z2*=0,故对第三层次进行优化的时候，在 LP2
的基础上加上约束,得 LP3,
022 ?? ?? dd
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
?
???
???
????
????
??
???
??
??
?
??
??
??
??
???
)4,,1( 0,,,
0
0
155
16 4
0 2
1532
1222
.,
3m i n,LP
21
21
1
442
331
2221
1121
21
43333
?iddxx
dd
d
ddx
ddx
ddxx
ddxx
xx
ts
dddz
ii
求解 LP3 得,
0.29,0.5,0.8,0.1
0,0.4,0.2
*
3431
4322121
????
???????
???
?????
zddd
dddddxx
到此时，所有各层次的优化都已经完成，而最后一个
层次的最优值 z3*=29.0,因此并没有取得最优解，这个值
只是该目标规划问题的满意解，这个解与用图解法求出的
解相同，就是图中 F 点。
§ 1．问题的提出与目标规划的数学模型
§ 2．目标规划的图解分析法
§ 3．用单纯形法求解目标规划
§ 4．求解目标规划的层次算法
§ 5．应用举例
§ 1．问题的提出与
目标规划的数学模型
线性规划、整数规划和后面将要学习的动态规划都是
解决单个目标函数在一组约束条件下的极值问题。但在许
多实际问题中，在一组约束条件下，往往要求实现多个目
标。例如，在企业安排生产问题中，既要利润高，又要消
耗低，还要考虑市场需求，等等。这些目标的重要性各不
相同，目标规划正是为了解决这类多目标规划问题而产生
的，它能把决策者的意愿反映到数学模型中去。
线性规划问题的局限性,
1,要求问题的解必须满足全部约束条件，但实际问
题中并非所有约束都需严格满足；
2,只能处理单目标的优化问题，因此线性规划模型
认为地将一些次要目标转为约束。而实际问题中，目标和
约束可以互相转化，处理时不一定严格区分；
3,线性规划中各个约束条件都处于同等重要的地位，
但实际问题中，各目标的重要性是有差别的；
4,线性规划寻求最优解，但很多实际问题中只需找
出满意解就可以了。
最佳生产计划问题
某工厂计划生产甲、乙两种产品，这两种产品的有关
数据如下表所示。
工厂在作决策时，要实现如下的目标,
目标 1,根据市场信息，产品甲的销售量有下降的趋
势，故考虑产品甲的产量不大于产品乙；
一、问题的提出
目标 2,超过计划供应的原料时，需要高价采购，使
成本增加，因而只采购计划供应的原料；
目标 3,应尽可能利用现有设备，但不希望加班；
目标 4,应尽可能达到并超过计划利润指标 (56元 )。
这样，在考虑产品生产决策时，不再是单纯追求利润
最大，而是同时要考虑多个目标，这样的问题一般的线性
规划方法已无法解决，需引入一种新的数学模型 ——目
标规划 。
二、目标规划模型的建立
1,偏差变量
用来表示实际值与目标值之间的差异。
d + —— 超出目标的差值，称为 正偏差变量 。
d - —— 未达到目标的差值，称为 负偏差变量 。
因实际决策值不可能既超过目标值又低于目标值，故
最终结果中恒有 d + · d - =0 (即两者至少有一个为 0)。
目标规划中，一般有多个目标值，每个目标值都相应
有一对偏差变量 。
2,绝对约束和目标约束
绝对约束 是指必须严格满足的等式约束或不等式
约束；如线性规划问题的所有约束条件，不能满足这些条
件的解称为非可行解，所以绝对约束是 硬约束 。
目标约束 是目标规划所特有的一种约束，它把要
追求的目标值作为右端常数项，在追求此目标值时允许发
生正偏差和负偏差。因此，目标约束是由决策变量，正、
负偏差变量和要追求的目标值组成的 软约束 。
目标约束不会不满足，但可能偏差过大 。
绝对约束,问题中的目标 2，在原料供应受严格限制
的基础上考虑，可写成绝对约束为
112 21 ?? xx
假设问题中甲、乙两产品的产量分别为 x1 和 x2 。
目标约束,问题中的目标 4 可写成目标约束为
?? ???? 1121 56108 ddxx
化为标准形式是,56108
1121 ???? ?? ddxx
线性目标约束的一般形式是,? ?
iiii bddXf ???
??
? ? ? ? ?
?
??
n
i
jiji
T
n xCXfxxxX
1
21,,,,?
其中,
3,优先因子和权系数
目标规划中，当决策者要求实现多个目标时，这些目
标之间是有主次区别的。
凡要求第一位达到的目标，赋于 优先因子 p1，要求第
二位达到的目标，赋于优先因子 p2 … 并规定 pk+1∝ pk，表
示 pk 比 pk+1 有绝对优先权。因此，不同的优先因子代表
着不同的优先等级。
若要区别具有相同优先因子的多个目标，可分别赋予
它们不同的 权系数 ?k 。越重要的目标，其权系数的值越
大。
在实现多个目标时，首先保证 p1 级目标的实现，这
时可不考虑其它级目标，而 p2 级目标是在保证 p1 级目标
值不变的前提下考虑的，以此类推。
4,目标函数
目标规划的目标函数是由各目标约束的正、负偏差变
量及相应的优先因子、权系数构成的，其中不含决策变量。
因为决策者的愿望总是尽可能缩小偏差，实现目标。故总
是将目标函数极小化，其基本形式有三种。
对于第 i 个目标, ? ?
iiii bddXf ??? ??
(1) 若要求 决策值超过目标值,则相应的负偏差变量
要尽可能地小，而对正偏差变量不加限制，目标函数的形
式为,
?
idm in
(2) 允许 达不到目标值,就是相应的正偏差变量要尽
可能地小,目标函数的形式为,
?idm in
(3) 恰好达到目标,则相应的正、负偏差变量都要尽
可能地小,目标函数的形式为,
? ??? ? ii ddm i n
加入优先因子和权系数后，建立目标函数，其一般形
式为,
? ???
?
????
?
??
L
l
lkllkl
K
k
k ddpz
11
m in ??
前述问题的目标规划模型可以写为,
? ? ???? ???? 3322211m i n dpddpdpz
?
?
?
?
?
?
?
?
?
??
????
????
????
??
??
??
??
??
。
，
，
，
，
3,2,1,0,,,
56108
102
0
112
s, t,
21
3321
2221
1121
21
iddxx
ddxx
ddxx
ddxx
xx
ii
目标规划的一般数学模型，见教材 135~136页。
§ 2．目标规划的图解分析法
对于只有两个决策变量的线性目标规划的数学模型，
可以用图解法来分析求解。传统的线性规划一般只是寻求
一个点，在这个点上得到单目标的最优值，目标规划一般
是寻求一个区域，这个区域提供了相互矛盾的目标集的折
衷方案。
步骤 1 建立直角坐标
系，令各偏差变量为 0，作
出所有的约束直线 。满足
所有绝对约束条件的区域，
用阴影标出。
步骤 2 作图表示差变量增减对约束直线的影响
在所有目标约束直线旁标上 d +,d -,如图所示。这
表明目标约束直线可以沿 d +,d -,所示的方向平移。
步骤 3 根据目标函数中的优先因子次序，逐步分析求
解。
根据目标函数中的优先因子次序，首先考虑具有优先
因子 p1 的目标的实现。目标函数要求实现 min d1+，从图
中可见，可以满足 d1+=0,这时，只能在三角形 OBC的区
域上取值；
考察具有优先因子 p2的
目标，此时可在线段 ED 上
取值；
考察优先因子 p3 的目标，
这就使取值范围缩小到线段
GD 上，该线段上所有点的
坐标，都是问题的解。
多目标规划问题的另一类表示方法
买糖问题
设商店有甲、乙、丙三种糖果，单价分别为 4元 /kg,
2.80元 /kg 和 2.40元 /kg。今要筹办一次节日茶话会，要求
用于买糖的钱数不超过 20元，糖的总量不少于 6kg,甲、
乙两种糖的总和不少于 3kg,问应如何确定最好的买糖方
案。
解,设购买甲,乙,丙三种糖果的斤数分别为 x1,x2,x3
用于买糖所花的钱数为 y1,所买糖的总斤数为 y2 。
我们希望 y1 取最小值,y2 取最大值。
m a x
m i n4.28.24
3212
3211
????
????
xxxy
xxxy
约束条件可以写为,
0,,
3
6
204.28.24
321
21
321
321
?
??
???
???
xxx
xx
xxx
xxx
这是含有两个目标的线性规划问题，这里可以将求 y2
的最大值转化为求（ - y2 ）的最小值，这时目标函数可以
写为,
? ? ? ?? ?TxfxfV 21,m i n?
其中,
Txxxxyxfyxf ),,(,)(,)( 3212211 ????
§ 3．用单纯形法求解目标规划
目标规划的数学模型与线性规划的数学模型基本相同，
因此利用单纯形法求解步骤也基本相同，但是需要尤其注
意它们之间的区别。
线性规划的单纯形法求解过程,
1,建立初始单纯形表，计算出所有变量的检验数。
2,在非基变量检验数中找到最大的正数 σj，它所对
应的变量 xj 作为换入基的变量。
3,对于所有 aij> 0 计算 bi /aij,其中最小的元素 θ 所
对应的基变量 xi 作为换出基的变量。
4,建立新单纯形表，重复上述步骤 2,3，直到所有
检验数都小于等于零。
由于目标规划的目标函数都是求极小化问题，而线性
规划问题的标准型中目标函数都是求极大化问题，因此在
用单纯形法求解时要注意一些重要的的差别。
? ?
?
?
?
?
?
?
?
??
????
????
???
???
??
??
??
??
???
)3,2,1( 0,,,
10023
40 2
10
m i n
21
3321
2221
111
32211
iddxx
ddxx
ddxx
ddx
dPddPz
ii
用单纯形法求解下述目标规划问题,
第一步,列出初始单纯形表，并计算检验数。
将表格中最后一行检验数按优先级改写为,
（这是与线性规划单纯形法的 第一个差别 ）
对两行检验数需分别进行处理。
第二步,确定换入基的变量。
在负检验数中，选择最小的一个 σj 所对应的变量 xj
作为换入基的变量。在这个问题中第一优先级 P1 所的检
验数中 – 1 是最小的，因此 x1 为换入基的变量。
这是与线性规划单纯形法的 第二个差别,在线性规划
中是将大于零的检验数中较大的一个对应的变量换入基。
这是仅仅因为目标函数取值有极大和极小的差别，对于目
标函数取极小的线性规划问题也可以同样进行处理。
第三步,确定换出基的变量。
对于所有 aij> 0 计算 bi /aij,其中最小的元素 θ 所对应
的基变量 xi 作为换出基的变量。（这与线性规划相同）
在这个问题中 min{bi /aij }=10，因此 d1- 为换出变量。
换入、换出基的变量确定过程如下表,
第四步,用换入变量替换换出变量，进行单纯形法迭
代运算，直至优先级 P1 所对应的检验数全为非负。
本例中，第一优先级计算后得,
由于优先级 P2 的检验数仍然有负值，因此可以继续
优化，重复上述步骤 2~4 。
确定换入、换出变量,
第一点说明,
目标函数按优先级顺序进行优化，当 P1 行所有检验
数非负时，说明第一级已经优化，可以转入下一级，考察
P2 行检验数，依此类推。
第二点说明,
从考察 P2 行检验数开始，注意应包括更高级别的优
先因子在内。如上述问题的进一步单纯形表如下,
对应的检验数为
P1 + (–3/2)P2 >0
对应的检验数为
P1 – P2 >0
对应的检验数为
P1 – 2P2 >0
因此上述三种情况都
不能选为换入基的变量，
这其实与线性规划相同。
判别迭代计算停止的准则,
(1) 检验数 P1,P2,…,Pk 行的所有值均
为非负；
(2) 若 P1,P2,…,Pi 行的所有检验数为
非负，而 Pi+1 行存在负检验数，但在负检验
数所在列的上面行中有正检验数（不一定是
相邻行，只要在起上方即可）。
§ 4．求解目标规划的层次算法
求解目标规划是从高优先级到低优先级逐层优化的，
求解目标规划的层次算法就是根据这样的思想构造的。
层次算法步骤,
第一步,对目标函数中的 P1 层次进行优化，建立第
一层次的线性规划模型 LP1 并求解。 LP1的目标函数为
? ??
?
???? ??
L
l
ll dwdwz
1
11111m in
LP1的约束条件含原目标规划的所有约束。
第二步,对 P2 层次进行优化。
由于下一层次的优化应在前面各层次优化的基础上进
行,若第一层次目标函数最优值为 z1*,则构建的 P2 层次
的线性规划模型 LP2,其目标函数为
? ??
?
???? ??
L
l
ll dwdwz
1
22222m in
约束条件除含有原目标规划的所有约束条件之外，由
于这一步优化是在前一步优化的基础上进行的，所以前一
步优化的结果应成为一个新的约束条件，即约束条件增加
了一个式子,
? ? *1
1
1111 zdwdw
L
i
ll ???
?
????
小于等于使得上一步的最优值在计算后不会发生改变
第三步,依此类推得到第 Ps( s ≥2) 层次进行优化时建
立的线性规划模型 LPs 为,
? ??
?
???? ??
L
l
sslssls dwdwz
1
m in
?
?
?
?
?
?
?
?
?
?
?
????
????
????
????
??
??
?
?
????
?
?
),,1( 0,,),,1( 0
),,1(
),,1(),(
)1,,1(
,.
1
1j
*
Llddnjx
Llgddxc
mi bxa
srzdwdw
ts
llj
lll
n
j
jlj
i
n
jij
rrrlrrl
??
?
?
?
当进行到 s=K 时，对 Pk 层次建立的线性规划模型
LPk 的最优解即为目标规划问题的满意解。 K是某一步。
例, 用层次算法求解下述目标规划。
? ? ? ?
?
?
?
?
?
?
?
?
?
?
?
??
???
???
????
????
??
??????
??
??
??
??
??
??????
)4,,1( 0,,,
155
16 4
0 2
1532
1222
.,
3m in
21
442
331
2221
1121
21
4333322211
?iddxx
ddx
ddx
ddxx
ddxx
xx
ts
dPddPddPdPz
ii
解,第一层次的优化模型 LP1为,
?
?
?
?
?
?
?
?
?
?
?
??
???
???
????
????
??
?
??
??
??
??
??
?
)4,,1( 0,,,
155
16 4
0 2
1532
1222
.,
m in,LP
21
442
331
2221
1121
21
111
?iddxx
ddx
ddx
ddxx
ddxx
xx
ts
dz
ii
利用线性规划的单纯形法对其求解，得,
0,75.3,5.8
,0,75.3,875.1
*
143
431121
???
??????
??
????
zdd
ddddxx
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
???
???
????
????
??
??
??
?
??
??
??
??
??
)4,,1( 0,,,
0
155
16 4
0 2
1532
1222
.,
m i n,LP
21
1
442
331
2221
1121
21
2122
?iddxx
d
ddx
ddx
ddxx
ddxx
xx
ts
ddz
ii
因为 z1*=0,因此在第二层次的优化模型中加上约束
条件 =0 (因为 最小就只能是 0，因此不用写小于号 ),?
1d ?1d
求解后所得最优值与最优解与 LP1 相同，即 z2*=0 。
由于 z2*=0,故对第三层次进行优化的时候，在 LP2
的基础上加上约束,得 LP3,
022 ?? ?? dd
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
?
???
???
????
????
??
???
??
??
?
??
??
??
??
???
)4,,1( 0,,,
0
0
155
16 4
0 2
1532
1222
.,
3m i n,LP
21
21
1
442
331
2221
1121
21
43333
?iddxx
dd
d
ddx
ddx
ddxx
ddxx
xx
ts
dddz
ii
求解 LP3 得,
0.29,0.5,0.8,0.1
0,0.4,0.2
*
3431
4322121
????
???????
???
?????
zddd
dddddxx
到此时，所有各层次的优化都已经完成，而最后一个
层次的最优值 z3*=29.0,因此并没有取得最优解，这个值
只是该目标规划问题的满意解，这个解与用图解法求出的
解相同，就是图中 F 点。
