數(shù)學(xué)建模會(huì)議分組問題

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

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

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

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

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

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

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

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

9、):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(group(K):sum(peo(J):x(I,J,K)<=2);for(peo(I):for(peo(J):y(I,J)<=sum(meet(K):sum

10、(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 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);

11、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(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

12、1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 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)

13、: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 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0

14、 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 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(gr

15、oup(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 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

16、1 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1;enddataEndmodel: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)

17、: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 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;enddataEn

18、d輸出結(jié)果第一次迭代 Local optimal solution found. Objective 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 solv

19、er steps: 11 Total solver iterations: 785第三次迭代 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 Infe

20、asibilities: 0.000000 Extended solver steps: 8 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

21、( R1, R3) 0.000000 Y( R1, R4) 0.000000 Y( R1, 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

22、( R3, R2) 0.000000 Y( R3, R3) 0.000000 Y( R3, 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

23、( R5, R1) 0.000000 Y( R5, R2) 1.000000 Y( R5, 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

24、( R6, R8) 0.000000 Y( R7, R1) 0.000000 Y( R7, 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

25、( R8, R7) 0.000000 Y( R8, R8) 1.000000 S( R1, 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

26、( R2, R6) 0.000000 S( R2, R7) 0.000000 S( R2, 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

27、( R4, R5) 0.000000 S( R4, R6) 0.000000 S( R4, 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

28、( R6, R4) 0.000000 S( R6, R5) 0.000000 S( R6, 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.000000 X( M5, R2, G1) 0.000000 X( M5, R2, G2) 0.00