《动态规划教学PPT》由会员分享，可在线阅读，更多相关《动态规划教学PPT（50页珍藏版）》请在金锄头文库上搜索。
1、 4 动态规划动态规划 4.1 多阶段决策问题与动态规划 4.2 动态规划的基本概念 4.3 动态规划的步骤 4.4 动态规划的应用 1 求解静态规划问题 2 资源分配问题 3 不确定性采购问题 4 排序问题 例2 机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为 gg(u), 这时机器的年完好率为a（0a1)在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为hh(v), 这时机器的年完好率为b（ab1）假定开始生产时完好的机器数量为s1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数
2、量,使五年内产品的总产量最高。4.1 多阶段决策问题与动态规划 多阶段决策问题和我们前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的的优化方法称为静态规划。 (1)阶段（stage）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称阶段变量，常用k表示。 (2)状态（state）状态表示每个阶段开始时所处的自然状况或客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。描述状态的变量称为
3、状态变量，第k阶段的状态变量常用sk表示。通常，在第一阶段状态变量s1是确定的，称初始状态。 (3)决策（decision）决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。4.2 动态规划的基本概念（一） (4)策略（policy）把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，或称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列p1,n u1,u2,un 称为全过程策略，简称 策 略
4、； 而 在 k子 过 程 上 的 决 策 序 列 pk,n uk,uk+1,un 称为k子过程策略，也简称子策略。 (5)状态转移方程 若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为sk+1Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。4.2 动态规划的基本概念（二） (6)指标函数和最优值函数 指标函数分为阶段指标函数和过程指标函数。阶段指标函数是对某一阶段的状态和决策产生的效益值的度量，用vk(sk,uk)表示。过程指标函数是指过程
5、所包含的各阶段的状态和决策所产生的总的效益值，记为 Vk,nVk,n(sk,uk,sk+1,uk+1,sn,un) 动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是： 各阶段指标函数的和 Vk,nvj(sj,uj)； 各阶段指标函数的积 Vk,nvj(sj,uj)。 把过程指标函数Vk,n对k子过程策略pk,n求最优，得到一个关于状态sk的函数，称为最优值函数，记为fk(sk)。即 fk(sk) opt Vk,n(sk,uk,sn,un) uk,un式中的“opt”（optimization）可根据具体问题而取min或max
6、。fk(sk)-表示第k阶开始状态为sk的情况下到末状态为sn作最优策略对应的指标值 (7)基本方程 通常动态规划问题的最优值函数满足递推关系式。设过程指标函数为各阶段指标函数的和的形式，即Vk,nvj(sj,uj)，则有 fk(sk) opt vk(sk,uk)+fk+1(sk+1) ukDk(sk) (kn,n-1,1) 递推方程 fn+1(sn+1)0 边界条件递推方程和边界条件一起称为动态规划的基本方程。 可根据边界条件，从k=n开始，由后向前逆推，逐步求得各阶段的最优决策和相应的最优值，最后求出f1(s1)时，就得到整个问题的最优解( (称为逆序解法称为逆序解法) )。此问题的基本方
7、程为此问题的基本方程为f fk k(s(sk k) )MindMindk k(u(uk k)+f)+fk+1k+1(s(sk+1k+1) ) u uk kDDk k(s(sk k) ) k k6,5,4,3,2,16,5,4,3,2,1f f7 7(s(s7 7) )0 04.3 动态规划的步骤（一）动态规划的步骤（一）当k=6时按基本方程由后向前按基本方程由后向前继续继续递推有递推有:当k=5时当k=4时当当k=3时时当当k=2时时当当k=1时时 由此可以看出，由此可以看出，A到到G的最短路长为的最短路长为18，路径为：，路径为： AB1C2D1E2F2G现在把动态规划法的步骤归纳如下：现在
8、把动态规划法的步骤归纳如下：(1) (1) 将所研究问题的过程划分为将所研究问题的过程划分为n n个恰当的阶段，个恰当的阶段， k k 1,2,n 1,2,n；(2) (2) 正确地选择状态变量正确地选择状态变量S Sk k，并确定初始状态并确定初始状态S S1 1的值；的值；(3) (3) 确定决策变量确定决策变量u uk k以及各阶段的允许决策集以及各阶段的允许决策集D Dk k(S(Sk k) )；(4) (4) 给出状态转移方程；给出状态转移方程；(5) (5) 给出满足要求的过程指标函数给出满足要求的过程指标函数V Vk,nk,n及相应的最优及相应的最优 值函数；值函数；(6) (6
9、) 写出递推方程和边界条件，建立基本方程；写出递推方程和边界条件，建立基本方程；(7) (7) 按照基本方程递推求解。按照基本方程递推求解。 以以上上步步骤骤是是动动态态规规划划法法处处理理问问题题的的基基本本步步骤骤，其其中中的前六步是建立动态规划模型的步骤。的前六步是建立动态规划模型的步骤。4.3 动态规划的步骤（二）动态规划的步骤（二）顺序解法顺序解法-即解题顺序与决策顺序一致即解题顺序与决策顺序一致4.3 动态规划的顺序解法（三）动态规划的顺序解法（三）即是在第即是在第k阶段末状态阶段末状态sk+1已知的情已知的情况况下下,确定前面的决策确定前面的决策uk,使从初始状态使从初始状态s1
10、到第到第k阶段末状态阶段末状态sk+1的策略最优的策略最优此时的状态转移方程应为此时的状态转移方程应为,从从sk+1出发通达出发通达uk解出解出sk,即从即从sk+1Tk(sk,uk)中反解出中反解出sk, skTrk(sk+1,uk)fk(sk+1)-表示第表示第k阶末状态为阶末状态为sk的情况下到第的情况下到第1阶初始状态为阶初始状态为s1作作最优策略对应的指标值最优策略对应的指标值,顺序解法基本方程为顺序解法基本方程为fk(sk+1) opt vk(sk+1,uk)+fk-1(sk) ukDrk(sk+1) (k1,n) 递推方程递推方程 f0(s1)0 边界条件边界条件4.3 动态规划
11、的顺序解法（三）动态规划的顺序解法（三）fk(sk)-表示第表示第k阶末状态为阶末状态为sk的情况下到第的情况下到第1阶初始状态为阶初始状态为s1作最作最优策略对应的指标值优策略对应的指标值,则则顺序解法基本方程为顺序解法基本方程为fk(sk) opt vk(sk,uk)+fk-1(sk-1) ukDrk(sk) (k1,n) 递推方程递推方程 f0(s0)0 边界条件边界条件如果如果sk表示第表示第k阶段末状态阶段末状态,s0表示第表示第1阶段初始状态阶段初始状态注注贝尔曼贝尔曼( (BallmanBallman) )最优化原理最优化原理 作为整个过程的最优策略具有作为整个过程的最优策略具有
12、这样的性质，即无论过去的状态和这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成状态而言，余下的诸决策必须构成最优策略。这就是说，不管引导到最优策略。这就是说，不管引导到这个现时状态的头一个状态和决策这个现时状态的头一个状态和决策是什么，所有的未来决策应是最优是什么，所有的未来决策应是最优的。的。例：机器负荷问题例：机器负荷问题 某种机器可以在高低两种某种机器可以在高低两种不同的负荷下进行生产在高负荷下进行生产不同的负荷下进行生产在高负荷下进行生产时，产品的年产量时，产品的年产量g g和投入生产的机器数量和投入生产的机器数量
13、u u的的关系为关系为 g g8u, 8u, 这时机器的年完好率为这时机器的年完好率为a=0.7a=0.7在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h h和投入和投入生产的机器数量生产的机器数量v v的关系为的关系为h h5v, 5v, 这时机器的这时机器的年完好率为年完好率为b=0.9b=0.9假定开始生产时完好的机假定开始生产时完好的机器数量为器数量为s s1 1，要求制定一个五年计划要求制定一个五年计划, ,在每年开在每年开始时决定机器在两种不同负荷下生产的数量始时决定机器在两种不同负荷下生产的数量, ,使五年内产品的总产量最高。使五年内产品的总产量最高。(1)按年数划
14、分为5个阶段，k=1,2,3,4,5(2)取第k年初完好的机器数sk为状态变量, s1=1000(3)取第k年投入高负荷的机器数xk为决策变量, 0xksk(4)状态转移方程为 sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk(5)指标函数为Vk,5=8xj+5(sj-xj)=(5sj+3xj)(6)基本方程为 fk(sk) max 5sj+3xj +fk+1(sk+1) k=5,4,3,2,1 0xksk f6(s6)0解:当k=5时f5(s5) max5s5+3x5+f6(s6)= max5s5+3x5=8s5 (x5*=s5) 0x5s5 0x5s5当k=4时f4(s4
15、)max5s4+3x4+8s5=max5s4+3x4+8(0.9s4-0.2x4) 0x4s4 0x4s4 = max12.2s4+1.4x4=13.6s4 (x4*=s4) 0x4s4当k=3时f3(s3)max5s3+3x3+13.6s4=max5s3+3x3+13.6(0.9s3-0.2x3) 0x3s3 0x3s3 = max17.24s3+0.28x3=17.5s3 (x3*=s3) 0x3s3当k=2时f2(s2)=max5s2+3x2+17.52s3=max5s2+3x2+17.52(0.9s2-0.2x2) 0x2s2 0x2s2 = max20.77s2-0.504x2=20
16、.7s4 (x2*=0) 0x2s2当k=1时f1(s1)=23.7s1 (x1*=0)f1(1000)=23700s1=1000, x1*=0s2=900, x2*=0s3=810, x3*=810s4=576, x4*=576s5=397, x5*=397 某些静态规划问题可用动态规划法来求解。某些静态规划问题可用动态规划法来求解。 例例 用动态规划法求解用动态规划法求解 max z=x1.x22.x3 x1+x2+x3=c xi0 i=1,2,34.4 动态规划的划的应用用(一一) 1 求解静求解静态规划划问题4.5 动态规划模型举例 4.5.1 产品生产计划安排问题 例1 某工厂生产某
17、种产品的月生产能力为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到： 1、保证满足每月的销售量，并规定计划期初和期末库存为零； 2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。 例1 产品生产计划安排设xk为第k阶段生产量，则有直接成本 dk(sk, xk)= ck xk+2sk状态转移公式为 sk+1= sk+ xk- yk总成本递推公式第第四四阶段阶段：(即第即第4月份月份)由边界条件和状态转移方程由边界条件和状态转移方程 s5=s4+x4-y4=
18、s4+x46=0 得得 s4+x4= 6 或或 x4= 6 s4估计估计第第四四阶段，即第阶段，即第4月份初库存的可能月份初库存的可能状态：状态： s4 0,5第四阶段最优决策表第三阶段：最大可能库存量 7 件由状态转移方程： s4=s3+x3-120 及 x310，可知 s32,7，min x3=5由阶段效果递推公式有：f3(2)=d3(2,10)+f4*(0) =22+8010+456=1260得第三阶段最优决策表，如下第三阶段最优决策表第二阶段：最大可能库存量 4 件由状态转移方程： s3=s2+x2-72 及 x210，可知 s20,4，min x2=5由阶段效果递推公式有：f2(1)
19、=d3(1,10)+f3*(4) =21+7210+1104=1826得得第第二二阶段最优决策表，阶段最优决策表，如下如下第三阶段最优决策表第四阶段：初始库存量 s4=0由状态转移方程： s3=s4+x4-60 可知 x46，由阶段效果递推公式有：f4(0,6)=d4(0,6)+f3*(0,10) =706+1902=2322得第四阶段最优决策表，如下回回溯溯得得此此表表 例2 生产库存管理问题(连续变量) 设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，
20、存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。解：四个季度为四个阶段，采用阶段编号与季度顺序一致。 设 sk 为第k季初的库存量，则边界条件为 s1=s5=0 设 xk 为第k季的生产量，设 yk 为第k季的订货量； sk ，xk ，yk 都取实数，状态转移方程为 sk+1=sk+xk - yk 仍采用反向递推，但注意阶段编号是正向的 目标函数为例2 生产库存管理问题(连续变量)第一步：(第四季度) 总效果 f4(s4,x4)=0.005 x42+s4 由边界条件有： s5= s4 + x4 y4=0，解得：x4*=1200 s4 将x4*代入 f4(s4,x4)得： f4*(s4
21、)=0.005(1200 s4)2+s4=7200 11 s4+0.005 s42第二步：(第三、四季度) 总效果 f3(s3,x3)=0.005 x32+s3+ f4*(s4) 将 s4= s3 + x3 500 代入 f3(s3,x3) 得： 例2 生产库存管理问题(连续变量)第三步：(第二、三、四季度) 总效果 f2(s2,x2)=0.005 x22+s2+ f3*(s3) 将 s3= s2 + x2 - 700 代入 f2(s2,x2) 得： 注意：最优阶段总效果仅是当前状态的函数，与其后的决策无关 例2 生产库存管理问题(连续变量)第四步：(第一、二、三、四季度) 总效果 f1(s1
22、,x1)=0.005 x12+s1+ f2*(s2) 将 s2= s1 + x1 600= x1 600 代入 f1(s1,x1) 得：由此由此回溯回溯：得最优生产：得最优生产库存方案库存方案 x1*=600，s2*=0； x2*=700，s3*=0； x3*=800，s4*=300； x4*=900。 4.5.2 资源分配问题例3 某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。解解：设分配人员的顺序为市场：设分配人员的顺序为市场1, 2, 3，采用，采用顺顺向阶段编号。向阶段编号。 设设 sk 为第为第k阶段尚未分配的人
23、员数，边界条件为阶段尚未分配的人员数，边界条件为 s1=9 设设 xk 为第为第k阶段分配的推销人员数；阶段分配的推销人员数；采用反向递推，采用反向递推， 状态转移方程为状态转移方程为 sk+1=sk xk 靜态规划靜态规划为为 例3 第三阶段：给第三市场分配 s3 有09种可能，第三阶段最优决策表如下：允许推销人员没用完时允许推销人员没用完时允许推销人员没用完时允许推销人员没用完时 例3 第二阶段：给第二市场分配 s2 有09种可能，第二阶段最优决策表如下：第一阶段：给第一市场分配 由边界条件 s1=9，第一阶段最优决策表如下：得决策过程：得决策过程：x1*=2, x2*=0, x3*=7,
24、 f1*=218 即即 市场市场1 分配分配 2人，市场人，市场2 不分配不分配 ，市场，市场3 分配分配 7人人最优解与分配的顺序有关吗最优解与分配的顺序有关吗？ 4.5.2 资源分配问题例4 项目选择问题 某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额 wk及其投资后的收益 vk如下表所示。投资总额为30万元，问如何选择项目才能使总收益最大。上述问题的静态规划模型如下： 这是一类这是一类0-1规划问题规划问题该问题是经典的该问题是经典的旅行背包问旅行背包问题题 (Knapsack)该问题是该问题是 NP-complete 例4 项目选择问题解：设项目选择的顺序为A, B, C
25、, D;1、阶段 k=1, 2, 3, 4 分别对应 D, C, B, A项目的选择过程2、第 k 阶段的状态 sk，代表第 k 阶段初尚未分配的投资额3、第 k 阶段的决策变量 xk,，代表第 k 阶段分配的投资额4、状态转移方程为 sk1= sk wk xk5、直接效益 dk(sk ,xk)= vk 或 06、总效益递推公式 该问题的难点在于各阶段的状态的确定，当阶段增加时，状该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。态数成指数增长。下面利用决策树来确定各阶段的可能状态。 例4 第一阶段(项目D)的选择过程s18 时，x1只能
26、取0；w1=8, v1=5例4 第二阶段(项目C)的选择过程 例4 第三阶段(项目B)的选择过程第四阶段第四阶段( (项目项目A) )的选择过程的选择过程 4.5.3 串联系统可靠性问题例5 有 A, B, C 三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果表明，机器 A, B, C 产生次品的概率分别为 pA=30%, PB=40%, PC=20%, 而产品必须经过三部机器顺序加工才能完成。为了降低产品的次品率，决定拨款 5 万元进行技术改造，以便最大限度地提高产品的成品率指标。现提出如下四种改进方案：方案1: 不拨款，机器保持原状；方案2: 加装监视设备，每部机器需款
27、 1 万元；方案3: 加装设备，每部机器需款 2 万元；方案4: 同时加装监视及控制设备，每部机器需款 3 万元；采用各方案后，各部机器的次品率如下表。 例5 串联机器可靠性问题解：为三台机器分配改造拨款，设拨款顺序为A, B, C，阶段序号反向编号为 k，即第一阶段计算给机器 C 拨款的效果。 设 sk 为第 k 阶段剩余款，则边界条件为 s3=5； 设 xk 为第 k 阶段的拨款额； 状态转移方程为 sk-1=sk-xk； 目标函数为 max R=(1-PA)(1-PB)(1-PC) 仍采用反向递推第一阶段 ：对机器 C 拨款的效果 R1(s1,x1)=d1(s1,x1) R0(s0,x0
28、)= d1(s1,x1)第二阶段最优决策表第二阶段 ：对机器 B, C 拨款的效果 由于机器 A 最多只需 3 万元，故 s2 2 递推公式： R2(s2,x2)=d2(s2,x2) R1(s1,x1*) 例：R2(3,2)=d2(3,2) R1(1,1)=(1-0.2) 0.9=0.72 得第二阶段最优决策表第二阶段最优决策表第三阶段 ：对机器 A, B, C 拨款的效果 边界条件：s3 = 5 递推公式： R3(s3,x3)=d3(s3,x3) R2(s2,x2*) 例：R3(5,3)=d3(5,3) R2(2,2)=(1-0.05) 0.64=0.608 得第三阶段最优决策表第二阶段最优
29、决策表回溯 ：有多组最优解。 I：x3=1, x2=3, x1=1, R3=0.8 0.9 0.9=0.648 II：x3=2, x2=2, x1=1, R3= 0.90.80.9=0.648III: x3=2, x2=3, x1=0, R3= 0.90.90.8 =0.648 资源分配问题可描述如下：设有某种原料，资源分配问题可描述如下：设有某种原料，总数量为总数量为a，分配给分配给n个使用者。已知第个使用者。已知第i个使用者个使用者得到数量得到数量xi的资源，可创造的收益为的资源，可创造的收益为gi（xi）。）。问问应如何分配该资源，才能使总收益最大。应如何分配该资源，才能使总收益最大。4
30、.4 动态规划的应用动态规划的应用(二二) 用用动动态态规规划划法法处处理理这这种种问问题题时时，通通常常把把给给一一个个使使用用者者分分配配资资源源的的过过程程看看成成一一个个阶阶段段，按按n n个个使使用用者者分分成成先先后后n n个个决决策策阶阶段段。即即先先给给第第1 1个个使使用用者者分分配配资资源源，为为第第一一阶阶段段；再再给给第第2 2个个使使用用者者分分配配，为为第第2 2阶阶段段；依依此此类类推推，最最后后给给第第n n个使用者分配，为第个使用者分配，为第n n阶段。阶段。 2 资源分配问题资源分配问题 例例 某工业部门根据国家计划安排，拟将五某工业部门根据国家计划安排，拟
31、将五台某种高效率的机器分配给所属的甲、乙、台某种高效率的机器分配给所属的甲、乙、丙三个工厂，各工厂得到不同数量的机器可丙三个工厂，各工厂得到不同数量的机器可获得的收益如下表。问应如何分配机器，才获得的收益如下表。问应如何分配机器，才能使各厂的总效益最大。能使各厂的总效益最大。 某某单单位位准准备备在在以以后后的的n n个个时时期期内内采采购购一一批批物物资资。各各时时期期的的价价格格不不是是确确定定的的，而而是是按按照照某某种种已已知知的的概概率率分分布布取取值值。试试制制定定采采购购策策略略，确确定定在在哪哪一一时时期期以以什什么么价价格格采采购购，能能使使采采购购价价的的数数学学期期望望值
32、值最最低低。这这类类问问题题也也适合用动态规划法进行处理。下面通过实例加以说明。适合用动态规划法进行处理。下面通过实例加以说明。例例7 7 某厂生产上需要在近五周某厂生产上需要在近五周内采购一批原料，而估计在未内采购一批原料，而估计在未来五周的价格有波动，其浮动来五周的价格有波动，其浮动价格和概率策得如下表。试确价格和概率策得如下表。试确定该厂应在哪一周以什么价格定该厂应在哪一周以什么价格购入，能使其采购价的数学期购入，能使其采购价的数学期望值最小，并求出期望值。望值最小，并求出期望值。4.4 动态规划的应用(三) 3 不确定性采购问题解:按釆购期限5周分为5个阶段,将每周的价格看作该阶段的状
33、态y yk k-为状态为状态变变量量, ,表表示笫示笫k k周的实际价格周的实际价格y ykEkE-表表示笫示笫k k周周等待等待, ,而在以后采取最优决策时采而在以后采取最优决策时采购价格的购价格的期望值期望值f fk k(y(yk k) -) -表表示笫示笫k k周周实际价格实际价格为为y yk k时时, ,从第从第k k周周至至第第5 5周周釆取最优决策所得的最小期望值釆取最优决策所得的最小期望值基本方程为 设有n个工件需要在机床A、B上加工，每个工件都必须先经过A而后B两道加工工序。以ai、bi分别表示工件i(1in)在A、B上的加工时间。问应如何在两机床上安排各工件的加工顺序，使在机
34、床A上加工第一个工件开始到在机床B上加工完最后一个工件为止，所用的加工总时间最少？ 加工工件在机床A上有加工顺序问题，在机床B上也有加工顺序问题。可以证明：最优加工顺序在两台机床上可同时实现。因此，最优排序方案可以只在机床A、B上加工顺序相同的排序中寻找。即使如此，所有可能的方案仍有n!个，这是一个不小的数，用穷举法是不现实的。4.4 动态规划的应用(四) 4 排序问题 用用动动态态规规划划法法可可以以推推出出，工工件件i i应应该该排排在在工工件件j j之之前前的的条条件件为为 min(amin(ai i,b,bj j)min(a)min(aj j,b,bi i) )。根根据据这这个个条条件
35、件，构造下列排序方法：构造下列排序方法： a a1 1 a a2 2 a an n 1) 1)建立工时矩阵建立工时矩阵 M= M= b b1 1 b b2 2 b bn n 2)2)在在工工时时矩矩阵阵M M中中找找出出最最小小元元素素（若若不不止止一一个个可可任任选选其其一一），若若它它在在上上行行，则则相相应应的的工工件件排排在在最最前前位位置置；若它在下行，则相应的工件排在最后位置。若它在下行，则相应的工件排在最后位置。 3)3)将将排排定定位位置置的的工工件件所所对对应应的的列列从从M M中中划划去去，然然后后对对余余下下的的工工件件再再按按2)2)进进行行排排序序。如如此此进进行行下下去去，直直到到把所有工件都排完为止。把所有工件都排完为止。 当加工顺序排定之后，工件在当加工顺序排定之后，工件在A A上没有等待时间，上没有等待时间，而在而在B B上则常常需要等待。因此，寻求最优排序方案上则常常需要等待。因此，寻求最优排序方案只有尽量减少在只有尽量减少在B B上等待加工的时间，才能使总加工上等待加工的时间，才能使总加工时间最短。时间最短。 例 设有5个工件需在机床A、B上加工，加工的次序为先A后B，每个工件需要的加工时间如下表。 试安排加工顺序，使总加工时间最少，并求出总加工时间。
