01234560000000
1×01×11×81×271×641×125
2×02×12×82×272×64
3×03×13×83×27
4×04×14×8
5×05×1
6×0
0018276412800,111112
表6.3 计算结果fs16x12 f2(s1－x1)f1(s1)0011×6424×2739×8416×1525×0636×01082x1*x1由表6.3知，x1*=2，s1=6，则s2= s1－x1*=6－2=4，查表6.2得：x2*=1，则s3= s2－x2*=4－1=3，查表6.1得：x3*=3，所以最优解为：x1*=2，x2*=1，x3*=3，f1(s1)=108。
上面讨论的问题仅有一个约束条件。对具有多个约束条件的问题，同样可以用动态规划方法求解，但这时是一个多维动态规划问题，解法上比较繁琐一些。
例7 某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表6.4所示。试问在各地区如何设置销售点可使每月总利润最大。
表6.4 利润值
地区123
销售点
0000
1161210
2251714
3302116
4322217
解： 如前所述，建立动态规划数学模型：将问题分为3个阶段，k=1，2，3；
决策变量xk表示分配给第k个地区的销售点数；
状态变量为sk表示分配给第k个至第3个地区的销售点总数；状态转移方程：sk+1=sk－xk，其中s1=4；允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝
阶段指标函数：gk（xk）表示xk个销售点分配给第k个地区所获得的利润；最优指标函数fk（sk）表示将数量为sk的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：
[gk(xk)?fk?1(sk?xk)]??fk(sk)?0max?xk?sk???f4(s4)?0k?3,2,1数值计算如表所示。
表6.5 k=3时计算结果
fs301234g3（x3）f3(s3)0010141617123401014161701234x3*x3表6.6 k=2时计算结果fs201234g2(x2)+f3(s2－x2)x2000+100+140+160+1712+012+1012+1412+1617+017+1017+1421+021+1022+01234f2(s2)x2*01222273101122,3表6.7 k=1时计算结果fs14g1(x1)+f2(s1－x1)x100+31116+27225+22330+12432+0f1(s1)x1*472所以最优解为：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。
例9 （生产—库存问题）
某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提
下总成本最小。
解: 以每个时期作为一个阶段，该问题分为4个阶段，k=1，2，3，4；决策变量xk表示第k阶段生产的产品数；状态变量sk表示第k阶段初的库存量；
以dk表示第k阶段的需求，则状态转移方程：sk+1=sk+xk－dk；k=4，3，2，1由于期初及期末库存为0，所以s1=0，s5=0；
允许决策集合Dk（sk）的确定：当sk≥dk时，xk可以为0，当sk j?kj?k44Dk（sk）=｛xk| max（0，dk－sk）≤xk≤min（?dj?sk，6）｝ j?k4阶段指标函数rk（sk，xk）表示第k期的生产费用与存贮费用之和： ?0.5skrk(sk,xk)???3?xk?0.5sk用，动态规划基本方程为： xk?0xk?1,2,3,4,5,6最优指标函数fk（sk）表示第k期库存为sk到第4期末的生产与存贮最低费 min[rk(sk,xk)?fk?1(sk?1)]??fk(sk)?xk?Dk(sk)???f5(s5)?0k?4,3,2,1先求出各状态允许状态集合及允许决策集合，如表6.8所示。 表6.8 状态允许状态集合及允许决策集合 s1D1(s 1)s2D2(s2)s3D3(s3)s4D4(s4) 0｛2,3,4,5,6｝0 1 2 3｛0,1,2,3,4,5,6 ｝ 3｛0,1,2,3｝ 3｛1｝ 4｛0,1,2,3,4,5｝4｛0,1,2｝ 4｛0｝ 5 6 ｛3,4,5,6｝｛2,3,4,5,6｝｛1,2,3,4,5,6｝0 1 2 ｛2,3,4,5,6｝｛1,2,3,4,5｝｛0,1,2,3,4｝ 0｛4｝ 1｛3｝ 2｛2｝ ｛0,1｝｛0｝ 由基本方程计算各阶段策略，结果如下表所示。 表6.9 k=4时计算结果 s401234 x44*3*2*1*0* x4?0?0.5s4r4(s4,x4)???3?x4?0.5s4x4?076.565.52 s500000 f5(s5)00000 f4(s4)7*6.5*6*5.5*2* s3x323456*12345*0*12340*1230*120*10* 表6.10 k=3时计算结果 x3?0?0.5s3r3(s3,x3)??s4= s3+ x3－2 ?3?x3?0.5s3x3?0567894.55.56.57.58.5156781.55.56.57.52672.56.53 0123401234012341234234344 f4(s4)76.565.5276.565.5276.565.526.565.5265.525.522 f3(s3)1212.51313.511*11.51212.51310.5*8*11.51212.5108*11.5129.58*11.598*8.55* 0 1 2 3 456 表6.11 k=2时计算结果 s2 x23 0 45*623 1 4*56 x2?0?0.5s2r2(s2,x2)???3?x2?0.5s2x2?067895.56.57.58.59.5 s3= s2+ x2－3 012301234 f3(s3)1110.5881110.5888 f2(s2)1717.516*1716.51715.5*16.517.5 12 2 3*4560*12 3 34560*1 4 2345 56789101.55.56.57.58.59.510.52678910 0123450123456123456 1110.588881110.58888510.588885 1616.515*16171812.5*1614.515.516.517.515.512.5*1415161715 s1x1 2345*6 表6.12 k=1时计算结果 x1?0?0.5s1r1(s1,x1)??s2= x1－2 3?x?0.5sx?0111?5 6789 01234 f2(s2)1615.51512.512.5 f1(s1)2121.52220.5*21.5 0 逆向追踪可得：x1*=5，s2=3，x2*=0，s3=0，x3*=6，s4=4，x4*=0，即第1时期生产5个单位，第3时期生产6个单位，第2，4时期不生产，可使总费用最小，最小费用为20.5千元。 例10 （库存—销售问题） 设某公司计划在1至4月份从事某种商品经营。已知仓库最多可存储600件这种商品，已知1月初存货200件，根据预测知1至4月份各月的单位购货成本及销售价格如表6.13所示，每月只能销售本月初的库存，当月进货供以后各月销售，问如何安排进货量和销售量，使该公司四个月获得利润最大（假设四月底库存为零）。 表6.13 单位购货成本及销售价格 月份 123 购货成本C 403840 销售价格P 454239
动态规划例1 求解下列整数规划的最优解
