单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,第6章 动态规划应用举例,第1节 资源分配问题,1.1 一维资源分配问题,,资源分配问题可描述如下：设有某种原料，总数量为,a,，分配给,n,个使用者已知第,i,个使用者得到数量,x,i,的该种资源，可创造的收益为,g,i,(,x,i,)问应如何分配该资源，才能使总收益最大用动态规划法处理这种问题时，通常把给各个使用者分配资源的过程分别看成一个阶段，按使用者分成先后,的,n,个阶段即先给第1个使用者分配资源，为第一阶段；再给第2个使用者分配，为第,二,阶段；依此类推，最后给第,n,个使用者分配，为第,n,阶段静态规划模型：,,按使用者划分为,n,个阶段，,k,=1,2,..,,n,；,,取第,k,阶段初（给第,k,个使用者分配资源时）资源的剩余量,s,k,为状态变量，,s,1,=a；,,取分配给第,k,个使用者的资源数量,x,k,为决策变量，0≤,x,k,≤,s,k,(,k,=1,2,…,,n,-1)，,x,n,=,s,n,；,,状态转移方程为,s,k,+1,=,s,k,-,x,k,；,,指标函数为,V,k,n,=,Ʃ,g,j,(,x,j,),；,,基本方程为：,（,k,=,n,-1,…,2,1）,由于资源数量常常要求取整数，则状态变量和决策变量也就取整数，所以求解时常采用列表的形式。
例2 某工业部门根据国家计划安排，拟将五台某种高效率的机器分配给所属的甲、乙、丙三个工厂，各工厂得到不同数量的机器可获得的收益如下表问应如何分配机器，才能使各厂的总效益最大机器数,甲 乙 丙,0,,1,,2,,3,,4,,5,0 0 0,,3 5 4,,7 10 6,,9 11 11,,12 11 12,,13 11 12,解：,分成3个阶段，,k,=1,2,3；,s,k,为状态变量，,s,1,=5；,x,k,为决策变量，0≤,x,k,≤,s,k,，,x,3,=,s,3,；,状态转移方程,s,k,+1,=,s,k,-,x,k,,；,基本方程为：,,,f,k,(s,k,)＝ max {,g,k,(,x,k,)+,f,k,+1,(,s,k,+1,)},k,=,2,1,,,0≤,x,k,≤,s,k,,,,f,3,(,s,3,)＝,s,3,(,x,3,*,=,s,3,),,当,k,=3时：,s,3,,x,3,,g,3,(,x,3,),,f,3,(,s,3,),0,0,0*,0,1,1,4*,4,2,2,6*,6,3,3,11*,11,4,4,12*,12,5,5,12*,12,当,k,=2时：,s,2,,x,2,,g,2,(,x,2,)+,f,3,(,s,3,),,f,2,(,s,2,),0,0,0+0=0*,0,1,0,,1,0+4=4,,5+0=5*,5,2,0,,1,,2,0+6=6,,5+4=9,,10+0=10*,10,3,0,,1,,2,,3,0+11=11,,5+6=11,,10+4=14*,,11+0=11,14,4,0,,1,,2,,3,,4,0+12=12,,5+11=16*,,10+6=16*,,11+4=15,,11+0=11,16,5,0,,1,,2,,3,,4,,5,0+12=12,,5+12=17,,10+11=21*,,11+6=17,,11+4=15,,11+0=11,21,当,k,=1时：,s,1,,x,1,,g,1,(,x,1,)+,f,2,(,s,2,),,f,1,(,s,1,),5,0,,1,,2,,3,,4,,5,0+21=21*,,3+16=19,,7+14=21*,,9+10=19,,12+5=17,,13+0=13,21,总效益最大为21万元，分配方案为：,(1)甲—0台, 乙—2台, 丙—3台；(2)甲—2台, 乙—2台, 丙—1台。
1.2 二维资源分配问题,二维资源分配问题可描述如下：设有两种原料，数量各为,a,和,b,，分配给,n,个使用者已知第,i,个使用者得到两种资源的数量各为,x,i,和,y,i,时，可创造的收益为,g,i,(,x,i,,,y,i,)问应如何分配该资源，才能使总收益最大与一维资源分配问题类似，把给各,个使用者分配资源的过程分别,看成一个阶段,，按使用者分成先后,的,n,个阶段由于,要分配两种资源，所以状态变量要有两个，决策变量也要有两个静态规划模型：,,按使用者划分为,n,个阶段，,k,=1,2,..,,n,；,,取第,k,阶段初（给第,k,个使用者分配资源时）两种资源各自的剩余量,s,k,和,t,k,为状态变量,,s,1,=,a,,,t,1,=,b,；,,取分配给第,k,个使用者两种资源的数量,x,k,和,y,k,为决策变量，0≤,x,k,≤,s,k,, 0≤,x,k,≤,s,k,(,k,=1,…,,n,-1),,x,n,=,s,n,,,y,n,=,t,n,；,,状态转移方程为：,s,k,+1,=,s,k,-,x,k,，,t,k,+1,=,t,k,-,y,k,；,,指标函数为,V,k,n,=,Ʃ,g,j,(,x,j,,,y,j,),；,,基本方程为：,（,k,=,n,-1,…,2,1）,虽然建模过程和一维资源分配问题没多大区别，但求解模型却极为困难。
为此，需进行简化处理1. 拉格朗日乘数法,引入拉格朗日乘数,λ,，将二维问题化为,这是一个一维分配问题取定,λ,为某一值，求解得,,,x,i,*,=,x,i,(,λ,),，,y,i,*,=,y,i,(,x,i,(,λ,),,,λ,)=,y,i,(,λ,),,可证，若,Ʃ,y,i,(,λ,)=,b,，则对应的{,x,i,*,,,y,i,*,}就是原问题的最优解否则，就用插值法调整,λ,的值，渐进地使,Ʃ,y,i,(,λ,)=,b,得到满足2. 逐次逼近法,逐次逼近法的做法是，先保持一个变量不变，对另一个变量求最优，然后交替地固定，以迭代的形式反复进行，直到满足某种要求为止先设,x,(0),={,x,1,(0),,,x,2,(0),,…,,x,n,(0),}为满足,Ʃ,x,i,(0),=,a,的一个可行解，固定,x,在,x,(0),，对,y,求解，则变为一维问题,用一维方法解得,y,(0),={,y,1,(0),,,y,2,(0),,…,,y,n,(0),}，再固定,y,在,y,(0),，对,x,求解一维问题,解得,x,(1),={,x,1,(1),,,x,2,(1),,…,,x,n,(1),}，再固定,x,在,x,(1),，对,y,求解一维问题。
依次轮换下去，得解序列{,x,(,k,),}、 {,y,(,k,),}由于,Ʃ,g,i,(,x,i,(0),,,y,i,(0),),≤,Ʃ,g,i,(,x,i,(1),,,y,i,(0),),≤,Ʃ,g,i,(,x,i,(1),,,y,i,(1),),，故函数值序列{,Ʃ,g,i,(,x,i,(,k,),,,y,i,(,k,),)},是单调上升的，但不一定收敛到整体的最优解，一般只能收敛到某一局部最优解因此，在实际计算时，可选择几个初始点,x,i,(0),进行计算，然后从几个局部最优解中选出一个最好的3. 粗格子点法 （疏密法）,先将0≤,x,≤,a,, 0≤,y,≤,b,分成网格，然后在格子点上进行计算为了使计算可行，可先用少数格子点进行粗糙计算，在求出相应最优解后，再在最优解附近的小范围内进一步细分，求出在细分格子点上的最优解继续细分下去，直至满足要求为止第2节 生产与存储问题,2.1 生产计划问题,设某公司对某种产品要制定,n,个阶段的生产计划已知它的初始库存为0，每阶段生产产品数量的上限为,m,；第,k,阶段，对该产品的需求量为,d,k,，生产产品量为,x,k,时的生产费用为,c,k,(,x,k,)，开始时有库存量,v,k,需要支付的存储费用为,h,k,(,v,k,)；,n,阶段末的终了库存为0。
问该公司应如何制定生产计划，从而使总成本最小用动态规划的方法：,状态转移方程为：,v,k,+1,=,v,k,+,x,k,-,d,k,k,阶段的产品生产量,x,k,为决策变量，则,k,阶段开始时的库存量,v,k,为状态变量，,v,1,=0；,划分为,n,个决策阶段，,k,=1,2,...,,n,；,,基本方程为：,在求解生产计划问题时，常常需要先给出状态变量,v,k,的取值范围，即确定可达状态集易推出：,例 某工厂要对一种产品制定今后四个时期的生产计划，据估计四个时期的需求量依次为2、3、2和4假定该厂生产每批产品的固定成本为3万元，每单位产品的成本为1万元，若不生产就为0；每个时期生产能力的上限为6个单位，每单位产品存放每期的存储费用为0.5万元还假定第一期开始时和第四期结束时的库存量都为0试问该厂应如何安排各期的生产与库存，才能在满足需求的条件下，使总成本最小基本方程为：,状态变量,v,k,的可达状态集：,则有，,v,1,=0，0≤,v,2,≤4，0≤,v,3,≤6，0≤,v,4,≤4k,阶段的费用有两部分，生产费用为,库存费用为,h,k,(,v,k,)=0.5,v,k,，,k,阶段的总费用为,c,k,(,x,k,)+,h,k,(,v,k,)。
0,,当,x,k,=0时,,3+,x,k,当,x,k,=1,...,6时,,∞ 当,x,k,＞6时,c,k,(,x,k,)=,解 分成四个阶段，,k,=1,2,3,4；,k,阶段初的库存,v,k,为状态变量，,v,1,=0；,k,阶段的产品生产量,x,k,为决策变量，,（,d,1,=2,,d,2,=3,,d,3,=2,,d,4,=4）,状态转移方程为：,v,k,+1,=,v,k,+,x,k,-,d,k,,,k,=4时：,v,4,,x,4,,c,4,(,x,4,)+,h,4,(,v,4,)+,f,5,(,v,5,),f,4,(,v,4,),0,4,(3+4)+0+0=7*,7,1,3,(3+3)+0.5+0=6.5*,6.5,2,2,(3+2)+0.5,•,2+0=6*,6,3,1,(3+1)+0.5,•,3+0=5.5*,5.5,4,0,0+0.5,•,4+0=2*,2,k,=3时：,v,3,,x,3,,c,3,(,x,3,)+,h,3,(,v,3,)+,f,4,(,v,4,),f,3,(,v,3,),0,2,,3,,4,,5,,6,(3+2)+0+7=12,,(3+3)+0+6.5=12.5,,(3+4)+0+6=13,,(3+5)+0+5.5=13.5,,(3+6)+0+2=11*,11,1,1,,2,,3,,4,,5,(3+1)+0.5+7=11.5,,(3+2)+0.5+6.5=12,,(3+3)+0.5+6=12.5,,(3+4)+0.5+5.5=13,,(3+5)+0.5+2=10.5*,10.5,2,0,,1,,2,,3,,4,0+0.5,•,2+7=8*,,(3+1)+0.5,•,2+6.5=11.5,,(3+2)+0.5,•,2+6=12,,(3+3)+0.5,•,2+5.5=12.5,,(3+4)+0.5,•,2+2=10,8,3,0,,1,,2,,3,0+0.5,•,3+6.5=8*,,(3+1)+0.5,•,3+6=11.5,,(3+2)+0.5,•,3+5.5=12,,(3+3)+0.5,•,3+2=9.5,8,4,0,,1,,2,0+0.5,•,4+6=8*,,(3+1)+0.5,•,4+5.5=11.5,,(3+2)+0.5,•,4+2=9,8,5,0,,1,0+0.5,•,5+5.5=8*,,(3+1)+0.5,•,5+2=8.5,8,6,0,0+0.5,•,6+2=5*,5,v,2,,x,2,,c,2,(,x,2,)+,h,2,(,v,2,)+,f,3,(,v,3,),f,2,(,v,2,),0,3,,4,,5,,6,(3+3)+0+11=17,,(3+4)+0+10.5=17.5,,(3+5)+0+8=16*,,(3+6)+0+8=17,16,1,2,,3,,4,,5,,6,(3+2)+0.5+11=16.5,,(3+3)+0.5+10.5=17,,(3+4)+0.5+8=15.5*,,(3+5)+0.5+8=16.5,,(3+6)+0.5+8=17.5,15.5,2,1,,2,,3,,4,,5,,6,(3+1)+0.5,•,2+11=16,,(3+2)+0.5,•,2+10.5=16.5,,(3+3)+0.5,•,2+8=15*,,(3+4)+0.5,•,2+8=16,,(3+5)+0.5,•,2+8=17,,(3+6)+0.5,•,2+8=18,15,k,=2时：,,3,0,,1,,2,,3,,4,,5,,6,0+0.5,•,3+11=12.5*,,(3+1)+0.5,•,3+10.5=16,,(3+2)+0.5,•,3+8=14.5,,(3+3)+0.5,•,3+8=15.5,,(3+4)+0.5,•,3+8=16.5,,(3+5)+0.5,•,3+8=17.5,,(3+6)+0.5,•,3+5=15.5,12.5,4,0,,1,,2,,3,,4,,5,0+0.5,•,4+10.5=12.5*,,(3+1)+0.5,•,4+8=14,,(3+2)+0.5,•,4+8=15,,(3+3)+0.5,•,4+8=16,,(3+4)+0.5,•,4+8=17,,(3+5)+0.5,•,4+5=15,12.5,k,=2时：,（续）,k,=1时：,v,1,,x,1,,c,1,(,x,1,)+,h,1,(,v,1,)+,f,2,(,v,2,),f,1,(,v,1,),0,2,,3,,4,,5,,6,(3+2)+0+16=21,,(3+3)+0+15.5=21.5,,(3+4)+0+15=22,,(3+5)+0+12.5=20.5*,,(3+6)+0+12.5=21.5,20.5,于是得，总成本最小为20.5万元。
x,1,*,=5，,x,2,*,=0，,x,3,*,=6，,x,4,*,=0,再顺序递推出最优计划为：,即：第一个时期生产产品5个单位，第二个时期不安排生产，第三个时期生产产品6个单位，第四个时期不安排生产2.2 不确定性采购问题,,某单位准备在以后的,n,个时期内采购一批物资各时期的价格不是确定的，而是按照某种已知的概率分布取值试制定采购策略，确定在哪一时期以什么价格采购，能使采购价的数学期望值最低这类问题也适合用动态规划法进行处理,下面通过实例加以说明例 某厂生产上,须,在近五周内采购一批原料，而估计在未来五周的价格有波动，其浮动价格和概率策得如下表试确定该厂应在哪一周以什么价格购入，能使其采购价的数学期望值最小，并求出期望值价格,500 600 700,概率,0.3 0.3 0.4,,解：,（1）按采购周数分成5个阶段，,k,=1,2,…,5；,（2）取第,k,阶段(第,k,周)的实际价格,y,k,为状态变量；,（4）用,f,k,(,y,k,)表示：前,k,-1周未采购，第,k,周状态为,y,k,时，从第,k,周到第5周按最优策略所得到的采购价的期望值。
即,f,k,(,y,k,)为最优值函数；,（5）用,y,kE,表示：前,k,-1周未采购，从第,k,周到第5周按最优策略所得到的总的采购价的期望值1 采购,,（3）第,k,阶段，设,x,k,= ，为决策变量；,,0 等待,显然，,y,kE,=,Ef,k,(,y,k,)=0.3,f,k,(500)+0.3,f,k,(600)+0.4,f,k,(700),（6）基本方程为：,,,f,k,(y,k,)＝ min{,y,k,,,y,(,k,+1),E,,},k,=4,3,2,1,,,,,f,5,(,y,5,)＝,y,5,,k,=5时：,f,5,(500)=500,,f,5,(600)=600,,f,5,(700)=700 (,x,5,*=1),y,5,E,=0.3*500+0.3*600+0.4*700=610,k,=4时：,f,4,(500)=min{500,610}=500, (,x,4,*=1),,,f,4,(600)=min{600,610}=600, (,x,4,*=1),,,f,4,(700)=min{700,610}=610, (,x,4,*=0),,,y,4,E,=0.3*500+0.3*600+0.4*610=574,k,=3时：,f,3,(500)=min{500,574}=500, (,x,3,*=1),,,f,3,(600)=min{600,574}=574, (,x,3,*=0),,,f,3,(700)=min{700,574}=574, (,x,3,*=0),,,y,3,E,=0.3*500+0.3*574+0.4*574=551.8,k,=2时：,f,2,(500)=min{500,551.8}=500, (,x,2,*=1),,,f,2,(600)=min{600,551.8}=551.8, (,x,2,*=0),,,f,2,(700)=min{700,551.8}=551.8, (,x,2,*=0),,,y,2,E,=0.3*500+0.3*551.8+0.4*551.8=536.26,,k,=1时：,f,1,(500)=min{500,536.26}=500 (,x,1,*=1),,,f,1,(600)=min{600,536.26}=536.26 (,x,1,*=0),,,f,1,(700)=min{700,536.26}=536.26 (,x,1,*=0),,,y,1,E,=0.3*500+0.3*536.26+0.4*536.26=525.382,最优的采购策略为：在一、二、三周时，价格为500时采购，否则就等待；在第四周时，价格为500和600都要采购，价格为700就等待；第五周时，无论什么价都要采购。
由此可知，采购价的期望值最小为525.382对于不确定性采购问题，还可考虑每期价格的概率分布不同、价格的概率分布为连续分布等情况，都可用与上例类似的方法进行求解第3节 背包问题,,一个人带一个背包上山，其可携带物品重量的限度为,a,公斤设有,n,种物品可供他选择装入背包，已知第,i,种物品每件重量为,w,i,公斤，上山过程中的效用是携带数量,x,i,的函数,c,i,(,x,i,)问此人应如何携带各种物品，才能使总效用最大用动态规划法处理这种问题时，通常把,一种,物品决定带多少件,的过程看成一个阶段，按物品种类分成先后,的,n,个阶段即先,决定,第1种物品带多少件,，为第一阶段；再决定第2种物品，为第,二,阶段；依此类推，最后决定第,n,种物品,，为第,n,阶段静态规划模型：,,按物品种类划分为,n,个阶段，,k,=1,2,..,,n,；,,取第,k,阶段初（决定第,k,种物品带多少件时）可携带重量的剩余量,s,k,为状态变量，,s,1,=a；,,取第,k,种物品携带的数量,x,k,为决策变量，则有0≤,x,k,≤[,s,k,/,w,k,] (,k,=1,2,…,,n,-1) ；,,状态转移方程为,s,k,+1,=,s,k,-,w,k,x,k,；,,指标函数为,V,k,n,=,Ʃ,c,j,(,x,j,),；,对背包问题求解的难点在于，除第一阶段外，其它阶段的可达状态集不容易给出，下面通过实例说明给出可达状态集的方法。
k,=,n,,…,2,1）,基本方程为：,,例 用动态规划法求解,,max,z,=4,x,1,+5,x,2,+6,x,3,,3,x,1,+4,x,2,+5,x,3,≤10,,,x,i,≥0(取整数),i,=1,2,3,解：,按变量划分为3个阶段，,k,=1,2,3,取,k,阶段时常数项(资源)的余量,s,k,为状态变量，,s,1,=10,取,x,k,为决策变量，0≤,x,k,≤[,s,k,/,w,k,],状态转移方程为,s,k,+1,=,s,k,-,w,k,x,k,,（,w,1,=3,,w,2,=4,,w,3,=5）,指标函数为,V,k,,3,=,Ʃ,c,j,x,j,（,c,1,=4,,c,2,=5,,c,3,=6）,基本方程为,f,k,(,s,k,)= max {,c,k,x,k,+,f,k+,1,(,s,k,+1,)},k,=3,2,1,,0≤,x,k,≤[,s,k,/,w,k,],,f,4,(,s,4,)=0,,由于,s,1,=10，因而求解此问题就是计算,f,1,(10)而,可见，要先计算,f,2,(10),,f,2,(7),,f,2,(4),,f,2,(1)于是，需计算,f,3,(10),,f,3,(7),,f,3,(6),,f,3,(4),,f,3,(3),,f,3,(2),,f,3,(1),,f,3,(0) 。
f,3,(4)=,f,3,(3)=,f,3,(2)=,f,3,(1)=,f,3,(0)=0 (,x,3,*,=0),,从而，有,最后，有,所以，最优解为,x,1,*,=2,,x,2,*,=1,,x,3,*,=0，,z,*,=13,,二维背包问题：一个人带一个背包上山，其可携带物品重量的限度为,a,公斤，体积的限度为,b,立方米设有,n,种物品可供他选择装入背包，已知第,i,种物品每件重量为,w,i,公斤，每件体积为,v,i,立方米，上山过程中的效用是携带数量,x,i,的函数,c,i,(,x,i,)问此人应如何携带各种物品，才能使总效用最大静态规划模型：,（,k,=,n,,…,2,1）,基本方程为：,二维背包问题，其第,k,阶段有两个状态变量，但决策变量仍只有一个，所以求解难度并没有实质性增加二维背包问题的求解方法与一维背包问题基本相同第4节 复合系统可靠性问题,,某种机器的工作系统由,n,个部件串联组成，只要一个部件失灵，整个系统就不能工作为提高系统可靠性，每个部件都装备了备用件，并设计了备用件自动投入装置已知，部件,i,装备,u,i,个配件时的可靠性为,p,i,(,u,i,)，一个备用件的费用为,c,i,，重量为,w,i,；整个系统备用件的总费用不超过,c,，总重量不超过,w,。
问应如何选择各部件的备用件数，使整个系统的可靠性最大其静态规划模型为,,按部件划分为,n,个阶段；取第,k,阶段初费用剩余量,s,k,和重量剩余量,t,k,为状态变量，,s,1,=c,,t,1,=,w,；,,取给部件,k,安装的备用件数,u,k,为决策变量，则有1≤,u,k,≤min{[,s,k,/,c,k,],[,t,k,/,w,k,]} ；,,状态转移方程为,s,k,+1,=,s,k,-,c,k,u,k,,,t,k,+1,=,t,k,-,w,k,u,k,,指标函数为,V,k,n,=,П,p,j,(,u,j,),；,基本方程为：,该问题的特点是，指标函数为连乘形式，边界条件当然为1另外，和背包问题一样，求解时要先顺推出各阶段的可达状态集例,某,厂设计的电子设备由三种元件,D,1,、,D,2,、,D,3,组成已知三种元件的价格和可靠性如下表所示，要求设计中使用元件的费用不超过105元问应如何设计，使设备的可靠性达到最大（不考虑重量限制）元件,,D,1,,D,2,,D,3,价格(元/件),30 15 20,可靠性,0.9 0.8 0.5,解：,按变量划分为3个阶段，,k,=1,2,3；,s,k,为状态变量，,s,1,=105；,u,k,为决策变量，1≤,u,k,≤[,s,k,/,c,k,]；状态转移方程,s,k,+1,=,s,k,-,c,k,u,k,(,c,1,=30,,c,2,=15,,c,3,=20)；指标函数,V,k,,3,=,П,p,j,(,u,j,),(,p,1,(,u,1,),,=1-0.1,u,1,,,p,2,(,u,2,),,=1-0.2,u,2,,,p,3,(,u,3,),,=1-0.5,u,3,)。
基本方程为,f,k,(,s,k,)= max {,p,k,(,u,k,),f,k+,1,(,s,k,+1,)},k,=3,2,1,,1≤,u,k,≤[,s,k,/,c,k,],,f,4,(,s,4,)=1,,由于,s,1,=105，而,则要先计算,f,2,(75),,f,2,(45),,f,2,(15),于是计算,f,3,(60),,f,3,(45),,f,3,(30),,f,3,(15),,f,3,(0) 从而得：,,第5节 排序问题,,设有,n,个工件需要在机床,A,、,B,上加工，每个工件都必须先经过,A,而后,B,,两道加工工序以,a,i,、,b,i,分别表示工件,i,(1≤,i,≤,n,),在,机床,A,、,B,上的加工时间问应如何在两机床上安排各工件的加工顺序，使在机床,A,上加工第一个工件开始到在机床,B,上加工完最后一个工件为止，所用的加工总时间最少？,加工工件在机床,A,上有加工顺序问题，在机床,B,上也有加工顺序问题可以证明：最优加工顺序在两台机床上可同时实现因此，最优排序方案可以只在机床,A,、,B,上加工顺序相同的排序中寻找,即可,即使如此，所有可能的方案仍有,n,!,个，这是一个不小的数，用穷举法是不现实的。
下面,用动态规划法对排序问题进行研究当加工顺序排定之后，工件在,A,上没有等待时间，而在,B,上则常常需要等待因此，只有尽量减少在,B,上等待加工的时间，才能使总加工时间最短现,以在机床,A,上更换工件的时刻作为阶段的分界点，分成,n,个阶段第,k,阶段时，,X,k,表示尚未在,A,上加工的工件集合，,t,k,表示已在,A,上加工完的工件还需要在,B,上的加工时间，(,X,k,,,t,k,)作为状态令,f,k,(,X,k,,,t,k,)为从状态(,X,k,,,t,k,)出发，对还未在,A,上加工的剩余工件按最优排序，完成全部加工任务还需要的时间，即为k-子过程最优值函数f,k,(,X,k,,,t,k,,,i,)为从状态(,X,k,,,t,k,)出发，对还未在,A,上加工的剩余工件先加工工件,i,，再对其它剩余工件按最优排序，完成全部加工任务还需要的时间则有,,,f,k,(,X,k,,,t,k,,,i, j,)为从状态(,X,k,,,t,k,)出发，对还未在,A,上加工的剩余工件先加工工件,i,再加工工件,j,，再对其它剩余工件按最优排序，完成全部加工任务还需要的时间由于,f,k,(,X,k,,,t,k,)是关于,t,k,的增函数，则当,z,ij,(,t,k,)≤,z,ji,(,t,k,)时，有,f,k,(,X,k,,,t,k,,,i, j,)≤,f,k,(,X,k,,,t,k,,,j, i,)。
这时，把工件,i,放在工件,j,之前加工更有利于缩短总加工时间于是有,,条件,min(,a,i,,b,j,)≤min(,a,j,,b,i,)是,工件,i,应该排在工件,j,之前的条件，只要一个排序任意两个工件的前后关系都满足这个条件，则为最优排序根据这个条件，构造下列排序方法：,（2）在工时矩阵,M,中找出最小元素（不止一个,时,可任选其一）,，若它在上行，则相应的工件排在最前位置；若它在下行，则相应的工件排在最后位置3）将排定位置的工件所对应的列从,M,中划去，然后对余下的工件再按(2)进行排序如此进行下去，直到把所有工件都排完为止1）,建立工时矩阵,,,例 设有5个工件需在机床,A,、,B,上加工，加工的次序为先,A,后,B,，每个工件需要的加工时间如下表（单位：小时） 试安排加工顺序，使机床连续加工完所有工件的总加工时间最少，并求出总加工时间工件号,A B,1,,2,,3,,4,,5,3 6,,7 2,,4 7,,5 3,,7 4,,解：,3 7 4 5 7,,建立工时矩阵：M=,,6 2 7 3 4,工件的排序为：,→ 2,1 →,→ 4,3 →,5,3 4 7 5 7,,排序后的工时矩阵为：M′=,,6 7 4 3 2,已在A上加工完的工件,,还需要在B上的加工时间：,t= 6, 9, 6, 4, 2,总加工时间（工期）为：T=(3+4+7+5+7)+2=28(小时）,,。