442
解: 按月份划分阶段，k=1，2，3，4；
状态变量sk表示第k月初的库存量，s1=200，s5=0；
44
决策变量： xk表示第k月售出的货物数量，yk表示第k月购进的货物数量；状态转移方程：sk+1=sk+yk－xk；
允许决策集合：0≤xk≤sk，0≤yk≤600－（sk－xk）；
阶段指标函数为：pkxk－ckyk表示k月份的利润，其中pk为第k月份的单位销售价格，ck为第k月份的单位购货成本；
最优指标函数fk（sk）表示第k月初库存为sk时从第k月至第4月末的最大利润，则动态规划基本方程为：
max[pkxk?ckyk?fk?1(sk?1)]?fk(sk)?0?xk?sk?0?yk?600?(sk?xk)???f5(s5)?0k?4,3,2,1k=4时，
f4(s4)?0?x4?s40?y4?600?(s4?x4)max(44x4?42y4)?44s4x4*=s4y4*=0
k=3时，
f3(s3)???0?x3?s30?y3?600?(s3?x3)0?x3?s30?y3?600?(s3?x3)0?x3?s30?y3?600?(s3?x3)max[39x3?40y3?f4(s4)]maxmax[39x3?40y3?44(s3?y3?x3)](44s3?5x3?4y3)为求出使44s3－5x3+4y3最大的x3，y3，须求解线性规划问题：
maxz?44s3?5x3?4y3?x3?s3???x3?y3?600?s3?x,y?0?33只有两个变量x3，y3，可用图解法也可用单纯形法求解，取得最优解，x3*=0，y3*=600－s3，f3（s3）=40s3+2400
k=2时，
f2(s2)???0?x2?s20?y2?600?(s2?x2)0?x2?s20?y2?600?(s2?x2)0?x2?s20?y2?600?(s2?x2)max[42x2?38y2?f3(s3)]maxmax[42x2?38y2?40(s2?y2?x2)?2400](40s2?2x2?2y2?2400)类似地求得：x2*=s2，y2*=600，f2（s2）=42s2+3600
k=1时，
f1(s1)???0?x1?s10?y1?600?(s1?x1)max[45x1?40y1?f2(s2)][45x1?40y1?42(s1?y1?x1)?3600](42s1?3x1?2y1?3600)0?x1?s10?y1?600?(s1?x1)0?x1?s10?y1?600?(s1?x1)maxmax类似地求得：x1*=s1，y1*=600，f1（s1）=45s1+4800=13800逆向追踪得各月最优购货量及销售量：x1*=s1=200
x2*=s2=s1+ y1*－x1*=600x3*=0
x4*=s4=（s3+ y3*－x3*）=600
y1*=600；
y2*=600；
y3*=600－s3=600－（s2+ y2*－x2*）=0
y4*=0
即1月份销售200件，进货600件，2月份销售600件，进货600件，3月份销售量及进货量均为0，4月份销售600件，不进货，可获得最大总利润13800。
例11某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季节是从10月1日至3月31日。下个销售季节各月的需求预测值如表6.14所示。
月份需求
1040
表6.14 需求预测值
1120
1230
140
230
(单位：双)
320
该鞋店的此种鞋完全从外部生产商进货，进货价每双4美元。进货批量的基本单位是箱，每箱10双。由于存贮空间的限制，每次进货不超过5箱。对应不同的订货批量，进价享受一定的数量折扣，具体数值如表6.15所示。
表6.15 数量折扣数值表
进货批量数量折扣
1箱4%
2箱5%
3箱10%
4箱20%
5箱25%
假设需求是按一定速度均匀发生的，订货不需时间，但订货只能在月初办理一次，每次订货的采购费（与采购数量无关）为10美元。月存贮费按每月月底鞋的存量计，每双0.2美元。由于订货不需时间，所以销售季节外的其他月份的存贮量为“0”。试确定最佳的进货方案，以使总的销售费用最小。
解：阶段：将销售季节6个月中的每一个月作为一个阶段，即k?1,2,?,6；状态变量：第k阶段的状态变量Sk代表第k个月初鞋的存量；决策变量：决策变量xk代表第k个月的采购批量；
状态转移律：Sk?1?Sk?xk?dk（dk是第k个月的需求量）；边界条件：S1?S7?0，f7(S7)?0；
阶段指标函数：rk(Sk,xk)代表第k个月所发生的全部费用，即与采购数量无关的采购费Ck、与采购数量成正比的购置费Gk和存贮费Zk.其中：
0,xk?0；Gk?px?xk；Zk?0.2(Sk?xk?dk)Ck?{10,xk?0最优指标函数：最优指标函数具有如下递推形式
fk(Sk)?min{Ck?Gk?Zk?fk?1(Sk?1)xk?min{Ck?Gk?0.2(Sk?xk?dk)?fk?1(Sk?xk?dk)}xk当k?6时（3月）：
表6.16 k?6时计算结果
S6x6f6（S6）
02086
101048
2000
当k?5时（2月）：
表6.17 k?5时计算结果
x5
S5
01020304050
86504
1349852
17213690
0
10
20
30204168122
40188142
50164
?x5f5(S5)16414212286504
504030000
当k?4时（1月）：
表6.18 k?4时计算结果
x4S40102030405060
164144126
212192174140
250230212178144
282262244210176132
0
10
20
30
40302282264230196152
50304286252218170
?x4f4(S4)302282250212164144126
4030、402010000
当k?3时（12月）：
表6.19 k?3时计算结果
x3S3
0
10
20
30
40
50
?x3f3(S3)010203040
302284
350332302
388370340310
420402372342290
422392362310292
414384332314298
50505000
414384332302284
当k?2时（11月）：
表6.20 k?2时计算结果
x2S2010
462
0
10
20500472
30504454
40474446
50468452
?x2f2(S2)468446
5040
当k?1时（10月）：
表6.21 k?1时计算结果
x1S10
0
10
20
30
40606
50608
x1?40
f1(S1)
606
利用状态转移律，按上述计算的逆序可推算出最优策略：10月份采购4箱（40双），11月份采购5箱（50双），12月份不采购，1月份采购4箱（40双），2月份采购5箱（50双），3月份不采购；最小的销售费用为606美元。
例13 某工厂生产三种产品，各产品重量与利润关系如表6.24所示，现将此三种产品运往市场销售，运输能力总重量不超过6吨，问如何安排运输使总利润最大？
表6.24重量与利润关系表123种类
234单位重量（吨）
80130180单位利润（元）
解： 设xi为装载第i种货物的件数，i=1，2，3，该问题数学模型为：
maxz?80x1?130x2?180x3?2x1?3x2?4x3?6??xi?0且为整数(i?1,2,3)按前述方法建立动态规划模型；k=3时，
f3(s3)?max(180x3)sx3?0,1,?,[3]4计算结果如表6.25所示。
表6.25 k=3时计算结果fs3c3(x3)x30001180f3(s3)x3*0,1,2,34,5,6018001k=2时，
f2(s2)??sx2?0,1,?,[2]3sx2?0,1,?,[2]3max[130x2?f3(s3)]max[130x2?f3(s2?3x2)]计算结果如表6.26所示。
表6.26 k=2时计算结果fs2c2(x2)+ f3(s2－3 x2)x200+00+00+1800+180130+0130+0130+012f2(s2)x2*0,1,234,56260+001301802600102k=1时，f1(s1)?max[80x1?f2(s2)]x1?0,1,2,3?max[80x1?f2(s1?2x1)]x1?0,1,2,3计算结果如表6.27所示。
表6.27 k=1时计算结果fs16c1(x1)+ f2(s1－2 x1)x100+260180+1802160+03240+0f1(s1)x1*2600,1反向追踪得最优方案Ⅰ：x1*=0，x2*=2，x3*=0；最优方案Ⅱ：x1*=1，x2*=0，x3*=1最大总利润为260元。
动态规划例1 求解下列整数规划的最优解
