圈圖上的兩類組合優(yōu)化問題

楊曉兵，王 勤

(中國計量大學(xué) 理學(xué)院，浙江 杭州 310018)

圈圖上的兩類組合優(yōu)化問題

楊曉兵，王 勤

(中國計量大學(xué) 理學(xué)院，浙江 杭州 310018)

在圈圖上研究了兩類組合優(yōu)化問題.第一類問題主要研究在要求圖中各邊的最大調(diào)整費用不能超過給定預(yù)算時，如何對各邊權(quán)進行調(diào)整，使得其他各頂點到給定頂點的距離之和最大，得到了線性時間算法；第二類問題主要研究在要求圈圖上的所有邊的調(diào)整費用之和不超過給定預(yù)算時，如何對各邊權(quán)進行調(diào)整，使得某一固定頂點到給定頂點的距離盡可能的大，得到了求解該問題的多項式時間算法.

圈圖；組合優(yōu)化問題；多項式時間算法

組合優(yōu)化是運籌學(xué)和理論計算機科學(xué)的重要分支. 在對組合優(yōu)化問題的研究中，我們希望找到問題的多項式時間算法. 但是當(dāng)一個組合優(yōu)化問題是NP-困難問題時，我們則致力于尋找該問題在特殊情形下的多項式時間算法，比如說在樹圖、圈圖、星圖、二分圖等特殊網(wǎng)絡(luò)結(jié)構(gòu)中對問題進行研究.

本文研究了圈圖上的兩類組合優(yōu)化問題. 圈圖是一類特殊的網(wǎng)絡(luò)結(jié)構(gòu),被國內(nèi)外學(xué)者廣泛研究,并在實際生活中得到應(yīng)用.例如城市規(guī)劃中的選址問題,要在城市中選擇一些地點作為醫(yī)院、學(xué)校、圖書館、消防站等，或者作為機場、垃圾站、燃氣廠、發(fā)電廠等. 前者稱為非厭惡型選址問題，后者為厭惡型選址問題. 在一些情況下，如果設(shè)施已經(jīng)存在，我們就需要在一定的預(yù)算下調(diào)整網(wǎng)絡(luò)參數(shù)，使得調(diào)整后的網(wǎng)絡(luò)盡可能的滿足要求[1]. 以上問題都可以轉(zhuǎn)化為圈圖上的最優(yōu)化問題.

文獻[2]研究了在中歐鐵路貨運集拼方案的設(shè)想基礎(chǔ)上,通過構(gòu)建混合整數(shù)規(guī)劃模型,研究社會福利最大化時的鐵路貨運集拼中心的最優(yōu)選址與顧客選擇.文獻[3]研究了需求和供給不確定的物流網(wǎng)絡(luò)選址問題.在假設(shè)隨機變量服從正態(tài)分布的前提下，給出一個確定型模型，并用拉格朗日松弛算法的改進算法進行求解，其結(jié)果證明了算法的有效性.文獻[4]針對垃圾中轉(zhuǎn)站選址問題進行了研究，構(gòu)建了多目標(biāo)情形下的基于逆向物流網(wǎng)絡(luò)的中轉(zhuǎn)站選址模型,并采用基于遺傳算法的多目標(biāo)進化算法對模型進行了求解.最后通過實際算例對模型及算法進行了驗證.文獻[5]用改進蟻群算法對應(yīng)急物流中心選址問題進行了研究.文獻[6]研究了特殊圈上的逆1-maxian問題，給出了一個多項式時間算法并得到了任意預(yù)算下的最優(yōu)解.文獻[7]研究了在時間限制條件下，面向節(jié)點成本的物流中心選址問題.通過分析問題的求解模型，證明了該問題是NP-困難的，并給出了一個近似比為ln(n)的隨機近似算法.文獻[8]用分支切割算法研究了厭惡型p-median選址問題，并通過求解其0-1規(guī)劃模型證明了該算法的有效性.文獻[9]研究了電力系統(tǒng)設(shè)施選址優(yōu)化問題，該問題是NP-困難的.文獻[9]用改進的遺傳算法與局部搜索算法解決了該問題并為企業(yè)提供了切實可行的方案.文獻[10]研究了危險廢棄物回收中心選址問題,將風(fēng)險最小化和風(fēng)險公平性最大化這兩個目標(biāo)函數(shù)結(jié)合起來,構(gòu)造出模型，并用改進重心法進行了求解.

以下是本文各節(jié)的主要內(nèi)容.在第一節(jié)中，我們給出圈圖上的第一類組合優(yōu)化問題的具體描述和求解該問題的線性時間算法；在第二節(jié)中，我們研究了圈圖上的第二類組合優(yōu)化問題，即如何在現(xiàn)有的費用預(yù)算下調(diào)整網(wǎng)絡(luò)的參數(shù)，使得網(wǎng)絡(luò)中的一個固定頂點到給定頂點的距離盡可能的大.我們得到了求解該問題的多項式時間算法.在第三節(jié)中，我們給出了一些下一步可以繼續(xù)研究的問題.

1 第一類優(yōu)化問題及其算法

我們將證明如果該問題的最優(yōu)解集X≠?，那么存在x∈X滿足0≤xi≤bi,i=1,…,n.我們有以下定理:

如果在權(quán)w下，圈圖上的頂點vj,j∈{1,…,n-1}滿足

則稱頂點vj為在權(quán)向量w下的圈圖的中心點.我們可得到以下算法1.

算法1:

第3步 最優(yōu)權(quán)調(diào)整向量即為x*，最優(yōu)目標(biāo)函數(shù)值為

定理2 算法1可以正確求解圈圖上的第一類組合優(yōu)化問題，其時間復(fù)雜性為O(n).

此時目標(biāo)函數(shù)值

在第1步中，對每條邊做增量需要進行一次除法和一次比較操作，所以共需要O(n)時間.求出圈圖的中心點需要每次進行一次加法和一次與m的比較操作，因此也需要O(n)時間.計算D*也可以在O(n)時間內(nèi)完成.因此，算法1的時間復(fù)雜性為O(n).

2 第二類優(yōu)化問題及其算法

本節(jié)主要研究圈圖上的第二類組合優(yōu)化問題.這里我們要研究的圈圖和其中的參數(shù)與第一節(jié)中相同.但在該問題中，我們給出一個固定頂點vs,s∈{1,…,n-1}.我們要求當(dāng)所有邊的調(diào)整費用之和不超過費用預(yù)算B時，如何調(diào)整邊上的權(quán)值，使得vs到v0的距離盡可能的大.與定理1的證明方法類似可知，我們可以只考慮圈圖上每條邊的權(quán)值不能減少的第二類組合優(yōu)化問題.因此，該問題可以描述為如下的數(shù)學(xué)規(guī)劃問題:

算法2:

在第2步中，我們對v0到vs長度較小的路上的邊權(quán)進行調(diào)整.每一條邊權(quán)的增量受到費用、調(diào)整量的上界和v0到vs兩條路長度差Δd的限制.若達到了費用限制或所有邊調(diào)整到上界的費用之和不超過費用限制，且所有邊調(diào)整量上界之和不超過Δd，則停止，已找到最優(yōu)解.若達到了Δd的限制，則此時vs是新的邊權(quán)向量下圈圖的中心點，在保持vs是中心點的情況下，我們繼續(xù)進行后面的運算.若達到了邊上調(diào)整量上界的限制，我們繼續(xù)對下一條單位費用最小的邊進行調(diào)整.

當(dāng)vs成為中心點時，我們進行第3步.在這一步，我們每次分別考慮一條E1和E2中的單位調(diào)整費用最小的邊，在這兩條邊的調(diào)整量的上界和費用的限制下，對這兩條邊作相同的增量，若達到了費用限制，則停止，此時已找到最優(yōu)解.若達到了某條邊調(diào)整量的上界，則繼續(xù)考慮下一條單位調(diào)整費用最小的邊.若有某一條路上的邊已不能再作調(diào)整，則此時也得到最優(yōu)解.因此，我們有以下的定理3.

定理3 算法2可以正確求解圈圖上的第二類組合優(yōu)化問題，其時間復(fù)雜性為O(nlogn).

證明:算法2的正確性可由以上分析得出.在第1步，我們分別對兩部分邊的費用作遞增排序，這需要O(nlogn)的時間.在第2步和第3步中，我們依次對邊權(quán)作增量，這需要O(n)時間.所以，算法2的時間復(fù)雜性為O(nlogn).

3 結(jié) 語

本文研究了圈圖上的兩類組合優(yōu)化問題，分別得到了求解問題的線性時間算法和多項式時間算法.下一步，我們可以繼續(xù)考慮這兩類問題在其他范數(shù)下的模型求解，也可以繼續(xù)對其他網(wǎng)絡(luò)結(jié)構(gòu)中的問題模型進行研究.

[1] ZHANG J Z, LIU Z H, MA Z F.Some reverse location problems[J]. European Journal of Operational Research,2000,124(1):77-88.

[2] 蔣雪瑩,王曉蕾,朱道立.“一帶一路”戰(zhàn)略下的物流基礎(chǔ)設(shè)施選址問題研究[J].上海管理科學(xué),2015,37(5):1-6. JIANG X Y, WANG X L, ZHU D L. Research on the problem of site selection of logistics infrastructure under the “one belt one road” development strategy [J]. Shanghai Management Science,2015,37(5):1-6.

[3] 何方國.隨機條件下一個網(wǎng)絡(luò)選址問題的模型及算法[J].武漢理工大學(xué)學(xué)報(信息與管理工程版)，2015,37(3):274-277. HE F G. A model and algorithm on logistics location under uncertainty [J]. Journal of WUT(Information & Management Engineering),2015，37(3):274-277.

[4] 陳燕升.基于遺傳算法的城市生活垃圾中轉(zhuǎn)站選址問題研究[J].物流技術(shù),2014,33(8):275-277,329. CHEN Y S. Study on location problem of urban domestic trash transfer station based on genetic algorithm[J]. Logistics Technology,2014,33(8):275-277,329.

[5] 韋曉,常相全.基于改進蟻群算法的應(yīng)急物流中心選址問題研究[J].價值工程,2014,33(17):26-27. WEI X, CHANG X Q. Emergency logistics center location issue based on improved ant colony algorithm[J]. Value Engineering,2014,33(17):26-27.

[6] 朱芳，王勤.特殊圈上的逆1-maxian問題[J].中國計量學(xué)院學(xué)報,2014,25(4):439-442. ZHU F, WANG Q. Inverse 1-maxian problem on special cycles[J]. Journal of China University of Metrology,2014,25(4):439-442.

[7] 孫玉芳,王守強.應(yīng)急物流中心選址問題算法研究[J].新型工業(yè)化，2014,4(6):37-42. SUN Y F, WANG S Q. Algorithm for emergency logistics center location[J]. The Journal New Industrialization,2014,4(6):37-42.

[8] PIETRO B, MARTINE L, FRANCESCO M. A branch-and-cut method for the obnoxious p-median problem[J]. 4OR-A Quarterly Journal of Operations Research,2007,5(4):299-314.

[9] 莫漢培,陳秋良,張子臻.遺傳算法求解電力設(shè)施選址問題[J].計算機技術(shù)與發(fā)展,2016,26(3):197-201. MO H P, CHEN Q L, ZHANG Z Z. Solving grid system facility location problem based on improved genetic algorithm[J].Computer Technology and Development,2016,26(3):197-201.

[10] 程珩,牟瑞芳.基于改進重心法的危險廢棄物回收中心選址問題研究[J].交通運輸工程與信息學(xué)報,2014,12(4):109-113. CHENG Y, MOU R F.Location research of hazardous waste recycling center based on improved gravity method[J]. Journal of Transportation Engineering and Information,2014,12(4):109-113.

Two combinatorial optimization problems on cycles

YANG Xiaobing, WANG Qin

(College of Sciences, China Jiliang University, Hangzhou 310018, China)

Two combinatorial optimization problems were studied on cycle graphs. One was how to adjust the weight of each edge to avoid the cost of each edge exceeding the given budget, to adjust the sum of distances from all the other vertices to the maximum. A linear-time algorithm was proposed. The other problem was to adjust the edge weights to avoid the cost of each edge exceeding the given budget, and to adjust the distance from a fixed vertex to the given vertex to the maximum. A polynomial-time algorithm was also presented in this case.

cycle graph; combinatorial optimization problem; polynomial-time algorithm

2096-2835(2017)02-0247-05

10.3969/j.issn.2096-2835.2017.02.018

2017-01-21 《中國計量大學(xué)學(xué)報》網(wǎng)址：zgjl.cbpt.cnki.net

國家自然科學(xué)基金資助項目(No. 11171316).

楊曉兵(1989-)，男，山西省忻州人，碩士研究生，主要研究方向為網(wǎng)絡(luò)優(yōu)化.E-mail: yangxiaobing467977@163.com 通信聯(lián)系人：王勤，女，教授. E-mail: wq@cjlu.edu.cn

TP301；O221

A