管理运筹学(第三版)课后习题答案
第 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 + = 100% 故对偶价格不变
900000 900000 f
4、解:
a x=
1
x= 1.5
2x= 0
3x= 1 最优目标函数 18.5
4
8.5
b 约束条件 2 和 3 对偶价格为 2 和 3.5
c 选择约束条件 3,最优目标函数值 22
d 在负无穷到 5.5 的范围内变化,其最优解不变,但此时最优目标函数值变化 e 在 0 到正无穷的范围内变化,其最优解不变,但此时最优目标函数值变化 5、解:
a 约束条件 2 的右边值增加 1 个单位,目标函数值将增加 3.622 b 才有可能大于零或生产
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
z = ∑ min (5x8
i
+ y
i
+ s x + y
+ ∑ + ∑ s ) (4.5 7 ) ( 1.5 )
i=6
i
i
i=1
1i
2i
i=1
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 1
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
300 250
350 200 250 150
最优解如下
********************************************
起
至 销点
发点 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.
10
销量 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
0 10
1.
第 8 章 整数规划
求解下列整数规划问题 max z=5x +8x2
1
a. s.t.
x +x ≤ 6,
1 1 1
2 2
2
5x +9x ≤ 45, x ,x ≥ 0,且为整数
目标函数最优解为 :
1
x *=0,x *=5,z*=40。
2
b. max z=3x +2x
1
2
s.t.
2x +3x ≤ 14,
1 1
2 2
2x +x
≤ 9,
为整数。
2
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 s.t.
20x +5x +10x +12x +25x
1
5
≤ 400000,
1 1 1
2 4
2
3
3 4
4 5
5
x +2x +3x +4x +5x ≤ 50000, x +4x ≤ 10000
0.1x +0.2x +0.4x +0.1x +0.2x
1 i
2
3
4
5
≤ 750,
x ≥ 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 ≤ 25,
1
2
3
4
5
1 1 1
2 2
2
3 3
3
4 4 4
5 5
x +7x +9x +4x +6x ≤ 25, 8x +10x +2x +x +10x
5
≤ 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
12 3 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
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
23 1
23
1 2 3
2 3
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
⎩ ,当不指派第 人去完成第 项工作时。
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 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 三个城市建立的指派问题的效率矩阵 分别如下表所示:
第 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
+
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.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 ⎪
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
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
1
2
x
3
x
4
+ d = 20
⎪2.5+ 0.5+ 0.3− d4 ⎪d −=0 ⎪ 1 0 ⎪d −=
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 ) + ( ) 1
2 2 3 4 3 5
⎧1+5
−= x1
x2
− d1
++d180 ⎪1
5
⎪ + x − d+
+ d −=
⎪ x1
2 2 2
100 ⎪3 12 x + =
100 +d−
⎨ −⎪1
d33
100
-
+
d1
d3
-
d+ 2
dd2 -
1
100
200 300
图 1
图解法求解如图 1:目标 1,2 可以达到,目标 3 达不到,所以有满意解为 A 点 (150,120)。
4、解:设该汽车装配厂为达到目标要求生产产品 A x1
件,生产产品 B x2
件。
+
+
+ −
min (
+ d ) P d
P d( )
1
1
⎧1
+1
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
i−
≥ 0, i = 1, 2,3
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)、目标规划模型为:
−
+
2
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
11
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
第 10 章 动态规划
1、最优解:A―B2―C1―D1―E;A―B3―C1―D1―E;A―B3―C2―D2―E
最优值:13
2、最优解:项目 A:300 万元、项目 B:0 万元、项目 C:100 万元、
最优值:Z=71+49+70=190 万元
3、设每个月的产量是 Xi 百台(i=1、2、3、4)
最优解:X1=4、X2=0、X3=4、X4=3
即第一个月生产 4 台,第一个月生产 0 台,第一个月生产 4 台,第一个月生 产 3 台。
最优值:Z=252000 元
4、最优解:运送第一种产品 5 件
最优值:Z=500 元
6.最优解(0,200,300,100)或(200,100,200,100)或者(100,100, 300,100)或(200,200,0,200)。总利润最大增长额为 134 万。
7.在区 1 建 3 个分店,在区 2 建 2 个分店,不在区 3 建立分店。最大总利润 22。 8.最优解为:第一年继续使用,第二年继续使用,第三年更新,第四年继续使 用,第五年继续使用,总成本=4500 元。
9.最优解为第一年购买的设备到第二、三、四年初各更新一组,用到第 5 年末,
其总收入为 17 万元。
10.最优解为第一批投产 3 台,如果无合格品,第二批再投产 3 台,如果仍全部 不合格,第三批投产 4 台。总研制费用最小为 796 元。 最大利润为 14000。 12.
最优策略为(1,2,3)或者(2,1,3),即该厂应订购 6 套设备,可分别分给三个厂 1,2,3 套或者 2,1,3 套。每年利润最大为 18 万元。
第 11 章 图与网络模型
习题 1
解:这是一个最短路问题,要求我们求出从 v到 v配送的最短距离。用
1
7
Dijkstra 算法求解可得到这问题的解为 27。我们也可以用此书附带的管理运筹学
软件进行计算而得出最终结果为:
从节点 1 到节点 7 的最短路 ************************* 起点 终点 距离
---- ---- ----
1 2 4 2 3 12 3 5 6 5 7 5
此问题的解为:27
即:配送路线为: v→ v→ v→ v→ v
1
2
3
5
7
习题 2
解:这是一个最短路的问题,用 Dijkstra 算法求解可得到这问题的解为 4.8, 即在 4 年内购买、更换及运行维修最小的总费用为:4.8 万元。
最优更新策略为:第一年末不更新 第二年末更新 第三年末不更新
第四年末处理机器
我们也可以用此书附带的管理运筹学软件进行求解,结果也可以得出此问题 的解为 4.8。
习题 3
解:此题是一个求解最小生成树的问题,根据题意可知它要求出连接 v到 v
1
8
的最小生成树。解此题可以得出结果为 18。也可以使用管理运筹学软件,得出 如下结果:
此问题的最小生成树如下: ************************* 起点 终点 距离
---- ---- ----
1 3 2
3 4 2 1 2 4 2 5 2 5 7 3
7 8 2
7 6 3
此问题的解为:18
习题 4
解:此题是一个求解最大流的问题,根据题意可知它要求出连接 v到 v的最
1
6
大流量。解此题可以得出最大流量为 22。使用管理运筹学软件,我们也可以得
出结果为:
v从节点 1 到节点 6 的最大流
1
************************* 起点 终点 距离
---- ---- ----
1 2 6
1 4 6 1 3 10 2 4 0 2 5 6 3 4 5 3 6 5 4 5 5 4 6 6 5 6 11
此问题的解为:22
即从 v到 v的最大流量为:22
1
6
习题 5
解:此题是一个求解最小费用最大流的问题,根据题意可知它要求出连接 v
1
到 v的最小费用最大流量。解此问题可以得出最大流为 5,最小费用为 39。使用
6
管理运筹学软件,我们也可以得出结果如下:
从节点 1 到节点 6 的最大流 *************************
起点 终点 流量 费用
---- ---- ---- ----
1 2 1 3
1 3 4 1 2 4 2 4 3 2 1 1 3 5 3 3 4 6 2 4