目标规划典型例题.doc

§6.4 主要解题方法和典型例题分析
题型I 目标规划数学模型的建立
当线性规划问题有多个目标需要满足时，就可以通过建立目标规划数学模型来描述。目标规划数学模型的建立步骤为：第一步，确定决策变量；第二步，确定各目标的优先因子；第三步，写出硬约束和软约束；第四步，确定目标函数。
例6-1 某公司生产甲、乙两种产品，分别经由I、II两个车间生产。已知除外购外，生产一件甲产品需要I车间加工4小时，II车间装配2小时，生产一件乙产品需I车间加工1小时，II车间装配3小时，这两种产品生产出来以后均需经过检验、销售等环节。已知每件甲产品的检验销售费用需40元，每件乙产品的检验销售费用需50元。I车间每月可利用的工时为150小时，每小时的费用为80元；II车间每月可利用的工时为200小时，每小时的费用为20元，估计下一年度平均每月可销售甲产品100台，乙产品80台。公司根据这些实际情况定出月度计划的目标如下：
P1：检验和销售费用每月不超过6000元；
P2：每月售出甲产品不少于100件；
P3：I、II两车间的生产工时应该得到充分利用；
P4：I车间加班时间不超过30小时；
P5：每月乙产品的销售不少于80件。
试确定该公司为完成上述目标应制定的月度生产计划，建立其目标规划模型。
解：先建立目标规划的数学模型。设x1为每月计划生产的甲产品件数，x2为每月生产的乙产品的件数。根据题目中给出的优先等级条件，有以下目标及约束：
（1） 检验及销售费用目标及约束；
（2） 每月甲产品的销售目标及约束；
（3） I、II两车间工时利用情况目标及约束
I车间，II车间
（4） I车间加班时间目标及约束

（5） 每月乙产品销售目标及约束
根据优先等级层次，确定优先因子和权系数，得出目标规划的数学模型如下：

例6-2 有三个产地向四个销地供应物资。产地Ai(i=1,2,3)的供应量ai、销地Bj(j=1,2,3,4)的需要量bj、各产销地之间的单位物资运费Cij如表5-1所示。表中，ai和bj的单位为吨，Cij的单位为元/吨。编制调运方案时要求按照相应的优先级依次考虑下列六个目标：
P1：B4是重点保证单位，其需要量应尽可能全部满足；
P2：A3向B1提供的物资不少于100吨；
P3：每个销地得到的物资数量不少于其需要量的80%；
P4：实际的总运费不超过当不考虑P1至P6各目标时的最小总运费的110%；
P5：因路况原因，尽量避免安排A2的物资运往B4；
P6：对B1和B3的供应率要尽可能相同；
试建立该问题的目标规划模型。
表6-1
Bj
cij
Ai
B1
B2
B3
B4
ai
A1
5
2
6
7
300
A2
3
5
4
6
200
A3
4
5
2
3
400
bj
200
100
450
250

解：设xij为从Ai运往Bj的运输量，首先求出当不考虑P1至P6各目标时的最小总运费为2950元。
在各级目标中没有涉及到供应量，因此供应量构成硬约束：

根据各优先级目标，可写出相应的目标及目标约束。
P1：B4是重点保证单位，其需要量应尽可能全部满足

P2：A3向B1提供的物资不少于100吨

P3：每个销地得到的物资数量不少于其需要量的80%

P4：实际的总运费不超过当不考虑P1至P6各目标时的最小总运费的110%。

P5：因路况原因，尽量避免安排A2的物资运往B4

P6：对B1和B3的供应率要尽可能相同

综上所述，将该问题列成优先目标规划模型：

题型II 目标规划的图解法
目标规划的图解法就是通过图形来确定所给目标规划的满意解，虽然比较直观，但因为是平面图，所以最多只能求解包含两个决策变量的目标规划问题。其解题步骤是：第一步，建立直角坐标系，作出硬约束的限制区域；第二步，作出其他约束条件当偏差变量为0时的图形，确定其它各约束条件的限制区域；第三步，结合决策变量的可行范围，按优先因子考察各偏差变量的变化对目标函数的影响，确定尽可能满足目标的满意解。
例6-3 用图解法找出以下目标规划问题的满意解。

解：第一步，因为本题没有硬约束，所以先作出偏差变量为0时，各目标约束所确定的直线，如图5-1所示。
第二步，按优先因子考虑各偏差变量的变化对目标函数的影响，确定约束条件所限定的x1,x2范围。要满足，只能在CD射线上取得满意解；显然，在CD射线上，

。其次，在CD射线上使达到极小点的只能是C点。
第三步，确定满意解。由图6-1可知，满意解为
x1
D

C
50

100/8
B
A
20/3

0
4
F
100/6
E
x2
-5
3x1+5x2=20
8x1+6x2=100
x1-10x2=50
图6-1

例6-4 用图解法找出以下目标规划问题的满意解。

解：第一步，首先作出硬约束等式直线AB：
第二步，再作出偏差变量为0时，各目标约束所确定的直线DI和CH，如图6-2所示。
第三步，按优先因子考虑各偏差变量的变化对目标函数的影响，确定约束条件所限定的x1,x2范围。要满足，并且满足硬约束所在范围，只能在GC线段上取得满意解；而要满足，满意解又只能是在CE线段上。
第三步，确定满意解。由图6-2可得满意解为C(0，5.2)和E（0.6，4.7）连线上任一点。

0
D
C
B

E
F
G
A

H
I

x2
x1
x1+2x2=10
10x1+12x2=62.4
2x1+x2=8
图6-2

题型III 目标规划的单纯形法
例6-5 用单纯形法求以下目标规划问题的满意解。

解：第一步，将原规划化为标准型

第二步，取为初始基变量，列初始单纯形表，如表6-2所示。
表6-2
cj
0
0
0
P2
0
P1
P1

CB
XB
b
x1
x2
x3

P2

10
1
[2]
0
1
-1
0
0
10/2
P1

62.4
10
12
0
0
0
1
-1
62.4/12
0
x3
8
2
1
1
0
0
0
0
8/1

cj-zj
P1
-10
-12
0
0
0
0
2

P2
-1
-2
0
0
1
0
0

第三步，取k=1，检查检验数的P1行的负数，取最小者-12对应的变量x2为换入变量，并用最小比值原则确定换出变量为，见表6-3。
表6-3
cj
0
0
0
P2
0
P1
P1

CB
XB
b
x1
x2
x3

0
x2
5
1/2
1
0
1/2
-1/2
0
0
-
P1

2.4
4
0
0
-6
[6]
1
-1
2.4/6
0
x3
3
3/2
0
1
-1/2
1/2
0
0
3/(1/2)
cj-zj
P1
-4
0
0
6
-6
0
2

P2
0
0
0
1
0
0
0

第四步，还是取k=1，检查检验数的P1行的负数，取最小值-6对应的变量为换入变量，并用最小比值规则确定换出变量，见表6-4。
表6-4
cj
0
0
0
P2
0
P1
P1

CB
XB
b
x1
x2
x3

0
x2
5.2
5/6
1
0
0
0
1/12
-1/12
-
0

0.4
2/3
0
0
-1
1
1/6
-1/6

0
x3
2.8
7/6
0
1
0
0
-1/12
1/12

cj-zj
P1
0
0
0
0
0
1
1

P2
0
0
0
1
0
0
0

第五步，检查检验数的P1行，P2行，都没有负数了，故得到满意解。且因为非基变量x1的检验数为0，所以存在多重解。
例6-6用单纯形法求解下列目标规划问题。

解：第一步：该问题已经化为标准形，以，，，为基变量，建立初始单纯形表，如表6-5所示。
表6-5 初始单纯性表

b

10
1
1
1
-1
0
0
0
0
0
0

4
[1]
0
0
0
1
-1
0
0
0
0

56
5
3
0
0
0
0
1
-1
0
0

12
1
1
0
0
0
0
0
0
1
-1
cj-zj
P1
0
0
0
2
0
3
0
0
0
0
P2
0
0
0
0
0
0
0
0
0
1
P3
-5
-3
0
0
0
0
0
1
0
0

第二步：在表6-5中，检验数矩阵中第一列、第二列均有负数，因此此表对应的解不是满意解，需要进行迭代。以为进基变量，为出基变量，进行基变换运算，结果如表6-6所示。
表6-6 第一次迭代表

b

6
0
[1]
1
-1
-1
1
0
0
0
0

4
1
0
0
0
1
-1
0
0
0
0

36
0
3
0
0
-5
5
1
-1
0
0

8
0
1
0
0
-1
1
0
0
1
-1
cj-zj
P1
0
0
0
2
0
3
0
0
0
0
P2
0
0
0
0
0
0
0
0
0
1
P3
0
-3
0
0
5
-5
0
1
0
0

第三步：在表5-6中，检验数矩阵中第二列仍有负数，以为进基变量，为出基变量，进行基变换运算，结果如表6-7所示。
表6-7 第二次迭代表

b

6
0
[1]
1
-1
-1
1
0
0
0
0

4
1
0
0
0
1
-1
0
0
0
0

18
0
0
-3
3
-2
2
1
-1
0
0

2
0
0
-1
1
0
0
0
0
1
-1
cj-zj
P1
0
0
0
2
0
3
0
0
0
0
P2
0
0
0
0
0
0
0
0
0
1
P3
0
0
3
-3
2
-2
0
1
0
0

第三步：在表6-7中，检验数矩阵中每一列第一个非零元素均为非负数，因此此表所对应的解为满意解。满意解为，目标达到情况是：第一级目标达到最优，第二级目标达到最优，第三级目标，没有达到最优。

（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）