數(shù)學建模會議分組問題

1、會議分組問題摘要本文解決會議分組問題，即在會議次數(shù)以及參會人數(shù)確定的情況下求取不同地區(qū)之間最大的見面概率的會議安排方式，通過設置相應參數(shù)，逐步建立數(shù)學模型，并采用編程進行計算，并最終確定會議人員參加會議的分組方案。下面將分別對三個問題進行闡述： 問題1是已知有名代表參加會議，要分個場次，每場會議中有個小組，先對數(shù)據(jù)進行了矩陣化處理，其中引入常值元素來區(qū)分不同地區(qū)的代表，以l×n的矩陣表示每個人在某一場的出席情況，以此建立非線性整數(shù)變量規(guī)劃模型。為了達到盡可能使來自不同地區(qū)的代表能有見面交流機會的目的，本文以每組代表人數(shù)基本均衡、每個會議每個代表有且只能在一個小組內(nèi)為約束條件，根據(jù)m個

2、矩陣的加和等一系列運算的結果，得到m場會議之后與會人員的見面情況，從而進行優(yōu)化，最終確立出最優(yōu)的分組方案。針對問題2，本文通過建立分組矩陣、開會矩陣，制定約束條件，構造相遇矩陣以及構造異地代表是否見面函數(shù)，逐步建立最終的數(shù)學模型。但是用lingo計算大量數(shù)據(jù)的非線性模型運行時間太長，無法獲得運算結果（超過5個小時），因此采用分部計算的形式來求解此模型，也就是一共有次會議，須經(jīng)過多次迭代，每次迭代只計算一次會議的會面情況，每次迭代時更新目標函數(shù)的系數(shù)，上一次已經(jīng)會面的代表假設為同一地區(qū)，則這次計算常值系數(shù)，只計算未見面的代表會見面次數(shù)的最大值，迭代完畢之后將次結果綜合考慮，并最后得到模型的最優(yōu)方

3、案。針對問題3，將問題1中的、分別取做8、5、5，采用問題（1）所建立的模型以及問題2設計的算法，運行程序，得到的分配結果如下：表2 會議的分組方案第一組第二組第三組第四組第五組第一次2、874、513、6第二次514、63、82、7第三次3、741、82、65第四次74、82、631、5第五次41、673、82關鍵詞：會議分組；矩陣分析；迭代運算；整數(shù)規(guī)劃；約束條件1、 問題的重述 會議分組是一個很實際的問題，目前國內(nèi)外許多重要會議都是以分組形式進行研討，以便充分交流、溝通。本文是將相應的參數(shù)進行了設置，參會代表n名，m個場次，每場會議l個小組，并且要求每個小組的人數(shù)基本均衡。本文要以使得盡

4、可能讓任意兩個來自不同地區(qū)的代表之間都有見面交流的機會為目的，建立數(shù)學模型，并設計求解上述分組模型的有效算法。同時，設置一些具體數(shù)值對已經(jīng)建立的模型以及算法進行驗算，即、分別取做37、5、5，根據(jù)問題1所建立的模型以及問題2設計的算法，給出5場會議的每一場各個組中具體有哪些代表參加的安排方案。二、問題假設1、每場次，每個專家都會參加，沒有人缺席。2、每次會議對于專家的吸引力相同。3、每個會議每個代表有且只能在一個小組內(nèi)。三、符號說明表一 符號說明在第次會議中的第組中第次會議分組矩陣和是否在第次會議分在同一組第次會議開會矩陣相遇矩陣所有會議中和是否相遇異地矩陣和是否來自同一地區(qū)會議的場次數(shù)代表總

5、數(shù)分組總數(shù)異地代表會面總數(shù)異地代表是否見面四、模型建立及求解模型建立第次會議的分組矩陣為其中的取值為0或1，表示代表在第次會議中的第組中，表示表示代表不在第次會議中的第組中，由于在每次會議中每個人只能被分到一個組內(nèi)，則滿足如下關系：又由于要求每組代表的人數(shù)盡量均勻，滿足如下關系：構造第次會議開會矩陣在第次會議中，代表和代表分在同一組時，否則，為的單位陣。次會議中代表的會面情況可表示為其中的元素為表示代表和代表分在同一組的次數(shù)。構造相遇矩陣其中，表示代表和代表曾被分到一個組內(nèi)，否則根據(jù)已知條件構造異地矩陣，其中表示代表和代表來自不同地區(qū)，否則。構造異地代表是否見面函數(shù)其中，表示不同地區(qū)的代表和曾

6、被分到一個組內(nèi)，否則。使得盡可能讓任意兩個來自不同地區(qū)的代表之間都有見面交流的機會，綜上建立的非線性整數(shù)變量規(guī)劃模型為模型求解考慮到模型中有變量相乘的形式，用計算運行時間比較長，因此可以采用分部計算來求解模型。即就是一共有次會議，可以迭代次來計算，每次迭代只計算一次會議的會面情況，每次迭代時更新異地矩陣，將已經(jīng)會面的代表和設為同一地區(qū)，只計算未見面的代表會面次數(shù)的最大值，迭代完畢之后將次結果綜合考慮，便得到模型的最優(yōu)方案。其計算過程如下：步驟1：設置初值步驟2：第一次迭代，計算第一次會議代表的會面情況，使得：且滿足如下約束： 步驟3：重復步驟2，計算第二次會議代表的會面情況，以此類推，第次迭代

7、為由步驟3求得第次會議代表的會面情況步驟4：得出第個代表和第個代表的會面情況模型檢驗將、分別取做8、5、5，采運行程序下面以表格中前8個代表分為5個小組5次會議來說明模型的正確性。表2 會議的分組方案第一組第二組第三組第四組第五組第一次2、874、513、6第二次514、63、82、7第三次3、741、82、65第四次74、82、631、5第五次41、673、825、 結論本文綜合考慮三個問題以及其內(nèi)部數(shù)學關系，逐步深入地通過建立分組矩陣、開會矩陣，制定約束條件，構造相遇矩陣以及構造異地代表是否見面函數(shù)，逐步建立最終的數(shù)學模型。但是用lingo計算大量數(shù)據(jù)的非線性模型運行時間太長，無法獲得運算

8、結果，因此采用分部計算的形式，逐步迭代來進行模型求解（程序均為自行編寫，迭代的輸出結果詳見附錄），故將問題1中的、（分別取做37、5、5）取為8、5、5，從而驗證了算法的正確性，并得到最終的會議安排方案。參考文獻1王沫然，matlab與科學計算，電子工業(yè)出版社，第三版2同濟大學數(shù)學系，線性代數(shù)，高等教育出版社，第五版3附錄lingo代碼model:sets:peo/r1.r8/;meet/m1/;group/g1.g5/;link(peo,peo):y,s;encount(meet,peo,group):x;endsetsmax=sum(link(i,j):s(i,j)*y(i,j);for(

9、link(i,j):bin(y(i,j);for(encount(i,j,k):bin(x(i,j,k);for(meet(i):for(peo(j):sum(group(k):x(i,j,k)=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)>=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)<=2);for(peo(i):for(peo(j):y(i,j)<=sum(meet(k):sum(group(l):x(k,i,l)*x(k,j,l);data:s=0 0 0 0 1 1

10、1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1;enddataendmodel:sets:peo/r1.r8/;meet/m2/;group/g1.g5/;link(peo,peo):y,s;encount(meet,peo,group):x;endsetsmax=sum(link(i,j):s(i,j)*y(i,j);for(link(i,j):bin(y(i,j);for(encount(i,j,k):bin

11、(x(i,j,k);for(meet(i):for(peo(j):sum(group(k):x(i,j,k)=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)>=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)<=2);for(peo(i):for(peo(j):y(i,j)<=sum(meet(k):sum(group(l):x(k,i,l)*x(k,j,l);data:s=0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0

12、 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1;enddataendmodel:sets:peo/r1.r8/;meet/m3/;group/g1.g5/;link(peo,peo):y,s;encount(meet,peo,group):x;endsetsmax=sum(link(i,j):s(i,j)*y(i,j);for(link(i,j):bin(y(i,j);for(encount(i,j,k):bin(x(i,j,k);for(meet(i):for(peo(j):sum(group(

13、k):x(i,j,k)=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)>=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)<=2);for(peo(i):for(peo(j):y(i,j)<=sum(meet(k):sum(group(l):x(k,i,l)*x(k,j,l);data:s=0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1

14、0 1 1 0 0 0 1 1 0 0 1 1 1 1 1;enddataendmodel:sets:peo/r1.r8/;meet/m4/;group/g1.g5/;link(peo,peo):y,s;encount(meet,peo,group):x;endsetsmax=sum(link(i,j):s(i,j)*y(i,j);for(link(i,j):bin(y(i,j);for(encount(i,j,k):bin(x(i,j,k);for(meet(i):for(peo(j):sum(group(k):x(i,j,k)=1);for(meet(i):for(group(k):sum

15、(peo(j):x(i,j,k)>=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)<=2);for(peo(i):for(peo(j):y(i,j)<=sum(meet(k):sum(group(l):x(k,i,l)*x(k,j,l);data:s=0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1;enddataendmod

16、el:sets:peo/r1.r8/;meet/m5/;group/g1.g5/;link(peo,peo):y,s;encount(meet,peo,group):x;endsetsmax=sum(link(i,j):s(i,j)*y(i,j);for(link(i,j):bin(y(i,j);for(encount(i,j,k):bin(x(i,j,k);for(meet(i):for(peo(j):sum(group(k):x(i,j,k)=1);for(meet(i):for(group(k):sum(peo(j):x(i,j,k)>=1);for(meet(i):for(gro

17、up(k):sum(peo(j):x(i,j,k)<=2);for(peo(i):for(peo(j):y(i,j)<=sum(meet(k):sum(group(l):x(k,i,l)*x(k,j,l);data:s=0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1;enddataend輸出結果第一次迭代 local optimal solution found. object

18、ive value: 7.000000 objective bound: 7.000000 infeasibilities: 0.000000 extended solver steps: 12 total solver iterations: 695第二次迭代 local optimal solution found. objective value: 6.000000 objective bound: 6.000000 infeasibilities: 0.000000 extended solver steps: 11 total solver iterations: 785第三次迭代

19、local optimal solution found. objective value: 5.000000 objective bound: 5.000000 infeasibilities: 0.000000 extended solver steps: 7 total solver iterations: 545第四次迭代 local optimal solution found. objective value: 4.000000 objective bound: 4.000000 infeasibilities: 0.000000 extended solver steps: 8

20、total solver iterations: 916 第五次迭代 local optimal solution found. objective value: 5.000000 objective bound: 5.000000 infeasibilities: 0.000000 extended solver steps: 13 total solver iterations: 1049 variable value y( r1, r1) 0.000000 y( r1, r2) 0.000000 y( r1, r3) 0.000000 y( r1, r4) 0.000000 y( r1,

21、 r5) 0.000000 y( r1, r6) 1.000000 y( r1, r7) 0.000000 y( r1, r8) 0.000000 y( r2, r1) 0.000000 y( r2, r2) 0.000000 y( r2, r3) 0.000000 y( r2, r4) 0.000000 y( r2, r5) 1.000000 y( r2, r6) 0.000000 y( r2, r7) 0.000000 y( r2, r8) 0.000000 y( r3, r1) 0.000000 y( r3, r2) 0.000000 y( r3, r3) 0.000000 y( r3,

22、 r4) 0.000000 y( r3, r5) 0.000000 y( r3, r6) 0.000000 y( r3, r7) 0.000000 y( r3, r8) 0.000000 y( r4, r1) 0.000000 y( r4, r2) 0.000000 y( r4, r3) 0.000000 y( r4, r4) 0.000000 y( r4, r5) 0.000000 y( r4, r6) 0.000000 y( r4, r7) 0.000000 y( r4, r8) 0.000000 y( r5, r1) 0.000000 y( r5, r2) 1.000000 y( r5,

23、 r3) 0.000000 y( r5, r4) 0.000000 y( r5, r5) 0.000000 y( r5, r6) 0.000000 y( r5, r7) 0.000000 y( r5, r8) 0.000000 y( r6, r1) 1.000000 y( r6, r2) 0.000000 y( r6, r3) 0.000000 y( r6, r4) 0.000000 y( r6, r5) 0.000000 y( r6, r6) 0.000000 y( r6, r7) 0.000000 y( r6, r8) 0.000000 y( r7, r1) 0.000000 y( r7,

24、 r2) 0.000000 y( r7, r3) 0.000000 y( r7, r4) 0.000000 y( r7, r5) 0.000000 y( r7, r6) 0.000000 y( r7, r7) 0.000000 y( r7, r8) 0.000000 y( r8, r1) 0.000000 y( r8, r2) 0.000000 y( r8, r3) 0.000000 y( r8, r4) 0.000000 y( r8, r5) 0.000000 y( r8, r6) 0.000000 y( r8, r7) 0.000000 y( r8, r8) 1.000000 s( r1,

25、 r1) 0.000000 s( r1, r2) 0.000000 s( r1, r3) 0.000000 s( r1, r4) 0.000000 s( r1, r5) 0.000000 s( r1, r6) 1.000000 s( r1, r7) 1.000000 s( r1, r8) 0.000000 s( r2, r1) 0.000000 s( r2, r2) 0.000000 s( r2, r3) 0.000000 s( r2, r4) 0.000000 s( r2, r5) 1.000000 s( r2, r6) 0.000000 s( r2, r7) 0.000000 s( r2,

26、 r8) 0.000000 s( r3, r1) 0.000000 s( r3, r2) 0.000000 s( r3, r3) 0.000000 s( r3, r4) 0.000000 s( r3, r5) 1.000000 s( r3, r6) 0.000000 s( r3, r7) 0.000000 s( r3, r8) 0.000000 s( r4, r1) 0.000000 s( r4, r2) 0.000000 s( r4, r3) 0.000000 s( r4, r4) 0.000000 s( r4, r5) 0.000000 s( r4, r6) 0.000000 s( r4,

27、 r7) 1.000000 s( r4, r8) 0.000000 s( r5, r1) 0.000000 s( r5, r2) 1.000000 s( r5, r3) 1.000000 s( r5, r4) 0.000000 s( r5, r5) 0.000000 s( r5, r6) 0.000000 s( r5, r7) 0.000000 s( r5, r8) 1.000000 s( r6, r1) 1.000000 s( r6, r2) 0.000000 s( r6, r3) 0.000000 s( r6, r4) 0.000000 s( r6, r5) 0.000000 s( r6,

28、 r6) 0.000000 s( r6, r7) 0.000000 s( r6, r8) 1.000000 s( r7, r1) 1.000000 s( r7, r2) 0.000000 s( r7, r3) 0.000000 s( r7, r4) 1.000000 s( r7, r5) 0.000000 s( r7, r6) 0.000000 s( r7, r7) 0.000000 s( r7, r8) 1.000000 s( r8, r1) 0.000000 s( r8, r2) 0.000000 s( r8, r3) 0.000000 s( r8, r4) 0.000000 s( r8, r5) 1.000000 s( r8, r6) 1.000000 s( r8, r7) 1.000000 s( r8, r8) 1.000000 x( m5, r1, g1) 0.000000 x( m5, r1, g2) 1.000000 x( m5, r1, g3) 0.000000 x( m5, r1, g4) 0.000000 x( m5, r1, g5) 0.