1
1
100037×4,
顯然這是滿足約束條件的,9個家具公司的雇員董事成比例分配,37個董事在開會小組中人數均分。對于X1和X4的前9行重新排列,10-37行重新排列,就可以得到滿足條件的不同場次分組矩陣X2,X3和X5,X6,X7。
對于初解X0={X1,X2,X3,X4,X5,X6,X7}來說,任意同時變換X1~X7的前9行,10-37行中任意行的位置,就可得到一個滿足約束條件的鄰近解X′={X′1,X′2,X′3,X′4,X′5,X′6,X′7}和該初始解的鄰域。
5.2 利用模擬退火算法求得全局最優解
模擬退火算法(Simulated Annealing,SA)最早由Kirkpatrick等應用于組合優化領域,它是基于Monte-Carlo迭代求解策略的一種隨機尋優算法,其出發點是基于物理中固體物質的退火過程與一般組合優化問題之間的相似性。陳華根等(2004)也對模擬退火算法的機理進行了研究,模擬退火算法基本原理如下:(1)給定初始狀態X,選擇合適的退火策略,給定初始溫度T0以足夠高的值;(2)在X的鄰域內選擇X′,并計算Δf=f(X′)-f(X)(其中f(X)為目標函數);(3)若Δf<0(或Δf>0)則接受X′為下一次模擬的初始狀態,否則算接受新點的概率p(Δf)=exp(-Δftk),產生[0,1]區間上均勻分布的隨機數c,即c=rand(1)。若p(ΔF)≥r,則接受新點做下一次模擬的初始狀態,否則仍取原點作為下一次模擬的初始狀態;(4)重復(2)-(3)步,直至系統達到平衡狀態;(5)按第一步給定的退火策略下降t,重復(2)-(4)步,直至t=0或某一預定的低溫。衰減函數的選取:衰減函數用于控制溫度的退火速度,一個常用的衰減函數為 Tk+1 = K*Tk,其中K是一個非常接近于1的常數,這里我們取K=0.9。
6 實驗結果與分析
根據運行程序得到其中一種會議成員的分配方案如下:
表1 上午會議安排方案
第一組 第二組 第三組 第四組 第五組 第六組
第一場
9:00~9:30 2,12,14,
24,29,34 4,9,13
20,26,35 5,10,17
19,30,32 1,8,15
23,27,36,37 3,7,18
22,28,31 6,11,16
21,25,33
第二場
9:40~10:10 1,11,14
22,30,35 3,9,13
21,27,31,37 4,7,16
20,29,34 6,10,18
24,25,36 2,12,15
19,26,33 5,8,17
23,28,32
第三場
10:20~10:50 5,11,16
22,28,31 2,12,15
21,26,34 6,10,13
20,29,35,37 3,8,18
23,27,36 4,7,14
19,30,33 1,9,17
24,25,32
表2 下午會議安排方案
第一組 第二組 第三組 第四組
第四場
2:00~2:30 4,7,12,13,17
21,28,32,35,37 1,6,9,16,20
24,26,31,34 2,8,11,14,19
23,25,29,36 3,5,10,15,18
22,27,30,33
第五場
2:40~3:10 3,5,9,15,18
23,25,29,35 1,8,12,13,17
24,27,31,36 2,6,10,16,19
22,28,30,34,37 4,7,11,14,20
21,26,32,33
第六場
3:20~3:50 1,7,9,16,18
23,26,29,35 2,8,12,13,19
21,27,31,36,37 4,6,10,14,20
22,25,30,33 3,5,11,15,17
24,28,32,34
第七場
4:00~4:30 1,8,11,16,19
22,25,29,36 2,5,9,15,18
21,26,30,33 4,6,10,13,17
23,27,32,35 3,7,12,14,20
24,28,31,34,37
其中f(x)=215.0779,m(x)=326,g(x)=48.6948。
表3 參會成員互相見面次數統計
相互見面次數 0 1 2 3 4 5
模擬退火算法 103 234 166 83 17 1
根據上表知,見面次數大部分集中在1次和2次之間,基本實現預期目標。模型的優點包括兩個方面:一方面,本模型具有相當好的適用性。對于會議成員類型不同,數目任意,以及衡量交叉混合程度的標準有所增減的情況,均可應用本算法;另一方面,本模型具有很強的可推廣性。由于對會議成員總數,會議場次,會員類型,參與層次等參數沒有特殊要求,所以此模型有很大的可推廣性。模型的缺點主要表現為:(1)權系數的取值帶有一定的主觀性。如果能通過嚴密的數學方法得出權系數的值將使模型更具科學性。(2)結果不具唯一性。隨著循環次數的不同以及隨機初解取值的差異,得到的minf(x)會有所不同,同時產生的分配方案也有所差異。7 結論
本文研究利用組合優化方法解決會議成員的分配問題。
首先,引入分組矩陣與相遇矩陣的概念以及他們之間存在的數學關系,以便于后面對會議成員組成的集合進行討論,接著根據所需研究問題的限制條件確定相應的約束條件。然后,采用加權系數的方法將多目標函數歸結轉化為單一的目標函數,同時把分組矩陣作為決策變量,大量減少了模型中決策變量的個數,便于建立相應的數學模型。最后,通過置換初始解,得到該初始可行解的一個鄰近解,進而得到該初始可行解的一個鄰域,繼而采用模擬退火算法在全局范圍內進行迭代,最終可以得到該模型的一個較為滿意的解,從而解決會議成員的分配問題。
參考文獻
[1]西蒙.管理決策新科學[M].北京:中國科學社會出版社,1982.
[2]斯蒂芬·P·羅賓斯.管理學(第九版)[M].北京:中國人民大學出版社,2008.
[3]劉興堂,梁炳成.復雜系統建模理論、方法與技術[M].北京:科學出版社,2008,(1).
[4]模擬退火算法[EB/OL].http://baike.baidu.com/view/18185.htm.
[5]陳華根,吳健生.模擬退火算法機理研究[J].同濟大學學報,2004,32(6):802805.
[1]
[2]
1
100037×4,
顯然這是滿足約束條件的,9個家具公司的雇員董事成比例分配,37個董事在開會小組中人數均分。對于X1和X4的前9行重新排列,10-37行重新排列,就可以得到滿足條件的不同場次分組矩陣X2,X3和X5,X6,X7。
對于初解X0={X1,X2,X3,X4,X5,X6,X7}來說,任意同時變換X1~X7的前9行,10-37行中任意行的位置,就可得到一個滿足約束條件的鄰近解X′={X′1,X′2,X′3,X′4,X′5,X′6,X′7}和該初始解的鄰域。
5.2 利用模擬退火算法求得全局最優解
模擬退火算法(Simulated Annealing,SA)最早由Kirkpatrick等應用于組合優化領域,它是基于Monte-Carlo迭代求解策略的一種隨機尋優算法,其出發點是基于物理中固體物質的退火過程與一般組合優化問題之間的相似性。陳華根等(2004)也對模擬退火算法的機理進行了研究,模擬退火算法基本原理如下:(1)給定初始狀態X,選擇合適的退火策略,給定初始溫度T0以足夠高的值;(2)在X的鄰域內選擇X′,并計算Δf=f(X′)-f(X)(其中f(X)為目標函數);(3)若Δf<0(或Δf>0)則接受X′為下一次模擬的初始狀態,否則算接受新點的概率p(Δf)=exp(-Δftk),產生[0,1]區間上均勻分布的隨機數c,即c=rand(1)。若p(ΔF)≥r,則接受新點做下一次模擬的初始狀態,否則仍取原點作為下一次模擬的初始狀態;(4)重復(2)-(3)步,直至系統達到平衡狀態;(5)按第一步給定的退火策略下降t,重復(2)-(4)步,直至t=0或某一預定的低溫。衰減函數的選取:衰減函數用于控制溫度的退火速度,一個常用的衰減函數為 Tk+1 = K*Tk,其中K是一個非常接近于1的常數,這里我們取K=0.9。
6 實驗結果與分析
根據運行程序得到其中一種會議成員的分配方案如下:
表1 上午會議安排方案
第一組 第二組 第三組 第四組 第五組 第六組
第一場
9:00~9:30 2,12,14,
24,29,34 4,9,13
20,26,35 5,10,17
19,30,32 1,8,15
23,27,36,37 3,7,18
22,28,31 6,11,16
21,25,33
第二場
9:40~10:10 1,11,14
22,30,35 3,9,13
21,27,31,37 4,7,16
20,29,34 6,10,18
24,25,36 2,12,15
19,26,33 5,8,17
23,28,32
第三場
10:20~10:50 5,11,16
22,28,31 2,12,15
21,26,34 6,10,13
20,29,35,37 3,8,18
23,27,36 4,7,14
19,30,33 1,9,17
24,25,32
表2 下午會議安排方案
第一組 第二組 第三組 第四組
第四場
2:00~2:30 4,7,12,13,17
21,28,32,35,37 1,6,9,16,20
24,26,31,34 2,8,11,14,19
23,25,29,36 3,5,10,15,18
22,27,30,33
第五場
2:40~3:10 3,5,9,15,18
23,25,29,35 1,8,12,13,17
24,27,31,36 2,6,10,16,19
22,28,30,34,37 4,7,11,14,20
21,26,32,33
第六場
3:20~3:50 1,7,9,16,18
23,26,29,35 2,8,12,13,19
21,27,31,36,37 4,6,10,14,20
22,25,30,33 3,5,11,15,17
24,28,32,34
第七場
4:00~4:30 1,8,11,16,19
22,25,29,36 2,5,9,15,18
21,26,30,33 4,6,10,13,17
23,27,32,35 3,7,12,14,20
24,28,31,34,37
其中f(x)=215.0779,m(x)=326,g(x)=48.6948。
表3 參會成員互相見面次數統計
相互見面次數 0 1 2 3 4 5
模擬退火算法 103 234 166 83 17 1
根據上表知,見面次數大部分集中在1次和2次之間,基本實現預期目標。模型的優點包括兩個方面:一方面,本模型具有相當好的適用性。對于會議成員類型不同,數目任意,以及衡量交叉混合程度的標準有所增減的情況,均可應用本算法;另一方面,本模型具有很強的可推廣性。由于對會議成員總數,會議場次,會員類型,參與層次等參數沒有特殊要求,所以此模型有很大的可推廣性。模型的缺點主要表現為:(1)權系數的取值帶有一定的主觀性。如果能通過嚴密的數學方法得出權系數的值將使模型更具科學性。(2)結果不具唯一性。隨著循環次數的不同以及隨機初解取值的差異,得到的minf(x)會有所不同,同時產生的分配方案也有所差異。7 結論
本文研究利用組合優化方法解決會議成員的分配問題。
首先,引入分組矩陣與相遇矩陣的概念以及他們之間存在的數學關系,以便于后面對會議成員組成的集合進行討論,接著根據所需研究問題的限制條件確定相應的約束條件。然后,采用加權系數的方法將多目標函數歸結轉化為單一的目標函數,同時把分組矩陣作為決策變量,大量減少了模型中決策變量的個數,便于建立相應的數學模型。最后,通過置換初始解,得到該初始可行解的一個鄰近解,進而得到該初始可行解的一個鄰域,繼而采用模擬退火算法在全局范圍內進行迭代,最終可以得到該模型的一個較為滿意的解,從而解決會議成員的分配問題。
參考文獻
[1]西蒙.管理決策新科學[M].北京:中國科學社會出版社,1982.
[2]斯蒂芬·P·羅賓斯.管理學(第九版)[M].北京:中國人民大學出版社,2008.
[3]劉興堂,梁炳成.復雜系統建模理論、方法與技術[M].北京:科學出版社,2008,(1).
[4]模擬退火算法[EB/OL].http://baike.baidu.com/view/18185.htm.
[5]陳華根,吳健生.模擬退火算法機理研究[J].同濟大學學報,2004,32(6):802805.
本文為全文原貌 未安裝PDF瀏覽器用戶請先下載安裝 原版全文