解得最优解为： 起 到 达 飞 109 110 1 0 0 0 113 0 1 0 0 114 0 0 0 1 104 105 111 112
0 0 1 0 或为： 起 到 达 飞 109 110 0 1 0 0 113 1 0 0 0 114 0 0 0 1 104 105 111 112 或为: 起 0 0 1 0 到 达 飞 109 110 1 0 0 0 113 0 1 0 0 114 0 0 1 0 104 105 111 112 或为： 起 0 0 0 1 到 达 飞 109 110 0 1 0 0 113 1 0 0 0 114 0 0 1 0 104 105 111 112 0 0 0 1
第 9 章 目标规划
1.某工厂试对产品 A、B 进行生产。市场需求并不是很稳定，因此对每种产
品分别预测了在销售良好和销售较差时的预期利润。这两种产品都经过甲、乙两 台设备加工。已知产品 A 和 B 分别在甲和乙设备上的单位加工时间，甲、乙设备 的可用加工时间以及预期利润如下表所示，要求首先是保证在销售较差时，预期 利润不少于 5 千元，其次是要求销售良好时，预期利润尽量达到 1 万元。试建立
多目标规划模型并求解。 设备 单位加工时间 产品 A B 可用时间 4 3 甲 乙 2 5 销 售 良 好 时 的 预 期 8 6 利 润 5 5 (百元／件) 销 售 较 差 时 的 预 期 利 润
45 30 100 50 (百元／件)
1、解：设工厂生产 A 产品 x件，生产 B 产品 x件。按照生产要求，建立如下目
1
2
标规划模型：
?
min
( ) ( ) P d1 P d2 ? x x ≤ 45 4+ 3
? x x ≤ 30 ?2+ 5
?
? x x = 50 ?5+ 5? d++d
? x x ? d+ d ?=100
1
2
1
2
1
2
1
2
1
1+
+
?
?8+ 62
1
2
+
1
2
i
2
??x x d d, ,i,? ≥ 0, i = 1, 2
= 11.25, x = 0, d ?=0, d ?=10, d= 6.25, d= 0
2 1 2 1 2
由管理运筹学软件先求解得： x
+
+
1
由图解法或进一步计算可知，本题在求解结果未要求整数解的情况下，满意解有 无穷多个，为线段α (135 /14,15 / 7) (1 α )(45 / 4,0), α ∈[0,1] 上的任一点。
2、解：设食品厂商在电视上发布广告 x次，在报纸上发布广告 x次，在广播中
1
2
发布广告 x次。
3
目标规划模型为：
?
+
min ( )
11
+
( )?+( )
2
3
P d1 P d2 P d3 ?x≤
10 ? ≤ 20 ? xx 15
x + 5x
3
+ P d
( )
+
4 4
?
= 400
2
? ≤ ?
x ?20+10 ? x x
1
2
1
2
3
3
? d++d
1
1
x d
2
2
?=
0
?0.7? 0.3? 0.3?++d ?? x x x ?=0 0.3 ? 0.3 + 0.7
2 3 ? d++d ? x 1 + ? x x 20
? + d = 2.5+ 0.5+ 0.3? d4 ?
??x x x d d, , ,3 i,? ≥ 0, i = 1, 2,3, 4 用管理运筹学软件先求下述问题：
3
3
1
2
3
4+
1
2
i
min d ?
?x≤ 10 ? ≤ ?x 20
15 x
13
1
?
x + 5x
2
= 400
? ≤ ?
x ?20+10 ? x x
1
2
1
2
3
3
? d++d
1
1
x d
2
2
?=
0
?0.7? 0.3? 0.3?++d ?? x x x ?=0 0.3 ? 0.3 + 0.7
2 3 ? d++d ? x 1 + ? x x 20
? + d = 2.5+ 0.5+ 0.3? d4
3
3
1
2
3
4
?
??x x x d d1, , ,23 i,i? ≥ 0, i = 1, 2,3, 4
+
得： d?=0 ，将其作为约束条件求解下述问题：
1
min d ?
2
? ≤ x 10
20 ??x2
1
≤ ? ≤ ?x 15
x x + 5x
3
?
?=
1
1
400 0 = 0
3 ? d++d 20+10 ? x x x d ?0.7? 0.3? 0.3?++d ?? x x x
1
2
1
2
3
2
2
1
2
3
3
3
?=
?
? 0.3? 0.3+ 0.7? d++d 20 ? + ?
x x x + d = 2.5 + 0.5 + 0.3
2 3 ? d4
? 1 ?d ?= 0 ? 1
x x x d d, , ,, ? ≥ 0, i = 1, 2,3, 4
4
+
?
1 2 3 i i
得最优值 d?=0 ，将其作为约束条件计算下述问题：
2
、
1、解： x2 第 2 章 线性规划的图解法 6 A 1 O 0 B 1
C 3
6 x1
a.可行域为 OABC。
b.等值线为图中虚线所示。
c.由图可知，最优解为 B 点，最优解： x1
=
69 。 7 2、解： a x 2 1 0.6 0.1 O
0.1
0.6
x1
x1
= 0.2
有唯一解 x2
= 0.6 函数值为 3.6
b 无可行解 c 无界解
12
15
x2= ，7 7 最优目标函数值：
d 无可行解
e 无穷多解
1
20 = x 92 f 有唯一解 3 函数值为
3 8 x =
3
2
3、解：
a 标准形式：
max f = 3x1
+ 2x2
+ 0s1
+ 0s2
+ 0s3
x + + =
30 91 2x s
x + 2 2 1
31
2 x+ s =
13
2
2 x +
s 9
+ = 21
x x2
3
s s ≥ 0
b 标准形式：
1
, x2
, s1,
,
2
3
max f = ? x x s s
41
? 63
? 01
? 02
3 x? x ? s = 6 1
2 1 x + + = 1
2x s 10
2
2
7 x1
? 6x2
= 4
x1
, x2
, c 标准形式：
s, s ≥ 0
1
2
= ? +x'x'
' ? max f 2 ? 2 x s s
0 ? 02
1 2
2
1
? x + x ' ? '
+ = x s 3
5
5 70
1
2
2
1
2x'
? 5x'
+ 5x'
= 50 1 2
2
x'
+ x'
? ' ? = 30 31 22
2x s x, '
x2 2
2
',x2
',, s ≥ 0
1 s1
2
4 、解：
z = x + x + +
标准形式： max 10 5 s s
1 2 0 0
x+ 31
5
1
4 + s = 9 x1
2 + s = 8 x2
x, x, , s ≥ 0
s2
22
1
2
1
x +
1
2
s= 2, s= 0
1
2
5 、解：
f = x + x + + + min 11 8 s s s
1 2 标准形式： 0 0 0
x + 2 ? s = 20
x1
10
? =
x +
3 3x s 18
2 2
36 x +
2
11
1 2 3
4
1
? =
9x
2
2
1
s
3
x
1
2
3
1
s= 0, s= 0, s= 13 6 、解： b 1 ≤ c≤ 3
1
s s ≥ 0 , x, s, ,
2
3
c 2 ≤ c≤ 6
2
x= 6 x= 4 d
12
e
x∈ [ ]8 x = 16 ? 2x
1
2
f 变化。原斜率从 ? 变为 ? 1
3
7、解： 模型：
max z = 500x+ 400x
1
2
2 1
2x≤ 300
1
1
2
3x≤ 540
x x ≤ 440 2+ 2 x x ≤ 300 1.2+ 1.5 , ≥ 0 x x2
21
21
2
1
a x= 150 x= 70 即目标函数最优值是 103000 b 2，4 有剩余，分别是 330，15。均为松弛变量 c 50， 0 ，200， 0 额外利润 250
min z 20x+19x+ 20x+ 28x+17x+18x+ 24x+ 27x+ 20x +20x+26x +16x +15x +18x +15x +17x +20x +24x +19x +16x32 33 s.t.
x +x +x +x +x =1，
11
12
13
14
15
21
22
23
31
2425
34 35 41 42 43 44 45
11 21
12 22
13 23
14 24
15 25
x +x +x +x +x =1， +x +x +x +x =1 ， x
31 41 51 11 12 13 14 15
32 42 52 21 22 23 24 25
33 43 53 31 32 33 34 35
34 44 54 41 42 43 44 45
35 45 55 51 52 53 54 55
x +x +x +x +x =1，
x +x +x +x +x =1， x +x +x +x +x =1，
x +x +x +x +x =1， x +x +x +x +x =1， x +x +x +x +x =1， x +x +x +x x
ij
+x =1，
0-1 i=1 2 3 4 5 j=1 2 3 4 5 为 变量，
目标函数最优解为:
x *=0,x *=1,x *=0,x *=0,x *=0,x *=1,x *=0,x *=0,x *=0,x *=0,x *=0,
11 32
12 33
13 34
14 35
15 41
21 42
22 43
23 44
24 45
25
31
x *=0,x *=1,x *=0,x *=0,x *=0,x *=0,x *=0,x *=0,x *=1,z*=68
即安排甲做 B 项工作，乙做 A 项工作，丙做 C 项工作，丁做 E 项工作，最 少时间为 68 分钟。
d.该问题为人多任务少的问题，其目标函数的数学模型为：
min z 20x+19x+ 20x+ 28x+18x+ 24x+ 27x+ 20x +26x +16x31 +15x +18x +17x +20x +24x +19x +16x +17x +20x +21x
11
12
13
14
21
22
23
24
32
3334
41 42 43 44 51 52
53 54
s.t.
≤ ，
x +x 1 +x +x12 13 14
x +x +x +x ≤ 1，
11
21 31 41 51 11 12 13 14
22 32 42 52 21 22 23 24
23 33 43 53 31 32 33 34
24
x +x +x +x
34 44
≤ 1， ≤ 1，
54 41 42 43 44
51 52 53 54
x +x +x +x ≤ 1，
x +x +x +x
x +x +x +x +x =1，
x +x +x +x +x =1， x +x +x +x +x =1， x +x +x +x +x =1， x
0-1 i=1 2 3 4 j=1 2 3 4 5 i为 变量， j
目标函数最优解为:
x *=0,x *=0,x *=0,x *=0,x *=0,x *=0,x *=0,x *=1,x *=0,x *=0,x *=1,
11
12 41
13 42
14 43
21 44
22 51
23 52
24 53
31 54
32
33
x *=0,x *=1,x *=0,x *=0,x *=0,x *=0,x *=1,x *=0,x *=0,z*=69
34
或
x *=0,x *=0,x *=0,x *=0,x *=1,x *=0,x *=0,x *=0,x *=0,x *=0,x *=1,
11 34
12 41
13 42
14 43
21 44
22 51
23 52
24 53
31 54
32
33
x *=0,x *=0,x *=0,x *=0,x *=1,x *=0,x *=1,x *=0,x *=0,z*=69
或
x *=0,x *=1,x *=0,x *=0,x *=0,x *=0,x *=0,x *=0,x *=0,x *=0,x *=1,
11 34
12 41
13 42
14 43
21 44
22 51
23 52
24 53
31 54
32
33
x *=0,x *=0,x *=0,x *=0,x *=1,x *=1,x *=0,x *=0,x *=0,z*=69
即安排乙做 D 项工作，丙做 C 项工作，丁做 A 项工作，戊做 B 项工作；或
安排乙做 A 项工作，丙做 C 项工作，丁做 D 项工作，戊做 B 项工作；或安排甲
做 B 项工作，丙做 C 项工作，丁做 D 项工作，戊做 A 项工作，最少时间为 69 分钟。
7.解：设飞机停留一小时的损失为 a 元，则停留两小时损失为 4a 元，停留 3
小时损失为 9 元，依次类推，对 A、B、C 三个城市建立的指派问题的效率矩阵 分别如下表所示：
城市 A 起 到 达 飞 101 4a 361a 225a 484a 196a 102 9a 400a 256a 529a 225a 103 64a 625a 441a 16a 400a 104 169a 36a 4a 81a 625a 105 225a 64a 16a 121a 9a 106 107 108 109 110
解得最优解为： 起 到 达 飞 106 107 108 109 110 起 到 飞 101 0 0 0 0 1 102 1 0 0 0 0
103 0 0 0 1 0 104 0 1 0 0 0 105 0 0 1 0 0 城市 B 达 106 256a 225a 100a 64a 256a 107 529a 484a 289a 225a 529a 108 9a 4a 441a 361a 9a 111 625a 576a 361a 289a 625a 112 36a 25a 576a 484a 36a 101 102 103 113 114
解得最优解为： 起 到 达 飞 101 102 0 0 1 0 0
103 1 0 0 0 0 104 0 0 0 1 0 105 0 0 0 0 1 106 107 108 109 110
0 1 0 0 0 或为： 起 到 达 飞 101 102 0 0 1 0 0
103 0 0 0 0 1 104 0 0 0 1 0 105 1 0 0 0 0 106 107 108 109 110 0 1 0 0 0 城市 C 起 到 达 飞 109 49a 25a 169a 64a 110 225a 169a 441a 256a 113 225a 169a 441a 256a 114 49a 25a 169a 64a 104 105 111 112
c.该目标函数的数学模型为：
min z=100y +300y +200y +7x +2x +5x1
2 3 1 2 3
s.t.
x +x +x =2000，
1 2 3
0.5x +1.8x +1.0x
≤ 2800，
1
2
3
x ≤ 800，
1
x ≤ 1200，
2
x ≤ 1400，
3
x ≤ y M，
1 1 x ≤ y M， 2 2 x ≤ y M ，
3
3
x1
， ，x2
x3
≥ 0，且为整数， ， ， 为y1
y2
y3
0-1变量。 目标函数最优解x *=0,x *=1000,x *=1000,y =0,y =1,y =1,z*=7500
23 1 2 为 :1
d.该目标函数的数学模型为：
min z=100y +300y +200y +7x +2x +5x1
2 3 1 2 3
s.t.
x +x +x =2000，
1 2 3
x ≤ 800， 1
x ≤ 1200，
2
x ≤ 1400，
3
x ≤ y M，
1 1 x ≤ y M，
2
2
x ≤ y M ，
3 3
，且为整数， ， ， 为 变量。
x ， ，x x ≥ 0 y y y0-1
1
2
3
1
23
目标函数最优解x *=0,x *=1200,x *=800,y =0,y =1,y =1,z*=6900
23 1 2 为 :1
5．解：设 xij 为从 Di 地运往 Ri 地的运输量，i=1，2，3，4，j=1，2，3 分别代表从北京、上海、广州、武汉运往华北、华中、华南的货物件数，并规定，
?1 i
yi
= ? ，当 地被选设库房，
0 i
3
3
? ，当 地没被选设库房。 该目标函数的数学模型为：
min z 45000y+ 50000y+ 70000y+ 40000y+ 200x+ 400x+ 500x
1
2
3
4
11
12
13
+300x21+ 250x +400x +600x +350x +300x +350x +150x +350x2223
31 32 33 41 42 43
s.t.
x +x +x +x =500，
11 12 13 11
21 22 23 12
31 32 33 13
2122 3132
41 42 43
1 23 33
x +x +x +x =800， x +x +x +x =700， x +x +x ≤ 1000y ， x +x +x x +x +x y
2 1 3
2 4 4
≤ 1000y，
2
≤ 1000y，
3
4
x +x +x4142 43 ≤ 1000y，
≤ y ，
≤ 2，
3
4
y +y +y +y y +y ≤ 1，
，且为整数， 为 分量，i=1 2 3 4
x ≥ 0 y 0-1
ij
i
目标函数最优解为
x *=500,x *=0,x *=500,x *=0,x *=0,x *=0,x *=0,x *=0,x *=0,
11 41
42 12
13 43
21 1
2 22
3
23 4
31
32
33
x *=0,x *=800,x *=200,y =1,y =0,y =0,y =1,z*=625000
:
也就是说在北京和武汉建库房，北京向华北和华南各发货 500 件，武汉向华 中发货 800 件，向华南发货 200 件就能满足要求，即这就是最优解。
，当指派第 人去完成第 项工作时，
i i j j
6．解：引入 0-1 变量 xij，并令 x= ??1
0
? ，当不指派第 人去完成第 项工作时。
a.为使总消耗时间最少的目标函数的数学模型为：
ij
min z 20x+19x+ 20x+ 28x+18x+ 24x+ 27x+ 20x +26x
11
12
13
14
21
22
23
2431
+16x +15x +18x +17x +20x +24x +19xs.t.
x +x +x +x =1，
11 21 31
12 22 32
13 23 33
14 24 34
3233 34 41 42 43 44
x +x +x +x =1， x +x +x +x =1， x +x +x =1， +x
41 11
42 21
43 31
44 41
x +x +x +x =1，
x +x +x +x =1，
12 13 14
22 23 24
32 33 34
42 43 44
x +x +x +x =1， x +x +x +x =1，
，，，。 为 变量，
x 0-1 i=1 2 3 4 j=1 2 3 4
ij
目标函数最优解为 :
x *=0,x *=1,x *=0,x *=0,x *=1,x *=0,x *=0,x *=0,x *=0,x *=0,x *=1,
11 34
12 41
13 42
14 43
21 44
22
23
24
31
32
33
x *=0,x *=0,x *=0,x *=0,x *=1,z*=71
或
x *=0,x *=1,x *=0,x *=0,x *=0,x *=0,x *=0,x *=1,x *=0,x *=0,x *=1,
11 34
12 41
13 42
14 43
21 44
22
23
24
31
32
33
x *=0,x *=1,x *=0,x *=0,x *=0,z*=71
即安排甲做 B 项工作，乙做 A 项工作，丙 C 项工作，丁 D 项工作，或者是
安排甲做 B 项工作，乙做 D 项工作，丙 C 项工作，丁 A 项工作，最少时间为 71
分钟。
b.为使总收益最大的目标函数的数学模型为： 将 a 中的目标函数改为求最大值即可。 目标函数最优解为 :
x *=0,x *=0,x *=0,x *=1,x *=0,x *=1,x *=0,x *=0,x *=1,x *=0,x *=0,
11 34
12 41
13 42
14 43
21 44
22
23
24
31
32
33
x *=0,x *=0,x *=0,x *=1,x *=0,z*=102
即安排甲做 D 项工作，乙做 C 项工作，丙 A 项工作，丁 B 项工作，最大收 益为 102。
c.由于工作多人少，我们假设有一个工人戊，他做各项工作的所需的时间均 为 0，该问题就变为安排 5 个人去做 5 项不同的工作的问题了，其目标函数的数
学模型为：