动态规划例1 求解下列整数规划的最优解

天大,考研,运筹学,管理科学与工程

例1 求解下列整数规划的最优解：

maxZ 4x1 5x2 6x3

3x1 4x2 5x3≤10s..t xj≥0 j 1,2,3 ,xj为整数.

解 （1）建立动态规划模型：

阶段变量：将给每一个变量xj赋值看成一个阶段，划分为3个阶段，且阶段变量k=1,2,3. 设状态变量sk表示从第k阶段到第3阶段约束右端最大值，则sj 10. 设决策变量xk表示第k阶段赋给变量xk的值(k 1,2,3). 状态转移方程：s2 s1 3x1,s3 s2 4x2.

阶段指标：u1(s1,x1) 4x1,u2(s2,x2) 5x2,u3(s3,x3) 6x3. 基本方程；

fk(sk) max uk sk,xk fk 1 sk 1 sk k 3,2,1 0≤x3≤

ak

f(s) 0. 44

其中a1 3,a2 4,a3 5. （1） 用逆序法求解： 当k 3时，

f3 s3 max 6x3 f4 s4 maxs

s

3 0≤x3

5

3

0≤x3≤

5

6x3 ,

而s3 0,1,2,3,4,5,6,7,8,9,10 . x 表示不超过x的最大整数。因此，当s3 0,1,2,3,4时，当s3 56,789,x3 0；

时，当s3 10时，1，2，由此确定f3 s3 .x3可取0或1；x3可取0，

现将有关数据列入表4.1中

表4.1中.

天大,考研,运筹学,管理科学与工程

当时，有

f2 s2 maxs

2

0≤x2≤

4

5x

2

f3 s3 maxs

2

0≤x2≤

4

5x

2

f3 s2 4x2 ,

而s2 0,1,2,3,4,5,6,7,8,9,10 。所以当s2 0,1,2,3时，x2 0；当s2 4,5,6,7时，

x2 0或1；当s2 8,9,10时x2 0,1,2。由此确定f2 s2 。现将有关数据列入表4.2中.

当时,有

f1 s1 maxs

1

0≤x1≤

3

4x f s

1

2

2

1

0≤x1≤

3

maxs

4x f s 3x ,

1

2

1

1

而s1 10,故x1只能取0,1,2,3,由此确定f1 s1 。现将有关数据列入表4.3中。 表 4.3 及

x1 2时,f1(s1)取得最大值13.又由s2 4查表4.2得x2 1,

天大,考研,运筹学,管理科学与工程

s3 0,再由表4.1查得x3 0.因此,最优解为 x 2,x 1,x 0,最优解maxZ 13.

3

3

3

例5 用动态规划方法解下列非线性规划问题

2

max z x1 x2 x3

x1 x2 x3 c

xi 0 i 1,2,3

解： 解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。

按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1，2，3 设状态变量为s1，s2，s3，s4并记s1≤c 取问题中的变量x1，x2，x3为决策变量 状态转移方程为： s3=x3 允许决策集合为： x3=s3

s3+x2=s2 0≤x2≤s2

s2+x1=s1≤c

0≤x1≤s1

v3（x3）=x3，各指标函

各阶段指标函数为：v1（x1）=x1

v2（x2）=x22

数以乘积方式结合，最优指标函数fk（sk）表示从第k阶段初始状态sk出发到第3阶段所得到的最大值，则动态规划基本方程为：

max[vk(xk) fk 1(sk 1)] k 3,2,,1 fk(sk) xk Dk(sk)

f4(s4) 1

用逆序解法由后向前依次求解： k=3时，

f3(s3) max[v3(x3) f4(s4)] max(x3) s3

x3 D3(s3)

x3 s3

x3*=s3

k=2时，

22

f2(s2) max[v2(x2) f3(s3)] max(x2 s3) max[x2 (s2 x2)]

x2 D2(s2)

0 x2 s2

0 x2 s2

令h2（s2，x2）=x22（s2－x2） 用经典解析法求极值点：

dh22

2x2s2 3x2 0 dx2

解得：x2

2s2 3

x2=0（舍）

d2h2

2s2 6x2 2

dx2所以x2

d2h2

2 2s2 0 2

dx2x2 s2

3

2

s2是极大值点。 3

2243

f2(s2) (s2)2(s2 s2) s2

3327

*

x2

2

s2 3

天大,考研,运筹学,管理科学与工程

k=1时，

f1(s1) max[v1(x1) f2(s2)] max(x1

x1 D1(s1)

0 x1 s1

434

s2) max[x1 (s1 x1)3]

0 x1 s12727

令h1(s1,x1) x1

4

(s1 x1)3 27

dh1412

(s1 x1)3 x1(s1 x1)2( 1) 0 dx12727解得：x1

1

s1 4

x1=s1（舍）

d2h11212242422

(s x)( 1) (s x) x(s x) (s1 x1)(2x1 s1)11111112

27272727dx1

d2h192

s1 0 1

27dx12x1 s1

4

1

s1是极大值点。 4

14114s1 (s1 s1)3 s1 427464

14

s1) 64

所以x1

f1(s1)

*x1

1

s1 4

由于s1未知，所以对s1再求极值，

0 s1 c

maxf1(s1) max(

0 s1 c

显然s1=c时，f1（s1）取得最大值

f1(s1)

14

c 64

14

c 64

4313

f2(s2) s2 c

2716f1(s1) f3(s3) s3

1

c 4

反向追踪得各阶段最优决策及最优值： s1=c

3c 41c 4

*x1

*

s2 s1 x1

11

s1 c 4421*

x2 s2 c

32

1

c 4

*

s3 s2 x2 *

x3 s3

*

所以最优解为：x1

11114**

c,x2 c,x3 c,z* c 42464

例6 用动态规划方法解下列非线性规划问题

3

max z x12 x2 x3

x1 x2 x3 6

xj 0 j 1,2,3

解： 按变量个数将原问题分为三个阶段，阶段变量k=1，2，3；

选择xk为决策变量；

天大,考研,运筹学,管理科学与工程

状态变量sk表示第k阶段至第3阶段决策变量之和；

取小区间长度Δ=1，小区间数目m=6/1=6，状态变量sk的取值点为：

k 2 sk 0,1,2,3,4,5,6

s1 6

状态转移方程：sk+1=sk－xk；

允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝ k=1，2，3

xk，sk均在分割点上取值；

阶段指标函数分别为：g1（x1）=x12

g2（x2）=x2

g3（x3）=x33，

最优指标函数fk（sk）表示从第k阶段状态sk出发到第3阶段所得到的最大值，动态规划的基本方程为：

[gk(xk) fk 1(sk 1)] k 3,2,1 fk(sk) 0max xk sk

f4(s4) 1

k=3时，

33f3(s3) max(x3) s3

x3 s3

s3及x3取值点较多，计算结果以表格形式给出，见表6.1-6.3所示。

表6.1 计算结果

天大,考研,运筹学,管理科学与工程

1121123= 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 利润值

将问题分为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)] k 3,2,1 fk(sk) 0max xk sk

f4(s4) 0

天大,考研,运筹学,管理科学与工程

数值计算如表所示。

表6.5 k=3时计算结果

1231售点，第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<dk时，至少应生产dk－sk，故xk的下限为max（0，dk－sk）每期最大生产能力为6，xk最大不超过6，由于期末库存为0，xk还应小于本期至4期需求之和减去本期的库存量， dj sk，所以xk的上限为min（ dj sk，6），故有：

j k

j k

4

4

Dk（sk）=｛xk| max（0，dk－sk）≤xk≤min（ dj sk，6）｝

j k

4

阶段指标函数rk（sk，xk）表示第k期的生产费用与存贮费用之和：

xk 0 0.5sk

rk(sk,xk)

xk 1,2,3,4,5,6 3 xk 0.5sk

最优指标函数fk（sk）表示第k期库存为sk到第4期末的生产与存贮最低费用，动态规划基本方程为：

min[rk(sk,xk) fk 1(sk 1)] k 4,3,2,1 fk(sk) xk Dk(sk)

f5(s5) 0

先求出各状态允许状态集合及允许决策集合，如表6.8所示。

表6.8 状态允许状态集合及允许决策集合

由基本方程计算各阶段策略，结果如下表所示。

天大,考研,运筹学,管理科学与工程

3 4

1* 0*

5.5 2

0 0

0 0

5.5* 2*

s3

x3 2 3 4 5 6* 1 2 3 4 5* 0* 1 2 3 4 0* 1 2 3 0* 1 2 0* 1 0*

表 6.10 k=3 时计算结果 x3 0 0.5s3 r3 ( s3 , x3 ) s4= s3+ x3-2 3 x3 0.5s3 x3 05 6 7 8 9 4.5 5.5 6.5 7.5 8.5 1 5 6 7 8 1.5 5.5 6.5 7.5 2 6 7 2.5 6.5 3 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 1 2 3 4 2 3 4 3 4 4

f4(s4) 7 6.5 6 5.5 2 7 6.5 6 5.5 2 7 6.5 6 5.5 2 6.5 6 5.5 2 6 5.5 2 5.5 2 2

f3(s3) 12 12.5 13 13.5 11* 11.5 12 12.5 13 10.5* 8* 11.5 12 12.5 10 8* 11.5 12 9.5 8* 11.5 9 8* 8.5 5*

0

1

2

3

4 5 6

表 6.11s2 x2

k=2 时计算结果s3= s2+ x2-3 f3(s3) f2(s2)

x2 0 0.5s 2 r2 ( s 2 , x 2 ) 3 x2 0.5s 2 x2 06 7 8 9 5.5 6.5 7.5 8.5 9.5 5 6 7 8 9

3 0 4 5*

0 1 2 3 0 1 2 3 4 0 1 2 3 4

11 10.5 8 8 11 10.5 8 8 8 11 10.5 8 8 8

17 17.5 16* 17 16.5 17 15.5* 16.5 17.5 16 16.5 15* 16 17

6 2 3 1 4*

5 6 1 2 2 3*

4 5

天大,考研,运筹学,管理科学与工程

1223344生产5个单位，第3时期生产6个单位，第2，4时期不生产，可使总费用最小，最小费用为20.5千元。

例10 （库存—销售问题）

设某公司计划在1至4月份从事某种商品经营。已知仓库最多可存储600件这种商品，已知1月初存货200件，根据预测知1至4月份各月的单位购货成本及销售价格如表6.13所示，每月只能销售本月初的库存，当月进货供以后各月销售，问如何安排进货量和销售量，使该公司四个月获得利润最大（假设四月底库存为零）。

表6.13 单位购货成本及销售价格

状态变量sk表示第k月初的库存量，s1=200，s5=0；

决策变量： 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)] k 4,3,2,1 fk(sk)

0 xk sk 0 yk 600 (sk xk)

f5(s5) 0

k=4时，

f4(s4)

0 x4 s4

0 y4 600 (s4 x4)

max

(44x4 42y4) 44s4

x4*=s4 y4*=0

k=3时，

f3(s3)

0 x3 s3

0 y3 600 (s3 x3)0 x3 s3

0 y3 600 (s3 x3)0 x3 s3

0 y3 600 (s3 x3)

max

[39x3 40y3 f4(s4)]

maxmax

[39x3 40y3 44(s3 y3 x3)] (44s3 5x3 4y3)

为求出使44s3－5x3+4y3最大的x3，y3，须求解线性规划问题：

max z 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 s2

0 y2 600 (s2 x2)0 x2 s2

0 y2 600 (s2 x2)0 x2 s2

0 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 s1

0 y1 600 (s1 x1)

max

[45x1 40y1 f2(s2)]

[45x1 40y1 42(s1 y1 x1) 3600] (42s1 3x1 2y1 3600)

0 x1 s1

0 y1 600 (s1 x1)0 x1 s1

0 y1 600 (s1 x1)

maxmax

类似地求得：x1*=s1，y1*=600，f1（s1）=45s1+4800=13800 逆向追踪得各月最优购货量及销售量： x1*=s1=200 x3*=0

y1*=600；

y2*=600； y4*=0

y3*=600－s3=600－（s2+ y2*－x2*）=0

x2*=s2=s1+ y1*－x1*=600

x4*=s4=（s3+ y3*－x3*）=600

即1月份销售200件，进货600件，2月份销售600件，进货600件，3月份销售量及进货量均为0，4月份销售600件，不进货，可获得最大总利润13800。

例11某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季节是从10月1日至3月31日。下个销售季节各月的需求预测值如表6.14所示。

表6.14 需求预测值 (单位：双)

该鞋店的此种鞋完全从外部生产商进货，进货价每双4美元。进货批量的基本单位是箱，每箱10双。由于存贮空间的限制，每次进货不超过5箱。对应不同的订货批量，进价享受一定的数量折扣，具体数值如表6.15所示。

表6.15 数量折扣数值表

假设需求是按一定速度均匀发生的，订货不需时间，但订货只能在月初办理一次，每次订货的采购费（与采购数量无关）为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月）：

天大,考研,运筹学,管理科学与工程

利用状态转移律，按上述计算的逆序可推算出最优策略：10月份采购4箱（40双），11月份采购5箱（50双），12月份不采购，1月份采购4箱（40双），2月份采购5箱（50双），3月份不采购；最小的销售费用为606美元。 例13 某工厂生产三种产品，各产品重量与利润关系如表6.24所示，现将

此三种产品运往市场销售，运输能力总重量不超过6吨，问如何安排运输使总利润最大？

imax z 80x1 130x2 180x3

2x1 3x2 4x3

6

xi 0且为整数(i 1,2,3)

按前述方法建立动态规划模型； k=3时，

f3(s3) max(180x3)

s

x3 0,1, ,[3]

4

计算结果如表6.25所示。

天大,考研,运筹学,管理科学与工程

f2(s2)

s

x2 0,1, ,[2]

3s

x2 0,1, ,[2]

3

max[130x2 f3(s3)]

max[130x2 f3(s2 3x2)]

计算结果如表6.26所示。

f1(s1) max[80x1 f2(s2)]

x1 0,1,2,3

max[80x1 f2(s1 2x1)]

x1 0,1,2,3

计算结果如表6.27所示。

12312x3*=1最大总利润为260元。

本文来源：https://www.bwwdw.com/article/wgp4.html