松弛算法ppt課件-閱讀頁(yè)
2025-05-16 00:02本頁(yè)面
【正文】 mtj j ljld c a???? ?Step4 : 1 1 , 2tkkti tiikt t ste pik????? ? ???? ? ?????返 回例 對(duì)集合覆蓋問(wèn)題 1 2 3 41314234m in 2 3 4 51. . 11{ 0 , 1 } , 1 , 2 , 3 , 4jx x x xxxs t x xx x xxj? ? ?????? ? ???假設(shè) : (1 .5 ,1 .6 , 2 .3 ) T? ?1 2 3 4( ) m i n { 1 . 1 0 . 8 0 . 3 1 . 2 } 5 . 3LRz x x x x? ? ? ? ? ? ?()LRz ? 最優(yōu)解為 : (1 , 0 , 0 , 0 , ) , ( ) 4 . 2LRxz ???第三行沒(méi)有被覆蓋 ,在可覆蓋第三行中選費(fèi)用最小的列 m i n { 0 . 8 , 0 . 3 ,1 . 2 } 0 . 3? ?? 代 替1231 . 5 01 . 6 02 . 2 0 . 3????? ? ? ? ??? ? ? ? ????? ? ? ? ??? ? ? ? ?? ? ? ???1 2 4( ) m in { 1 .1 0 .5 0 .9 } 5 .6 4 .5LRz x x xLR? ? ? ? ? ? ?1 3 2 4最 優(yōu) 解 為 : x = x = 1 , x = x = 0 案例應(yīng)用 能力約束單機(jī)排序問(wèn)題 111m od :m in, 1 , 2{ } , 1 m a x{ , 1 }1 , 0.0,1 , 2 。約束條件 (1): 產(chǎn)品需求兩約束 約束條件 (2): 個(gè)時(shí)段產(chǎn)能約束 約束條件 (3): 準(zhǔn)備時(shí)間 ,i t i t ix Y T為 自 由 變 量 ， 為 因 變 量下算法Ａ的基本思想是將 中較大權(quán)數(shù)所對(duì)應(yīng)的產(chǎn)品盡可能早地生產(chǎn)． { , 1 }i in? ?Step1: 當(dāng) 時(shí) , ,依時(shí)段 t能力 約束 (2),將 盡可能往前安排直到 全部 生產(chǎn) ,可能出現(xiàn)以下幾種情況 : (a)若 的全部需求沒(méi)有全部生產(chǎn) ,且時(shí)段 t 的能力足以滿(mǎn)足 的生產(chǎn)準(zhǔn)備，則以時(shí) 段 t的最大余能力生產(chǎn) ，剩余未能生產(chǎn)的 分到 時(shí)段， 返回 step1。 (c)若 沒(méi)有全部產(chǎn)出，且無(wú)法在該時(shí)段生產(chǎn)， 則 ,返回 step1。 , { 1 , 2 }S U n??? 1t ?U ?? * m a x { | }ii iU????*i *id*i*i*i1t? 1tt??*i { * }S S i??{1, }Sn? U U S??{ * }U U i??Step2: 若 則 返回 step2. , {1 , }U S n??? 1 , { 1 , }t t U n S? ? ? ?算法Ａ 能力約束排序問(wèn)題的拉格朗日松弛算法 01 1 1m od :m a x ( )m a x m i n { { [ ] } }( : )( ) , m a x{ | 1 , }. . ( 1 ) ( 3 )n T ni i t i it i it tXi t iit n T ielZZT a x s Y cL RPX x T T i nst??????? ? ??????? ? ? ????? ? ????? ? ?1 1 11 1 11{ [ ] }[ ( ) ] }: ( , , , ) ( ) ,n T ni i t i it i it ti t in T Ti i t i it i it t ti t tTi i t i it i ittT a x s Y cT a x s Y ch i X T T a x s Y? ? ?? ? ?? ? ?? ? ?? ? ??? ? ?? ? ? ?? ? ?? ? ?? ? ??記 : g(X,T, )=再 記 則 有 :11m a x ( ) m a x m i n ( , , )( : )m a x { m i n ( , , , ) }XnTttXitZ Z g X TL RPh i X T c????????????????????求解以上 LRP問(wèn)題分以下兩步 : (1)對(duì)給定的 ,求下子問(wèn)題 (SUBP) 0??111m in ( , , , ) m in { ( ) }( : ) . . ( 1 ) ( 3 ) ,( ) m in ( , , , )Ti i t i it i itXXtnTttith i X T T a x s YSU B P s tZ h i X T c? ? ?? ? ?????? ? ??????? ???????得(2) 對(duì)所有 求 0??0max ( )Z? ??定理 對(duì)于充分大 T,若 已知且非負(fù) ,則 SUBP一定有以下形式的最優(yōu)解 ( 1, 2 , )t tT? ?* , 0 *0*iitd t t t Txtt? ? ? ??? ???注 :由此定理可知 ,求 SUBP最優(yōu)解只要判斷 ** ( ) ( ) , 0 ( 4 )i t i i i i t i i it a d s t a d s t T? ? ? ?? ? ? ? ? ? ? ?()it n TXx ??若 為滿(mǎn)足 (4)的最優(yōu)解 ,則下向量為 LRP的次梯度 . 1( ) ( ( 1 , ) , ( , ) )( 5 )( , ) { [ ] } , 1 ,ni it i it tiv X v X v T Xv t X a x s Y c t T??? ???? ? ? ? ???Step0 : 為算法 A求得的目標(biāo)值 01 , 0 , *TZ??? 1k? Step1: 解 SUBP,以 (4)式分別求每個(gè)產(chǎn)品的最優(yōu) 值 ,再由 (5)求其次梯度 , 若不滿(mǎn)足判定準(zhǔn)則 ,則 1 m a x { 0 , ( ) }kk k vX? ? ?? ??111( 1 ) ( ) 0 1 , 1 。kkkT k k s te pT T T T k k s te p??????? ? ?? ? ? ? ? ?當(dāng) 時(shí) ， 返 回當(dāng) 時(shí) ， 返 回若 滿(mǎn) 足 判 停 準(zhǔn) 則 ， 則 轉(zhuǎn) step2.Step2 : 若所求到的解為 WCS可行解 ,停
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1