数学建模第九章排序问题ppt课件.ppt

《数学建模第九章排序问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模第九章排序问题ppt课件.ppt（86页珍藏版）》请在三一办公上搜索。

1、第九章 排序问题,组合优化理论,Combinatorial Optimization Theory,第九章 排序问题,4 旅行商问题,1 单机排序问题,2 平行机排序问题,3 车间作业排序问题,一个机械加工车间要加工一批机器零件，每一个零件都具有相同的工序，即按相同的顺序在几个不同的机床上加工，但每个零件在每个机床上的加工时间可能不同 . 如何按排加工顺序才能以最短的时间加工完所有的零件 .,机械加工,Example 1,第九章 排序问题,这是一个流水线排序问题 .,第九章 排序问题,在计算机多道程序操作系统中，并发执行多个进程，任何时刻CPU只能执行一个进程，进程的到达时间是不同的，怎样调度

2、这些进程才能使CPU的利用率最高或进程的平均周转时间最短？,进程调度,事先不知道每个进程的到达时间和执行时间在线排序,事先知道随机到达时间和执行时间的分布、数学期望、方差，目标是极小化平均周转时间的数学期望随机排序,Example 2,第九章 排序问题,机场调度,在一个飞机场，有几十个登机门，每天有几百架飞机降落和起飞，登机门的种类和大小是不同的，而班机的机型和大小也是不同的.,飞机按时刻表降落和起飞，当飞机占有登机门时,旅客上下飞机，飞机要接受加油、维护和装卸行李等服务 . 由于天气和机场的原因，飞机不能起飞，登机时间推迟.,调度人员如何制订一个登机门的分配方案，使机场的利用率最高或晚点起飞

3、的飞机最少.,登机门机器， 飞机零件， 机场的规定约束条件,Example 3,第九章 排序问题,由于效率的度量方法的不同、引进不同的约束条件和机器的数量、类型等，使之得到不少的排序模型，也使排序问题有了更多的应用.,用一台或一台以上的机器加工两个或两个以上的零件（任务）时，确定加工顺序使效率最高。, 排序（Scheduling）问题,由于应用范围逐渐扩大，新的问题不断出现，因而从事这一领域研究的人与日俱增，其内容也越来越丰富，应用也越来越广泛.,第九章 排序问题,确定性排序,随机性排序,在线排序 （On-line Scheduling ）,半在线排序 (Semi- On-line Sched

4、uling ),离线排序 （Off-line Scheduling ）,(Deterministic Scheduling),所有数据在进行决策前都是已知的,（Stochastic Scheduling）,有的数据在进行决策前是未知的，是随机变量,但它们的分布是已知的,常见的目标函数（效率的度量方法）,用 C = (C1，C2，Cn) 表示任务的完工时间，极小化的目标函数总是完工时间 Cj 的函数.,（1） 时间表长,时间表长（schedule length，makespan）定义为,它等于最后一个被加工完任务的完工时间，小的时间表长意味着处理机有高的利用率.,第九章 排序问题,第九章 排序问

5、题,（2） 平均加权流时间和加权总完工时间,平均加权流时间（mean weighted flow time）是,任务的到达时间,其中 是任务Tj 的流（周转）时间，,它等于任务在系统中等待时间和加工时间的和.,对平均加权流时间进行变形，可得极小化 F 相当于极小化加权总完工时间（total weighted completion time ）,( 如果 wj = 1 j = 1,2,n 即 为总完工时间),第九章 排序问题,式中的第一项的分母和第二项都是常数，所以,第九章 排序问题,（3） 最大延误,最大延误（maximum lateness）定义为,任务的截止期限,（4） 加权总误工,加权总

6、误工（total weighted tardiness）是,其中 Lj = Cj dj 是任务 Tj 的延误时间 .,其中 Dj = max Cj dj ，0 是任务 Tj 的误工时间 .,第九章 排序问题,（5） 加权误工任务数,加权误工任务数（weighted number of tardy tasks）是,第九章 排序问题,排序问题的三要素：,机器（处理机）、作业（任务）、目标函数,用三元组,描述一个排序模型,：机器的数量和类型；：作业的约束条件； ：优化的目标函数.,基本假设：,（1）任务或作业和处理机都是有限的；,（2）在任一时刻，任何处理机只能加工一个任务或一 道工序;,（3）极小

7、化单一目标函数.,第九章 排序问题,Definition 1,对于一个可行排序，如果有准备好被加工的任务或工序，不准有空闲的处理机，称这种可行排序为无耽搁排序（nondelay schedule）；否则称为耽搁排序（delay schedule）。,无耽搁排序相当于有工作可做就不能闲着. 对于大多数排序问题，包括所有的可中断排序，最优排序是无耽搁排序，然而也有一些不可中断排序问题的最优排序是耽搁排序.,第九章 排序问题,排序问题,1：表示一台机器rj: 表示任务有不 同的到达时间,n = 2，t = (10，5)，r = (0，1)，w = (1，5),该问题有两个可行排序，用 Gantt C

8、harts 表示：,0 10 15,A,B,0 1 6 16,B,A,nondelay schedule:,delay schedule:,Z1 = 10*1+15*5 = 85,Z2 = 6*5 + 16*1 = 46,Example 4,第九章 排序问题,阿克米自行车的装配问题,这是一个 排序问题.,由两名熟练工人进行装配，要求装完时间最早.,0 2 5 7 8 9 1516 23 31,P1,P2,A,B,C,E,F,G,H,I,J,D,Example 5,第九章 排序问题,如果每道工序的加工时间减少1，最优时间表会小于 31 吗？是 26 吗？,0 1 3 4 5 7 13 20 27

9、,A,B,J,D,C,E,F,G,H,I,P1,P2,最优耽搁排序,第九章 排序问题,A,B,C,D,E,F,G,H,I,J,0 1 3 4 5 7 1213 18 20 32,P1,P2,最优无耽搁排序,第九章 排序问题,如果加工时间不变而增加一个装配工人，最优时间表会小于31 吗？,最优耽搁排序,0 2 4 5 6 8 14 15 22 30,P1,P2,P3,A,D,F,G,E,C,H,B,I,J,第九章 排序问题,最优无耽搁排序,0 2 4 5 6 8 1415 21 36,P1,P2,P3,A,D,E,F,G,H,I,B,C,J,Go back,1 单机排序问题,第九章 排序问题,单

10、机排序问题是最简单的一类排序问题，同时也是最重要的排序问题之一. 首先单机排序问题比较容易求出解决方法，这些方法对于研究较复杂的排序问题具有指导作用，可为处理复杂排序问题提供近似算法；其次，单机排序问题大量存在于现实生活中，具有广泛的实际背景，许多实际问题都可以归结为单机排序问题 .,1 单机排序问题,设一个机修车间有 n台不同的机床要进行大修, 它们的维修时间已知为 t1, t2, , tn , 而机床 Ai 在车间逗留的过程中每单位时间的损失费为 wi (i =1,n),如何排序？,试求一种排序，使得 n台机床在修理完毕时，总的损失为最小.,A1,A2,A3,A4,如何排序？猜,Examp

11、le 6,第九章 排序问题,设 n台机床维修的排序为 (k1, k2, , kn) 则机床,的维修完毕的时间为,n 台机床按此排序维修完时，总的损失费为,本题要寻找一种排序 （r1, r2, , rn）满足,Solution :,1 单机排序问题,设有两排序,（1）,（2）,分析排序（1）与（2）的优劣,总损失费仅在km,km+1处有区别,按（1）排序,按（2）排序,第九章 排序问题,排序（2）优于排序（1）.,Theorem 1,满足下列条件的排序 （r1,r2,rn）,为问题 的最优排序 .,1 单机排序问题,如: 考虑排序问题,其中 n = 5, t = (12，4，7，11，6)， w

12、 = (4，2，5，5，6),由,此时,得最优排序为,第九章 排序问题,在 Ex. 6 中，如果考虑各待维修的机床在机修车间平均逗留时间（或总逗留时间）最短，,如何排序？,这只是 Ex. 6 中 wj =1/n 和 wj = 1 的特例,为最优排序 .,或,所以，满足下列条件的排序（r1, r2, rn）,1 单机排序问题,以下讨论的排序问题都与工期有关，即每个任务均有一个工期。工期 dj表示对任务 Tj限定的完工时间.如果不按期完工，应受到一定的惩罚.,任务没有准备时间的最大延误的排序问题比较简单，只需将任务按最早工期优先（Earliest Due Date first，简记 EDD）规则，

13、就可以得到最优排序. 按照这一规则，任务按 dj 不减的顺序进行排序.,第九章 排序问题,Theorem 2,prove,由EDD规则可以求得最优排序,Go on,对于问题 EDD 规则可以得到最优排序 .,Example 7,考虑排序问题 ，其中 n = 6 , t = ( 3, 1, 4, 1, 3, 2)，d = (2, 10, 6, 4, 11, 12),1 单机排序问题,Theorem 2 的证明,Go back,只需证明任何不满足EDD规则的排序，均可转化为满足EDD规则而目标函数不增。,设某一排序 s 违反了 EDD 规则，则在此排序中，至少有两个相邻任务,p dk dj,p d

14、k dj,Tj,Tj,Tk,Tk,第九章 排序问题,在许多情况下，延误时间的长短并不重要。只要有延误发生，造成的影响是一样的. 例如用航天飞机发射太空站，每个太空站都要完成特定的太空观测任务, 误期发射的太空站将失去作用. 此时，目标应使误期发射的太空站数目最少.,误工任务数问题,Example 8,设有 n 个工件 T1, T2, , Tn 要在一台机器上加工，加工时间分别为 t1, t2, , tn ，要求的交货日期分别为 d1, d2, , dn . 试求一种加工排序，使得误期交货的工件最少 .,算法:,（1）把任务按 EDD 规则排序；,（2）计算各任务的完工时间，如果当前排序已无延

15、误任务，则转（5），否则转（3）；,（3）找到第一个延误任务，不妨设为第 k 个任务；,（4）在前 k 个任务中选取并删除加工时间最长的任 务，得到一个部分排序，转（2）；,（5）将删除的任务以任何顺序排在所得的部分排序 之后，得到最优排序.,prove,Go on,1 单机排序问题,Theorem 3,对于问题 , 上述算法给出最优排序,第九章 排序问题,Theorem 3 的证明,假定 ，令 Fk 表示前 k 个任务构成的集合 T1,T2,Tn 的子集，满足下述两个条件：,集合 Fn 与最优排序相对应 . 下面用数学归纳法证明算法产生的排序就是 Fn .,1、在任务集 T1,T2,Tk 的

16、所有子集中，Fk 具有最 多按期完工的任务，按期完工的任务数记为 Nk ;2、在 T1,T2,Tk 的所有含有 Nk 个按期完工任务 的子集中，Fk 中的任务所用的总加工时间最少 .,1 单机排序问题,分两种情况讨论：,当 k = 1 时，显然满足；,假设对前 k 个任务算法产生的排序是 Fk，Fk 满足上述两个条件；,对前 k+1 个任务，由 Fk 出发，按算法要求可产生满足上述两个条件的 Fk+1 ,Case 1 将任务 Tk+1 加入 Fk 后，Tk+1 按期完工 . 此时， Nk+1 = Nk + 1 , Fk+1 = Fk Tk+1 ，显然上述两个条件满足；,第九章 排序问题,Cas

17、e 2 将Tk+1 加入 Fk 后，任务Tk+1 没有按期完工 .,由 Nk 是任务集 T1,T2,Tk 的子集中按期完工任务数最大的一个，以及 Fk 是含有 Nk 个任务的子集中加工总时间最少的一个，可知 Nk+1 = Nk . 将 Tk+1 加入 Fk 中没有增加按期完工的任务数，但应从任务集 Fk Tk+1 中删除加工时间最大的一个任务，因此 Fk+1 满足上述两个条件 .,1 单机排序问题,按EDD规则，重新排序得右表.,此时，任务T8 延误，而在前三项任务中， T8 的加工时间最长,所以将T8 放至最后，得一新表.,Example 9,考虑排序问题 ，其中 n = 8,t = ( 1

18、0, 6, 3, 1, 4, 8, 7, 6 ) , d = (35, 20, 11, 8, 6, 25, 28, 9 ),Solution :,第九章 排序问题,此时，任务 T7 延误，而在前六项任务中， T6 的加工时间最长，所以将 T6 放至最后，得一新表.,1 单机排序问题,目前，前六项任务中已没有延误任务，所以此时为最优排序.,有两个任务T8 、T6 延误.,第九章 排序问题,设 Dj 表示任务 Tj 的误工时间，使整个误工最小的排序是十分重要的 . 因为单纯讨论使误工任务数最少可能会使有些任务的等待时间变得很长 .如果将目标函数换成 ，研究它的极小化，则不会产生上述现象，这也很有应

19、用背景 .,自然会想到能否按 EDD 规则排序，即按 dj 不减的顺序进行排序 . 能得到最优排序吗？,1 单机排序问题,设排序 （r1, r2, , rn）(1) 满足,与排序 （r1, , ri+1, ri, , rn）(2) 进行比较：,若 Tri , Tri+1 在（1）中不误期，则在（2）中Tri+1 不误期,而在 Tri 前插入 tri+1单位时间,就有误期的可能；,若 Tri 在（1）中不误期，而 Tri+1 在（1）中误期 l 单位时间，则由于 ，任务 Tri 在（2）的误期,第九章 排序问题,Go back,若 Tri 在(1)中有误期 l 单位时间，而Tri+1 在(1)中

20、没有误期，则在(2)中 Tri+1 仍没有误期，而在 Tri 前插入 tri+1 单位时间，任务 Tri 在(2)中的误期,若 Tri、Tri+1 在(1)中都有误期 l、s 单位时间，则,平行机排序问题（Parallel Machine Scheduling）是多处理机排序问题的一种情况 . 所谓平行机是指参与完成任务的的处理机具有完全相同的作用，即任务在任一处理机上处理都可以. PMS 是排序中研究较早，很有代表性的一个问题，在理论上它是单机排序问题的推广，在应用上则具有更广泛的实际背景.,任务集,无关（任务间是独立的）,相关（任务有紧前要求）,处理机,同速机,恒速机,变速机,2 平行机排

21、序问题,第九章 排序问题,可中断如何？,同速机不可中断地处理无关任务集的时间表长问题 .,设有 m 台完全相同的处理机 Pj ( j = 1 m ) , n个相互独立的任务 Ji ( i = 1 n ), Ji 的加工时间为 ti ( i = 1 n ),则问题可用 IP 描述如下：,2 平行机排序问题,该问题与装箱问题是密切相关的，有相同的判定问题，常互称为对偶问题. 把箱子与处理机对应，物品与任务对应，则装箱问题是箱长给定，目标是箱子数最少. 该问题是箱子数给定，而使箱子长度最短.,(1)考察它的连续松弛问题,则松弛问题的最优值,(2) 对原问题的任一实例 I ，一定有,Theorem 4

22、,第九章 排序问题,二、近似算法,1、LS 算法 （List Scheduling）,LS算法是由Graham于1966年首先提出，他在研究LS算法的近似程度时，第一次提出了近似算法的最坏情况进行分析的办法.从此讨论近似算法的绝对或渐进性能比，就广泛地应用于组合优化的研究中.,Theorem 5,问题 最优值的一个下界为,2 平行机排序问题,LS算法的思想是按任务给定的顺序，将每一个工件分给最早空闲的机器（也即使该工件最早完工的机器）加工，在安排当前任务的加工时，不要求知道下一个工件的信息，所以特别适用于在线排序问题.,LS 算法,step 1 设 Lj = 0 j = 1 m k = 1,s

23、tep 2,若 令,若 k = n + 1 时，停止；否则 重复 step 2 .,第九章 排序问题,prove,0 1 2 4 7 8 9 14,P1,P2,P3,Solution :,Example 10,考虑排序问题 ，其中,m = 3，n = 7， t = ( 1, 4, 2, 8, 6, 3, 7) .,你有想法吗？,Theorem 6,2 平行机排序问题,2、LPT 算法 （Largest Processing Time）,LPT 算法思想是先将任务按其加工时间从大到小的顺序排列，然后用LS算法排序。这也是Graham 给出的,它要求任务的信息全部已知后才开始加工。,见前例 t =

24、 (1, 4, 2, 8, 6, 3, 7 ),按加工时间重新排列,J = ( J4, J7, J5, J2, J6, J3, J1 ) t = ( 8, 7, 6, 4, 3, 2, 1 ),Theorem 7,第九章 排序问题,0 6 7 8 10 11,P2,P3,P1,一定是最优值吗？理由：1、 2、反例,Go back,J = ( J4, J7, J5, J2, J6, J3, J1 ) t = ( 8, 7, 6, 4, 3, 2, 1 ),2 平行机排序问题,Theorem 6 的证明,Proof :,分两步,(1) 证明对任意的实例 I,(2) 说明该界不可改进 .,（1）用反

25、证法证明,假设该结论不成立，则存在一反例 I 使,考虑反例中任务数最少的一个（称为最小反例）.,第九章 排序问题,由于 I 为最小反例，所以 fLS(I) 等于最后一个任务 Jn 的完工时间 .,因为若不然，设 Jk 的完工时间等于 fLS(I)，,考虑新的任务集 J1, J2, , Jk , 则对由此任务得到的新实例 I* 有,因此 有,说明 I* 是一个更小的反例 .,由 s 为开始加工 Jn 时刻，则 fLS(I) = s + tn .,由 LS 规则,Jn 是分给最早空闲的机器加工，,2 平行机排序问题,由 Th 5 知,因此,这与 I 是反例矛盾，此矛盾说明,（2）考虑任务集 J1，

26、J2，J m2 m + 1 ，其加工时间分别为： t1 = t2 = = t m2-m = 1 , t m2-m+1 = m ,第九章 排序问题,Go back,需分给 m 台机器加工，易证 fLS(I) = 2m 1, fopt(I) = m .,故,因此 有,车间作业排序问题是多处理机中多类型机排序问题,m个处理机具有不同的功能,处理机集,车间作业排序问题：,1、同顺序(流水)作业排序问题,3、自由(开放)作业排序问题,2、异顺序作业排序问题,3 车间作业排序问题,设有作业集,每个作业 Jj 有 m 道工序：T1j，T2j，Tmj，,工序 Tij 的加工时间为 tij,各作业分别在处理机

27、P1，P2 , Pm 上完成各道工序.,第九章 排序问题,Note:,在流水作业排序问题中，各作业均依次在处理,机 P1, P2, , Pm 上完成各道工序. 但对于同一台处理,机, 各作业在其上的加工顺序可能不同.,排列排序（permutation schedule）,各作业在全部处理机上的加工顺序相同的排序,对于 的情况，同顺序作业排序问题的最优排序未必是排列排序. 即排列排序中可能不含有最优排序 .,3 车间作业排序问题,m 个处理机，流水作业,排列排序共有两个，排序时间表长均为,0 1 5 6 7 11 12,P1,P2,P3,P4,最优排序不是排列排序，也不是无耽搁排序,Exampl

28、e 11,考虑排序问题 其中 m = 4, n = 2.,第九章 排序问题,Theorem 8,对于流水作业排序问题，至少存在一个 最优排序，在此最优排序中，其最前面两台处理P1 , P2 上各作业的加工顺序相同.,Theorem 9,对于流水作业排序问题，至少存在一个 最优排序，在此最优排序中，其最后两台处理Pm-1 , Pm 上各作业的加工顺序相同.,P1,P1,P2,P2,一定有在第一台处理机上无耽搁的最优排序,3 车间作业排序问题,Shortest ProcessingTime first Longest ProcessingTime first,Theorem 10,对于排序问题 ，

29、Johnson 算法,产生最优排序.,Johnson 算法 ( SPT-LPT),(1) 把作业按工序加工时间分成两个子集：,对于满足 t1j = t2j 的作业可分在任一集中；,(2) 先将集 J1 中的作业按 t1j 不减排列 (SPT 规则)，,再将集 J2 中的作业按 t2j 不增排列 (LPT 规则).,第九章 排序问题,0 2 5 6 1112 42 4647,P1,P2,Example 12,考虑排序 其中 n = 5,Solution :,由 Johnson 算法可得：,J1 中的作业按 t1j 不减排列：J5,J1,J4; J2 中的作业按 t2j 不增排列：J3, J2,

30、所以最优排列为 J5, J1, J4, J3, J2,时间表长为 Cmax = 47 .,3 车间作业排序问题,Example 13,考虑排序 其中 n = 3,Solution :,建立整数规划模型 .,设 xij 为作业 Ji 在处理机 Pj 上开始加工的时间，第一组约束为每一作业在处理机上加工顺序：,第九章 排序问题,第二组约束为一族选择性的约束条件，以保证每一处理机同一时间只能处理一个作业：,如对 P1,有：,或,引进 0-1 变量 y1 , 上述选择性约束条件为：,类似 y2, y3, y4 为 0-1 变量，对处理机 P2, P3. P4 有,3 车间作业排序问题,Go back,

31、第三组约束条件为三个作业的完工时间,将它化为线性约束,目标函数为,若在原问题上再要求作业 J2 在各处理机上的加工和等待时间总和不超过 21 .,第九章 排序问题,4 旅行商问题,（Traveling Salesman Problem）,TSP :,有一位旅行售货员，欲到城市 v1，v2,，vn 进行商品销售，已知： 的距离为 wij.( , ).他从其中某个城市出发，需访问每一个城市一次且仅一次（在欧氏距离下）而回到出发的城市.问应如何计划他的旅行路线，使他所走路线的总长度最短？,一、旅行商问题的描述,4 旅行商问题,设：,TSP 问题的数学模型：,表示回路通过 第 i 个城市到第 j 个城

32、市的边,否则,第九章 排序问题,二、分枝定界法,1、最小生成树算法解 TSP,网络中构成 Hamilton 回路的条件：,a、回路与各个顶点之间有且仅有两条边关联；,b、回路是连通的.,仅以连通作为问题的松弛条件。显然，在赋权网络中，总权数最小的连通子图为最小生成树 .,4 旅行商问题,设 G = ( V, E, W)，构造一个新的网络,构造过程如下：,任选 V 中顶点 vx 用两个顶点 s、f 代替,对所有 的边，,对所有的,第九章 排序问题,M 为足够大的数，使应用最小生成树算法时与 s、f 关联的边不被选入最小生成树 .,显然，在原网络 G 中的最优 Hamilton 回路,与开网络 中

33、最优 Hamilton 道路,是对应一致的，且 的长度比 恰好多 2M .,4 旅行商问题,210,222,211,207,400,31,33,37,210,34,20,222,15,211,207,Example 14,考虑一个对称网络 G，,解它的 TSP .,Solution :,令 M = 200 得费用矩阵 如右上：,第九章 排序问题,210,222,211,207,400,31,33,37,210,34,20,222,15,211,207,483,S、f 不能与一 个顶点相连,可去掉 35 吗？,4 旅行商问题,210,222,211,207,400,31,33,37,210,34

34、,20,222,15,211,207,483,496,第九章 排序问题,210,222,211,207,400,31,33,37,210,34,20,222,15,211,207,501,4 旅行商问题,210,222,211,207,400,31,33,37,210,34,20,222,15,211,207,487,此时，问题 p3 为可行解，且没有目标值 小于 487 的活问题。所以，问题 p3 的解是原问题的最优解。旅行路线为：,Zmin= 87,第九章 排序问题,2、分配问题算法解 TSP,去掉约束条件（3），恰好为分配问题. 所以，取分配问题为 TSP 的松弛问题.,dii= M,4

35、 旅行商问题,（原问题的下界）,Example 15,考虑一个非对称网络的 TSP 问题，,距离矩阵如右：,Solution :,任取一可行解 C：,其余 xij = 0 .,于是，初始定界（上界）,用匈牙利法求 D 的最优分配，得：,其余 xij = 0,第九章 排序问题,由于松弛解产生了子圈，因此要破圈分支.,D,D1,D2,*,考察 D 的分支，D1: x15 = 0; D2 : x15 = 1 且 x51 = 0,x15 = 0,x15 = 1 且 x51 = 0,x13 = x32 = x24 = x45 = x51 = 1,解 D1 得 x13 = x32 = x24 = x45

36、= x51 = 1,其余 xij = 0 是原问题的可行解,4 旅行商问题,此时已没有活问题，所以 D2 的松弛解即为最优解,D,D1,D2,*,*,x15 = 0,x15 = 1 且 x51 = 0,解 D2 得 x15 = x54 = x43 = x32 = x21 = 1,其余 xij = 0 是原问题的可行解,第九章 排序问题,三、近似算法,1、最近邻域算法（NN）,作为一步算法，在第二章中已介绍，,Theorem 11,对任意 TSP 实例 I,且存在一系列实例 In , 使,从而,4 旅行商问题,2、生成树加倍法（MST）,生成树加倍法的基本思想是通过对网络 G（V，E，W）的最小

37、生成树 T 的每条边加倍得到 Euler 图，再删去Euler 回路中的重复顶点，得到 G 的一个环游，作为 算 法的解.,Theorem 12,RMST = 2,第九章 排序问题,1,1,4,3,2,2,3,3,1,3,4,4,4,3,2,Example 16,用生成树加倍法求 TSP 的近似解.,Solution :,得到最小生成树，如图,重绕生成树 (以 v1 为始点 ) 得 Euler 回路，,删除重复点，得 TSP 的近似解,fC0 = 13,4 旅行商问题,四、应用例题,有个配制油漆的公司,要配红漆500加仑(R),蓝漆750加仑(Blue),白漆1000加仑(H),黑漆900加仑

38、(Blank),黄漆200加仑(Y),清洗配制油漆的机器所需的时间取决于上一次所配漆的颜色与下一次欲配漆的颜色，时间如表，问如何安排配漆次序，使清洗时间最省？,Example 17,第九章 排序问题,这是一个一台机器 n 个工件有调试时间的排序问题.,它可化为 Hamilton 回路问题：,1、若仅考虑一次循环，则在 5 个点上再加上一个点 z ，与 z 关联的边的时间为零，其余为清洗时间；,2、若该工作是日复一日，则不必引进点，只需求5 个点的最优 Hamilton 回路.,4 旅行商问题,在轧钢等生产工艺中，为了保证工件的温度，在一台机器上加工以后，必须立即转送到下一台机器上加工，中间不允

39、许出现等待现象. 现设共有 n 个工件 Ji（i =1n）需加工，且加工中具有以下特点：,a. 加工不同工件时，使用机器的顺序可以不同；,b. 每一工件在每台机器上至少加工一次；,c. 每台机器加工各工件的顺序相同；,d. 不允许有中间等待.,要求确定一个工件的排序,使得总加工时间最少.,Example 18,第九章 排序问题,先看一个3 台机器，2 个工件的实例：,P1,P2,P3,2,1,1,1,2,2,1,2,2,1,从图中可知，由于工件加工时间确定，要使总加工时间最少，关键是开工时间差，而工件加工次序不同，时间差不一样. 为此，先求出每一对工件 Ji，Jj 的两个最小时间差.,4 旅行商问题,Cij 表示 工件 Ji 加工后加工工件 Jj 的最小时间差.,构造一网络 G : 以 Ji ( i = 1n) 及 z 为顶点，Cij 为（Ji，Jj）的权，（z，Ji）的权为零，而 （Ji，z）的权为 Pi ( Pi 为 工件 Ji 的总加工时间)，则原问题即为在 G 上寻找最优的 Hamilton 回路.,第九章 排序问题,旅行售货员问题是很有应用前景的模型，如公安值勤人员的最优巡回路线、流水作业生产线的顺序问题、装配线进度问题、数控机床的运行问题，以至机组人员的轮班安排、教师任课班级负荷分配等问题，都是直接或间接与旅行售货员问题有关.,第九章 排序问题,完,