、
1、解:
C 3
6 x1
a.可行域为 OABC。
b.等值线为图中虚线所示。
c.由图可知,最优解为 B 点,最优解: x1
=
O
0.1
0.6
x1
x1
= 0.2
有唯一解 x2
= 0.6 函数值为 3.6
b 无可行解 c 无界解
d 无可行解
e 无穷多解
12
15
x2
=
,最优目标函数值:
20 x 92
f 有唯一解 3 函数值为3 8
x 3
12
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 9
x +
+ s = 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 + 4 + x+ 1 s =
2
2 31
2
xs
=
x +
2
1
5
1
2
9 8
x, x, , s ≥ 0
s2
1
2
1
1
2
s= 2, s= 0
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
s= 0, s= 0, s= 13 6 、解: b 1 ≤ c≤ 3
1
≥ 0 s s 1
, x, s, ,
2
3
c 2 ≤ c≤ 6
2
x= 6 x= 4 d
12
e
x∈ [ ]8 x = 16 − 2x
1
2
f 变化。原斜率从 −
3
7、解: 模型:
max z = 500x+ 400x
1
2
2 1
变为 − 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 d 在 [0,500]变化,最优解不变。 e 在 400 到正无穷变化,最优解不变。
f 不变
8 、解:
a
b
a 模型: min f = 8x+ 3x
50x+ 100x≤ 1200000
a
b
5x+ 4x≥ 60000
a
b
100x≥ 300000 , x ≥ 0 xb
基金 a,b 分别为 4000,10000。 回报率:60000
ba
b 模型变为: max z = 5x+ 4x
a
b
50x+ 100x≤ 1200000 100x≥ 300000 , x ≥ 0 xb
a
b
ba
1
2
推导出: x= 18000 x= 3000
故基金 a 投资 90 万,基金 b 投资 30 万。
第 3 章 线性规划问题的计算机求解
1、解:
a x= 150 x= 70
1
2
目标函数最优值 103000
b 1,3 使用完 2,4 没用完 0,330,0,15 c 50,0,200,0
含义: 1 车间每增加 1 工时,总利润增加 50 元
3 车间每增加 1 工时,总利润增加 200 元 2、4 车间每增加 1 工时,总利润不增加。 d 3 车间,因为增加的利润最大
e 在 400 到正无穷的范围内变化,最优产品的组合不变 f 不变 因为在 [0,500]的范围内
g 所谓的上限和下限值指当约束条件的右边值在给定范围内变化时,约束条
件 1 的右边值在 [200,440]变化,对偶价格仍为 50(同理解释其他约束条件) h 100×50=5000 对偶价格不变 i 能
j 不发生变化 允许增加的百分比与允许减少的百分比之和没有超出 100% k 发生变化 2、解:
a 4000 10000 62000
b 约束条件 1:总投资额增加 1 个单位,风险系数则降低 0.057
约束条件 2:年回报额增加 1 个单位,风险系数升高 2.167 c 约束条件 1 的松弛变量是 0,约束条件 2 的剩余变量是 0
约束条件 3 为大于等于,故其剩余变量为 700000 d 当 c不变时, c在 3.75 到正无穷的范围内变化,最优解不变
2
1
当 c不变时, c在负无穷到 6.4 的范围内变化,最优解不变
1
2
e 约束条件 1 的右边值在 [780000,1500000]变化,对偶价格仍为 0.057(其他 同理)
f 不能 ,理由见百分之一百法则二 3 、解:
a 18000 3000 102000 153000 b 总投资额的松弛变量为 0 基金 b 的投资额的剩余变量为 0 c 总投资额每增加 1 个单位,回报额增加 0.1
基金 b 的投资额每增加 1 个单位,回报额下降 0.06 d c不变时, c在负无穷到 10 的范围内变化,其最优解不变
1
2
c不变时, c在 2 到正无穷的范围内变化,其最优解不变
2
1
e 约束条件 1 的右边值在 300000 到正无穷的范围内变化,对偶价格仍为 0.1
约束条件 2 的右边值在 0 到 1200000 的范围内变化,对偶价格仍为-0.06 600000 300000 = 100% 故对偶价格不变
900000 900000 f
4、解:
a 8.5
x= x= 1.5
1
2
x= 0
3x= 1 最优目标函数 18.5
4
b 约束条件 2 和 3 对偶价格为 2 和 3.5
c 选择约束条件 3,最优目标函数值 22
d 在负无穷到 5.5 的范围内变化,其最优解不变,但此时最优目标函数值变化 e 在 0 到正无穷的范围内变化,其最优解不变,但此时最优目标函数值变化 5、解:
a 约束条件 2 的右边值增加 1 个单位,目标函数值将增加 3.622 b
x产品的利润提高到 0.703,才有可能大于零或生产
2
c 根据百分之一百法则判定,最优解不变
15 65
d + > 100 % 根据百分之一百法则二,我们不能判定
− 30 − 9.189
因为
111.25 15
其对偶价格是否有变化
第 4 章 线性规划在工商管理中的应用
1、解:为了用最少的原材料得到 10 台锅炉,需要混合使用 14 种下料方 428
639
850
547
969
1180
剩余
758
设按 14 种方案下料的原材料的根数分别为 x1,x2,x3,x4,x5,x6,x7,x8,x9, x10,x11,x12,x13,x14,则可列出下面的数学模型: min f=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14 s.t. 2x1+x2+x3+x4 ≥ 80
x2+3x5+2x6+2x7+x8+x9+x10≥ 350 x3+x6+2x8+x9+3x11+x12+x13≥ 420
x4+x7+x9+2x10+x12+2x13+3x14 ≥ 10
x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14≥ 0 用管理运筹学软件我们可以求得此问题的解为:
x1=40,x2=0,x3=0,x4=0,x5=116.667,x6=0,x7=0,x8=0, x9=0,x10=0,x11=140,x12=0,x13=0,x14=3.333 最优值为 300。
2、解:从上午 11 时到下午 10 时分成 11 个班次,设 xi 表示第 i 班次安排的临时 工的人数,则可列出下面的数学模型:
min f=16(x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11) s.t. x1+1 ≥ 9
x1+x2+1 ≥ 9 x1+x2+x3+2 ≥ 9 x1+x2+x3+x4+2 ≥ 3
x2+x3+x4+x5+1 ≥ 3
x3+x4+x5+x6+2 x4+x5+x6+x7+1 x6+x7+x8+x9+2
≥ 3 ≥ 6 ≥ 12
x5+x6+x7+x8+2 ≥ 12
x7+x8+x9+x10+1 ≥ 7 x8+x9+x10+x11+1 ≥ 7
x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11≥ 0 用管理运筹学软件我们可以求得此问题的解为:
x1=8,x2=0,x3=1,x4=1,x5=0,x6=4,x7=0,x8=6,x9=0, x10=0,x11=0 最优值为 320。
a、 在满足对职工需求的条件下,在 10 时安排 8 个临时工,12 时新安排 1
个临时工,13 时新安排 1 个临时工,15 时新安排 4 个临时工,17 时新
安排 6 个临时工可使临时工的总成本最小。
b、 这时付给临时工的工资总额为 80 元,一共需要安排 20 个临时工的班
次。
约束 对偶价格 松弛/剩余变量
------- ------------------ -------------
1 0 -4
2 0 0
3 2 0
4 9 0
5 0 -4
6 5 0
7 0 0
8 0 0
9 0 -4
10 0 0
11 0 0
根据剩余变量的数字分析可知,可以让 11 时安排的 8 个人工作 3 小时,13 时安排的 1 个人工作 3 小时,可使得总成本更小。
C、设在 11:00-12:00 这段时间内有 x个班是 4 小时, y个班是 3 小时;
1
1
设在 12:00-13:00 这段时间内有 x个班是 4 小时, y个班是 3 小时;其他时
2
2
段也类似。
则:由题意可得如下式子:
11
11
=
∑ x + ∑ y
i=1 1
1
min z 1612
i=1
S.T + y + ≥
1 9 x1
+ + + y + ≥ xyx2
1 9
+ + + + + y + ≥
1 +1 9
xyxyx3
≥ + + + + + + y +
1+1 3
xxyxyx4
+ + + + + + y + ≥
1 3
xxyxyx5
≥ + + + + + + y +
1+ 1 3
xxyxyx6
+ + + + + + y + ≥
1 6
xxyxyx7
≥ + + + + + + y +
1+1 12
xxyxyx8
≥ + + + + + + y +
1+1 12
xxyxyx9
+ + + + + + y + ≥
1 7
xxyxyx10
+ + + + + + y + ≥
1 7
xxyxyx11
x≥ 0, y≥ 0 i=1,2,…,11
11
1
2
1
1
2
2
3
1
2
2
3
3
4
2
3
3
4
4
5
3
4
4
5
5
6
4
5
5
6
6
7
5
6
6
7
7
8
6
7
7
8
8
9
7
8
8
9
9
10
8
9
9
10
10
11
i
i
稍微变形后,用管理运筹学软件求解可得:总成本最小为 264 元。
安排如下:y1=8( 即在此时间段安排 8 个 3 小时的班),y3=1,y5=1,y7=4,x8=6 这样能比第一问节省:320-264=56 元。
3、解:设生产 A、B、C 三种产品的数量分别为 x1,x2,x3,则可列出下面的
数学模型:
max z=10 x1+12 x2+14 x2 s.t. x1+1.5x2+4x3≤ 2000 2x1+1.2x2+x3 ≤ 1000
x1≤ 200 x2≤ 250 x3 ≤ 100 x1,x2,x3≥ 0
用管理运筹学软件我们可以求得此问题的解为:
x1=200,x2=250,x3=100 最优值为 6400。
a、在资源数量及市场容量允许的条件下,生产 A 200 件,B 250 件,C 100
件,可使生产获利最多。
b、A、B、C 的市场容量的对偶价格分别为 10 元,12 元,14 元。材料、台
时的对偶价格均为 0。说明 A 的市场容量增加一件就可使总利润增加 10
元,B 的市场容量增加一件就可使总利润增加 12 元,C 的市场容量增加 一件就可使总利润增加 14 元。但增加一千克的材料或增加一个台时数都
不能使总利润增加。如果要开拓市场应当首先开拓 C 产品的市场,如果
要增加资源,则应在 975 到正无穷上增加材料数量,在 800 到正无穷上
增加机器台时数。
4、解:设白天调查的有孩子的家庭的户数为 x11,白天调查的无孩子的家庭的户
数为 x12,晚上调查的有孩子的家庭的户数为 x21,晚上调查的无孩子的家庭 的户数为 x22,则可建立下面的数学模型: min f=25x11+20x12+30x21+24x22 s.t. x11+x12+x21+x22≥ 2000
x11+x12 = x21+x22 x11+x21≥ 700
x12+x22≥ 450
x11, x12, x21, x22 ≥ 0
用管理运筹学软件我们可以求得此问题的解为:
x11=700,x12=300,x21=0,x22=1000 最优值为 47500。
a、白天调查的有孩子的家庭的户数为 700 户,白天调查的无孩子的家庭的户
数为 300 户,晚上调查的有孩子的家庭的户数为 0,晚上调查的无孩子的
家庭的户数为 1000 户,可使总调查费用最小。
b、白天调查的有孩子的家庭的费用在 20-26 元之间,总调查费用不会变化;
白天调查的无孩子的家庭的费用在 19-25 元之间,总调查费用不会变化; 晚上调查的有孩子的家庭的费用在 29-无穷之间,总调查费用不会变化;
晚上调查的无孩子的家庭的费用在-20-25 元之间,总调查费用不会变 化。
c、调查的总户数在 1400-无穷之间,总调查费用不会变化;
有孩子家庭的最少调查数在 0-1000 之间,总调查费用不会变化; 无孩子家庭的最少调查数在负无穷-1300 之间,总调查费用不会变化。
5、解:设第 i 个月签订的合同打算租用 j 个月的面积为 xij,则需要建立下面的 数学模型:
min f=2800(x11+x21+x31+x41)+4500(x12+x22+x32)+6000(x13+x23)
+7300 x14
s.t.x11+x12+x13+x14≥ 15
x12+x13+x14+x21+x22+x23 ≥ 10 x13+x14+x22+x23+x31+x32≥ 20 x14+x23+x32+x41≥ 12 xij ≥ 0,i,j=1,2,3,4
用管理运筹学软件我们可以求得此问题的解为:
x11=5,x12=0,x13=10,x14=0,x21=0,x22=0,x23=0,x31=10, x32=0,x41=0
最优值为 102000。
即:在一月份租用 500 平方米一个月,租用 1000 平方米三个月;在三月 份租用 1000 平方米一个月,可使所付的租借费最小。
6、解:设 xij表示第 i 种类型的鸡需要第 j 种饲料的量,可建立下面的数学模型:
max z=9(x11+x12+x13)+7(x21+x22+x23)+8(x31+x32+x33)-5.5
(x11+x21+x31)-4(x12+x22+x32)-5(x13+x23+x33)
s.t. x11≥ 0.5(x11+x12+x13)
x12≤ 0.2(x11+x12+x13) x21≥0.3(x21+x22+x23) x23 ≤ 0.3(x21+x22+x23)
x33≥ 0.5(x31+x32+x33)
x11+x21+x31 ≤ 30 x12+x22+x32≤ 30 x13+x23+x33≤30
xij ≥ 0,i,j=1,2,3
用管理运筹学软件我们可以求得此问题的解为:
x11=30,x12=10,x13=10,x21=0,x22=0,x23=0,x31=0, x32=20,x33=20 最优值为 365。
即:生产雏鸡饲料 50 吨,不生产蛋鸡饲料,生产肉鸡饲料 40 吨。
7、
设 Xi——第 i 个月生产的产品 I 数量
Yi——第 i 个月生产的产品 II 数量
Zi,Wi 分别为第 i 个月末产品 I、II 库存数
S1i,S2i分别为用于第(i+1)个月库存的自有及租借的仓库容积(立方米)。则
可建立如下模型:
5
12
12
+ y + s x + y
+ ∑ z = ∑ + ∑ s
min (5x8 ) (4.5 7 ) ( 1.5 )
i
i=1
i
i=6
i i
i=1
1i 2i
s.t.
X1-10000=Z1 X2+Z1-10000=Z2
X3+Z2-10000=Z3 X4+Z3-10000=Z4 X5+Z4-30000=Z5 X6+Z5-30000=Z6 X7+Z6-30000=Z7 X8+Z7-30000=Z8 X9+Z8-30000=Z9
X10+Z9-100000=Z10 X11+Z10-100000=Z11
X12+Z11-100000=Z12
Y1-50000=W1 Y2+W1-50000=W2 Y3+W2-15000=W3 Y4+W3-15000=W4 Y5+W4-15000=W5 Y6+W5-15000=W6 Y7+W6-15000=W7 Y8+W7-15000=W8
Y9+W8-15000=W9 Y10+W9-50000=W10 Y11+W10-50000=W11
Y12+W11-50000=W12
S1i≤15000 1≤i≤12 Xi+Yi≤120000 1≤i≤12
0.2Zi+0.4Wi=S1i+S2i 1≤i≤12 Xi≥0, Yi≥0, Zi≥0, Wi≥0, S1i≥0, S2i≥0
用管理运筹学软件我们可以求得此问题的解为: 最优值= 4910500
X1=10000, X2=10000, X3=10000, X4=10000, X5=30000, X6=30000, X7=30000, X8=45000, X9=105000, X10=70000, X11=70000, X12=70000; Y1= 50000, Y2=50000, Y3=15000, Y4=15000, Y5=15000,
Y6=15000, Y7=15000, Y8=15000, Y9=15000, Y10=50000, Y11=50000, Y12=50000; Z8=15000, Z9=90000, Z10 =60000, Z1=30000; S18=3000, S19=15000, S110=12000, S111=6000; S28=3000;
其余变量都等于 0
8、解:设第 i 个车间生产第 j 种型号产品的数量为 xij,可建立下面的数学模型: max z=25(x11+x21+x31+x41+x51)+20(x12+x32+x42+x52)+17(x13
+x23+x43+x53)+11(x14+x24+x44)
s.t. x11+x21+x31+x41+x51 ≤ 1400
x12+x32+x42+x52≥ 300 x12+x32+x42+x52 ≤ 800 x13+x23+x43+x53≤ 8000 x14+x24+x44≥ 700
5x11+7x12+6x13+5x14 ≤ 18000
6x21+3x23+3x24≤ 15000 4x31+3x32 ≤ 14000
3x41+2x42+4x43+2x44≤ 12000 2x51+4x52+5x53≤ 10000
xij ≥ 0,i=1,2,3,4,5 j=1,2,3,4
用管理运筹学软件我们可以求得此问题的解为:
x11=0,x12=0,x13=1000,x14=2400,x21=0,x23=5000,x24=0, x31=1400,x32=800,x41=0,x42=0,x43=0,x44=6000,x51=0,
x52=0,x53=2000 最优值为 279400
9、解:设第一个月正常生产 x1,加班生产 x2,库存 x3;第二个月正常生产 x4,
加班生产 x5,库存 x6;第三个月正常生产 x7,加班生产 x8,库存 x9;第 四个月正常生产 x10,加班生产 x11,可建立下面的数学模型:
min f = 200(x1+x4+x7+x10)+300(x2+x5+x8+x11)+60(x3+x6
+x9)
s.t.
x1≤4000 x4≤4000 x7≤4000 x10≤4000 x3≤1000 x6≤1000 x9≤1000 x2≤1000 x5≤1000 x8≤1000 x11≤1000
x1+ x2- x3=4500 x3+ x4+ x5- x6=3000 x6+ x7+ x8- x9=5500 x9+ x10+ x11=4500
x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11≥0
计算结果是:
minf= 3710000 元
x1=4000 吨,x2=500 吨,x3=0 吨,x4=4000 吨, x5=0 吨 x6=1000 吨, x7=4000 吨, x8=500 吨, x9=0 吨, x10=4000 吨,x11=500 吨。
,
第 5 章
单纯形法
1、解:表中 a、c、e、f 是可行解,a、b、f 是基本解,a、f 是基本可行解。
2、解:a、该线性规划的标准型为: max 5 x1+9 x2
s.t.0.5 x1+x2+s1=8
x1+x2-s2=10
0.25 x1+0.5 x2-s3=6
x1,x2,s1,s2,s3≥0.
b、有两个变量的值取零,因为有三个基变量、两个非基变量,非基变量
取零。
c、(4,6,0,0,-2) d、(0,10,-2,0,-1)
e、不是。因为基本可行解要求基变量的值全部非负。
3 0 0 0 0 0 0
6 30* 25 0 0 0
b、线性规划模型为:
max 6 x1+30 x2+25 x3 s.t.3 x1+x2+s1 = 40
2 x1+x3+s2= 50 2 x1+x2-x3+s3=20
x1,x2,x3,s1,s2,s3≥0
c、初始解的基为(s1,s2,s3),初始解为(0,0,0,40,50,20),
对应的目标函数值为 0。
d、第一次迭代时,入基变量是 x2,出基变量为 s3。
4、解:最优解为(2.25,0),最优值为 9。
X2
1
5、解:a、最优解为(2,5,4),最优值为 84。
b、最优解为(0,0,4),最优值为-4。
6、解:a、有无界解
b、最优解为(0.714,2.143,0),最优值为-2.144。
7、解:a、无可行解
b、最优解为(4,4),最优值为 28。 c、有无界解
d、最优解为(4,0,0),最优值为 8。
第 6 章 单纯形法的灵敏度分析与对偶
1
a. c1≤24 b. c2≥6 c. cs2≤8
2
a. c1≥-0.5 b. -2≤c3≤0 c. cs2≤0.5
3
a. b1≥150
b. 0≤b2≤83.333 c. 0≤b3≤150
4
a. b1≥-4 b. 0≤b2≤300 c. b3≥4
5 a. b. c. d. e.
利润变动范围 c1≤3,故当 c1=2 时最优解不变 根据材料的对偶价格为 1 判断,此做法不利 0≤b2≤45
最优解不变,故不需要修改生产计划
此时生产计划不需要修改,因为新的产品计算的检验数为-12 小于零,对原生 产计划没有影响。
6
均为唯一最优解,根据从计算机输出的结果看出,如果松弛或剩余变量为零且对 应的对偶价格也为零,或者存在取值为零的决策变量并且其相差值也为零时,可
知此线性规划有无穷多组解。 7
a. min f= 10y1+20y2.
s.t. y1+y2≥2,
y1+5y2≥1, y1+y2≥1, y1, y2≥0.
b. max z= 100 y1+200 y2. s.t. 1/2 y1+4 y2≤4,
2 y1+6 y2≤4,
2 y1+3 y2≤2,
y1, y2≥0.
8.
a. min f= -10 y1+50 y2+20 y3-20 y4. s.t. -2 y1+3 y2+ y3- y2≥1,
≥2, 3 y1+ y2
- y1+ y2+ y3- y2 =5, y1, y2, y2≥0, y3 没有非负限制。
b. max z= 6 y1-3 y2+2 y3-2 y4.
s.t. y1- y2- y3+ y4≤1, 2 y1+ y2+ y3- y4=3, -3 y1+2 y2- y3+ y4≤2, y1, y2, y4≥0, y3没有非负限制
9. 对偶单纯形为 max z=4 y1-8 y2+2 y3 s.t y1- y2≤1,
- y1- y2+ y3≤2, y1-2 y2- y3≤3, y1, y2, y3≥0
目标函数最优值为: 10 最优解: x1=6, x2=2, x3=0
第 7 章 运输问题
1.
最优解如下
********************************************
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- ----- 1 0 250 0 50 2 400 0 0 0 3 0 0 350 150 此运输问题的成本或收益为: 19800
此问题的另外的解如下:
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- 1 0 250 50 0 2 400 0 0 0 3 0 0 300 200 此运输问题的成本或收益为: 19800
(2)如果 2 分厂产量提高到 600,则为产销不平衡问题
最优解如下
********************************************
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- 1 0 250 0 0 2 400 0 0 200 3 0 0 350 0
----- -----
此运输问题的成本或收益为: 19050
注释:总供应量多出总需求量 200
第 1 个产地剩余 50 第 3 个产地剩余 150
(3)销地甲的需求提高后,也变为产销不平衡问题
最优解如下
********************************************
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- ----- 1 50 250 0 0 2 400 0 0 0 3 0 0 350 150 此运输问题的成本或收益为: 19600
注释:总需求量多出总供应量 150
第 1 个销地未被满足,缺少 100 第 4 个销地未被满足,缺少 50
最优解如下
********************************************
起
至 销点
发点 1 2 3 4 5 6 8
-------- ----- ----- ----- ----- ----- ----- ----- ----- 1 0 0 100 0 0 200 0 0 2 0 0 0 0 350 0 0 150
3 0 50 0 100 0 0 0
4 0 100 0 0 0 0 0 0 5 150 0 50 0 0 0 0 0 此运输问题的成本或收益为: 1.050013E+07
7 250
最优解如下
********************************************
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- -----
1 2 0 0
2 1 1 0
3 0 0 3
4 0 4 0
5 0 0 2
6 0 0 0
7 0 0 0
此运输问题的成本或收益为: 8465
此问题的另外的解如下:
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- -----
1 2 0 0
2 1 2 0
3 0 0 3
4 0 3 0 1 0 0 0 2 3 0 0 0 1
5 0 0 0 2
6 0 0 2 0
7 0 0 3 0
此运输问题的成本或收益为: 8465
最优解如下
********************************************
起
至 销点
发点 1 2 3 4 5 6 -------- ----- ----- ----- ----- ----- ----- 1 1100 0 300 200 0 0 2 0 1100 0 0 600 0 3 0 0 1100 0 0 0 4 0 0 0 1100 0 0 5 0 0 0 0 1000 100 6 0 0 0 0 0 1100 此运输问题的成本或收益为: 130000
5.
建立的运输模型如下
min f = 500x1+300 x2+550 x3+650 x4. s.t. 54 x1+49 x2+52 x3+64 x4≤1100, 57 x1+73 x2+69 x3+65 x4≤1000,
最优解如下
********************************************
起 至 销点
发点 1 2 3 4 5
-------- ----- ----- ----- ----- ----- 1 250 300 550 0 0 2 250 0 0 650 100
此运输问题的成本或收益为: 113300 6.
销量 20 10 0 10 0 20 5 0
b. 最优解如下
********************************************
起 至 销点
发点 1 2 3 -------- ----- ----- -----
1 0 0 15 2 20 5 0 3 0 5 5 此运输问题的成本或收益为: 145
c. 该运输问题只有一个最优解,因为其检验数均不为零
d. 最优解如下
********************************************
起 至 销点
发点 1 2 3 -------- ----- ----- -----
1 0 0 15 2 25 0 0 此运输问题的成本或收益为: 135
1.
第 8 章 整数规划
求解下列整数规划问题 max z=5x +8x2
1
a. s.t.
x +x
1 1 1
2 2
≤ 6, ≤ 45, ≥ 0,且为整数
2
5x +9x
2
x ,x
目标函数最优解为 :
1
x *=0,x *=5,z*=40。
b. max z=3x +2x
1
2
s.t.
2x +3x
1 1
2 2
≤ 14, ≤ 9,
为整数。
2
2x +x
x1,x2 0, x1且 目标函数最优解为 :
1
x *=3,x *=2.6667,z*=14.3334。
c. max z=7x +9x +3x
1
2
3
s.t.
-x +3x +x
1
2
3
≤ 7,
0-1变量。
7x +x +x ≤ 38,
1 2 3
且 为整数, 为x
x ,x ,x ≥ 0, x
1
2
3
1
3
目标函数最优解为 :
1
x *=5,x *=3,x *=0,z*=623
2。
2.解:设 xi为装到船上的第 i 种货物的件数,i=1,2,3,4,5。则该船装载的货 物取得最大价值目标函数的数学模型可写为:
max z=5x +10x +15x +18x +25x2 3 4 5 s.t.
20x +5x +10x +12x +25x ≤ 400000,
1
1 1 1
1 2 4
2
3
3 4
4 5
5
x +2x +3x +4x +5x ≤ 50000, x +4x
2
3
≤ 10000
≤ 750,
4
5
0.1x +0.2x +0.4x +0.1x +0.2x
x
i
≥ 0,且为整数,i=1 2 3 4 5
目标函数最优解为 :
1
x *=0,x *=0,x *=0,x *=2500,x *=2500,z*=107500 .3
2
4 5
3.解:设 xi为第 i 项工程,i=1,2,3,4,5,且 xi为 0-1 变量,并规定,
i ⎧
1, 当第 项工程被选定时, x= ⎨ i
⎩ ,当第 项工程没被选定时。
根据给定条件,使三年后总收入最大的目标函数的数学模型为:
i
max z 20x+ 40x+ 20x+15x+ 30x s.t.
5x +4x +3x +7x +8x
1
2
3
4
5
≤ 25, ≤ 25,
1 1 1
2 2
2
3 3
3
4 4 4
5 5
5
x +7x +9x +4x +6x
8x +10x +2x +x +10x ≤ 25, 为 变量,i=1 2 3 4 5 x 0-1
i
目标函数最优解为 :
1
x *=1,x *=1,x *=1,x *=1,x *=0,z*=953
2
4 5
4.解:这是一个混合整数规划问题
设 x1、x2、x3分别为利用 A、B、C 设备生产的产品的件数,生产准备费
只有在利用该设备时才投入,为了说明固定费用的性质,设
⎧1,当利用第 种设备生产时,即i x >0,
i
y = ⎨ i
0 i x =0。 ⎩ ,当不利用第 种设备生产时,即
故其目标函数为:
i
min z 100y +300y +200y +7x +2x +5x
3 12 1 2 3
为了避免没有投入生产准备费就使用该设备生产,必须加以下的约束条件, M 为充分大的数。
x ≤ y M,
1 2 3
1 2 3
x ≤ y M, x ≤ y M ,
设 M=1000000
a. 该目标函数的数学模型为:
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
≤ 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
x1
, ,x2
x3
≥ 0,且为整数, , , 为y1
y2
y3
0-1变量。 目标函数最优解x *=370,x *=231,x *=1399,y =1,y =1,y =1,z*=10647 为 : 1
3
b.该目标函数的数学模型为:
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 ≤ 2500, 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 *=625,x *=1375,y =0,y =1,y =1,z*=8625 1
3
23 1 2
23
1 2
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 为 :1
3
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 1
2
3
1
2y0-1
3
目标函数最优解x *=0,x *=1200,x *=800,y =0,y =1,y =1,z*=6900
23 1 为 :1
3
5.解:设 xij 为从 Di 地运往 Ri 地的运输量,i=1,2,3,4,j=1,2,3 分别代表从北京、上海、广州、武汉运往华北、华中、华南的货物件数,并规定,
⎧1 i
yi
= ⎨ ,当 地被选设库房,
0 i
该目标函数的数学模型为:⎩ ,当 地没被选设库房。
2
2
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
43
31 32 33 41 42
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
3
4
≤ 1000y,
2
≤ 1000y,
3
4
x +x +x4142 43 ≤ 1000y,
≤ y ,
y +y +y +y ≤ 2, 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
⎩ ,当不指派第 人去完成第 项工作时。
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 12
42 21 22
43 31 32
44 41 42
x +x +x +x =1,
x +x +x +x =1,
x +x +x +x =1,
13 14
23 24
33 34
43 44
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 项不同的工作的问题了,其目标函数的数
学模型为:
min z 20x+19x+ 20x+ 28x+17x+18x+ 24x+ 27x+ 20x +20x+26x +16x +15x +18x +15x +17x +20x +24x +19x +16x32 33
11
12
13
14
15
21
22
23
31
2425
34 35 41 42 43
44 45
s.t.
x +x +x +x +x =1,
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
11
x +x +x +x ≤ 1,
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
解得最优解为:
城市 B
解得最优解为:
或为:
城市 C
解得最优解为:
或为:
或为:
第 9 章 目标规划
1.某工厂试对产品 A、B 进行生产。市场需求并不是很稳定,因此对每种产
品分别预测了在销售良好和销售较差时的预期利润。这两种产品都经过甲、乙两 台设备加工。已知产品 A 和 B 分别在甲和乙设备上的单位加工时间,甲、乙设备 的可用加工时间以及预期利润如下表所示,要求首先是保证在销售较差时,预期 利润不少于 5 千元,其次是要求销售良好时,预期利润尽量达到 1 万元。试建立
多目标规划模型并求解。
(百元/件)
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
2
+
1
2
i
⎩⎪x x d d, ,i,−
2
由管理运筹学软件先求解得: x
1
≥ 0, i = 1,
= 11.25, x = 0, d −=0, d −=10, d= 6.25, d= 0
+
+
2 1 2 1 2
由图解法或进一步计算可知,本题在求解结果未要求整数解的情况下,满意解有 无穷多个,为线段α (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.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.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
得: 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
min d+
3
⎧x1≤ 10 ⎪ ≤ ⎪ 20 xx3 15 x + 5x −=400 2
⎪ ≤ ⎪
x
⎪20+10 3 − d1
++d1
1
2
⎪ x x x d −=0 0.7 − 0.3 − 0.3
⎨−⎪1 2 3 2
2
x
x x−+ +d −
= 0 ⎪ 0.31
− 0.32
+ 0.73
− d3
++d3 20
⎪ + −
x x x + d = 2.5 + 0.5 + 0.3
⎪ 1 2 3 − d4
4
⎪d −= 0
1
⎪⎪0
d2−
=
⎪x x x d d i
− ≥ 0, i = 1, 2,3, 4
⎩ , , ,i
+,
1 2 3
得最优值 d3
+=0 ,将其作为约束条件计算下述问题:
min d+
4
⎧ ≤ x1
10
⎪⎪20 x2
≤ ⎪ ≤ ⎪x 3
⎪
x 15
x + 5x
−=
400 201
+102
3 − d1
++d1
⎪ x x x d −=
0 ⎪0.71
− 0.32
− 0.33
−2
++d2
−
⎪−
= x x x 0
⎨ 0.31
− 0.32
+ 0.73
− d3
++d3
⎪ +
−
x
x x + d =
20
⎪2.5+ 0.5+ 0.3− d4 ⎪d −=0 ⎪ 1 0 ⎪d −=
1
2
3
4
2
⎪⎪d3
+
=
⎪x x x d d −
, , ,+
得: ⎩ 1 2 ,3
i
i
≥ 0, i = 1, 2,3, 4
x = 9.474, x = 20, x = 2.105, d= 0, d −=0, d= 8.387, d −=0, d= 0, d −=7.368,
+
+
+
1
+
2 3 1 1 2 2 3 3
d= 14.316, d −=0,
4
4
所以食品厂商为了依次达到 4 个活动目标,需在电视上发布广告 9.474 次,报纸
上发布广告 20 次,广播中发布广告 2.105 次。(管理运筹学 2.0 可一次求解上述
问题)
3、解:(a)设该化工厂生产 x升粘合剂 A 和 x升粘合剂 B。则根据工厂要求,
1
2
建立以下目标规划模型:
−
+
−
−
−
min
( + d ) + ( + d ) + ( ) P d1 2 2 3 4 3 5
1
−= +5
80 ⎪3 x 12 x− d++d
⎪ + x − d+ d −=
2 2 2
100 ⎪ x
12 ⎪3 100 x + =
1
2
1
1+
1
+d−
⎨ −⎪d3
−1
3+
+ d
2
+
-
d
1
-
d1
d2 -
d
3
200 100
图 1 图解法求解
300
图解法求解如图 1:目标 1, 3 达不到,所以有满意解为 A 点 (150,120)。
4、解:设该汽车装配厂为达到目标要求生产产品 A x件,生产产品 B x件。
1
2
+
+
min (
1
P d1 ⎧1+1
−
+ + d ) P d
( ) 2
2
3 −=
(a)目标规划模型为:
60 ⎪6 x 6 x− d++d
1
5 ⎪1
⎪ + x − d+ d −=
2
180 ⎨3 x 6 2 2
2
1
1+
1
⎪
x x d
⎪4+ 3−++d ⎪x x x d d ⎩ , , ,+,
1
2
3
3
i
−=
1300
1 2 3
i−
≥ 0, i = 1, 2,3
用图解法求解: 如图所示,所示解为区域 ABCD,有无穷多解。
(b)由上图可知,如果不考虑目标 1 和目标 2,仅仅把它们加工时间的最大限
度分别为 60 和 180 小时作为约束条件,而以利润最大化为目标,那么最优解为 C 点(360,0),即生产产品 A360 件,最大利润为 1420 元。结果与(a)是不相
同的,原因是追求利润最大化而不仅仅是要求利润不少于 1300 元。
(c)如果设目标 3 的优先权为 P1,目标 1 和目标 2 的优先权为 P2,则由上图可 知,满意解的区域依然是 ABCD,有无穷多解,与(a)的解是相同的,原因是
(a)和(c)所设定的目标只是优先级别不同,但都能够依次达到。
5.在环境污染日益得到重视的今天,越来越多的企业开始注重工业废水污
水排污。某纸张制造厂生产一般类型纸张的利润为 300 元/吨,每吨纸产生的工
业废水的处理费用为 30 元;生产某种特种纸张的利润为 500 元/吨,每吨特种
纸产生的工业废水的处理费用为 40 元。
该纸张制造厂近期目标如下:
目标 1:纸张利润不少于 15 万;
目标 2:工业废水的处理费用不超过 1 万元。
a.设目标 1 的优先权为 P,目标 2 的优先权为 P,P>P,建立目标规划模型
1
2
1
2
并用图解法求解。
b.若目标 2 的优先权为 P,目标 1 的优先权为 P,建立目标规划模型并求解。 所得的解是否与 a 中的解相同?
c. 若目标 2 的罚数权重为 5,目标 1 的罚数权重为 2,建立加权目标规划模 型求解。
1
2
5、解:设该纸张制造厂需要生产一般类型纸张 x吨,生产特种纸张 x吨。
1
2
(a)、目标规划模型为:
−
+
min
( )
P d1 P d2
−
⎧ x = 150000 x 300+ 500− d++d ⎪ x x − d+ d −=10000 ⎨30+ 402 2 ⎪x x d d , ,, − ≥ 0, i = 1, 2
( )
1
2
1
2
1
1+
1
2+
+
⎩
1 2 i i
+
+
= 0, x = 300, d −=0, d −=0, d= 0, d= 200
2 1 2 1 2
图解法略,求解得 x (b)、目标规划模型为:
1
+
( ) P d1
⎧ x −=150000 x 300+ 500− d++d ⎪ x x − d+ d −=10000 ⎨30+ 402 2 ⎪x x d d
⎩ , ,+, i− ≥ 0, i = 1,
1 2
2 = 250, d −=250, d −=0, d= 0, d= 0
= 0, x
2 1 2 1 2
图解法略,求解得 x
min P d( )
1
2
2
1
2
1
1+
1
2
i
+
+
1
+
−
由此可见,所得结果与(a)中的解是不相同的。 (c)、加权目标规划模型为: min P d(5 ++ d −
2 )
⎧ x −=150000 x 300+ 500− d++d ⎪ x x − d+ d −=10000 ⎨30+ 402 2 ⎪x x d d ⎩ , ,+, i− ≥ 0, i = 1, 2 1 2
= 0, x = 300, d −=250, d −=0, d= 0, d= 12000
1
2
1
1+
1
2
i
+
+
1 2 1
求解得 x
1
2 1 2 1 2
、
1、解:
C 3
6 x1
a.可行域为 OABC。
b.等值线为图中虚线所示。
c.由图可知,最优解为 B 点,最优解: x1
=
O
0.1
0.6
x1
x1
= 0.2
有唯一解 x2
= 0.6 函数值为 3.6
b 无可行解 c 无界解
d 无可行解
e 无穷多解
12
15
x2
=
,最优目标函数值:
20 x 92
f 有唯一解 3 函数值为3 8
x 3
12
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 9
x +
+ s = 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 + 4 + x+ 1 s =
2
2 31
2
xs
=
x +
2
1
5
1
2
9 8
x, x, , s ≥ 0
s2
1
2
1
1
2
s= 2, s= 0
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
s= 0, s= 0, s= 13 6 、解: b 1 ≤ c≤ 3
1
≥ 0 s s 1
, x, s, ,
2
3
c 2 ≤ c≤ 6
2
x= 6 x= 4 d
12
e
x∈ [ ]8 x = 16 − 2x
1
2
f 变化。原斜率从 −
3
7、解: 模型:
max z = 500x+ 400x
1
2
2 1
变为 − 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 d 在 [0,500]变化,最优解不变。 e 在 400 到正无穷变化,最优解不变。
f 不变
8 、解:
a
b
a 模型: min f = 8x+ 3x
50x+ 100x≤ 1200000
a
b
5x+ 4x≥ 60000
a
b
100x≥ 300000 , x ≥ 0 xb
基金 a,b 分别为 4000,10000。 回报率:60000
ba
b 模型变为: max z = 5x+ 4x
a
b
50x+ 100x≤ 1200000 100x≥ 300000 , x ≥ 0 xb
a
b
ba
1
2
推导出: x= 18000 x= 3000
故基金 a 投资 90 万,基金 b 投资 30 万。
第 3 章 线性规划问题的计算机求解
1、解:
a x= 150 x= 70
1
2
目标函数最优值 103000
b 1,3 使用完 2,4 没用完 0,330,0,15 c 50,0,200,0
含义: 1 车间每增加 1 工时,总利润增加 50 元
3 车间每增加 1 工时,总利润增加 200 元 2、4 车间每增加 1 工时,总利润不增加。 d 3 车间,因为增加的利润最大
e 在 400 到正无穷的范围内变化,最优产品的组合不变 f 不变 因为在 [0,500]的范围内
g 所谓的上限和下限值指当约束条件的右边值在给定范围内变化时,约束条
件 1 的右边值在 [200,440]变化,对偶价格仍为 50(同理解释其他约束条件) h 100×50=5000 对偶价格不变 i 能
j 不发生变化 允许增加的百分比与允许减少的百分比之和没有超出 100% k 发生变化 2、解:
a 4000 10000 62000
b 约束条件 1:总投资额增加 1 个单位,风险系数则降低 0.057
约束条件 2:年回报额增加 1 个单位,风险系数升高 2.167 c 约束条件 1 的松弛变量是 0,约束条件 2 的剩余变量是 0
约束条件 3 为大于等于,故其剩余变量为 700000 d 当 c不变时, c在 3.75 到正无穷的范围内变化,最优解不变
2
1
当 c不变时, c在负无穷到 6.4 的范围内变化,最优解不变
1
2
e 约束条件 1 的右边值在 [780000,1500000]变化,对偶价格仍为 0.057(其他 同理)
f 不能 ,理由见百分之一百法则二 3 、解:
a 18000 3000 102000 153000 b 总投资额的松弛变量为 0 基金 b 的投资额的剩余变量为 0 c 总投资额每增加 1 个单位,回报额增加 0.1
基金 b 的投资额每增加 1 个单位,回报额下降 0.06 d c不变时, c在负无穷到 10 的范围内变化,其最优解不变
1
2
c不变时, c在 2 到正无穷的范围内变化,其最优解不变
2
1
e 约束条件 1 的右边值在 300000 到正无穷的范围内变化,对偶价格仍为 0.1
约束条件 2 的右边值在 0 到 1200000 的范围内变化,对偶价格仍为-0.06 600000 300000 = 100% 故对偶价格不变
900000 900000 f
4、解:
a 8.5
x= x= 1.5
1
2
x= 0
3x= 1 最优目标函数 18.5
4
b 约束条件 2 和 3 对偶价格为 2 和 3.5
c 选择约束条件 3,最优目标函数值 22
d 在负无穷到 5.5 的范围内变化,其最优解不变,但此时最优目标函数值变化 e 在 0 到正无穷的范围内变化,其最优解不变,但此时最优目标函数值变化 5、解:
a 约束条件 2 的右边值增加 1 个单位,目标函数值将增加 3.622 b
x产品的利润提高到 0.703,才有可能大于零或生产
2
c 根据百分之一百法则判定,最优解不变
15 65
d + > 100 % 根据百分之一百法则二,我们不能判定
− 30 − 9.189
因为
111.25 15
其对偶价格是否有变化
第 4 章 线性规划在工商管理中的应用
1、解:为了用最少的原材料得到 10 台锅炉,需要混合使用 14 种下料方 428
639
850
547
969
1180
剩余
758
设按 14 种方案下料的原材料的根数分别为 x1,x2,x3,x4,x5,x6,x7,x8,x9, x10,x11,x12,x13,x14,则可列出下面的数学模型: min f=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14 s.t. 2x1+x2+x3+x4 ≥ 80
x2+3x5+2x6+2x7+x8+x9+x10≥ 350 x3+x6+2x8+x9+3x11+x12+x13≥ 420
x4+x7+x9+2x10+x12+2x13+3x14 ≥ 10
x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14≥ 0 用管理运筹学软件我们可以求得此问题的解为:
x1=40,x2=0,x3=0,x4=0,x5=116.667,x6=0,x7=0,x8=0, x9=0,x10=0,x11=140,x12=0,x13=0,x14=3.333 最优值为 300。
2、解:从上午 11 时到下午 10 时分成 11 个班次,设 xi 表示第 i 班次安排的临时 工的人数,则可列出下面的数学模型:
min f=16(x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11) s.t. x1+1 ≥ 9
x1+x2+1 ≥ 9 x1+x2+x3+2 ≥ 9 x1+x2+x3+x4+2 ≥ 3
x2+x3+x4+x5+1 ≥ 3
x3+x4+x5+x6+2 x4+x5+x6+x7+1 x6+x7+x8+x9+2
≥ 3 ≥ 6 ≥ 12
x5+x6+x7+x8+2 ≥ 12
x7+x8+x9+x10+1 ≥ 7 x8+x9+x10+x11+1 ≥ 7
x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11≥ 0 用管理运筹学软件我们可以求得此问题的解为:
x1=8,x2=0,x3=1,x4=1,x5=0,x6=4,x7=0,x8=6,x9=0, x10=0,x11=0 最优值为 320。
a、 在满足对职工需求的条件下,在 10 时安排 8 个临时工,12 时新安排 1
个临时工,13 时新安排 1 个临时工,15 时新安排 4 个临时工,17 时新
安排 6 个临时工可使临时工的总成本最小。
b、 这时付给临时工的工资总额为 80 元,一共需要安排 20 个临时工的班
次。
约束 对偶价格 松弛/剩余变量
------- ------------------ -------------
1 0 -4
2 0 0
3 2 0
4 9 0
5 0 -4
6 5 0
7 0 0
8 0 0
9 0 -4
10 0 0
11 0 0
根据剩余变量的数字分析可知,可以让 11 时安排的 8 个人工作 3 小时,13 时安排的 1 个人工作 3 小时,可使得总成本更小。
C、设在 11:00-12:00 这段时间内有 x个班是 4 小时, y个班是 3 小时;
1
1
设在 12:00-13:00 这段时间内有 x个班是 4 小时, y个班是 3 小时;其他时
2
2
段也类似。
则:由题意可得如下式子:
11
11
=
∑ x + ∑ y
i=1 1
1
min z 1612
i=1
S.T + y + ≥
1 9 x1
+ + + y + ≥ xyx2
1 9
+ + + + + y + ≥
1 +1 9
xyxyx3
≥ + + + + + + y +
1+1 3
xxyxyx4
+ + + + + + y + ≥
1 3
xxyxyx5
≥ + + + + + + y +
1+ 1 3
xxyxyx6
+ + + + + + y + ≥
1 6
xxyxyx7
≥ + + + + + + y +
1+1 12
xxyxyx8
≥ + + + + + + y +
1+1 12
xxyxyx9
+ + + + + + y + ≥
1 7
xxyxyx10
+ + + + + + y + ≥
1 7
xxyxyx11
x≥ 0, y≥ 0 i=1,2,…,11
11
1
2
1
1
2
2
3
1
2
2
3
3
4
2
3
3
4
4
5
3
4
4
5
5
6
4
5
5
6
6
7
5
6
6
7
7
8
6
7
7
8
8
9
7
8
8
9
9
10
8
9
9
10
10
11
i
i
稍微变形后,用管理运筹学软件求解可得:总成本最小为 264 元。
安排如下:y1=8( 即在此时间段安排 8 个 3 小时的班),y3=1,y5=1,y7=4,x8=6 这样能比第一问节省:320-264=56 元。
3、解:设生产 A、B、C 三种产品的数量分别为 x1,x2,x3,则可列出下面的
数学模型:
max z=10 x1+12 x2+14 x2 s.t. x1+1.5x2+4x3≤ 2000 2x1+1.2x2+x3 ≤ 1000
x1≤ 200 x2≤ 250 x3 ≤ 100 x1,x2,x3≥ 0
用管理运筹学软件我们可以求得此问题的解为:
x1=200,x2=250,x3=100 最优值为 6400。
a、在资源数量及市场容量允许的条件下,生产 A 200 件,B 250 件,C 100
件,可使生产获利最多。
b、A、B、C 的市场容量的对偶价格分别为 10 元,12 元,14 元。材料、台
时的对偶价格均为 0。说明 A 的市场容量增加一件就可使总利润增加 10
元,B 的市场容量增加一件就可使总利润增加 12 元,C 的市场容量增加 一件就可使总利润增加 14 元。但增加一千克的材料或增加一个台时数都
不能使总利润增加。如果要开拓市场应当首先开拓 C 产品的市场,如果
要增加资源,则应在 975 到正无穷上增加材料数量,在 800 到正无穷上
增加机器台时数。
4、解:设白天调查的有孩子的家庭的户数为 x11,白天调查的无孩子的家庭的户
数为 x12,晚上调查的有孩子的家庭的户数为 x21,晚上调查的无孩子的家庭 的户数为 x22,则可建立下面的数学模型: min f=25x11+20x12+30x21+24x22 s.t. x11+x12+x21+x22≥ 2000
x11+x12 = x21+x22 x11+x21≥ 700
x12+x22≥ 450
x11, x12, x21, x22 ≥ 0
用管理运筹学软件我们可以求得此问题的解为:
x11=700,x12=300,x21=0,x22=1000 最优值为 47500。
a、白天调查的有孩子的家庭的户数为 700 户,白天调查的无孩子的家庭的户
数为 300 户,晚上调查的有孩子的家庭的户数为 0,晚上调查的无孩子的
家庭的户数为 1000 户,可使总调查费用最小。
b、白天调查的有孩子的家庭的费用在 20-26 元之间,总调查费用不会变化;
白天调查的无孩子的家庭的费用在 19-25 元之间,总调查费用不会变化; 晚上调查的有孩子的家庭的费用在 29-无穷之间,总调查费用不会变化;
晚上调查的无孩子的家庭的费用在-20-25 元之间,总调查费用不会变 化。
c、调查的总户数在 1400-无穷之间,总调查费用不会变化;
有孩子家庭的最少调查数在 0-1000 之间,总调查费用不会变化; 无孩子家庭的最少调查数在负无穷-1300 之间,总调查费用不会变化。
5、解:设第 i 个月签订的合同打算租用 j 个月的面积为 xij,则需要建立下面的 数学模型:
min f=2800(x11+x21+x31+x41)+4500(x12+x22+x32)+6000(x13+x23)
+7300 x14
s.t.x11+x12+x13+x14≥ 15
x12+x13+x14+x21+x22+x23 ≥ 10 x13+x14+x22+x23+x31+x32≥ 20 x14+x23+x32+x41≥ 12 xij ≥ 0,i,j=1,2,3,4
用管理运筹学软件我们可以求得此问题的解为:
x11=5,x12=0,x13=10,x14=0,x21=0,x22=0,x23=0,x31=10, x32=0,x41=0
最优值为 102000。
即:在一月份租用 500 平方米一个月,租用 1000 平方米三个月;在三月 份租用 1000 平方米一个月,可使所付的租借费最小。
6、解:设 xij表示第 i 种类型的鸡需要第 j 种饲料的量,可建立下面的数学模型:
max z=9(x11+x12+x13)+7(x21+x22+x23)+8(x31+x32+x33)-5.5
(x11+x21+x31)-4(x12+x22+x32)-5(x13+x23+x33)
s.t. x11≥ 0.5(x11+x12+x13)
x12≤ 0.2(x11+x12+x13) x21≥0.3(x21+x22+x23) x23 ≤ 0.3(x21+x22+x23)
x33≥ 0.5(x31+x32+x33)
x11+x21+x31 ≤ 30 x12+x22+x32≤ 30 x13+x23+x33≤30
xij ≥ 0,i,j=1,2,3
用管理运筹学软件我们可以求得此问题的解为:
x11=30,x12=10,x13=10,x21=0,x22=0,x23=0,x31=0, x32=20,x33=20 最优值为 365。
即:生产雏鸡饲料 50 吨,不生产蛋鸡饲料,生产肉鸡饲料 40 吨。
7、
设 Xi——第 i 个月生产的产品 I 数量
Yi——第 i 个月生产的产品 II 数量
Zi,Wi 分别为第 i 个月末产品 I、II 库存数
S1i,S2i分别为用于第(i+1)个月库存的自有及租借的仓库容积(立方米)。则
可建立如下模型:
5
12
12
+ y + s x + y
+ ∑ z = ∑ + ∑ s
min (5x8 ) (4.5 7 ) ( 1.5 )
i
i=1
i
i=6
i i
i=1
1i 2i
s.t.
X1-10000=Z1 X2+Z1-10000=Z2
X3+Z2-10000=Z3 X4+Z3-10000=Z4 X5+Z4-30000=Z5 X6+Z5-30000=Z6 X7+Z6-30000=Z7 X8+Z7-30000=Z8 X9+Z8-30000=Z9
X10+Z9-100000=Z10 X11+Z10-100000=Z11
X12+Z11-100000=Z12
Y1-50000=W1 Y2+W1-50000=W2 Y3+W2-15000=W3 Y4+W3-15000=W4 Y5+W4-15000=W5 Y6+W5-15000=W6 Y7+W6-15000=W7 Y8+W7-15000=W8
Y9+W8-15000=W9 Y10+W9-50000=W10 Y11+W10-50000=W11
Y12+W11-50000=W12
S1i≤15000 1≤i≤12 Xi+Yi≤120000 1≤i≤12
0.2Zi+0.4Wi=S1i+S2i 1≤i≤12 Xi≥0, Yi≥0, Zi≥0, Wi≥0, S1i≥0, S2i≥0
用管理运筹学软件我们可以求得此问题的解为: 最优值= 4910500
X1=10000, X2=10000, X3=10000, X4=10000, X5=30000, X6=30000, X7=30000, X8=45000, X9=105000, X10=70000, X11=70000, X12=70000; Y1= 50000, Y2=50000, Y3=15000, Y4=15000, Y5=15000,
Y6=15000, Y7=15000, Y8=15000, Y9=15000, Y10=50000, Y11=50000, Y12=50000; Z8=15000, Z9=90000, Z10 =60000, Z1=30000; S18=3000, S19=15000, S110=12000, S111=6000; S28=3000;
其余变量都等于 0
8、解:设第 i 个车间生产第 j 种型号产品的数量为 xij,可建立下面的数学模型: max z=25(x11+x21+x31+x41+x51)+20(x12+x32+x42+x52)+17(x13
+x23+x43+x53)+11(x14+x24+x44)
s.t. x11+x21+x31+x41+x51 ≤ 1400
x12+x32+x42+x52≥ 300 x12+x32+x42+x52 ≤ 800 x13+x23+x43+x53≤ 8000 x14+x24+x44≥ 700
5x11+7x12+6x13+5x14 ≤ 18000
6x21+3x23+3x24≤ 15000 4x31+3x32 ≤ 14000
3x41+2x42+4x43+2x44≤ 12000 2x51+4x52+5x53≤ 10000
xij ≥ 0,i=1,2,3,4,5 j=1,2,3,4
用管理运筹学软件我们可以求得此问题的解为:
x11=0,x12=0,x13=1000,x14=2400,x21=0,x23=5000,x24=0, x31=1400,x32=800,x41=0,x42=0,x43=0,x44=6000,x51=0,
x52=0,x53=2000 最优值为 279400
9、解:设第一个月正常生产 x1,加班生产 x2,库存 x3;第二个月正常生产 x4,
加班生产 x5,库存 x6;第三个月正常生产 x7,加班生产 x8,库存 x9;第 四个月正常生产 x10,加班生产 x11,可建立下面的数学模型:
min f = 200(x1+x4+x7+x10)+300(x2+x5+x8+x11)+60(x3+x6
+x9)
s.t.
x1≤4000 x4≤4000 x7≤4000 x10≤4000 x3≤1000 x6≤1000 x9≤1000 x2≤1000 x5≤1000 x8≤1000 x11≤1000
x1+ x2- x3=4500 x3+ x4+ x5- x6=3000 x6+ x7+ x8- x9=5500 x9+ x10+ x11=4500
x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11≥0
计算结果是:
minf= 3710000 元
x1=4000 吨,x2=500 吨,x3=0 吨,x4=4000 吨, x5=0 吨 x6=1000 吨, x7=4000 吨, x8=500 吨, x9=0 吨, x10=4000 吨,x11=500 吨。
,
第 5 章
单纯形法
1、解:表中 a、c、e、f 是可行解,a、b、f 是基本解,a、f 是基本可行解。
2、解:a、该线性规划的标准型为: max 5 x1+9 x2
s.t.0.5 x1+x2+s1=8
x1+x2-s2=10
0.25 x1+0.5 x2-s3=6
x1,x2,s1,s2,s3≥0.
b、有两个变量的值取零,因为有三个基变量、两个非基变量,非基变量
取零。
c、(4,6,0,0,-2) d、(0,10,-2,0,-1)
e、不是。因为基本可行解要求基变量的值全部非负。
3 0 0 0 0 0 0
6 30* 25 0 0 0
b、线性规划模型为:
max 6 x1+30 x2+25 x3 s.t.3 x1+x2+s1 = 40
2 x1+x3+s2= 50 2 x1+x2-x3+s3=20
x1,x2,x3,s1,s2,s3≥0
c、初始解的基为(s1,s2,s3),初始解为(0,0,0,40,50,20),
对应的目标函数值为 0。
d、第一次迭代时,入基变量是 x2,出基变量为 s3。
4、解:最优解为(2.25,0),最优值为 9。
X2
1
5、解:a、最优解为(2,5,4),最优值为 84。
b、最优解为(0,0,4),最优值为-4。
6、解:a、有无界解
b、最优解为(0.714,2.143,0),最优值为-2.144。
7、解:a、无可行解
b、最优解为(4,4),最优值为 28。 c、有无界解
d、最优解为(4,0,0),最优值为 8。
第 6 章 单纯形法的灵敏度分析与对偶
1
a. c1≤24 b. c2≥6 c. cs2≤8
2
a. c1≥-0.5 b. -2≤c3≤0 c. cs2≤0.5
3
a. b1≥150
b. 0≤b2≤83.333 c. 0≤b3≤150
4
a. b1≥-4 b. 0≤b2≤300 c. b3≥4
5 a. b. c. d. e.
利润变动范围 c1≤3,故当 c1=2 时最优解不变 根据材料的对偶价格为 1 判断,此做法不利 0≤b2≤45
最优解不变,故不需要修改生产计划
此时生产计划不需要修改,因为新的产品计算的检验数为-12 小于零,对原生 产计划没有影响。
6
均为唯一最优解,根据从计算机输出的结果看出,如果松弛或剩余变量为零且对 应的对偶价格也为零,或者存在取值为零的决策变量并且其相差值也为零时,可
知此线性规划有无穷多组解。 7
a. min f= 10y1+20y2.
s.t. y1+y2≥2,
y1+5y2≥1, y1+y2≥1, y1, y2≥0.
b. max z= 100 y1+200 y2. s.t. 1/2 y1+4 y2≤4,
2 y1+6 y2≤4,
2 y1+3 y2≤2,
y1, y2≥0.
8.
a. min f= -10 y1+50 y2+20 y3-20 y4. s.t. -2 y1+3 y2+ y3- y2≥1,
≥2, 3 y1+ y2
- y1+ y2+ y3- y2 =5, y1, y2, y2≥0, y3 没有非负限制。
b. max z= 6 y1-3 y2+2 y3-2 y4.
s.t. y1- y2- y3+ y4≤1, 2 y1+ y2+ y3- y4=3, -3 y1+2 y2- y3+ y4≤2, y1, y2, y4≥0, y3没有非负限制
9. 对偶单纯形为 max z=4 y1-8 y2+2 y3 s.t y1- y2≤1,
- y1- y2+ y3≤2, y1-2 y2- y3≤3, y1, y2, y3≥0
目标函数最优值为: 10 最优解: x1=6, x2=2, x3=0
第 7 章 运输问题
1.
最优解如下
********************************************
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- ----- 1 0 250 0 50 2 400 0 0 0 3 0 0 350 150 此运输问题的成本或收益为: 19800
此问题的另外的解如下:
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- 1 0 250 50 0 2 400 0 0 0 3 0 0 300 200 此运输问题的成本或收益为: 19800
(2)如果 2 分厂产量提高到 600,则为产销不平衡问题
最优解如下
********************************************
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- 1 0 250 0 0 2 400 0 0 200 3 0 0 350 0
----- -----
此运输问题的成本或收益为: 19050
注释:总供应量多出总需求量 200
第 1 个产地剩余 50 第 3 个产地剩余 150
(3)销地甲的需求提高后,也变为产销不平衡问题
最优解如下
********************************************
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- ----- 1 50 250 0 0 2 400 0 0 0 3 0 0 350 150 此运输问题的成本或收益为: 19600
注释:总需求量多出总供应量 150
第 1 个销地未被满足,缺少 100 第 4 个销地未被满足,缺少 50
最优解如下
********************************************
起
至 销点
发点 1 2 3 4 5 6 8
-------- ----- ----- ----- ----- ----- ----- ----- ----- 1 0 0 100 0 0 200 0 0 2 0 0 0 0 350 0 0 150
3 0 50 0 100 0 0 0
4 0 100 0 0 0 0 0 0 5 150 0 50 0 0 0 0 0 此运输问题的成本或收益为: 1.050013E+07
7 250
最优解如下
********************************************
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- -----
1 2 0 0
2 1 1 0
3 0 0 3
4 0 4 0
5 0 0 2
6 0 0 0
7 0 0 0
此运输问题的成本或收益为: 8465
此问题的另外的解如下:
起 至 销点
发点 1 2 3 4
-------- ----- ----- ----- -----
1 2 0 0
2 1 2 0
3 0 0 3
4 0 3 0 1 0 0 0 2 3 0 0 0 1
5 0 0 0 2
6 0 0 2 0
7 0 0 3 0
此运输问题的成本或收益为: 8465
最优解如下
********************************************
起
至 销点
发点 1 2 3 4 5 6 -------- ----- ----- ----- ----- ----- ----- 1 1100 0 300 200 0 0 2 0 1100 0 0 600 0 3 0 0 1100 0 0 0 4 0 0 0 1100 0 0 5 0 0 0 0 1000 100 6 0 0 0 0 0 1100 此运输问题的成本或收益为: 130000
5.
建立的运输模型如下
min f = 500x1+300 x2+550 x3+650 x4. s.t. 54 x1+49 x2+52 x3+64 x4≤1100, 57 x1+73 x2+69 x3+65 x4≤1000,
最优解如下
********************************************
起 至 销点
发点 1 2 3 4 5
-------- ----- ----- ----- ----- ----- 1 250 300 550 0 0 2 250 0 0 650 100
此运输问题的成本或收益为: 113300 6.
销量 20 10 0 10 0 20 5 0
b. 最优解如下
********************************************
起 至 销点
发点 1 2 3 -------- ----- ----- -----
1 0 0 15 2 20 5 0 3 0 5 5 此运输问题的成本或收益为: 145
c. 该运输问题只有一个最优解,因为其检验数均不为零
d. 最优解如下
********************************************
起 至 销点
发点 1 2 3 -------- ----- ----- -----
1 0 0 15 2 25 0 0 此运输问题的成本或收益为: 135
1.
第 8 章 整数规划
求解下列整数规划问题 max z=5x +8x2
1
a. s.t.
x +x
1 1 1
2 2
≤ 6, ≤ 45, ≥ 0,且为整数
2
5x +9x
2
x ,x
目标函数最优解为 :
1
x *=0,x *=5,z*=40。
b. max z=3x +2x
1
2
s.t.
2x +3x
1 1
2 2
≤ 14, ≤ 9,
为整数。
2
2x +x
x1,x2 0, x1且 目标函数最优解为 :
1
x *=3,x *=2.6667,z*=14.3334。
c. max z=7x +9x +3x
1
2
3
s.t.
-x +3x +x
1
2
3
≤ 7,
0-1变量。
7x +x +x ≤ 38,
1 2 3
且 为整数, 为x
x ,x ,x ≥ 0, x
1
2
3
1
3
目标函数最优解为 :
1
x *=5,x *=3,x *=0,z*=623
2。
2.解:设 xi为装到船上的第 i 种货物的件数,i=1,2,3,4,5。则该船装载的货 物取得最大价值目标函数的数学模型可写为:
max z=5x +10x +15x +18x +25x2 3 4 5 s.t.
20x +5x +10x +12x +25x ≤ 400000,
1
1 1 1
1 2 4
2
3
3 4
4 5
5
x +2x +3x +4x +5x ≤ 50000, x +4x
2
3
≤ 10000
≤ 750,
4
5
0.1x +0.2x +0.4x +0.1x +0.2x
x
i
≥ 0,且为整数,i=1 2 3 4 5
目标函数最优解为 :
1
x *=0,x *=0,x *=0,x *=2500,x *=2500,z*=107500 .3
2
4 5
3.解:设 xi为第 i 项工程,i=1,2,3,4,5,且 xi为 0-1 变量,并规定,
i ⎧
1, 当第 项工程被选定时, x= ⎨ i
⎩ ,当第 项工程没被选定时。
根据给定条件,使三年后总收入最大的目标函数的数学模型为:
i
max z 20x+ 40x+ 20x+15x+ 30x s.t.
5x +4x +3x +7x +8x
1
2
3
4
5
≤ 25, ≤ 25,
1 1 1
2 2
2
3 3
3
4 4 4
5 5
5
x +7x +9x +4x +6x
8x +10x +2x +x +10x ≤ 25, 为 变量,i=1 2 3 4 5 x 0-1
i
目标函数最优解为 :
1
x *=1,x *=1,x *=1,x *=1,x *=0,z*=953
2
4 5
4.解:这是一个混合整数规划问题
设 x1、x2、x3分别为利用 A、B、C 设备生产的产品的件数,生产准备费
只有在利用该设备时才投入,为了说明固定费用的性质,设
⎧1,当利用第 种设备生产时,即i x >0,
i
y = ⎨ i
0 i x =0。 ⎩ ,当不利用第 种设备生产时,即
故其目标函数为:
i
min z 100y +300y +200y +7x +2x +5x
3 12 1 2 3
为了避免没有投入生产准备费就使用该设备生产,必须加以下的约束条件, M 为充分大的数。
x ≤ y M,
1 2 3
1 2 3
x ≤ y M, x ≤ y M ,
设 M=1000000
a. 该目标函数的数学模型为:
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
≤ 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
x1
, ,x2
x3
≥ 0,且为整数, , , 为y1
y2
y3
0-1变量。 目标函数最优解x *=370,x *=231,x *=1399,y =1,y =1,y =1,z*=10647 为 : 1
3
b.该目标函数的数学模型为:
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 ≤ 2500, 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 *=625,x *=1375,y =0,y =1,y =1,z*=8625 1
3
23 1 2
23
1 2
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 为 :1
3
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 1
2
3
1
2y0-1
3
目标函数最优解x *=0,x *=1200,x *=800,y =0,y =1,y =1,z*=6900
23 1 为 :1
3
5.解:设 xij 为从 Di 地运往 Ri 地的运输量,i=1,2,3,4,j=1,2,3 分别代表从北京、上海、广州、武汉运往华北、华中、华南的货物件数,并规定,
⎧1 i
yi
= ⎨ ,当 地被选设库房,
0 i
该目标函数的数学模型为:⎩ ,当 地没被选设库房。
2
2
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
43
31 32 33 41 42
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
3
4
≤ 1000y,
2
≤ 1000y,
3
4
x +x +x4142 43 ≤ 1000y,
≤ y ,
y +y +y +y ≤ 2, 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
⎩ ,当不指派第 人去完成第 项工作时。
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 12
42 21 22
43 31 32
44 41 42
x +x +x +x =1,
x +x +x +x =1,
x +x +x +x =1,
13 14
23 24
33 34
43 44
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 项不同的工作的问题了,其目标函数的数
学模型为:
min z 20x+19x+ 20x+ 28x+17x+18x+ 24x+ 27x+ 20x +20x+26x +16x +15x +18x +15x +17x +20x +24x +19x +16x32 33
11
12
13
14
15
21
22
23
31
2425
34 35 41 42 43
44 45
s.t.
x +x +x +x +x =1,
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
11
x +x +x +x ≤ 1,
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
解得最优解为:
城市 B
解得最优解为:
或为:
城市 C
解得最优解为:
或为:
或为:
第 9 章 目标规划
1.某工厂试对产品 A、B 进行生产。市场需求并不是很稳定,因此对每种产
品分别预测了在销售良好和销售较差时的预期利润。这两种产品都经过甲、乙两 台设备加工。已知产品 A 和 B 分别在甲和乙设备上的单位加工时间,甲、乙设备 的可用加工时间以及预期利润如下表所示,要求首先是保证在销售较差时,预期 利润不少于 5 千元,其次是要求销售良好时,预期利润尽量达到 1 万元。试建立
多目标规划模型并求解。
(百元/件)
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
2
+
1
2
i
⎩⎪x x d d, ,i,−
2
由管理运筹学软件先求解得: x
1
≥ 0, i = 1,
= 11.25, x = 0, d −=0, d −=10, d= 6.25, d= 0
+
+
2 1 2 1 2
由图解法或进一步计算可知,本题在求解结果未要求整数解的情况下,满意解有 无穷多个,为线段α (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.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.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
得: 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
min d+
3
⎧x1≤ 10 ⎪ ≤ ⎪ 20 xx3 15 x + 5x −=400 2
⎪ ≤ ⎪
x
⎪20+10 3 − d1
++d1
1
2
⎪ x x x d −=0 0.7 − 0.3 − 0.3
⎨−⎪1 2 3 2
2
x
x x−+ +d −
= 0 ⎪ 0.31
− 0.32
+ 0.73
− d3
++d3 20
⎪ + −
x x x + d = 2.5 + 0.5 + 0.3
⎪ 1 2 3 − d4
4
⎪d −= 0
1
⎪⎪0
d2−
=
⎪x x x d d i
− ≥ 0, i = 1, 2,3, 4
⎩ , , ,i
+,
1 2 3
得最优值 d3
+=0 ,将其作为约束条件计算下述问题:
min d+
4
⎧ ≤ x1
10
⎪⎪20 x2
≤ ⎪ ≤ ⎪x 3
⎪
x 15
x + 5x
−=
400 201
+102
3 − d1
++d1
⎪ x x x d −=
0 ⎪0.71
− 0.32
− 0.33
−2
++d2
−
⎪−
= x x x 0
⎨ 0.31
− 0.32
+ 0.73
− d3
++d3
⎪ +
−
x
x x + d =
20
⎪2.5+ 0.5+ 0.3− d4 ⎪d −=0 ⎪ 1 0 ⎪d −=
1
2
3
4
2
⎪⎪d3
+
=
⎪x x x d d −
, , ,+
得: ⎩ 1 2 ,3
i
i
≥ 0, i = 1, 2,3, 4
x = 9.474, x = 20, x = 2.105, d= 0, d −=0, d= 8.387, d −=0, d= 0, d −=7.368,
+
+
+
1
+
2 3 1 1 2 2 3 3
d= 14.316, d −=0,
4
4
所以食品厂商为了依次达到 4 个活动目标,需在电视上发布广告 9.474 次,报纸
上发布广告 20 次,广播中发布广告 2.105 次。(管理运筹学 2.0 可一次求解上述
问题)
3、解:(a)设该化工厂生产 x升粘合剂 A 和 x升粘合剂 B。则根据工厂要求,
1
2
建立以下目标规划模型:
−
+
−
−
−
min
( + d ) + ( + d ) + ( ) P d1 2 2 3 4 3 5
1
−= +5
80 ⎪3 x 12 x− d++d
⎪ + x − d+ d −=
2 2 2
100 ⎪ x
12 ⎪3 100 x + =
1
2
1
1+
1
+d−
⎨ −⎪d3
−1
3+
+ d
2
+
-
d
1
-
d1
d2 -
d
3
200 100
图 1 图解法求解
300
图解法求解如图 1:目标 1, 3 达不到,所以有满意解为 A 点 (150,120)。
4、解:设该汽车装配厂为达到目标要求生产产品 A x件,生产产品 B x件。
1
2
+
+
min (
1
P d1 ⎧1+1
−
+ + d ) P d
( ) 2
2
3 −=
(a)目标规划模型为:
60 ⎪6 x 6 x− d++d
1
5 ⎪1
⎪ + x − d+ d −=
2
180 ⎨3 x 6 2 2
2
1
1+
1
⎪
x x d
⎪4+ 3−++d ⎪x x x d d ⎩ , , ,+,
1
2
3
3
i
−=
1300
1 2 3
i−
≥ 0, i = 1, 2,3
用图解法求解: 如图所示,所示解为区域 ABCD,有无穷多解。
(b)由上图可知,如果不考虑目标 1 和目标 2,仅仅把它们加工时间的最大限
度分别为 60 和 180 小时作为约束条件,而以利润最大化为目标,那么最优解为 C 点(360,0),即生产产品 A360 件,最大利润为 1420 元。结果与(a)是不相
同的,原因是追求利润最大化而不仅仅是要求利润不少于 1300 元。
(c)如果设目标 3 的优先权为 P1,目标 1 和目标 2 的优先权为 P2,则由上图可 知,满意解的区域依然是 ABCD,有无穷多解,与(a)的解是相同的,原因是
(a)和(c)所设定的目标只是优先级别不同,但都能够依次达到。
5.在环境污染日益得到重视的今天,越来越多的企业开始注重工业废水污
水排污。某纸张制造厂生产一般类型纸张的利润为 300 元/吨,每吨纸产生的工
业废水的处理费用为 30 元;生产某种特种纸张的利润为 500 元/吨,每吨特种
纸产生的工业废水的处理费用为 40 元。
该纸张制造厂近期目标如下:
目标 1:纸张利润不少于 15 万;
目标 2:工业废水的处理费用不超过 1 万元。
a.设目标 1 的优先权为 P,目标 2 的优先权为 P,P>P,建立目标规划模型
1
2
1
2
并用图解法求解。
b.若目标 2 的优先权为 P,目标 1 的优先权为 P,建立目标规划模型并求解。 所得的解是否与 a 中的解相同?
c. 若目标 2 的罚数权重为 5,目标 1 的罚数权重为 2,建立加权目标规划模 型求解。
1
2
5、解:设该纸张制造厂需要生产一般类型纸张 x吨,生产特种纸张 x吨。
1
2
(a)、目标规划模型为:
−
+
min
( )
P d1 P d2
−
⎧ x = 150000 x 300+ 500− d++d ⎪ x x − d+ d −=10000 ⎨30+ 402 2 ⎪x x d d , ,, − ≥ 0, i = 1, 2
( )
1
2
1
2
1
1+
1
2+
+
⎩
1 2 i i
+
+
= 0, x = 300, d −=0, d −=0, d= 0, d= 200
2 1 2 1 2
图解法略,求解得 x (b)、目标规划模型为:
1
+
( ) P d1
⎧ x −=150000 x 300+ 500− d++d ⎪ x x − d+ d −=10000 ⎨30+ 402 2 ⎪x x d d
⎩ , ,+, i− ≥ 0, i = 1,
1 2
2 = 250, d −=250, d −=0, d= 0, d= 0
= 0, x
2 1 2 1 2
图解法略,求解得 x
min P d( )
1
2
2
1
2
1
1+
1
2
i
+
+
1
+
−
由此可见,所得结果与(a)中的解是不相同的。 (c)、加权目标规划模型为: min P d(5 ++ d −
2 )
⎧ x −=150000 x 300+ 500− d++d ⎪ x x − d+ d −=10000 ⎨30+ 402 2 ⎪x x d d ⎩ , ,+, i− ≥ 0, i = 1, 2 1 2
= 0, x = 300, d −=250, d −=0, d= 0, d= 12000
1
2
1
1+
1
2
i
+
+
1 2 1
求解得 x
1
2 1 2 1 2