丁威+楊雪斌

作者簡介：丁威（1988-），男，福建龍巖人，福州大學管理學院碩士研究生，研究方向：技術經(jīng)濟分析及評價；楊雪斌（1988-），女，福建漳州人，福州大學管理學院碩士研究生，研究方向：系統(tǒng)分析。

摘 要：隨著經(jīng)濟的發(fā)展，越來越多的企業(yè)面臨諸多的決策問題，召開企業(yè)董事會是作出企業(yè)決策的有效途徑，針對現(xiàn)在企業(yè)董事會等參會成員分配的需要，提出利用組合優(yōu)化解決會議成員分配問題。

關鍵詞：組合優(yōu)化；模擬退火算法；會議成員分配

中圖分類號：F2 文獻標識碼：A 文章編號：16723198（2014）03002603

1 決策理論

現(xiàn)今，管理者面臨的各種關乎企業(yè)未來發(fā)展的決策越來越多，依靠科學的方法確定決策的形式及步驟對于企業(yè)發(fā)展至關重要。決策理論是在系統(tǒng)理論的基礎上發(fā)展起來的，主要代表人物是赫伯特·西蒙（Herbent Simon），其代表作為《管理決策新科學》。決策理論的觀點主要表現(xiàn)在三方面：突出決策在管理中的地位、系統(tǒng)闡述了決策原理以及強調(diào)了決策者的作用。西蒙認為管理決策包括四個主要階段：找出制定決策的理由、找到可能的行動方案、在諸行動方案中進行抉擇、對已進行的抉擇進行評價。斯蒂芬·羅賓斯認為決策的制定大體分為識別決策問題、確定決策標準、為決策標準分配權(quán)重、開發(fā)備擇方案、分析備擇方案、選擇備擇方案、實施備擇方案和評估決策結(jié)果，科學決策的作出關乎每個企業(yè)的存亡。

2 模型的假設

2.1 問題陳述

某公司欲制定長遠計劃，茲決定召開一次董事會議，會議參加者中有37位董事會成員（其中9位為雇員董事，其余為外部董事，這里37只是隨機選取的一個數(shù)字）。

董事會議時間上午從9點開始，下午從2點開始，每段會議持續(xù)半個小時，每段會議之間休息10分鐘。這次董事會議將分為7段分組討論會，每個小組上午舉行三段討論會，下午舉行四段討論會，而上午每段會議中有6個小組參加討論會，下午每段會議中有4個小組參加討論會。為了避免出現(xiàn)董事會議討論被權(quán)威人士控制的現(xiàn)象，通常安排數(shù)屆會議分組進行討論，各屆會議中小組成員不同，以使與會人員盡量交叉混合。

要求為董事長提供一份與會成員分配名單，其要滿足如下條件：（1）每個小組討論會中董事成員數(shù)量盡可能平均；（2）每個小組討論會中雇員董事成員與非雇員董事成員應符合一定的比例。

2.2 假設條件

（1）每種類型的與會董事地位相同；

（2）與會董事堅決服從會議組織者的安排；

（3）會議一旦開始，在結(jié)束之前與會董事不允許發(fā)生變動；

（4）各小組與會董事成員人數(shù)應盡可能平均。

該假設依據(jù)說明如下：會議成員分配模型應使與會董事混合得最好，并且在每個場次中保證董事們應在盡可能相互認識的基礎上重復見面的次數(shù)盡可能平均且盡量小。假設每個董事與其他董事在開會小組中都有相同的見面次數(shù)m0，同時第j場會議中第i小組的人數(shù)為yij，在本組會議中任意一個人在該小組所見的人數(shù)就是（yij-1），因而該小組yij個人所見的人數(shù)之和為yij（yij-1），則對全天所有的場次所有的小組會議來說，所有成員所見人數(shù)總和為：

∑3j=1∑6i=1yij（yij-1）+∑7j=4∑4i=1yij（yij-1）=∑3j=1∑6i=1y2ij+∑7j=4∑4i=1y2ij-37×7

∵假設全天會議結(jié)束后每一個董事和其他任何一個董事見面的次數(shù)均為m0，

∴全天所有成員所見人數(shù)之和也可以寫成37×36m0。

∴等式∑3j=1∑6i=1y2ij+∑7j=4∑6i=1y2ij-37×7=37×36m0成立。

在本式中，∑3j=1∑6i=1yij+∑7j=4∑4i=1yij=37×7，其中n=3×6+4×4=34。

所以根據(jù)Cauchy不等式有：∑3j=1∑6i=1y2ij+∑7j=4∑4i=1y2ij≥34×（37×734）2，解得m0≥1.29。

在實際運用中，m0的取值越小越好，取m0=1.29。所以他們?nèi)我鈨蓚€人見面的次數(shù)m0介于1和2之間，即上午：6，6，6，6，6，7；下午：9，9，9，10。

2.3 變量及符號說明

X：決策變量，其中元素xijk表示在第j場會議中，董事i在第k組；

m0：每個董事與其他董事的相同的見面次數(shù)；

P：分組矩陣，Pj表示第j場會議的分組矩陣；

Q：相遇矩陣，表示第j場會議的相遇矩陣；

Qsum：總相遇矩陣，即Qsum=∑7j=1Qj；

Q（1）sum：總相遇矩陣Qsum的轉(zhuǎn)換形式；

m（x）：目標函數(shù)Ⅰ，定義為Qsum中除了主對角線上的元素外，零元素的個數(shù)，即表示任意兩個與會董事沒有見面的次數(shù)；目標函數(shù)Ⅱ，定義為Qsum的范數(shù)的平方；

f（x）：總目標函數(shù)，定義為f（x）=λ1m（x）+λ2g（x），其中λ1+λ2=1。

3 模型的分析

3.1 分組矩陣和相遇矩陣的關系定理

這里本文引入分組矩陣和相遇矩陣。

定理：若P為分組矩陣，則其對應的相遇矩陣Q=PPT-E（E為單位矩陣）。

證明：對xi∈X，每次只能分在一個組中，即P的每一行中只有一個元素為1，其余的元素全部為0。

由矩陣M=PPT-E可得mij=∑mk=1（pik）2-1=0i=j

∑mk=1pik×pjki≠j

（1）若pik與pik（k∈{1，…，m}）不同時為1，即xi與xj不同在k組，即mij=0；

（2）若pik與pik同時為1，即xi與xj同在k組，即mij=1，滿足相遇矩陣的定義。

所以Q=M=PPT-E。

即定理得證。

3.2 約束條件

結(jié)合問題中的條件，我們定義變量xijk表示第i個人在第j場次的會議中分在第k組，

則xijk=1在第j場會議中，xi∈Gk

0在第j場會議中，xiGk，

其中

i=1…37，表示37個公司董事；

i=1…9，表示9個公司的雇員董事；

i=10…37表示28個公司的外部董事；

j=1…7表示全天開了7場次的會議；

k=1…6表示上午的三個場次的會議中，每個場次的會議分為6個小組，k=1…4表示下午的四個場次的會議中，每個場次的會議分為4個小組。

對于每個場次的分組來說，都一定存在有分組矩陣Pj，即：Pj=x1j1…x1jk

x2j1…x2jk

………

x37j1…x37jk，其中k=6（上午）或者4（下午）。

再根據(jù)題目給定的要求，可以得到如下的約束條件：

（1）每一次分組中，每個與會董事唯一的分在一組，

即∑6k=1xijk=1j=1，2，3i=1，…，37

∑4k=1xijk=1j=4，5，6，7i=1，…，37

（2）每次分組時，每組中的公司雇員董事應當合比例，

有1≤∑9i=1xijk≤2k=1，…，6j=1，2，3

2≤∑9i=1xijk≤3k=1，…，4j=4，5，6，7

（3）每次分組時，各小組的人數(shù)盡量平均分配，

有6≤∑37i=1xijk≤7k=1，…，6j=1，2，3

9≤∑37i=1xijk≤10k=1，…，4j=4，5，6，7

（4）xijk=1在第j場會議中，xi∈Gk

0在第j場會議中，xiGk

3.3 目標函數(shù)

7次分組會議完成以后，董事成員1-37之間相互見面的次數(shù)可由如下的公式表示：Qsum=∑7j=1Qj=（qsumij）37×37，Qsum為總的相遇矩陣。

其中

qsumij=∑3l=1∑6k=1xilk·xjlk+∑7l=4∑4k=1xilk·xjlki，j=1，…，37 i≠j

0i=j

3.3.1 目標函數(shù)Ⅰ的給出

考慮到與會董事之間的充分交流，要盡量保證每個與會董事之間都有見面的機會，即在Qsum中除了主對角線上元素外，0元素個數(shù)應盡可能少，首先對Qsum進行處理，得到Q（1）sum=Qsum+E37×37=（qsum（1）ij）37×37。

令mij=1qsum（1）ij=0

0否則，得到M=（mij）37×37，則目標函數(shù)I為m（x）=∑37i=1∑37j=1mij最小。

3.3.2 目標函數(shù)Ⅱ的給出

考慮到任意兩個董事重復見面的次數(shù)應盡可能相同，通過（qsumij）k可以放大不同董事與其他的董事見面次數(shù)上的單個差異，k的取值越大，放大的程度就越大。在本模型中，我們?nèi)《╧=2，即‖Qsum‖2F，因此得到目標函數(shù)Ⅱ為g（x）=‖Qsum‖2F=∑37i=1∑37j=1（qsumij）2。

在這里，我們認為g（x）達到最小時，任意兩個成員重復見面次數(shù)達到盡量平均這個目標就得以實現(xiàn)，而當m（x）達到最小時，充分見面這個目標也得以最好地滿足。

3.3.3 總目標函數(shù)的得到

考慮到兩個目標函數(shù)m（x）和g（x）存在著著不同的優(yōu)先級和數(shù)量級，于是對兩目標函數(shù)采用加以不同權(quán)系數(shù)衡量，得到總目標函數(shù)表達式，為f（x）=λ1m（x）+λ2g（x），其中λ1+λ2=1，λ1，λ2為權(quán)系數(shù)，這里取λ1=0.6，λ2=0.4。

4 模型的建立

綜合所述，得到如下模型：

目標函數(shù)Minf（x）=0.6m（x）+0.4g（x）

約束條件∑6k=1xijk=1j=1，2，3i=1，…，37

∑4k=1xijk=1j=4，5，6，7i=1，…，37

1≤∑9i=1xijk≤2k=1，…6j=1，2，3

2≤∑9i=1xijk≤3k=1，…4j=4，5，6，7

6≤∑37i=1xijk≤7k=1，…6j=1，2，3

9≤∑37i=1xijk≤10k=1，…4j=4，5，6，7

xijk只能是0或者1，i=1，…，37，j=1，……，7，k=1，…，6。

5 模型的求解

5.1 尋找問題的可行解空間

對于模型中的每個決策變量只能0或者1，因此可以看作是多目標0-1整數(shù)規(guī)劃問題，其變量的個數(shù)多達37×6×3+37×4×4=1258個，使用窮舉法搜索顯然是不可行的。考慮到模型中決策變量特點，采用每一場次會議的分組矩陣作為變量，決策變量的個數(shù)將會降低到7個，該模型可看作是參會成員集合的組合優(yōu)化問題?？紤]到分組矩陣的每一行中只能有一個元素為1，其余的元素全部為0，對于第一場和第四場的分組矩陣來說有：

X1=1

1

1

1

1

1

………

1

1

1

1

1037×6，X4=1

1

1

1

……

1

1

1

1

100037×4，

顯然這是滿足約束條件的，9個公司的雇員董事成比例分配，37個董事在開會小組中人數(shù)均分。對于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 利用模擬退火算法求得全局最優(yōu)解

模擬退火算法（Simulated Annealing，SA）最早由Kirkpatrick等應用于組合優(yōu)化領域，它是基于Monte-Carlo迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。陳華根等（2004）也對模擬退火算法的機理進行了研究，模擬退火算法基本原理如下：（1）給定初始狀態(tài)X，選擇合適的退火策略，給定初始溫度T0以足夠高的值；（2）在X的鄰域內(nèi)選擇X′，并計算Δf=f（X′）-f（X）（其中f（X）為目標函數(shù)）；（3）若Δf<0（或Δf>0）則接受X′為下一次模擬的初始狀態(tài)，否則算接受新點的概率p（Δf）=exp（-Δftk），產(chǎn)生[0，1]區(qū)間上均勻分布的隨機數(shù)c，即c=rand（1）。若p（ΔF）≥r，則接受新點做下一次模擬的初始狀態(tài)，否則仍取原點作為下一次模擬的初始狀態(tài)；（4）重復（2）-（3）步，直至系統(tǒng)達到平衡狀態(tài)；（5）按第一步給定的退火策略下降t，重復（2）-（4）步，直至t=0或某一預定的低溫。衰減函數(shù)的選?。核p函數(shù)用于控制溫度的退火速度，一個常用的衰減函數(shù)為 Tk+1 = K*Tk，其中K是一個非常接近于1的常數(shù)，這里我們?nèi)=0.9。

6 實驗結(jié)果與分析

根據(jù)運行程序得到其中一種會議成員的分配方案如下：

表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 參會成員互相見面次數(shù)統(tǒng)計

相互見面次數(shù) 0 1 2 3 4 5

模擬退火算法 103 234 166 83 17 1

根據(jù)上表知，見面次數(shù)大部分集中在1次和2次之間，基本實現(xiàn)預期目標。模型的優(yōu)點包括兩個方面：一方面，本模型具有相當好的適用性。對于會議成員類型不同，數(shù)目任意，以及衡量交叉混合程度的標準有所增減的情況，均可應用本算法；另一方面，本模型具有很強的可推廣性。由于對會議成員總數(shù)，會議場次，會員類型，參與層次等參數(shù)沒有特殊要求，所以此模型有很大的可推廣性。模型的缺點主要表現(xiàn)為：（1）權(quán)系數(shù)的取值帶有一定的主觀性。如果能通過嚴密的數(shù)學方法得出權(quán)系數(shù)的值將使模型更具科學性。（2）結(jié)果不具唯一性。隨著循環(huán)次數(shù)的不同以及隨機初解取值的差異，得到的minf（x）會有所不同，同時產(chǎn)生的分配方案也有所差異。7 結(jié)論

本文研究利用組合優(yōu)化方法解決會議成員的分配問題。

首先，引入分組矩陣與相遇矩陣的概念以及他們之間存在的數(shù)學關系，以便于后面對會議成員組成的集合進行討論，接著根據(jù)所需研究問題的限制條件確定相應的約束條件。然后，采用加權(quán)系數(shù)的方法將多目標函數(shù)歸結(jié)轉(zhuǎn)化為單一的目標函數(shù)，同時把分組矩陣作為決策變量，大量減少了模型中決策變量的個數(shù)，便于建立相應的數(shù)學模型。最后，通過置換初始解，得到該初始可行解的一個鄰近解，進而得到該初始可行解的一個鄰域，繼而采用模擬退火算法在全局范圍內(nèi)進行迭代，最終可以得到該模型的一個較為滿意的解，從而解決會議成員的分配問題。

參考文獻

[1]西蒙.管理決策新科學[M].北京：中國科學社會出版社，1982.

[2]斯蒂芬·P·羅賓斯.管理學（第九版）[M].北京：中國人民大學出版社，2008.

[3]劉興堂，梁炳成.復雜系統(tǒng)建模理論、方法與技術[M].北京：科學出版社，2008，（1）.

[4]模擬退火算法[EB/OL].http：//baike.baidu.com/view/18185.htm.

[5]陳華根，吳健生.模擬退火算法機理研究[J].同濟大學學報，2004，32（6）：802805.

1

1

100037×4，

顯然這是滿足約束條件的，9個公司的雇員董事成比例分配，37個董事在開會小組中人數(shù)均分。對于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 利用模擬退火算法求得全局最優(yōu)解

模擬退火算法（Simulated Annealing，SA）最早由Kirkpatrick等應用于組合優(yōu)化領域，它是基于Monte-Carlo迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。陳華根等（2004）也對模擬退火算法的機理進行了研究，模擬退火算法基本原理如下：（1）給定初始狀態(tài)X，選擇合適的退火策略，給定初始溫度T0以足夠高的值；（2）在X的鄰域內(nèi)選擇X′，并計算Δf=f（X′）-f（X）（其中f（X）為目標函數(shù)）；（3）若Δf<0（或Δf>0）則接受X′為下一次模擬的初始狀態(tài)，否則算接受新點的概率p（Δf）=exp（-Δftk），產(chǎn)生[0，1]區(qū)間上均勻分布的隨機數(shù)c，即c=rand（1）。若p（ΔF）≥r，則接受新點做下一次模擬的初始狀態(tài)，否則仍取原點作為下一次模擬的初始狀態(tài)；（4）重復（2）-（3）步，直至系統(tǒng)達到平衡狀態(tài)；（5）按第一步給定的退火策略下降t，重復（2）-（4）步，直至t=0或某一預定的低溫。衰減函數(shù)的選?。核p函數(shù)用于控制溫度的退火速度，一個常用的衰減函數(shù)為 Tk+1 = K*Tk，其中K是一個非常接近于1的常數(shù)，這里我們?nèi)=0.9。

6 實驗結(jié)果與分析

根據(jù)運行程序得到其中一種會議成員的分配方案如下：

表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 參會成員互相見面次數(shù)統(tǒng)計

相互見面次數(shù) 0 1 2 3 4 5

模擬退火算法 103 234 166 83 17 1

根據(jù)上表知，見面次數(shù)大部分集中在1次和2次之間，基本實現(xiàn)預期目標。模型的優(yōu)點包括兩個方面：一方面，本模型具有相當好的適用性。對于會議成員類型不同，數(shù)目任意，以及衡量交叉混合程度的標準有所增減的情況，均可應用本算法；另一方面，本模型具有很強的可推廣性。由于對會議成員總數(shù)，會議場次，會員類型，參與層次等參數(shù)沒有特殊要求，所以此模型有很大的可推廣性。模型的缺點主要表現(xiàn)為：（1）權(quán)系數(shù)的取值帶有一定的主觀性。如果能通過嚴密的數(shù)學方法得出權(quán)系數(shù)的值將使模型更具科學性。（2）結(jié)果不具唯一性。隨著循環(huán)次數(shù)的不同以及隨機初解取值的差異，得到的minf（x）會有所不同，同時產(chǎn)生的分配方案也有所差異。7 結(jié)論

本文研究利用組合優(yōu)化方法解決會議成員的分配問題。

首先，引入分組矩陣與相遇矩陣的概念以及他們之間存在的數(shù)學關系，以便于后面對會議成員組成的集合進行討論，接著根據(jù)所需研究問題的限制條件確定相應的約束條件。然后，采用加權(quán)系數(shù)的方法將多目標函數(shù)歸結(jié)轉(zhuǎn)化為單一的目標函數(shù)，同時把分組矩陣作為決策變量，大量減少了模型中決策變量的個數(shù)，便于建立相應的數(shù)學模型。最后，通過置換初始解，得到該初始可行解的一個鄰近解，進而得到該初始可行解的一個鄰域，繼而采用模擬退火算法在全局范圍內(nèi)進行迭代，最終可以得到該模型的一個較為滿意的解，從而解決會議成員的分配問題。

參考文獻

[1]西蒙.管理決策新科學[M].北京：中國科學社會出版社，1982.

[2]斯蒂芬·P·羅賓斯.管理學（第九版）[M].北京：中國人民大學出版社，2008.

[3]劉興堂，梁炳成.復雜系統(tǒng)建模理論、方法與技術[M].北京：科學出版社，2008，（1）.

[4]模擬退火算法[EB/OL].http：//baike.baidu.com/view/18185.htm.

[5]陳華根，吳健生.模擬退火算法機理研究[J].同濟大學學報，2004，32（6）：802805.

1

1

100037×4，

顯然這是滿足約束條件的，9個公司的雇員董事成比例分配，37個董事在開會小組中人數(shù)均分。對于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 利用模擬退火算法求得全局最優(yōu)解

模擬退火算法（Simulated Annealing，SA）最早由Kirkpatrick等應用于組合優(yōu)化領域，它是基于Monte-Carlo迭代求解策略的一種隨機尋優(yōu)算法，其出發(fā)點是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。陳華根等（2004）也對模擬退火算法的機理進行了研究，模擬退火算法基本原理如下：（1）給定初始狀態(tài)X，選擇合適的退火策略，給定初始溫度T0以足夠高的值；（2）在X的鄰域內(nèi)選擇X′，并計算Δf=f（X′）-f（X）（其中f（X）為目標函數(shù)）；（3）若Δf<0（或Δf>0）則接受X′為下一次模擬的初始狀態(tài)，否則算接受新點的概率p（Δf）=exp（-Δftk），產(chǎn)生[0，1]區(qū)間上均勻分布的隨機數(shù)c，即c=rand（1）。若p（ΔF）≥r，則接受新點做下一次模擬的初始狀態(tài)，否則仍取原點作為下一次模擬的初始狀態(tài)；（4）重復（2）-（3）步，直至系統(tǒng)達到平衡狀態(tài)；（5）按第一步給定的退火策略下降t，重復（2）-（4）步，直至t=0或某一預定的低溫。衰減函數(shù)的選取：衰減函數(shù)用于控制溫度的退火速度，一個常用的衰減函數(shù)為 Tk+1 = K*Tk，其中K是一個非常接近于1的常數(shù)，這里我們?nèi)=0.9。

6 實驗結(jié)果與分析

根據(jù)運行程序得到其中一種會議成員的分配方案如下：

表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 參會成員互相見面次數(shù)統(tǒng)計

相互見面次數(shù) 0 1 2 3 4 5

模擬退火算法 103 234 166 83 17 1

根據(jù)上表知，見面次數(shù)大部分集中在1次和2次之間，基本實現(xiàn)預期目標。模型的優(yōu)點包括兩個方面：一方面，本模型具有相當好的適用性。對于會議成員類型不同，數(shù)目任意，以及衡量交叉混合程度的標準有所增減的情況，均可應用本算法；另一方面，本模型具有很強的可推廣性。由于對會議成員總數(shù)，會議場次，會員類型，參與層次等參數(shù)沒有特殊要求，所以此模型有很大的可推廣性。模型的缺點主要表現(xiàn)為：（1）權(quán)系數(shù)的取值帶有一定的主觀性。如果能通過嚴密的數(shù)學方法得出權(quán)系數(shù)的值將使模型更具科學性。（2）結(jié)果不具唯一性。隨著循環(huán)次數(shù)的不同以及隨機初解取值的差異，得到的minf（x）會有所不同，同時產(chǎn)生的分配方案也有所差異。7 結(jié)論

本文研究利用組合優(yōu)化方法解決會議成員的分配問題。

首先，引入分組矩陣與相遇矩陣的概念以及他們之間存在的數(shù)學關系，以便于后面對會議成員組成的集合進行討論，接著根據(jù)所需研究問題的限制條件確定相應的約束條件。然后，采用加權(quán)系數(shù)的方法將多目標函數(shù)歸結(jié)轉(zhuǎn)化為單一的目標函數(shù)，同時把分組矩陣作為決策變量，大量減少了模型中決策變量的個數(shù)，便于建立相應的數(shù)學模型。最后，通過置換初始解，得到該初始可行解的一個鄰近解，進而得到該初始可行解的一個鄰域，繼而采用模擬退火算法在全局范圍內(nèi)進行迭代，最終可以得到該模型的一個較為滿意的解，從而解決會議成員的分配問題。

參考文獻

[1]西蒙.管理決策新科學[M].北京：中國科學社會出版社，1982.

[2]斯蒂芬·P·羅賓斯.管理學（第九版）[M].北京：中國人民大學出版社，2008.

[3]劉興堂，梁炳成.復雜系統(tǒng)建模理論、方法與技術[M].北京：科學出版社，2008，（1）.

[4]模擬退火算法[EB/OL].http：//baike.baidu.com/view/18185.htm.

[5]陳華根，吳健生.模擬退火算法機理研究[J].同濟大學學報，2004，32（6）：802805.