•多目标线性规划单纯形表(1)
z1 z2 x1 x2 x3 x4 x5 RHS z1 1 0 3 2 0 0 0 0 z2 0 1 -1 2 0 0 0 0 x3 0 0 1 1 1 0 0 6 x4 0 0 2 1 0 1 0 10 x5 0 0 1 2 0 0 1 10
如果非基变量在两个目标中的检验数都大于0，当前的基础 可行解是劣解。这个非基变量进基，两个目标都会改善。
第五章多目标规划
•多目标线性规划单纯形表(4)
z1 z2 x1 x2 x3 x4 x5 RHS z1 1 0 0 0 -1 -1 0 -16 z2 0 1 0 0 -5 3 0 0 x2 0 0 0 1 2 -1 0 2 x1 0 0 1 0 -1 1 0 4 x5 0 0 0 0 -3 1 1 2 •当前的解(x1,x2,x3,x4,x5)=(2,4,0,0,2), z1=16, z2=0是 Pareto解。对应于B点。 •x3进基，x2离基，两个目标同时会变差，回到劣解A。 •x4进基，x5离基，z1会变差，z2会改善，进到Pareto解C。
楼层 四层 七层 三层
第五章多目标规划
• 确定各目标最理想和最不理想的值，将各目标进 行归一化处理。最理想的值为1，最不理想的值为0， 将各决策方案的实际目标值转化为0～1之间的值。
最好
最差
实A 际B 指 标C
归A 一B 化C
面积（m2） 200 (1.0) 75 (0.0) 200 180 150 1.0 0.84 0.60
•当前的解(x1,x2,x3,x4,x5)=(0,5,1,5,0), z1=10, z2=8是 Pareto解。对应于D点。
•x1进基，x3离基，z1会改善，z2会变差，回到Pareto解C。 •x5进基，x2离基，z1会变差，z2会变差，将回到劣解O。 •已搜索到这个多目标规划的所有Pareto解B点，C点，D点。
•F
•C •B
•O
•A
• 当一个可行解的优化方向集合和可行域的交集为非空时， 两个目标z1，z2可以同时改善，即这样的可行解是劣解。优化方 向集合和可行域的交集为空集时，两个目标函数不可能同时改 善。这样的可行解是多目标规划的Pareto解。图中的可行解 B,C,D是多目标规划的Pareto解。Pareto解集为折线BCD。
第五章多目标规划
•多目标线性规划单纯形表(5)
z1 z2 x1 x2 x3 x4 x5 RHS z1 1 0 0 0 -4 0 1 -14 z2 0 1 0 0 4 0 -3 -6 x2 0 0 0 1 -1 0 1 4 x1 0 0 1 0 2 0 -1 2 x4 0 0 0 0 -3 1 1 2 •当前的解(x1,x2,x3,x4,x5)=(2,4,0,2,0), z1=14, z2=6是 Pareto解。对应于C点。 •x3进基，x1离基，z1会变差，z2会改善，进到Pareto解D。 •x5进基，x4离基，z1会改善，z2会变差，回到Pareto解B。
产量（吨）
1 1 1 总产量不低于12吨
•利润最大化的线性规划模型为：
•max z=9x1+4x2+x3
•s.t. 4x1+ 2x2+ 5x3≤38
• 2x1+ x2+ 3x3≤25
• 30x1+10x2+20x3≥100
• x1+ x2+ x3≥12
•
x1, x2, x3≥0
耗用原料约束 排放污染约束 销售总额约束 产量约束
第五章多目标规划
•多目标线性规划单纯形表(3)
z1 z2 x1 x2 x3 x4 x5 RHS z1 1 0 0 1/2 0 -3/2 0 -15 z2 0 1 0 5/2 0 1/2 0 5 x3 0 0 0 1/2 1 -1/2 0 1 x1 0 0 1 1/2 0 1/2 0 5 x5 0 0 0 3/2 0 -1/2 1 5 •当前的解(x1,x2,x3,x4,x5)=(5,0,1,0,5), z1=15, z2=-5是劣解。 对应于A点。 •x2进基，x3离基，z1，z2同时改善，进到Pareto解B。 •x4进基，x1离基，z1会变差，z2会改善，回到劣解O。
产量（吨）
总产量不低于12吨
总产量12吨
•如果允许排放的污染量从25立方米逐步减少，最优解 也将发生变化。变化情况如下表：：
第五章多目标规划
•多目标规划的例子(3)
允许排放的 产品A产量 产品B产量 产品C产量 最大利润 污染(m3) （吨） （吨） （吨） （万元）
25
7
5
0
83
19
7
5
0
83
18
第五章多目标规划
•多目标规划的例子(2)
•最优解如下表：
产品
条件
最优解
利润（万元/吨）
目标函数，最大化
总利润83万元
耗用原料（吨/吨） 耗用原料不超过38吨 耗用原料38吨
排放污染（m3/吨） 排放污染不超过25m3 排放污染19m3
销售价格（万元/吨） 销售总额不低于100万元 销售总额260万元
• a21x1+a22x2≤b2 • x1, x2≥0
•E
•设以z1为单目标的线性规划
最优解为B，以z2为单目标的
线性规划最优解为D。可行
域内部（不包括边界）的可
行解都是劣解。
•O
•z
2
•D
•z
2
•F
•C
•z
1
•B •z
1
•A
第五章多目标规划
•z2 •D
•C
•目标函数z1和z2
•E
•z2
同时改善的方向
6
6
0
78
17
5
7
0
73
16
4
8
0
68
15
3
9
0
63
14
2
10
0
58
13
1
11
0
53
12
0
12
0
48
11
没有可行解
第五章多目标规划
•利润最大化和排放污染最小化双目标问题的图
示 •最大利润（万元） •8
•排放污染最小和利润最大两 个目标可以同时实现的区域
3
•7
8
•允许排放的污染和
最大利润之间的关系
•7
劣解”或“Pareto”解，
非劣解的两个目标不可 •劣解 •劣解
•两个目标都可能实现的区域
能同时改进。
第五章多目标规划
•多目标规划问题的非劣解和非劣解集
•设多目标规划的可行域为，设其中的一个可行解 X*∈ ，它的K个目标值分别
•
f1(X*) ，f2(X*)， ……，fk(X*)
•如果对于任意的可行解X ∈ ，都至少有一个目标i， 使得
单价（元/m2） 3000 (1.0) 6000 (0.0) 4800 5500 4000 0.400 0.167 0.667
朝向 南 (1.0) 北 (0.0)
南 西
地段 甲 (1.0) 丁 (0.0)
丙 甲
楼层 三层 (1.0) 一层 (0.0)
四层 七层
东
乙
三层
1.0
0.4
0.9
0.4
•
fi(X)>fi(X*)
•则称X*为这个多目标规划的一个Pareto解（也称为非劣 解、有效解）。
•如果一个多目标规划问题有一个以上的Pareto解，这些 Pareto解组成的集合称为Pareto解集。
第五章多目标规划
•Pareto解集的图解
•f(x)
•f1(X) •f2(X)
•xz2的最优 解
•4
•x5= 0
•多目标规划的Pareto•解s.t集. x1+
•C
• 2x1+
x2 x2
≤6 ≤10
• x1+2x2 ≤10
•3
•z •x1=
2 •2 0
•1
•O
•x3= 0
•目标z1的• 最优x1，x2≥0
解
•B
•z1
•x4=
•x2=
0 •A
•0123456
0
第五章多目标规划
第五章多目标规划
•多目标线性规划单纯形表(6)
z1 z2 x1 x2 x3 x4 x5 RHS z1 1 0 2 0 0 0 -1 -10 z2 0 1 -2 0 0 0 -1 -8 x2 0 0 1/2 1 0 0 1/2 5 x3 0 0 1/2 0 1 0 -1/2 1 x4 0 0 3/2 0 0 1 -1/2 5
值Z2A，得到A点。……
用同样的方法得到B点。
•非劣解(Pareto解)
依次进行，得到两个目 •z2B
•B
标之间关系的曲线AB 和相应的区域。
•M •P’
•非劣解(Pareto解)
•区域内部的点N和M称
•N
为“劣解”，劣解的两 •z2A
•P •A
个目标同时可以改进。
曲线AB上的点称为“非
•z1B
•z1A •第一个目标
如果任何一个非基变量在两个目标中的检验数不同时大于0， 这个基础可行解是Pareto解，任何一个非基变量进基，一个 目标将会改善，而另一个目标将会变差。
第五章多目标规划
•多目标线性规划单纯形表(2)
z1 z2 x1 x2 x3 x4 x5 RHS z1 1 0 3 2 0 0 0 0 z2 0 1 -1 2 0 0 0 0 x3 0 0 1 1 1 0 0 6 x4 0 0 2 1 0 1 0 10 x5 0 0 1 2 0 0 1 10 •当前的解(x1,x2,x3,x4,x5)=(0,0,6,10,10), z1=0, z2=0是劣 解，对应于图中的O点。 •x1进基，x4离基，z1会改善，z2将会变差，进到劣解A。 •x2进基，x5离基，z1，z2可以同时改善，进到Pareto解D。