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

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

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

【學位級別】：博士

【部分圖文】：

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

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

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


本文編號：3139560