胡运权运筹学第七章习题解

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

解：

设阶段变量：k=1,2,3

状态变量：xk 第k个月初的库存量 决策变量：dk第k个月的生产量 状态转移方程：xk 1 xk rk dk 阶段指标：v(xk,dk) ckdk

由于在4月末，仓库存量为0，所以对于k=4阶段来说有两种决策：

5+4=9 x4 0

f(x4)=

1 x4 1

对K=3 f(x3) 5x3 4 f(x4)

K=2

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

7.4某公司有资金4万元，可向A，B，C三个项目投资，已知各项目不同投资额的相应效益值如表7-20所示，问如何分配资金可使总效益最大。 表 7-20

解：

1,2,3,4}，每一个项目表示一个阶段; 设阶段变量k，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

k=2, 0≤Ｕ2≤S2

k=1, 0≤Ｕ1≤S

1 所以根据以上计算，可以得到获得总效益最大的资金分配方案为（1，2，1）.

7.5为了保证某设备正常运行,须对串联工作的三种不同零件A1,A2,A3,分别确定备件数量。若增加备用零件数量，可提高设备正常运转的可靠性，但费用要增加，而总投资额为8千元。已知备用零件数和他的可靠性和费用关系如表所视，求

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

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

⎧

⎪f(s)=max{R(x)f(s)}kkKkk=1k+1⎪⎪

⎨f4(s4)=1⎪3

⎪CK(xk)≤SK-∑Ci(1)⎪i

=k+1⎩

所以有上可知当A1；A2；A3；分别为k=1;k=2;k=3时S1=8; S2=5,6,7; S3=1,2,3,4;

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

7.7 某工厂接受一项特殊产品订货，要在三个月后提供某种产品1000kg，一次交货。由于该产品用途特殊，该厂原无存货，交货后也不留库存。已知生产费用与月产量关系为：C=1000+3d+0.005d2，其中d为月产量（kg），C为该月费用（元）。每月库存成本为2元/kg，库存量按月初与月末存储量的平均数计算，问如何决定3个月的产量是总费用最小。 解：用动态规划法求解

阶段k：每一个月为一个阶段k=1,2,3 状态变量sk：第k个月初的库存量 决策变量dk：第k个月的生产量 状态转移方程：sk+1= sk+dk

最优指标函数：fk( sk)：第k个月状态为sk时到第3个月末的总费用最小

则第k个月的库存费用为：Ek= （sk +sk+1）/2⨯2= sk +sk+1=2 sk+dk

s1=0，d1+d2+d3=1000 当k=3时 f3(s3)=min{E3+C3}

=min{2s3+d3+1000+ 3d3+0.005d32} = min{3000+ 2d3+0.005d32} = 3000+2(1000- s3)+0.005(1000- s3)2 当k=2时

f2(s2)=min{E2+C2+ f3(s3)}

=min{2s2+d2+1000+3d2+0.005d22+3000+2(1000-

s3)+0.005(1000- s3)2}

=min{2s2+1000+4d2+0.005d22+3000+2(1000-s2-d2)+0.005(1000- s2-d2)2}

=min{6000+2d2+0.005d22+0.005(1000- s2-d2)2} 只有当d*2=1000- s2 时f2(s2)取最小值6000+2（1000-

s2）+0.005（1000- s2）2 f1(s1)=min{E1+C1+ f2(s2)}

=min{2 s1+ d1+1000+3 d1+0.005d12+6000+2

（1000- s2）+0.005（1000- s2）2}

=min{9000+4 d1+0.005d12+0.005（1000- d1）2}

=min{14000-6d1+0.01d12}

只有当d1*=300时f1(s1)取最小值13100元 此时s2= d1+ s1=300

那么d*2=1000- s2=700，f2(s2)=9850元 d*3=1000-d1-d2=0，f3(s3)=3000元

即：三个月的产量分别为300、700、0时，总费用最小。

7-11.某工厂生产三种产品，各产品重量与利润关系如表。现将此三种产品运往市场出售，运

解：设:Xk：第K种产品的数目；

Vk：第K种产品的利润；

Sk：第K种产品之初的总重量；Sk+1=Sk-XkWk; fk (Sk)：第K~3种产品的总价值； fk（Sk）=max{XkVk+`fk+1(Sk+1)}

且f4(S4)=0

K=3：f3(S3)=max0≤x

3≤1{V3X3+f4(S4)}=max0≤x3≤1{80X3}

K=2：f2(S2)=max0≤x2≤2{V2X2+f3(S3)}=max0≤x2≤2{130X2+f3(S3-3X2)}

K=1：f1(S1)=max0≤x1≤3{V1X1+f2(S2)}=max0≤x1≤3{80X1+f2(S1-2X1)}

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

7.12 某公司需要对某产品决定未来4个月内每个月的最佳存储量，以使总费用最小。已知各月对该产品的需求量和单位订货费用、存储费用如表7-23所示。假定每月初订货于月末到货并入库，下月开始销售。

解：

阶段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

={r2={r2

r2≥0 d3≤x2+r3-d2 } r2≥0 d3+d2 -x2≤r3 } r2≥0 85-x2≤r3 }

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

设阶段变量k，k∈{1,2,3,4,5},每一周表示一个阶段; 状态变量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

⎧8.1,s4=9

⎪

f4(S4)=min{ S4, S4E}=min{ S4, 8.1}=⎨8,s4=8

⎪7,s=7⎩4

所以在第四周如果价格为9，则等待下周购买，如果价格为8或7，则选择采购 k=3

S3E =0.4f4 (9)+0.3 f4(8)+ 0.3 f4(7)=7.74

⎧7.74,s3=9⎪

f3(S3)=min{ S3, S3E}=min{ S3, 7.74}=⎨7.74,s3=8

⎪7,s=7⎩3

所以在第三周如果价格为9或8，则等待下周购买，如果价格为7，则选择购买 k=2

S2E =0.4f3(9)+0.3 f3(8)+ 0.3 f3(7)=7.518

⎧7.518,s2=9⎪

f2(S2)=min{ S2, S2E}=min{ S2, 7.518}=⎨7.518,s2=8

⎪7,s=7⎩2

所以在第二周如果价格为9或8，则等待下周购买，如果价格为7，则选择购买 k=1

S1E =0.4f2(9)+0.3 f2(8)+ 0.3 f2(7)=7.3626

⎧7.3626,s1=9⎪

f1(S1)=min{ S1, S1E}=min{ S1, 7.518}=⎨7.3626,s1=8

⎪7,s=7⎩1

所以在第一周如果价格为9或8，则等待下周购买，如果价格为7，则选择购买

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

⎧0投资项目AXK=⎨

⎩1投资项目B

阶段指标VK=0.6*(1－XK)（2000+fk－1000）+XK(0.1*2000+0.9*1000+fk－10000) 基本方程

VK+fk-1}⎧fk=MAX{

⎨

⎩f0=0,k=0,1,2,3

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

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

7.15 某汽车公司的一个型号汽车，每辆年均利润函数r(t)与年均维修费用函数u(t) 如上表中所示 ，购买同型号新汽车每辆20万元，如果汽车公司将汽车卖出，其价格如下表所示，

解：设备更新问题

回收额的总期数为4

t为某个阶段的设备役龄；

r(t)为从役龄为t的设备得到的年均利润； u(t)为役龄为t的设备的年均维修费用； s(t)是役龄为t的设备的处理价格； 新设备的购置价格p=20万元； 四年盈利最大的更新计划。

状态变量选为设备的役龄t

决策只有两种可能，即保留或更新，记为K（保留）或P（更新）。 状态转移方程

uk=K⎧γ(t)-μ(t)

rk(t,uk)=⎨

uk=P⎩s(t)-P+γ(0)-μ(0)

阶段效应

⎧K:γ(t)-μ(t)+fk+1(t+1)⎫fk(t)=max⎨⎬ P:s(t)-P+γ(0)-μ(0)+f(1)k+1⎩⎭

uk=K⎧γ(t)-μ(t)

rk(t,uk)=⎨

⎩s(t)-P+γ(0)-μ(0)=s(t)-2uk=P

⎧K:γ(t)-μ(t)⎫

f3(t)=max⎨⎬ ⎩P:s(t)-2⎭

f4(t)=0

⎧K:γ(t)-μ(t)+f3(t+1)⎫

f2(t)=max⎨⎬

P:s(t)-2+15.5⎩⎭

f(t)=max⎧K:γ(t)-μ(t)+f2(t+1)⎫

⎨⎬1

⎩P:s(t)-2+29.5⎭

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