發(fā)布時(shí)間：2021-04-15 15:01

　　設(shè)施選址問題和獎(jiǎng)勵(lì)-收集斯坦納樹問題是計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)領(lǐng)域中的經(jīng)典問題,均有廣泛的實(shí)際應(yīng)用背景.本文通過設(shè)計(jì)近似算法,對(duì)設(shè)施選址問題和獎(jiǎng)勵(lì)-收集斯坦納樹問題的幾種變形進(jìn)行研究,包括:魯棒設(shè)施租賃問題,平方度量的軟容量設(shè)施選址問題,k-獎(jiǎng)勵(lì)-收集斯坦納樹問題,廣義獎(jiǎng)勵(lì)-收集斯坦納森林問題.基于原始對(duì)偶技巧,我們分別給出上述變形問題的近似算法和相應(yīng)的算法分析.在魯棒設(shè)施租賃問題中,給定設(shè)施集合,基數(shù)為n的顧客集合,時(shí)間段集合和非負(fù)整數(shù)q<n.每個(gè)時(shí)間段都有相應(yīng)的顧客子集到達(dá).每個(gè)設(shè)施有一種或多種租賃類型,每種租賃類型給定相應(yīng)的租賃長度.在某個(gè)時(shí)間段以某種類型租賃某個(gè)設(shè)施會(huì)產(chǎn)生租賃費(fèi)用,且被租賃的設(shè)施會(huì)從此時(shí)間段起以相應(yīng)的租賃長度為時(shí)長被租賃.連接顧客到設(shè)施會(huì)產(chǎn)生連接費(fèi)用,連接費(fèi)用等于顧客與設(shè)施之間的距離.每個(gè)顧客子集中的顧客只能被連接到它到達(dá)時(shí)被租賃的某個(gè)設(shè)施.在連接費(fèi)用滿足非負(fù)性,對(duì)稱性,和三角不等式的假設(shè)下,目標(biāo)是租賃一些設(shè)施,連接至少n-q個(gè)顧客,使得租賃費(fèi)用與連接費(fèi)用之和最小.解決此問題的難點(diǎn)在于魯棒設(shè)施租賃問題自然的線性規(guī)劃松弛的整數(shù)間隙是無界的.為了克服這個(gè)難點(diǎn),我們根... 

【文章來源】：北京工業(yè)大學(xué)北京市 211工程院校

【文章頁數(shù)】：85 頁

【學(xué)位級(jí)別】：博士

【部分圖文】：

圖３－１斷言證明的示意圖．??Ｆｉｇ．?３－１?Ｉｌｌｕｓｔｒａｔｉｏｎ?ｏｆ?ｔｈｅ?ｃｌａｉｍ．??

時(shí)的７值．可得，??ａ］ｔ?＾?ｍｉｎ｛７（ｉ，ｆｃ）Ｓ），７（ｉ，ｆｃ，ｓ）｝?＜?ｌ（ｉ，ｋ，ｓ）?＜?ａｊｔ－??由于連接費(fèi)用滿足三角不等式（參見圖３－２），我們結(jié)合情形１和情形２，此引理??得證．??°ｉｊ?—?ｃｉｊ?＋?ｃｉｊ?＋?ｃＴｊ?—?ａｊｔ?＋?＾ａｊｔ?—?＾ａｊｔ?＝?３ａｊｔ．??結(jié)合情形１和情形２，此引理得證．?口??用Ｘ表示設(shè)施集合｛（ｉ＇，ｆｃ＇，Ｓ＇），（＆，彳Ｓ／）｝，其中設(shè)施（ｉ＇，ｆｃ＇，ｓ＇）是實(shí)例ＺＡＴ的??最優(yōu)解中租賃費(fèi)用最大的設(shè)施．設(shè)施是算法最終臨時(shí)租賃的設(shè)施．用Ｘ??表示與Ｘ相關(guān)的被租賃的設(shè)施．即，??文：二?Ｕ?＊＾，Ｍ．??（ｉ，ｋ＾ｓ）ｅＸ??用Ｆ表示文中設(shè)施的租賃費(fèi)用．下面的引理給出租賃費(fèi)用Ｆ的上界．??引理３．３??Ｆ?＜３?ａ］ｔ－??（ｊ，ｔ）ｅｖ??證明只有公ｄ中顧客可對(duì)Ｘ中設(shè)施做貢獻(xiàn)．對(duì)任意設(shè)施（ｉ，ｆｃ，ｓ）?Ｇ元用表??示所有對(duì)做貢獻(xiàn)的顧客？即

＋?（４＿５）??由于距離是度量的（參見圖４－１），我們有??Ｃｊ／?ｊ?—?ｄｉｆ?ｊ??＾?＋?ｄｗｉｔ＾ｊ）??一?＂Ｉ－＾ｗｉｔＱ）＾）＾ｗｉｔ＾＇）＾??—ｄ＾ｊｆ２?＋?ｄｗｉｔ＾ｊｆ２?＋?ｃ２ｄｉｆｊｆｄｗｉｔ＾ｊ／?＋?ｄｗｉｔ＾－＾２?＋?２（ｄ＾＾／?＋?ｄｗｉｔ＾＾ｖ）ｄｗｉｔ＾＾??＜?３（ｄｉｆｊｆ）２?＋?３（ｄｗｉｔ（＾－／）２?＋?３（ｄｗｉｔ（＾－）２??—＾ｃ＾ｊｆ?＋?３ｃｗｉｔ＾ｊｆ?＋?３ｃｗｉｔ＾－＾－．?（４－６）??因?yàn)轭櫩停瘜?duì)設(shè)施《和設(shè)施ｗｉｔ（ｊ）都做貢獻(xiàn)，所以ｃ＃?＋?９／ｙ／ｌＯｉｖ?ｇ?和??ｃｗｉｔＷ／?Ｓ?％成立．由算法３，可得％?ｇ?ｔｗｉｔ⑴＝％．結(jié)合不等式（４－５）和不等式??（４－６），有??９ｆａ（Ｊ）?９ｆｉ，??ｃ＜ｒ（ｊ）ｊ?＋?１〇ｕ?＾?＾?３ｃ＾ｙ?＋??（?９／ｉ／?＼?．?．??３?＋?ｉ〇＾?ｉ?＋?３Ｃｗｉｔ（ｉ）＾?＋?３ｃｗｉ？ｉ）ｉ??＾?３（Ｘｊｆ?＋?＾ＯＬｊｆ?＋?Ｓｃｋｊ??＜?９ａｊ??＝ＱａＣｊ．??此引理得證．，?□??有了以上引理，我們可以分析出算法所得解的費(fèi)用與最優(yōu)解費(fèi)用的關(guān)系，給出??－３２－?


本文編號(hào)：3139560