胡运权运筹学第七章习题集解.doc
《胡运权运筹学第七章习题集解.doc》由会员分享，可在线阅读，更多相关《胡运权运筹学第七章习题集解.doc（23页珍藏版）》请在冰点文库上搜索。
,.
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;
阶段指标函数：
Vk（SkＵk）；
最优指标函数：
fk（Sk）=max{Vk（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{V2（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=2s+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{2s+d+1000+3d+0.005d+6000+2（1000-s）+0.005（1000-s）}
=min{9000+4d+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≥0dk+1≤Xk+1｝
=｛rk︱dk+1≤Xk+rk-dk｝
阶段指标：
Ckrk+PkXk
f5（X5）=0X5=0
fk（Xk）=min｛Vk（Xk,rk）+fk+1（Xk+1）｝
=min｛Ckrk+PkXk+fk+1（Xk+rk-dk）｝
对于k=4X5=0r4=0X4=d4
f4（X4）=min｛V4（X4,r4）+f5（X5）｝
=min｛30X4｝
=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-d3r3+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）={r2r20d3x2+r3-d2}
={r2r20d3+d2-x2r3}
={r2r2085-x2r3}
f2（x2）=min｛96325-715x2+115x2+9775｝
=min{106100-830x2}
当k=1时
f1（x1）=min｛850r1+30x1+106100-830（x1+r1-50）｝
=min{147600-800x1+20r1}
r1（x1）=｛r1︱r1≥0d2+d1﹣x1≤r1｝
=｛r1︱r1≥095﹣x1≤r1｝
f1（x1）=min｛147600-800x1+20（95﹣X1）｝
=min｛149500-820x1｝
根据题意x1=0r1*=95﹣x1
f1（x1）=149500r1*=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=Efk+1（Sk+1）=0.4fk+1（9）+0.3fk+1（8）+0.3fk+1（7）,
（2）
k=5
因为如果在第五周原材料尚未购买，则不管实际价格如何，都必须采取采购策略。
f5（S5）=S5,即f5（7）=7，f5（8）=8，f5（9）=9
k=4
S4E=0.4f5（9）+0.3f5（8）+0.3f5（7）=8.1
f4（S4）=min{S4,S4E}=min{S4,8.1}=
所以在第四周如果价格为9，则等待下周购买，如果价格为8或7，则选择采购
k=3
S3E=0.4f4（9）+0.3f4（8）+0.3f4（7）=7.74
f3（S3）=min{S3,S3E}=min{S3,7.74}=
所以在第三周如果价格为9或8，则等待下周购买，如果价格为7，则选择购买
k=2
S2E=0.4f3（9）+0.3f3（8）+0.3f3（7）=7.518
f2（S2）=min{S2,S2E}=min{S2,7.518}=
所以在第二周如果价格为9或8，则等待下周购买，如果价格为7，则选择购买
k=1
S1E=0.4f2（9）+0.3f2（8）+0.3f2（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
f3（t）
18
15.5
13.5
9
f2（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
升级会员 