丁威+楊雪斌

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

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

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

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

1 決策理論

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

2 模型的假設(shè)

2.1 問題陳述

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

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

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

2.2 假設(shè)條件

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

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

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

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

該假設(shè)依據(jù)說明如下：會議成員分配模型應(yīng)使與會董事混合得最好，并且在每個場次中保證董事們應(yīng)在盡可能相互認識的基礎(chǔ)上重復(fù)見面的次數(shù)盡可能平均且盡量小。假設(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

∵假設(shè)全天會議結(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 分組矩陣和相遇矩陣的關(guān)系定理

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

定理：若P為分組矩陣，則其對應(yīng)的相遇矩陣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）每次分組時，每組中的公司雇員董事應(yīng)當合比例，

有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ù)應(yīng)盡可能少，首先對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ù)Ⅱ的給出

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

在這里，我們認為g（x）達到最小時，任意兩個成員重復(fù)見面次數(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īng)用于組合優(yōu)化領(lǐng)域，它是基于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）重復(fù)（2）-（3）步，直至系統(tǒng)達到平衡狀態(tài)；（5）按第一步給定的退火策略下降t，重復(fù)（2）-（4）步，直至t=0或某一預(yù)定的低溫。衰減函數(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ù)期目標。模型的優(yōu)點包括兩個方面：一方面，本模型具有相當好的適用性。對于會議成員類型不同，數(shù)目任意，以及衡量交叉混合程度的標準有所增減的情況，均可應(yīng)用本算法；另一方面，本模型具有很強的可推廣性。由于對會議成員總數(shù)，會議場次，會員類型，參與層次等參數(shù)沒有特殊要求，所以此模型有很大的可推廣性。模型的缺點主要表現(xiàn)為：（1）權(quán)系數(shù)的取值帶有一定的主觀性。如果能通過嚴密的數(shù)學(xué)方法得出權(quán)系數(shù)的值將使模型更具科學(xué)性。（2）結(jié)果不具唯一性。隨著循環(huán)次數(shù)的不同以及隨機初解取值的差異，得到的minf（x）會有所不同，同時產(chǎn)生的分配方案也有所差異。7 結(jié)論

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

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

參考文獻

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

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

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

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

[5]陳華根，吳健生.模擬退火算法機理研究[J].同濟大學(xué)學(xué)報，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īng)用于組合優(yōu)化領(lǐng)域，它是基于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）重復(fù)（2）-（3）步，直至系統(tǒng)達到平衡狀態(tài)；（5）按第一步給定的退火策略下降t，重復(fù)（2）-（4）步，直至t=0或某一預(yù)定的低溫。衰減函數(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ù)期目標。模型的優(yōu)點包括兩個方面：一方面，本模型具有相當好的適用性。對于會議成員類型不同，數(shù)目任意，以及衡量交叉混合程度的標準有所增減的情況，均可應(yīng)用本算法；另一方面，本模型具有很強的可推廣性。由于對會議成員總數(shù)，會議場次，會員類型，參與層次等參數(shù)沒有特殊要求，所以此模型有很大的可推廣性。模型的缺點主要表現(xiàn)為：（1）權(quán)系數(shù)的取值帶有一定的主觀性。如果能通過嚴密的數(shù)學(xué)方法得出權(quán)系數(shù)的值將使模型更具科學(xué)性。（2）結(jié)果不具唯一性。隨著循環(huán)次數(shù)的不同以及隨機初解取值的差異，得到的minf（x）會有所不同，同時產(chǎn)生的分配方案也有所差異。7 結(jié)論

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

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

參考文獻

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

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

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

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

[5]陳華根，吳健生.模擬退火算法機理研究[J].同濟大學(xué)學(xué)報，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īng)用于組合優(yōu)化領(lǐng)域，它是基于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）重復(fù)（2）-（3）步，直至系統(tǒng)達到平衡狀態(tài)；（5）按第一步給定的退火策略下降t，重復(fù)（2）-（4）步，直至t=0或某一預(yù)定的低溫。衰減函數(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ù)期目標。模型的優(yōu)點包括兩個方面：一方面，本模型具有相當好的適用性。對于會議成員類型不同，數(shù)目任意，以及衡量交叉混合程度的標準有所增減的情況，均可應(yīng)用本算法；另一方面，本模型具有很強的可推廣性。由于對會議成員總數(shù)，會議場次，會員類型，參與層次等參數(shù)沒有特殊要求，所以此模型有很大的可推廣性。模型的缺點主要表現(xiàn)為：（1）權(quán)系數(shù)的取值帶有一定的主觀性。如果能通過嚴密的數(shù)學(xué)方法得出權(quán)系數(shù)的值將使模型更具科學(xué)性。（2）結(jié)果不具唯一性。隨著循環(huán)次數(shù)的不同以及隨機初解取值的差異，得到的minf（x）會有所不同，同時產(chǎn)生的分配方案也有所差異。7 結(jié)論

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

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

參考文獻

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

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

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

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

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