动态规划例1求解下列整数规划的最优解.docx
- 文档编号:14443689
- 上传时间:2023-06-23
- 格式:DOCX
- 页数:30
- 大小:69.57KB
动态规划例1求解下列整数规划的最优解.docx
《动态规划例1求解下列整数规划的最优解.docx》由会员分享,可在线阅读,更多相关《动态规划例1求解下列整数规划的最优解.docx(30页珍藏版)》请在冰点文库上搜索。
动态规划例1求解下列整数规划的最优解
例1求解下列整数规划的最优解:
maxZ4x-i5x26x3
3xi4x25x3w10st
■Xj>0j1,2,3,Xj为整数•
解
(1)建立动态规划模型:
阶段变量:
将给每一个变量Xj赋值看成一个阶段,划分为3个阶段,且阶段变量k=1,2,3.
设状态变量Sk表示从第k阶段到第3阶段约束右端最大值,则Sj10.
设决策变量Xk表示第k阶段赋给变量Xk的值(k1,2,3).
状态转移方程:
s33x1,s3s24x2.
4X1,U2(S2,X2)5X2,U3(S3,X3)6X3.
基本方程;
用逆序法求解:
3时,
x30;当S35,6,7,8,9时,x3可取0或1;当S310时,x3可取0,1,2,由此确定f3S3
现将有关数据列入表4.1中
表4.1中.
乙
6X3fqS)
f3(S3)
*
X3
0
1
2
0
0
0
0
1
0
0
0
2
0
0
0
3
0
0
0
4
0
0
0
5
0
6
6
1
6
0
6
6
1
7
0
6
6
1
8
0
6
6
1
9
0
6
6
1
10
0
6
12
12
2
当k2时,有
而S20,1,2,3,4,5,6,7,8,9,10。
所以当s2Q.1,2,3时,x20;当s4,5,6,7时,
X20或1;当S28,9,10时X20,1,2。
由此确定f2s。
现将有关数据列入表4.2中.
表4.2
S2\
5X2彳3(S2
4X2)
f3(S3)
*
X3
S3
0
1
2
0
0+0
0
0
0
1
0+0
0
0
1
2
0+0
0
0
2
3
0+0
0
0
3
4
0+0
5+0
5
1
0
5
0+6
5+0
6
0
5
6
0+6
5+0
6
0
6
7
0+6
5+0
6
0
7
8
0+6
5+0
10+0
10
2
0
9
0+6
5+6
10+0
11
1
5
10
0+12
5+6
10+0
12
0
10
当k1时,有
f1S|max4为f2s,max4为f2S|3x1
S1S1
0=X1w0=X1w
1313
而S,10,故X1只能取0,1,2,3,由此确定f1§。
现将有关数据列入表4.3中。
表4.3
4%f2
S]3x1
f1Si
*
X1
S2
、0
1
2
3
10
0+12
4+6
8+5
12+0
13
2
4
按计算顺序反推,由表4.3可知,当
x12时,f1(s1)取得最大值13.又由S24查表4.2得x21,及
0,再由表4.1查得x30因此,最优解为
x32,x31,x30,最优解maxZ13.
例5用动态规划方法解下列非线性规划问题
maxzx1x;x3
x1x2x3c
人0i1,2,3
解:
解决这一类静态规划问题,需要人为地赋予时间概念,从而将该问题转化为多阶段决策过程
按问题的变量个数划分阶段,把它看作一个三阶段决策问题,k=1,2,3
设状态变量为SI,S2,S3,S4并记S1 取问题中的变量XI,X2,X3为决策变量 状态转移方程为: S3=X3S3+X2=S2S2+X1=S1 允许决策集合为: X3=S30 各阶段指标函数为: Vi(Xi)=XiV2(X2)=X2V3(X3)=X3,各指标函 数以乘积方式结合,最优指标函数fk(Sk)表示从第k阶段初始状态Sk出发到第3阶段所得到的最大值,则动态规划基本方程为: fk(Sk)max、[Vk(Xk)fki(Sk1)] XkDk(Sk) f4(S4)1 用逆序解法由后向前依次求解: k=3时, f3(S3) k3,2,,1 X3RDaXS3)[V3(X3)f4(S4)] max(x3) 为S3 S3 * X3=S3 f;(S2) maxMg)fag] 沁D2(s2) max(x; 0X2S2 S3) max[x;(s2 0X2S2 X2)] k=2时, 2 令h2(S2,X2)=X2(S2—X2) 用经典解析法求极值点: dh2 dx2 2x? S2 3x; 解得: X2 2 3S2 X2=0(舍) d2h2 dxj 2S2 6X2 d2h2 dx: X2 2 3S2 2S2 所以X2 2 3S2 是极大值点。 f2(S2) (|S2)2(S2討寺 X2 k=1时, fi(Si) maX[vi(Xi)f2(S2)]maX(x- XD(S)0XiS —s2)max[xi 270Xs 43 ^7(SiXi)] 令hi(s Xi)Xi2y(SiXi)3 dx27 27 解得: xi 1 4s1 X1=S1 2/(s27 X-)2( 2 1)(s- 27 12 3 (舍) d2h Xi)2 d2h dx; dhi4 Xi)2(i) HXi(S Xi) ^(Si 27 xj(2xiSi) dx: Xi —s20 27 i 所以Xi-Si是极大值点。 4 -S—(s--s-)3 427464 由于Si未知,所以对Si再求极值, 4maxf-(Si)max(s-) 0s-c0s-c64 fi(Si) 丄Si4 Xi i ;Si 显然Si=c时,fi(SI)取得最大值 fi(Si) i c 64 Si=c x- Si c fi(S-) 1 4 4 64 *3 * 2 1 f2(s2) 4 S2Si xic X2 S2 c 27 4 3 2 * * 1 f3(S3) S3S2 x2c 4 X3 S3 4 c S3 所以最优解为: X-* * c,X2 * c,X3 1*c,z 4c 反向追踪得各阶段最优决策及最优值: 4 c4 3 S2 4 3 c i6 1 -c 4 例6用动态规划方法解下列非线性规划问题 23 maxzxiX2X3 xiX2X36 Xj0ji,2,3 解: 按变量个数将原问题分为三个阶段,阶段变量k=i,2,3; 选择Xk为决策变量; 状态变量sk表示第k阶段至第3阶段决策变量之和; 取小区间长度△=1,小区间数目m=6/仁6,状态变量sk的取值点为: sk0,1,2,3,4,5,6k2s16 状态转移方程: Sk+1=Sk—Xk; 允许决策集合: Dk(Sk)={Xk|0 Xk,Sk均在分割点上取值; 阶段指标函数分别为: g1(X1)=X12g2(X2)=X2g3(X3)=X33, 最优指标函数fk(Sk)表示从第k阶段状态Sk出发到第3阶段所得到的最大值,动态规划的基本方程为: fk(Sk)0max[gk(xQfk1(SkJ]k3,2,1 0xkSk f4(S4)1 k=3时, f3(S3)max(x;)S3 x32 S3及X3取值点较多,计算结果以表格形式给出,见表6.1-6.3所示。 表6.1计算结果 • S3 X3 f3(S3) * X3 0 1 2 3 4 5 6 0 0 0 0 1 1 1 1 2 8 8 2 3 27 27 3 4 64 64 4 5 125 125 5 6 216 216 6 0 0 0 0 1 0 1X0 0 0,1 2 0 1X1 2X0 1 1 3 0 1X8 2X1 3X0 8 1 4 0 1X27 2X8 3X1 4X0 27 1 5 0 1X64 2X27 3X8 4X1 5X0 64 1 6 0 1X125 2X64 3X27 4X8 5X1 6X0 128 2 表6.3计算结果 * 2 Xif2(Si—Xi) fi(Si) * xi 0 1 2 3 4 5 6 6 0 1X64 4X27 9X8 16X1 25X0 36X0 108 2 由表6.3知,xi=2,si=6,贝US2=si—xi=6—2=4,查表6.2得: x2=1,贝Us3=s2—x2=4—1=3,查表6.1得: x3=3,所以最优解为: xi=2,=1,x3=3,fi(si)=108。 上面讨论的问题仅有一个约束条件。 对具有多个约束条件的问题,同样可以用动态规划方法求解,但这时是一个多维动态规划问题,解法上比较繁琐一些。 例7某公司打算在3个不同的地区设置4个销售点,根据市场部门估计,在不同地区设置不同数量的销售点每月可得到的利润如表6.4所示。 试问在各地 区如何设置销售点可使每月总利润最大。 表6.4利润值 地区 销售点 0 1 2 3 4 1 0 16 25 30 32 2 0 12 17 21 22 3 0 10 14 16 17 解: 如前所述,建立动态规划数学模型: 将问题分为3个阶段,k=1,2,3; 决策变量Xk表示分配给第k个地区的销售点数; 状态变量为sk表示分配给第k个至第3个地区的销售点总数; 状态转移方程: Sk+1=Sk—Xk,其中S1=4; 允许决策集合: Dk(Sk)={Xk|0 阶段指标函数: gk(Xk)表示Xk个销售点分配给第k个地区所获得的利润;最优指标函数fk(Sk)表示将数量为Sk的销售点分配给第k个至第3个地区所得到的最大利润,动态规划基本方程为: fk(Sk)maX[gk(Xk)fk1(SkxQ]k3,2,1 0XkSk f4$)0 数值计算如表所示 表6.5k=3时计算结果 s3X g3(X3) f3(S3) * X3 0 1 2 3 4 0 0 0 0 1 10 10 1 2 14 14 2 3 16 16 3 4 17 17 4 表6.6k=2时计算结果 7 g2(x2)+f3(s2-X2) f2(S2) * X2 0 1 2 3 4 0 0 0 0 1 0+10 12+0 12 1 2 0+14 12+10 17+0 22 1 3 0+16 12+14 17+10 21+0 27 2 4 0+17 12+16 17+14 21+10 22+0 31 2,3 表6.7k=1时计算结果 S1 g1(X1)+f2(S1-X1) f1(S1) * X1 0 1 2 3 4 4 0+31 16+27 25+22 30+12 32+0 47 2 所以最优解为: xi=2,X2=1,X3=1,fi⑷=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+i=sk+xk—dk;k=4,3,2,1 由于期初及期末库存为0,所以S1=O,s5=0; 允许决策集合Dk(Sk)的确定: 当Sk>dk时,xk可以为0,当Skvdk时,至少应生产dk—sk,故xk的下限为max(0,dk—sk)每期最大生产能力为6,xk最大不超过6,由于期末库存为0,Xk还应小于本期至4期需求之和减去本期的库存 44 量,djsk,所以xk的上限为min(djsk,6),故有: jkjk 4 Dk(sk)={xk|max(0,dk—sk) 「k(Sk,Xk) 0.5sk Xk Xk 0.5sk Xk123,4,5,6 阶段指标函数rk(sk,xk)表示第k期的生产费用与存贮费用之和: 最优指标函数fk(Sk)表示第k期库存为Sk到第4期末的生产与存贮最低费 用,动态规划基本方程为: fg%倔2肿6,兀)fk1(sk1)]k4,3,21 f5(S5)0 先求出各状态允许状态集合及允许决策集合,如表6.8所示。 表6.8状态允许状态集合及允许决策集合 S1 0 D1(s 1) {234,5,6 } S2 0 1 2 3 4 D2(S 2) {3,4,5,6} {234,5,6 } {1,2,3,4,5, 6} {0,1,2,3,4,5, 6} {0,1,2,3,4, 5} S3 0 1 2 3 4 5 6 D3(S 3) {234,5,6 } {123,4,5 } {0,1,2,3,4} {0,1,2,3} {0,1,2} {0,1 } {0} S4 0 1 2 3 4 D4(S 4) {4} {3} {2} {1} {0} 由基本方程计算各阶段策略,结果如下表所示。 表6.9k=4时计算结果 S4 X4 0.5s4x40 r4(S4,X4) 3x40.5s4x40 S5 f5(S5) f4(S4) 0 * 4 7 0 0 * 7 1 * 3 6.5 0 0 * 6.5 2 * 2 6 0 0 * 6 3 1* 5.5 0 0 5.5* 4 * 0 2 0 0 * 2 表6.10k=3时计算结果 S3 X3 「3(S3,X3) 0.5s3 3x30.5S3 X30 X30 S4=S3+X3—2 f4(S4) f3(S3) 2: 5 0 7 12 3 6 1 6.5 12.5 0 4 7 2 6 13 5 8 3 5.5 13.5 * 6 9 4 2 * 11 1 4.5 0 7 11.5 2 5.5 1 6.5 12 1 3 6.5 2 6 12.5 4 7.5 3 5.5 13 5 8.5 4 2 10.5 * 0 1 0 「7 * 8 1 5 1 6.5 11.5 2 2 6 2 6 12 3 7 3 5.5 12.5 4 8 4 2 10 * 0 1.5 1 6.5 * 8 3 1 5.5 2 6 11.5 2 6.5 3 5.5 12 3 7.5 4 2 9.5 * 0 2 2 6 8* 4 1 6 3 5.5 11.5 2 7 4 2 9 5 * 0 2.5 r3 「5.5 * 8 1 6.5 4 2 8.5 6 * 0 3 4 2 * 5 表6.11k=2时计算结果 S2 X2 「2("2) 0.5s2 3X2 X20 0.5s2x20 S3=S2+X2—3 f3(S3) f2(S2) 3 6 0 11 17 4 7 1 10.5 17.5 0 5 8 2 8 16 6 9 3 8 17 2 5.5 0 11 16.5 3 6.5 1 10.5 17 1 * 4 7.5 2 8 * 15.5 5 8.5 3 8 16.5 6 9.5 4 8 17.5 1 5 0 11 16 2 6 1 10.5 16.5 2 * 3 7 2 8 * 15 4 8 3 8 16 5 9 4 8 17 6 10 5 8 18 * 0 1.5 0 11 * 12.5 1 5.5 1 10.5 16 2 6.5 2 8 14.5 3 3 7.5 3 8 15.5 4 8.5 4 8 16.5 5 9.5 5 8 17.5 6 10.5 6 5 15.5 * 0 2 1 10.5 * 12.5 1 6 2 8 14 2 7 3 8 15 4 3 8 4 8 16 4 9 5 8 17 5 10 6 5 15 表6.12k=1时计算结果 S1 X1 0.5$ 3x1 X1 0.5S]x1 0 0 S2=X1—2 f2(S2) f1(S1) 2 5 0 16 21 3 6 1 15.5 21.5 0 4 7 2 15 22 * 5 8 3 12.5 * 20.5 6 9 4 12.5 21.5 : 、\**** 逆向追踪可得: 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单位购货成本及销售价格 月份 购货成本C 销售价格P 1 40 45 2 38 42 3 40 39 4 42 44 解: 按月份划分阶段,k=1,2,3,4; 状态变量Sk表示第k月初的库存量,S1=200,S5=0; 决策变量: xk表示第k月售出的货物数量,yk表示第k月购进的货物数量;状态转移方程: Sk+1=Sk+yk—xk; 允许决策集合: 0WXk 阶段指标函数为: pkXk—ckyk表示k月份的利润,其中pk为第k月份的单位销售价格,a为第k月份的单位购货成本; fk(Sk) 0XkS? aX[PkXkCkyk 0yk600(s,x<) fk1(Sk1)] k4,3,2,1 最优指标函数fk(Sk)表示第k月初库存为Sk时从第k月至第4月末的最大利润,则动态规划基本方程为: f5(S5)0 f3(S3)n max [39x3 0 X3 0 y3 600(S3 X3) max [39x3 0 0 y3 600(S3 X3) 0 max (44s3 0 y3 600(S3 X3) 40y3fHsJ] 40y344(S3yX3)]
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 求解 下列 整数 最优
![提示](https://static.bingdoc.com/images/bang_tan.gif)