胡运权运筹学第七章习题解资料讲解.doc

精品文档
7.3某厂每月生产某种产品最多600件，当月生产的产品若未销出，就需贮存（刚入库的产品下月不付存储费）月初就已存储的产品需支付存储费，每100件每月1000元。已知每100件产品的生产费为5千元，在进行生产的月份工厂支出经营费4千元，市场需求如表7-19所示，假定1月初及4月底库存量为零，试问每月应生产多少产品，才能在满足需求条件下，使总生产及存贮费用之和最小。
月份
1
2
3
4
产品（100件）
5
3
2
1

解：
设阶段变量：k=1,2,3
状态变量： 第k个月初的库存量
决策变量：第k个月的生产量
状态转移方程：
阶段指标：
由于在4月末，仓库存量为0，所以对于k=4阶段来说有两种决策：
5+4=9
=
1
对K=3

0
1
2
3
4
5
6

0

2*5+4+9=23
3*5+4+1=20

20
3
1

1*5+4+9=18
2*5+4+1+1=16

16
2
2
2*5+9=19
1*5+1+4+1=11

11
1
3
3*1+1=4

4
0

K=2

d2
X2

0
1
2
3
4
5
6
f(x)
d
0

3*5+4+20=39
4*5+4+16=39
5*5+4+10
6*5+4+4
38
6
1

1+2*5+4+20=35
3*5+4+16+1=36
4*5+4+11+1=36
5*5+4+4+1=34

34
5
2

1*4+4+20+2=230
2*5+4+16+2=32
3*5+4+11+2=32
4*5+4+4+2=30

30
4
3
3+20=32
1*5+4+16+3=28
2*5+4+11+3=28
3*5+4+4+3=23

23
3
4
4+16=20
5+4+11+4=23
2*5+4+4+4=22

20
0
5
5+11=16
1*5+4+4+5=16

16
0
6
6+4=10

10
0

K=1时

0
1
2
3
4
5
6
F(x)
d
0

5*5+4+38=67
6*5+4+34=68
67
5

解得：第一个月生产500份，第二个月生产600份，第三个月生产0份，第四个月生产0份。

7.4某公司有资金4万元，可向A，B，C三个项目投资，已知各项目不同投资额的相应效益值如表7-20所示，问如何分配资金可使总效益最大。
表 7-20
项目
投资额
0
1
2
3
4
A
0
41
48
60
66
B
0
42
50
60
66
C
0
64
68
78
76
解：
设阶段变量k，，每一个项目表示一个阶段;
状态变量Sk，表示可用于第k阶段及其以后阶段的投资金额；
　决策变量Ｕk，表示在第k阶段状态为Sk下决定投资的投资额；
决策允许集合：0≤Ｕk≤Sk
状态转移方程：Sk+1=Sk-Ｕk;
阶段指标函数：V k(SkＵk)；
最优指标函数：fk(Sk)=max{ V k(SkＵk)+ fk+1(Sk+1)}
终端条件：f4(x4)=0；
K=4, f4(x4)=0
k=3, 0≤Ｕ3≤S3
S3 Ｕ3
f3(S3)=max{ V3(S3Ｕ3)+ f4(S4)}
f3(S3)
U3*
0
1
2
3
4
0
0

0
0
1
0
64

64
1
2
0
64
68

68
2
3
0
64
68
78

78
3
4
0
64
68
78
76
78
3
k=2, 0≤Ｕ2≤S2
S2 Ｕ2
f2(S2)=max{ V 2(S2Ｕ2)+ f3(S3)}
f2(S2)
U2*
0
1
2
3
4
0
0+0

0
0
1
0+64
42+0

64
0
2
0+68
42+64
50+0

106
1
3
0+78
42+68
50+64
60+0

114
2
4
0+78
42+78
50+68
60+64
66+0
124
3

k=1, 0≤Ｕ1≤S1
S1 Ｕ1
f1(S1)=max{ V1(S1Ｕ1)+ f2(S2)}
f1(S1)
U1*
0

3
4
0
0+0

0
0
1
0+64
41+0

64
0
2
0+106
41+64
48+0

106
1
3
0+114
41+106
48+64
60+0

114
0
4
0+124
41+114
48+106
60+64
55+0
155
1
所以根据以上计算，可以得到获得总效益最大的资金分配方案为（1，2，1）.

7.5为了保证某设备正常运行,须对串联工作的三种不同零件A1,A2,A3,分别确定备件数量。若增加备用零件数量，可提高设备正常运转的可靠性，但费用要增加，而总投资额为8千元。已知备用零件数和他的可靠性和费用关系如表所视，求A1,A2,A3,的备用零件数个为多少时可使设备运转的可靠性最高。
设备数
可靠性
备用零件费用（千元）
A1
A2
A3
A1
A2
A3
1
0.3
0.2
0.1
1
3
2
2
0.4
0.5
0.2
2
5
3
3
0.5
0.9
0.7
3
6
4

解：设第k阶段的状态为Sk；第k阶段决定投入的备件为Xk;Ck(Xk)为第k阶段选择k个零件的费用；Rk(Xk)为第k个阶段选择k个零件的可靠性。

状态转移方程为：Sk+1=Sk- Ck(Xk)
递退方程：

所以有上可知当A1；A2；A3；分别为k=1;k=2;k=3时S1=8; S2=5,6,7; S3=1,2,3,4;
当k=3时
S3
X3
F3(x3)
X3*
1
0
0
无
2
1
0.1
1
3
1
2
0. 1
0.2
2
4
1
2
3
0.1
0.2
0.7
3

当k=2时
S2
X2
F2(x2)
X2*
5
1
2
0. 2*0.1=0.02
0.5*0=0
1
6
1
2
3
0. 2*0.2=0.04
0. 5*0=0
0.9*0=0
1
7
1
2
3
0. 2*0.7=0.14
0.5*0.1=0.05
0.9*0=0
1

当k=1时
S1
X1
F1(x1)
X1*
8
1
2
3
0.3*0.14=0.042
0.4*0.04=0.016
0.5*0.02=0.01
1

由上表可知，最优解的可靠性为0.042；此时X1=1；X2=1；X3=3。

7.7 某工厂接受一项特殊产品订货，要在三个月后提供某种产品1000kg，一次交货。由于该产品用途特殊，该厂原无存货，交货后也不留库存。已知生产费用与月产量关系为：C=1000+3d+0.005d，其中d为月产量（kg），C为该月费用（元）。每月库存成本为2元/kg，库存量按月初与月末存储量的平均数计算，问如何决定3个月的产量是总费用最小。
解：用动态规划法求解
阶段k：每一个月为一个阶段k=1,2,3
状态变量s：第k个月初的库存量
决策变量d：第k个月的生产量
状态转移方程：s= s+d
最优指标函数：f( s)：第k个月状态为s时到第3个月末的总费用最小
则第k个月的库存费用为：E= （s +s）/22= s +s=2 s+d
s=0，d+d+d=1000
当k=3时
f(s)=min{E+C}
=min{2s+d+1000+ 3d+0.005d}
= min{3000+ 2d+0.005d}
= 3000+2(1000- s)+0.005(1000- s)
当k=2时
f(s)=min{E+C+ f(s)}
=min{2s+d+1000+3d+0.005d+3000+2(1000- s)+0.005(1000- s)}
=min{2s+1000+4d+0.005d+3000+2(1000-s-d)+0.005(1000- s-d)}
=min{6000+2d+0.005d+0.005(1000- s-d)}
只有当d=1000- s 时f(s)取最小值6000+2（1000- s）+0.005（1000- s）
f(s)=min{E+C+ f(s)}
=min{2 s+ d+1000+3 d+0.005d+6000+2（1000- s）+0.005（1000- s）}
=min{9000+4 d+0.005d+0.005（1000- d）}
=min{14000-6d+0.01d}
只有当d=300时f(s)取最小值13100元
此时s= d+ s=300
那么d=1000- s=700，f(s)=9850元
d=1000-d-d=0，f(s)=3000元
即：三个月的产量分别为300、700、0时，总费用最小。

7-11.某工厂生产三种产品，各产品重量与利润关系如表。现将此三种产品运往市场出售，运输总重量不超过6t，应运输每件产品各多少件使总利润最大？
产品
重量（t/每件）
利润（千元/每件）
1
2
80
2
3
130
3
4
180

解：设:：第K种产品的数目；
：第K种产品的利润；
：第K种产品之初的总重量；;
()：第K~3种产品的总价值；
（）=max{+`()}
且()=0
K=3：

0~3
4~6

数目
0
1
180
K=2：

6

0
0
0
0
0
0
1
0
1
0
0
0
2
0
2
0
0
0
3
0
1
3
0
0
130+0=130
130
1
4
0
1
4
1
0+180=180
130+0=130
180
0
5
0
1
5
2
0+180=180
130+0=130
180
0
6
0
1
2
6
3
0
0+180=180
130+0=130
260+0=260
260
2

K=1：

6
0
6
0+260=260

260

0/1
1
4
80+180=260
2
2
160+0=160
3
0
240+0=240

答:故最大利润为260，产品数目为“0，2，0”或“1，0，1”。

7.12 某公司需要对某产品决定未来4个月内每个月的最佳存储量，以使总费用最小。已知各月对该产品的需求量和单位订货费用、存储费用如表7-23所示。假定每月初订货于月末到货并入库，下月开始销售。
表7-23
月份k
1
2
3
4
需求量dk
50
45
40
30
单位订货费用Ck
850
850
775
825
单位存储费用Pk
35
20
40
30
解：
阶段k：月份 k=1，2，3，4，5
状态变量Xk：第k个月初的存量
决策变量r：第k个月的订货量
状态转移方程：Xk+1=Xk+rk-dk
决策允许集合：rk（Xk）=｛rk︱rk≥0 dk+1≤Xk+1｝
=｛rk︱dk+1≤Xk+rk-dk｝
阶段指标：Ckrk +PkXk
f5（X5）=0 X5=0
fk（Xk）=min｛Vk(Xk, rk)+fk+1(Xk+1)｝
=min｛Ckrk+ PkXk + fk+1(Xk+rk-dk)｝

对于k=4 X5=0 r4=0 X4=d4
f4（X4）=min｛V4(X4, r4)+f5(X5)｝
=min｛30 X4｝
=900
对于k=3
F3（X3）=min｛V3(X3, r3)+f4(X4)｝
=min｛C3r3+ P3X3 + f4(X4)｝
=min｛40r3+ 40X3 + 900｝
=min{775r3+40x3+900}
d4=x4 则 d4=x3+r3-d3 r3+d3+d4-x3=70-x3
f3(x3)=min{775(70-x3)+40x3+900}
=min{63250-735x3}
当k=2时
f2（x2）=min｛C2r2+ P2x2 + f3(x3)｝
=min{850r2+20x2+63250-735(x2+r2-d2)}
=min{850r2+20x2+63250-735x2-735r2+33075}
=min{96325-715x2+115r2}
R2(x2)={r2 r20 d3x2+r3-d2 }
={r2 r20 d3+d2 -x2r3 }
={r2 r20 85-x2r3 }
f2（x2）=min｛96325-715x2+115 x2+9775｝
=min{106100-830x2}
当k=1时
f1（x1）=min｛850r1+30x1+106100-830(x1+r1-50)｝
=min{147600-800x1+20r1}
r1（x1）=｛r1︱r1≥0 d2+d1﹣x1≤r1｝
=｛r1︱r1≥0 95﹣x1≤r1｝
f1（x1）=min｛147600-800 x1+20（95﹣X1）｝
=min｛149500-820 x1｝
根据题意x1=0 r1*=95﹣x1
f1（x1）=149500 r1*=95
r1*=95x2 =x1+r1-d1 =45
f2（x2）= 68750
r2*=85﹣45=40
x3 =x2+r2-d2=45+40-45=40
f3（x3）=33850
x4 = d4=30
f4（x4）=900

7.13 某罐头制造公司在近5周内需要一次性地购买一批原料，估计未来5周内价格有波动，其浮动价格及概率如表7-24所示，试求各周的采购策略，使采购这批原料价格的数学期望值最小。
表7-24
批单价
概率
9
0.4
8
0.3
7
0.3
解：
设阶段变量k，,每一周表示一个阶段;
状态变量Sk，表示第k阶段的实际价格；
　决策变量Ｕk，当Ｕk=1，表示第k周决定采购；当Ｕk=0，表示第k周决定等待。
SkE表示第k周决定等待，而在以后采用最优决策时采购价格的期望值；
fk(Sk)表示第k周实际价格为Sk时，从第k周至第五周采用最优决策所得的最小期望值。因而可写出逆序递推关系式为
fk(Sk)=min{ Sk, SkE} Sk∈{9,8,7} (1)
由SkE和fk(Sk)的定义可知
SkE=E fk+1 (Sk+1)=0.4fk+1 (9)+0.3 fk+1 (8)+ 0.3 fk+1(7), (2)
k=5
因为如果在第五周原材料尚未购买，则不管实际价格如何，都必须采取采购策略。
f5(S5)= S5 , 即f5(7) =7，f5(8)=8， f5(9)=9
k=4
S4E =0.4f5 (9)+0.3 f5 (8)+ 0.3 f5(7)=8.1

f4(S4)=min{ S4, S4E}=min{ S4, 8.1}=
所以在第四周如果价格为9，则等待下周购买，如果价格为8或7，则选择采购
k=3
S3E =0.4f4 (9)+0.3 f4(8)+ 0.3 f4(7)=7.74

f3(S3)=min{ S3, S3E}=min{ S3, 7.74}=
所以在第三周如果价格为9或8，则等待下周购买，如果价格为7，则选择购买
k=2
S2E =0.4f3(9)+0.3 f3(8)+ 0.3 f3(7)=7.518

f2(S2)=min{ S2, S2E}=min{ S2, 7.518}=
所以在第二周如果价格为9或8，则等待下周购买，如果价格为7，则选择购买
k=1
S1E =0.4f2(9)+0.3 f2(8)+ 0.3 f2(7)=7.3626

f1(S1)=min{ S1, S1E}=min{ S1, 7.518}=
所以在第一周如果价格为9或8，则等待下周购买，如果价格为7，则选择购买

7.14 某企业有1000万元资金可在三年内每年初对项目A、B投资，若每年初投资项目A，则年末以0.6的概率回收本利2000万元或以0.4的概率丧失全部资金；若投资项目B，则年末以0.1的概率回收本利2000万元或以0.9的概率回收1000万元。假定每年只能投资一次,每次1000万元（有多余资金也不使用），试给出三年末期望总资金最大的投资策略。
K表示第K年的投资方案过程，状态表示每年可投资的资金，表示第K年的投资决策
=
阶段指标=0.6*(1－)（2000+－1000）+(0.1*2000+0.9*1000+－10000)
基本方程

即每年年末期望最大总资金
ｋ

１
１０００
０
１２００
１２００
Ａ
１
１１００
２
１０００
０
１３２０
１３２０
ＡＡ
１
１３００
３
１０００
０
１３９２
１４２０
ＡＡＢ
１
１４２０

期望最大总资金的投资策略为Ａ－Ａ－Ｂ

7.15 某汽车公司的一个型号汽车，每辆年均利润函数r(t)与年均维修费用函数u(t) 如上表中所示 ，购买同型号新汽车每辆20万元，如果汽车公司将汽车卖出，其价格如下表所示，该公司年初有一辆新汽车，试给出四年盈利最大的更新计划。

项目 役龄
0
1
2
3
r (t)
20
18
17.5
15
u(t)
2
2.5
4
6

役龄
0
1
2
3
价格
17
16
15.5
15

解：设备更新问题
回收额的总期数为4
t为某个阶段的设备役龄；
r(t)为从役龄为t的设备得到的年均利润；
u(t)为役龄为t的设备的年均维修费用；
s(t)是役龄为t的设备的处理价格；
新设备的购置价格p=20万元；
四年盈利最大的更新计划。

状态变量选为设备的役龄t
决策只有两种可能，即保留或更新，记为K（保留）或P（更新）。
状态转移方程

阶段效应

t
0
1
2
3
r(t)- μ(t)
18
15.5
13.5
9
s(t)-2
15
14
13.5
13

t
0
1
2
3
f3(t)
18
15.5
13.5
9

t
0
1
2
3
f 3(t)
18
15.5
13.5
9
f 2(t)
33.5
29.5
29
28.5
γ(t)- μ(t)+ f3(t+1)
33.5=18+15.5
29
27

s (t)-2+15.5
30.5=15+15.5
29.5
29
28.5

t
0
1
2
3
f3(t)
18
15.5
13.5
9
f2(t)
33.5
29.5
29
28.5
f1t)
47.5
44.5
43
42.5
γ(t)- μ(t)+ f2(t+1)
47.5
44.5
42

s (t)-2+29.5
44.5
43.5
43
42.5

该企业汽车年初为役龄为0的新汽车。更新方案如图

t
0
1
2
3
f3(t)
18
15.5
13.5
9
f2(t)
33.5
29.5
29
28.5
f1t)
47.5
44.5
43
42.5

精品文档