大二下课程运筹学20172课件or04动态

决胜千运筹帷决胜千运筹帷动态规划动态规划里之外幄之中里之外幄之中1214C132A10649D155106E5113821211102

1214106 10

96

E4 131211

8 10

E55E22E和终点进行分析和讨论分别求C1，C2，C3到D1，D2的最短路87 分析得知：如果经过B1，则走B1-C1-D1-E；A 83592145A B2760E51822

1 1

22n

Sj:j阶段初系统所处状态rj(Sj,Xj):j阶段在状态 S=S1,

, j=1,2,,Xj(Sj)˛Dj(SjSj+1=T(Sj,Xj1,n(S1)=1(S1),X2(S2),,Xn(Snk,n(Sk)=k(Sk),Xk+1(Sk+1),,Xn(SnPk,n(Sk)=k(Sk),Xk+1(Sk+1),,Xn(Snfk(Sk)=Optrk(Sk,Xk)¯rk+1(Sk+1,Xk+1)¯¯rn(Sn,Xnfk(Sk)= k(Sk Xk˛Dk(Skfn+1(Sn+1)=0(or)

k=n,n-Anoptimalhasthepropertythatwhatevertheinitialstateandinitialdecisionare,thenremainingdecisionsmustconstituteanoptimalwithregardtothestateresultingfromfirstdecision.4.4产品，其收益为gi(xi)。问应如何分配，

有4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的有关。三个项目A、B、C的投资效益（万吨）和投入（万元）的关系见下表：

阶段k：每投资一个项目作为一个阶段；状态变量投资第k个项目前的余额；决策变量xk第k个项目的投资额；k=4，f4(s4)=0;k=3，0≤x3≤s3，s4=s3-00000010101102020211203030312213040404132231400000001010110202001120303001221304040213223140v1(s1,x1)v1(s1,x1)+f2(s2)4040113223140

0£ui£si,i第5年第4年第3年第2年第1年

f5(s5)=max5+5(s5-x5)+f6(s60£x5第5年=max5+5第5年0£x5x*=

f4(s4)=max8x4+0£x48x40£x48x40£x4

-x4)+第4年-第4年

+

-x4=maxx0£x4

4=

4…4x*=s44

=max{8x3+5(s3-x3)+13.6[0.7x3+0.9(s3-x3)]}第3年第3年 x

第2年第2年…x

2(产量

第1年第1年 x

(产量

每年投入高负荷运行的机器数以及每年初完好的机器数为：

一个工厂生产某种产品，1～7月份生产成本和产品需={xk|xk‡0,rk+1£sk- 因为s8=0 x7=0，所以 f5(s5)=min{c5x5+f6(s6)}x5˛D5(s5)={x5|x5‡0,r6£s5-r5+x5£H={x5|x5‡0,9-s5£x5£11-D5(s5)={x5|9-s5£x5£11-s5}=10(9-s5)-=min{-3x4-D4(s4)={x4|x4‡0,r5£s4-={x4|x4‡0,r5+r4-s4£x4£H+r4-={x4|x4‡0,5-s4£x4£12-由于在f4(s4)的表达式中x4的系数是-由此f4(s4)=-3(12-s4)-20s4+280=-17s4+244f3(s3)=min=min{13x3+244-=min{13x3+244-17(s3-=min{-4x3-f3(s3)=-4(14-s3)- =min{5x2-13-x2(s2)={x2|13-s2£x2£17-s2}由此f2(s2)=5(13-s2)-13s2+377=min{-7x1-根据题意s1=2D1(s1)={x1|k1 7 0 42 470wi，每件价值ci。现有一只可装载重量为W的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设第i种物品取xi s.t.w1x1+w2x2+…+wnxn≤W

sk+1=

vk=ck

fk(sk)

xk=0,1,,[w/wk

=xk=0,1,,[w/wk

fn+1(sn+1)=i123i123231f3(s3)=

{c3x3+f4(s40£x3£s3/ 0£x3£s3/由题意知，s1=5f1(s1f2(s2f3(s3)*=2s2=s1-2x1=1x2*=0s33x2=1x3以看出，如果背包得容量为W=4，W=3，W=2和

P=PNmax =Ppi(zii=s.t.

NNi=NN

ciz £wiz £i=z 0,

Dk(sk,uk)={x

|0£

£min([sk],[uk])}sk-1

-ck

ck = -wk-

vk=pk(xk

fk(sk,uk)=max{pk(xk)•fk-1(sk-1,uk-xk˛Dk(sk,uk给出具体问题，例4-8 =

-ck,x,kk-

s0= xk˛Dk(sk 124523563123分析状态空间 N-min{cij|j=1,2,3}£sk£10-min{ck+i,j|j=1,2,3} 2£s1£6,5£s2£9,6£s1£10,从状态转