（运筹学与控制论专业论文）带恶化和学习效应的排序模型.pdf

兰州大学2 0 1 0 届硕士学位论文 中文摘要 本文主要讨论了带恶化效应和学习效应的单机排序和单机成组排序问题。对 于这两个问题分别给出了两个模型，并对这些模型给出了相应的多项式算法。 第二章的第一、二节分别研究单机排序模型1i 既，l = ( 尼+ a ( 功，iao 和 1 i 段，1 = + a ) l ( o ，对目标函数分别为时间表长、总完工时间以及总完 工时间平方和，证明了多项式可解性；对目标函数为极小化最大延误，在满足 刀以当且仅当zs 以( ，= l ，2 刀) 的情况下，同样证明了多项式可解性。 第三章的第一、二节分别对单机成组排序问题的两个模型进行了研究。 对于模型11 只一= 口( 1 + r ，口dd ) 弓，= a ! , a t i f ( o 和模型1 1 只，】= a 。( + 刎卢，_ = 6 ，( 口+ ，g t i ( c ) ，当目标函数分别为时间 表长和总完工时间时，我们给出了多项式算法；当目标函数为加权总完工时间， 在且满足口。，- a 。，当且仅当蟛一s ，( ，= 1 ，2 功时，我们也给出了多项式算法。 关键词：排序、学习效应、恶化效应、多项式算法、成组技术 兰州大学2 0 1 0 届硕士学位论文 a b s t r a c t i nt h i sp a p e r , w ec o n s i d e rt h es i n g l e m a c hi n es c h e d u l i n ga n dt h es i n g l e - m a c hi n e s c h e d u l i n gu n d e rg r o u pc o n s u m p t i o nw i t ht h ee f f e c t so fd e t e r i o r a t i o na n dl e a r n i n g e a c hp r o b l e mh a st w os c h e d u l i n gm o d e l , a n df o rd i f f e r e n to b j e c t i v ef u n c t i o n , w eg i v e p o l y n o m i aia l g o ri t h m h l t h es e c o n d c h a p t e r , w es t u d yt w os i n g l e - m a c h i n es c h e d u l i n gm o d e l , 1i 勖，j = ( p , - + a ( 功，i 【da n d l f 办，j = 以广十( ，) ) i ( 回w e s h o wt h a tt h e m a k e s p a n , t o t a lc o m p l e ti o na n dt o t a ls q u a r eo fc o m p l e t i o ni sp o l y n o m i a l l ys o l v a b l e u n d e re a c ho ft h ep r o p o s e dm o d el s w ea l s os h o wi t sp o l y n o m i a l l ys o l v a b l ef o r t a r d i n e s sw h e nw ea s s u l r l et h a t 只- ( ，+ 1 ) 卢，一h - ) 0 ， 所以 c k t 】( 万) q 州】( 万。) 。 这与，r 是最优排序矛盾，定理证毕。 2 1 3 极小化总完工时间 定理2 对于问题1l 鳓，】= + a ( ，) 沙芦i e ，最优排序满足各个工件间按基本加 工时间( ，= l ，2 ，刀) 非减排序( s p t 规则) 。 证明：我们沿用定理l 所做的假设和证明结果，由定理l 的证明过程易知 q ，】( 万) ，】( 万。) 和q 删( 7 r ) g 州l ( t r ) ，于是有 q ，】( 7 r ) + e 【，+ l j ( 万) q ，】( 万。) + q l j ( t r 。) 。 可知万不是最优排序，定理证毕。 由定理2 的证明易得以下推论 推论1 对于问题l l 毁，】- - ( p j + a ( t ) ) r 卢l 口，最优排序满足各个工件之间按基 本加工时间只u = l ，2 ，刀) 非减排序( s p t 规则) 。 6 兰州大学2 0 1 0 届硕士学位论文 2 1 4 极小化最大延误 对于最大延误问题l i 角，】= + a ( 功，lk 情况比较复杂，但如果工件的基 本加工时间和工期有一致关系，即办办当且仅当嘭砟，则存在多项式算法。 定理3 对问题l i 毁，1 = + a ) 厂卢i k ，若工件的基本加工时间和工期有一致 关系，即p , - s a 当且仅当矿s 么，最优排序满足各工件之间按工期 z = 1 ，2 ，刀) 非减排序( e d d 规则) 。 证明：我们依然沿用定理l 证明过程中所做的假设和证明结果，根据定理i 的证 明过程，可知 工件z 与以在排序万中的最大延误分别为 厶，1 ( 万) = q ，1 ( 万) 一z ， 么，q 】( 疗) = 州1 ( 7 r ) 一之， 在排序刀中的最大延误分别为 磊，】( 万) = ，】( 万。) 一以， 厶，。】( 万) = q 。j ( 7 r ) - 4 ， 由定理1 知q ，1 ) ，】 。) 和州( 万) q 州】( 万) ，得删o ) 一( 万) ，又 因为只夕。及衫s 以，可知 毛，十i 】( 7 r ) 厶，j ( 万) ， 磊，+ 1 】( 趸) m 】( 巧) ， 得： m a x ( 厶，】( 丌) ，白1 j ( 万) ) m a x ( z 珥，j ( 7 r ) ，厶1 j ( 万) ) 。 定理证毕。 7 兰州大学2 0 1 0 届硕士学位论文 2 2 单机排序模型l i 绞，】= + 伍( ，) ) i 2 2 1 问题描述及符号说明 由于问题的相似性，我们沿用了上一节的符号和证明思路。在本节中，工件 的实际加工时间也是其开工时闻和加工位置的函数，假设工件z 排在第，个位 置加工，那么工件z 的实际加工时间乃，】为 p 。i 、；p 一七镁吣， l = 1 , 2 ，玎 其中刃为工件z 的基本加工时间；a ( 力为关于，非负单增的恶化函数：，为关于 ，的非负单减的学习函数，厣 ( 厂+ 1 ) 卢，( 办一所) 0 ， 所以 ，+ 】( 7 r ) 【，+ l j ( 万) 。 这与疗是最优排序矛盾，定理证毕。 由定理4 的证明过程可知，c 川( 7 r ) e , v i ( 万) 和气删( 7 r ) q 州】( 石) ，对问 题li 乃，】= ( + a p ) ) i ( o ，用相似的证明方法，可给出与定理2 、和推论1 相似的结论。 2 2 3 极小化总完工时间 定理5 对于问题l l 鼽，】= ，+ 晓p ) ) l 仁，最优排序满足各个工件间按基本 加工时间露( ，；l ，2 ，功非减排序( s p t 规则) 。 定理6 对于问题1l 局，】= 乙矿+ a ( ，) ) l 口，最优排序满足各个工件之间按基 本加工时间只( ，= l ，2 ，刀) 非减排序( s p t 规则) 。 2 2 4 极小化最大延误 在与定理3 同样的假设条件下，即工件的基本加工时间和工期有一致关系， 可得与定理3 相似的结论。 定理7 对于问题l f 履，】= 尸+ a p ) ) i 厶靠，若工件的基本加工时间和工期有一 致关系，即即7 , - 办当且仅当矽砟，存在最优排序满足各工件之间按工期 z ( ，= l ，2 ，刀) 非减排序( e d d 规则) 。 o 兰州大学2 0 1 0 届硕士学位论文 第三章具有恶化及学习效应的单机成组排序问题 引言 成组技术是利用任务的某种性质将任务分成若干组在进行加工，以提高生产 效率的一种方法，成组技术概念首先由h a m 和h i t o m i 2 9 提出。其中，同组工 件连续加工时不需要或需要较少的安装时间，不同组连续加工时需要一定的加工 时间。 h a m 和h i t o m i 2 9 提出成组概念以后，a 1 l a h v e r d i 3 0 3 ，c h e n g 3 1 3 等对成 组技术在实际中的应用做了研究：w uc c 等在 3 2 中考虑了准备时间和工件加 工时间都是简单线性恶化的单机成组排序问题，对目标函数为极小化最大完工时 间和极小化总完工时间分别给出了多项式算法；k u o 和y a n ge 3 3 提出带恶化效应 模型驴= 刃( 1 + 毁。1 + a ：1 + + 反一】) ，证明了对极小化时间表长问题和极小化 总完工时间问题是多项式可解的：w a n g 和l i n 3 4 研究了准备时间和工件加工时 间带线行恶化的单机成组排序问题，给出了时间表长、加权总完工时间的多项式 算法；l e e 和w u 3 5 对 1 8 的学习效应模型进行了成组化排序研究，模型为 ，= q 胪，= 芬，其中胪为组内学习函数，p 为组间学习函数，他们 给出了极小化时间表长的多项式算法，在假定各组工件数相同的前提下给出了极 小化总完工时间的多项式算法； 近两年，同时带学习效应和恶化效应的单机成组排序问题也得到了广泛的研 究。z h a n g 和y a n 3 6 对 3 5 加入了恶化效应，并在相同的假设下得出了同 3 5 一样的结论；y a n g 和y a n g 3 7 对组内存在学习效应，组间存在恶化效应的成组 模型进行了研究，他们对极小化时间表长和极小化总完工时间给出了多项式算 法。 i o 兰州大学2 0 1 0 届硕士学位论文 3 1 单机成组排序模型1 1 只彳，l ；a 。( i + 7 7 ，e - ! 口，j ) 吩，_ ；8 , g t i f ( c ) 3 1 1 问题描述及符号说明 设共有刀个工件被分成所组在一台机器上加工，所有的工件在，时刻到达， ， 0 。同一组的工件连续加工，不同组交换加工时需要准备时间。我们假设第 ，组q ( ，= l ，2 ，所) 有嘭个工件，则+ 1 1 2 + + = 刀。我们用，表示组6 ；第 个工件，工件z ，的实际加工时间是与其开工时间、所在组位置、本组前面所 加工工件基本加工时间相关的函数，假设工件z ，在组e 中排在第，个位置加工， 那么，工件屯的实际加工时间乃，l 为 r - 1 只，】= a z ( i + n ，c c d _ - i ) 毋一， i - - - i ，2 ，所， j = l x ，乃 ，斟 其中a ，是工件的基本加工时间；是工件z 的开工时间， ， 0 ； e - i ( 1 + t 7 ，a i ，1 ) 砷是组q ( ，= 1 ，2 ，功恶化函数，恶化系数t 7 ， o ，哆l ；卢是学 闰 习函数，学习系数勿 0 。 组q 的实际准备时间是其开工时间的线性函数 毋= a ，= l ，2 ，历 6 ，是组6 ；的基本准备时间。除以上符号外我们用c t ，】( 巧) 表示在排序万中，组6 ； 的工件z 排在第，个位置时的完工时间。 首先引用孙丽 3 8 的两个引理 引理1 ( 允+ “1 + 九矿1 ( 等户) 一q + a ( 1 + 矽( 等户) 2 。，其中a 1 ，哆1 ， b ， 0 ，z 0 ，= l ，2 以- i 。 兰州大学2 0 1 0 届硕士学位论文 引理2 ( a + 月( 1 + a 力研二笋) 4 ) 一q + 枞( 1 + z ) 砷( 二笋) 辛) 。，其中o 乃s 月 0 ，又由引理l 知 a + ( 1 + 九力弓( 叫k + l4 一( 1 + a ( 1 + 力q ( 兰芸与4 ) o ， c免 故上式大于等于零，因为倪“ a 。，7 ， o ，仍1 ，所以有 ，-i，-i ( 1 + r 7 ，a 月+ 7 7 。) q - ( 1 + 7 7 ，口【d + r l p e ，) 唧0 ， - i i = 1 又因似扣( 1 + r ，a 刺) 珥胪( 后+ l 严享0 ，则有 弛艮( 1 帆善尸哪州讯1 饥喜a 44 + r z o , 尸_ ( 1 + 7 7 荟r - - i 唧扩m 综上可知c 枷。】) 一仁h “。】( 7 r ) 0 ，这与万是最优排序矛盾，定理证毕。 r - - i 定理2 对问题l i p , 一= 口( 1 + 叩，a d ，i 尸，= 6 曰i 气，最优排序满足各 组之间任意排序。 证明：假设在排序7 r 中鸟与e 是两个相邻的工件组，且q 排在9 之前，同时假 设6 ；的开工时间为，o ，组e 各工件的完工时间为 q 1 1 0 r ) = 6 o ( 1 + a ，i 。l ( 1 + 仇咿p ) = 觋( 1 + 畅l 】) ， c 2 】( 7 r ) = 谚矗( 1 + i 】) ( 1 + g 2 】( 1 + 亿珥1 1 1 ) 弓2 毒) ， 1 3 兰州大学2 0 1 0 届硕士学位论文 一知i q 圳 ) = e 矗( 1 + 1 1 ) 县( “畅册( 1 + 吃善4 尸胪) ， 组e 各工件的完工时间为 e i l l ( 万) = t 乞毋1 ( 万) ( 1 + 口“1 1 ) ， e 2 】( 万) = 影c 珈】( 7 r l + 吁一( 1 + 哆，【2 】( i + ? 】_ 哆| l j ) 乃砂) ， “7 r ) = 嘭e 川】( 万) ( 1 + 哆川) n ( 1 + 纠( 1 + 7 1 ，】户矿) h = 2厶i m h - - i = a , a o ( 1 + a ；i u ) ( 1 + i 】) n ( 1 + a 厨( 1 + ，7 ，“尸胪) 知2= 1 市，-l n ( 1 + a j i b ( 1 + r ，口j l z l 尸矿) h = 2岛l 由上式可知两组的最大完工时间 ) 与两组问的加工时间无关，只与各组间 的加工顺序有关，对问题1 1 只，l = 口( 1 + r ，a 疽，l 尸，= a , g t i c = ，结合 定理1 的结论可得其多项式算法 算法1 步骤l ：各组内工件按口，非减排序 步骤2 ：各组之间的顺序任意。 算法l 的计算复杂性为o ( n l g 刀) 。 3 1 3 极小化总完工时间 p l 定理3 对问题11 只一= 口( 1 + 叩，口矗d ) 弓，j ，= 5 f , a r ie c 0 ，又乇够 o ，易知 ( 羔q ，( 疗) + 羔e 川( 万) ) 一( 羔e 。p i ( 丌) + 羔c 。p 如) ) o 。 1月i，- l_ i 这与万是最优排序矛盾，定理证毕。 r - ! 由定理3 、4 ，可得问题1 1 只，1 = a ( 1 + 7 7 ，a d ，i ) 吩，j , = s , g r ) z q _ ，的 闰 多项式算法 算法2 步骤l ：各组内工件按a “非减排序 1 6 兰州大学2 0 1 0 届硕士学位论文 叩+ a 刺) 兀( 1 + 口删( 1 + r l ，a “严庐) 一l 步骤2 ：各组之间按_ 等- ：丛7 _ 一非减排序。 4 ( 1 + 嘭川) ( 兀o ( 1 + 嘭胎1 ( 1 + 仇畅刀尸庐) ) 算法2 的计算复杂性为o ( n l gn ) ，刀为各组工件数之和。 3 1 4 极小化加权总完工时间 当目标函数为加权总完工时间时，问题将变的十分复杂，但如果各组内工件 的基本加i 时间与各自的权值存在逆一致关系时，即a 。口，当且仅当 蟛，哆，( ，= l ，2 功，那么问题 1 1 只一= a ( 1 + r ，口矗矗) q ，j ，= 6 ，刀l k q 存在多项式算法。 r - i 定理5 对问题1 1 只，= a 0 + ) 7 乏口疆日) 珥，j ，= 艿，甜i 吆- ，仁，若各组内工 居l 件的基本加工时间与各自的权值满足：a ，仅，当且仅当w o , s 哆，( ，= l ，2 朋) ， 则最优排序满足各组内工件按! 鱼( ，：1 ，2 。朋) 非减排序。 证明：我们沿用定理2 的假设和定理l 的结论，假设a ， - - o r ，当且仅当 幡罐舣扣逸o g i , vh 2 惫k - i 0 腻舭艘义 爿2 瓦考蒜，和儿。瓦差高i ，可知。 o 是它的开工时间， 口 0 ，彦 o ；肛 0 ， ( 胪一( 后+ 1 ) 岛) o ， ( a ，一一吩，) 0 ， 所以 c ；，( 7 r ) c j 。( i t ) 。 这与万是最优排序矛盾，定理证毕。 定理8 对问题l i 以i 一= a ( 口+ 匆) ，= 6 ，( a + b t ) , g t i c = ，最优排序满足各组 之间的次序任意排序。 证明：假设在排序7 r 中g 与g 是两个相邻的工件组，且q 排在嘭之前，同时假 设6 ；的开工时间为，0 ，组谚各工件的完工时间为 c ，【q ( 7 r ) = t o + a , ( a + b t o ) + a , 1 日p + 6 ( ，o + 4 仞+ 勿。) ) ) l 以 = ( ，o + 珈啦) ( + ) 一善， c 2 】何) 。c f q + a ，i 习( 口+ 占c 【q ) 2 岛 = ( ，o + 和城) ( + ，) ( 1 + 芦，) 一号， c 州c 万，= ( ，o + 匀( - + 魍) 彝( - + 缸，m 尸，) 一詈， 2 l 兰州大学2 0 1 0 届硕士学位论文 组9 各工件的完工时间为 弓。【i 】( 万) = q 坤l ( ，) + t ( 口+ 西c 啼】( 万) ) + a _ ，【日( 口+ 彦( e 胁】( 万) + 嗲，e 期】( 万) ) ) l 乃 = ( 矗+ 訇( ，+ 历，) ( t + 够) 垂( + 缸。阳户) ( ，+ 施a l l l & ) 善， e 习( 万) = e q 协) + 哆 2 】+ 6 e q ( t r ) ) 2 丹 = ( o + 司( + 笳，) ( + 够) 鼻( + 施嘲7 ) ( + 吼【l 】l 办) ( + 施“习2 易) 一号， e w ( 丌) = ( 乇+ 三) ( t + 硒) ( 1 + 够) 冉( t + 施尸) 唾( - + 缸朋产) 一j a ， 由上式可知两组的最大完工时间引( ，r ) 与两组间的加工时间无关，只与各组间 的加工顺序有关，结合定理7 的结论可得极小化时间表长问题的最优算法 算法4 步骤l ：各组内工件按口，非减排列； 步骤2 ：各组之间的顺序任意。 算法4 的计算复杂性为o ( n l gn ) ，刀为各组工件数之和。 3 2 3 极小化总完工时间 定理9 对问题l i 乃，l = 口- ，( 口+ 刎，= 6 ，( 口+ 蛾吲q ，最优排序满足各 组内工件按基本加工时间a j ，( = l ，2 ，哆) 非减排序( s p t 规则) 。 证明：我们沿用定理l 的所有假设，由定理1 可知： e 州朋( 7 r ) = 乇+ 仅，。( a + b t o ) k 砖， c ，坷引( 万) = ，o + a 咖( 口+ 6 ，o ) 胪， 则 c p 】( 万) 一仁l i 以( 万) = ( 哆，一口，) ( 口+ 纸) ， 因为 ( + 纸) o ，7 0 ，( c 一，) 0 ， 2 2 兰州大学2 0 1 0 届硕士学位论文 所以 c ，【t 】( 万) 一仁i f 棚( 万) 0 ， 由定理7 的结论易知： c 订t + i 】( 石) 一“l j ( 万) 0 ， 于是( e 缸棚何) + t 哇州( 万”一( t 唾棚( 万。) + e d “。】( 7 r ) ) 0 ，这与万是最优排序矛盾， 定理证毕。 为了万便足理1 0 的叙述和证明，我们1 i 夏设a 删a 2 】口4 】( ，= l ，2 朋) ， 并定义 z = 【l + 够) 珥( 1 + 斑们产) ，( ，= 1 ，2 功 影= ( 1 + 够) 窆a ( 1 + b a j , t 棚胪) ，( ，：1 ，2 功 在a l l a ：j a ，啊1 ( ，= 1 ，2 功假设下，z 和f 均是依赖各组排序的固定值。 定理1 0 对问题li 以，1 = 口。( 口+ 勿) ，= 6 ，( 口+ ，a r i zc , ，最优排序满足 矿l 各组之问按兰乒( ，= l ，2 功非减排序。 证明：假设在最优排序7 r 中，组间排序违反了上述原则，则至少存在两个相邻的 组g 和g ，组6 ；排在g 之前，但三专 _ x ) f - i 。假设q 在矗时刻开始加工， 将排序万作变动如下：对调巧和g 的位置，保持其余各组工件顺序不变，从而得 到新的排序7 ，结合定理2 的证明过程，可知在排序万中组6 ；和组g 的总完工 时间为 喜q ，】( 万，= ( 乇+ 詈) ( ，+ 够) 壹g 。l n h = l ( - + 缸棚，) 一哆詈= t o + 詈) 牛- 哆i ， 耄，】( 万，= ( ，o + 詈) z ( + 够) 壹g - i 冉( - + 施卅，庐) 一哆詈= ( ，o + 訇z 杉一哆詈， 同理，在排序7 r 。中有 兰州大学2 01 0 届硕士学位论文 善( 万) _ ( ，o + 和一乃考， ，1 。 。 喜( 万l o + 善) 硝一专，i i， ， ( 兰e ( 尢) + 壹e 川协) ) 一( 壹e 川) + 童e 驴，伽) ) 2 ( ，o + 割( ( 髟+ z 杉) 一( 杉+ _ 功 = ( ，o + 匐弼哼一等， 根据假设可等一等卜又因为( 乇+ 舻，隅 ( 壹岛，( 万) + 兰，( 万) ) 一( 壹e 驴】( 刀。) + - c 驴】( 万) ) o 。 这与万是最优排序矛盾，定理证毕。 由定理9 、1 0 ，可得问题ll 以，1 = 口( 口+ 匆) ，= 6 ，( 口+ ，凹i q 的 多项式算法 算法5 步骤1 ：各组内工件按a 。非减排序； 步骤2 组与组之间按坐掣= = 垒! 坐糊拣步骤2 ：组与组之间按 七二非减排序。 ( 1 + 够) n ( 1 + 缸) 算法5 的计算复杂性为o ( n l g # ) ，刀为各组工件数之和。 3 2 4 极小化加权总完工时间 对加权总完工时间问题，在本节的模型下，同样使问题变的很复杂，但如果 各组内工件的基本加工时间与各自的权值存在逆一致关系时，即a ，a 。，当且仅 2 4 兰州大学2 0 1 0 届硕士学位论文 当嘭，岷，( ，= l 2 枘，那么问题 l l 以，j = a ( 口+ 励) 卢，彤= 6 ，( 口+ 鲫，刀i 吆，仁 同样存在多项式算法。 定理1 1 对问题l l 以一；瑾0 4 - 刎，乃= 6 ，( 口+ ，口l 嵫q _ ，若各组内工 件的基本加工时间与各自的权值满足：a 。a ，当且仅当嘭一，u = 1 , 2 , - i t ) ， 最优排序满足各组内工件按丝( ，；1 ，2 。朋) 非减排序。 w l 。， 证明：我们沿用定理7 的假设，假设a 。饯 当且仅当形一s 岷， 类于上节定理5 ，定义 扯f z , vh 爿2 袅，比5 袅，+ ，。+ ， 可知0 乃- - - y 0 ，茏 由上可得 ( 。g 研- l ( ，r ) + _ “i l ( 万) ) 一( 岷z l 吐q ( 万) + 岷夏“瓤l l ( 万) ) o 。 这与万是最优排序矛盾，定理证毕。 为了方便定理1 2 的叙述和证明，我们假设口圳口悯a ，】( ，= l ，2 劝， 在定理1 0 定义 z = ( 1 + 历，) f i ( i + 缸刚尸，) ，( ，= 1 ，2 枘 2 5 的基础上定义 兰州大学2 0 10 届硕士学位论文 彤= ( 1 + 魍) a , i 哆捌i i o + 施删，) ，( ，= l ，2 。朋) g = l 石i l 在a i 】：l a ，胁l ( ，= l ，2 功假设下，z 和彤均是依赖各组排序的固定值 定y ii v 对问题li 忍一= 口( 口+ 勿) 卢，s j = 6 ，( 口+ ，刀i 岷q ，最优排序满 足各组之间按考尹( ，= 1 ，2 功非减排序。 证明l 假设在最优排序万中，组间排序违反了上述原则，则至少存在两个相邻的 组q 和e ，组谚排在哆之前，但等_ x j f - i 。假设g 在名时刻开始加工， 将排序疗作变动如下：对调仁和g 的位置，保持其余各组工件顺序不变，从而得 到新的排序万，结合定理2 的证明过程，可知在排序万中组6 ；和组谚的总完工 时间为 弘梳c 咖( 厶+ 珈删萎骢( 慨删矿7 ) 一缸呖a = ( 乇+ 詈) 彤一喜“胡荔a ， 耄哆朋e 川( 万) = t o + 荔a ) x ，( + 够) 兰g = l 哆括，鼻( 1 + 哆肋，炉) 一詈耋哆詹， = ( 乇+ 习川一甓， 同理，在排序万中有 一，、一 萎哆川e 驴，( 石) 2 ( ，o + 号) 杉一詈萎哆詹， ，i l ，1 1 窆r = l 哆p ，c ，旷，c 万，= 。+ 詈) 杉彤一旦bg 至l l 哆詹， 则 兰州大学2 0 1 0 届硕士学位论文 ( 喜吐h e 卅何) + 喜哆驴，e p ，何) 卜( 喜哆彦，弓t 如。) + 喜q t 一七，伍。) ) = ( ，o + 匐( ( 彤+ z 杉) 一( 杉+ t 彤” = t o + a 、x , - z 一等， 根据假设有( 等一等卜又因为( 乇+ 加，于是 ( 毒一q ，伽) + 壹哆廿j 弓pj 协) ) 一( 壹哆t 彭七舻) + 窆哆t 。如) 沦o 。 这与丌是最优排序矛盾，定理证毕。 由定理1 1 和定理1 2 可以得极小