數(shù)學建模lingo程序解決會議分組問題

答卷編號（參賽學校填寫）：答卷編號（競賽組委會填寫）：論文題目：F題:會議分組問題組別：本科生參賽學校：東北電力大學報名序號：參賽隊員信息(必填)：姓名專業(yè)班級及學號聯(lián)系電話參賽隊員1張鵬寧電自1011班100929023715043269112參賽隊員2張學陽數(shù)學101班100930013215043259842參賽隊員3張慧琴電自1011班100518012915143284582答卷編號（競賽組委會填寫）：評閱情況（省賽評閱專家填寫）：省賽評閱1：省賽評閱2：省賽評閱3：省賽評閱4：省賽評閱5：會議分組問題摘要本文針對會議分組這個實際問題，以運籌學最優(yōu)分配為基礎，采用編程完成了代表參加會議的分組方案。針對問題（1），已知有名代表參加會議，要分個場次，每場會議中有個小組，先對數(shù)據(jù)進行了矩陣化處理，其中引入常值元素來區(qū)分不同地區(qū)的代表，為了達到盡可能使來自不同地區(qū)的代表能有見面交流機會的目的，以每組代表人數(shù)基本均衡、每個會議每個代表有且只能在一個小組內(nèi)為約束條件，建立非線性整數(shù)變量規(guī)劃模型，從而確立出最優(yōu)的分組方案。針對問題（2），考慮到模型中有變量相乘的形式，用計算大量數(shù)據(jù)的非線性模型運行時間較長，因此采用分部計算的形式來求解此模型，也就是一共有次會議，可以迭代次來計算，每次迭代只計算一次會議的會面情況，每次迭代時更新目標函數(shù)的系數(shù)，上一次已經(jīng)會面的代表假設為同一地區(qū)，則這次計算常值系數(shù)，只計算未見面的代表會見面次數(shù)的最大值，迭代完畢之后將次結果綜合考慮，便得到模型的最優(yōu)方案。針對問題（3），將問題（1）中的、、分別取做37、5、5，采用問題（1）所建立的模型以及問題（2）設計的算法，運行程序，但由于迭代次數(shù)過多，本文取、、分別為9、5、5，也即所給表格中前九個代表開5次會議，每次會議分五組，得到的分配結果如下：第一組第二組第三組第四組第五組第一次1，72，93，64，85第二次4，91，572，63，8第三次4，67，91，823，5第四次2，56，834，71，9第五次2，83，71，65，94關鍵詞：分組；迭代；優(yōu)化；非線性1．問題的重述目前，國內(nèi)外許多重要會議都是以分組形式進行研討，以便充分交流、溝通。一般地，一個由N名代表參加的會議，要分為M個場次，每場會議分為L個小組，并且要求每個小組的人數(shù)基本均衡。問題1：請建立分組方案的數(shù)學模型，使得盡可能讓任意兩個來自不同地區(qū)的代表之間都有見面交流的機會。問題2：設計求解上述分組模型的有效算法。問題3：現(xiàn)有一個學術團體要舉行由37位專家參加的學術研討會，每個專家所在地區(qū)的信息見表1。會議分5場進行，每場會議又分5個小組，每個小組人數(shù)要基本均衡。請根據(jù)問題1所建立的模型以及問題2設計的算法，給出5場會議的每一場各個組中有哪些代表參加的安排方案。2．問題的分析對于問題一，已知有名代表參加會議，要分個場次，每場會議中有個小組，令表示第個人在第次會議中被分到第個組的可能，的值只能為1或者0，1表示第個人在第次會議中被分到第個組；0表示第個人在第次會議中沒被分到第個組。再令表示第個代表和第個代表分到第組的可能，的值也只有1和0,1表示個代表和第個代表分到第組；0表示i個代表和第j個代表未分到第k組。再設一個時令系數(shù)，當和代表是同一個地方時，為0；當和代表不是同一個地方時，為1。是經(jīng)過判斷與相乘后得到的數(shù)值，用表示第個代表和第個代表五場會議相遇的次數(shù)，當相遇的次數(shù)為0時的數(shù)值為0，當相遇的次數(shù)不為0時，的數(shù)值是1，目標函數(shù)是所有的相加達到最大時才能盡可能讓任意兩個來自不同地區(qū)的代表之間都有見面交流的機會。對于問題二，考慮到模型中有變量相乘的形式，用計算大量數(shù)據(jù)的非線性模型運行時間比較長，因此可以采用分部計算的形式來求解此模型，也就是一共有次會議，可以迭代次來計算，每次迭代只計算一次會議的會面情況，每次迭代時更新目標函數(shù)的系數(shù)，講上一次已經(jīng)會面的代表假設為同一地區(qū)，也就是如果第個代表和第個代表上一次會面，則這次計算時令系數(shù)，只計算未見面的代表會面次數(shù)的最大值，迭代完畢之后將次結果綜合考慮，便得到模型的最優(yōu)方案。對于問題三，將問題（1）中的、、分別取做37、5、5，采用問題（1）所建立的模型以及問題（2）設計的算法，運行程序，但由于迭代次數(shù)過多，耗費時間過多，因此本文取、、分別為9、5、5，也即所給表格中前九個代表開5次會議，每次會議分五組，即檢驗一下程序的可用性。3．符號說明編號為的代表在第次會議中的第組中分組矩陣代表和代表分在同一組的可能第次會議相遇矩陣總的相遇矩陣目標函數(shù)常值會議的場次數(shù)分組總數(shù)代表總數(shù)會議的次序代表和是否會過面4．模型的建立與求解4．1問題1的模型建立與求解表1第k次會議的安排情況代表小組12……1……2…………如上表所示為第次會議的安排情況，為分組總數(shù)，為代表總數(shù)，其中的取值為0或1，表示編號為的代表在第次會議中的第組中，表示編號為的代表不在第次會議中的第組中，由于在每次會議中每個人只能被分到一個組內(nèi)，則滿足如下關系第次會議的分組矩陣為又由于要求每組代表的人數(shù)盡量均勻，因此還滿足如下關系令其中為的對稱陣，的元素為在第次會議中，代表和代表分在同一組時的值為1，否則為0，為的單位陣。次會議中代表的會面情況可表示為其中的元素為表示代表和代表分在同一組的次數(shù)。設地區(qū)異同矩陣為，其元素表示代表和代表來自不同地區(qū)，否則。令表示代表和代表曾被分到一個組內(nèi)，否則令表示不同地區(qū)的代表和曾被分到一個組內(nèi)，否則目標函數(shù)為：使得盡可能讓任意兩個來自不同地區(qū)的代表之間都有見面交流的機會，綜上建立的非線性整數(shù)變量規(guī)劃模型為其中由題意定的常值。4．2問題2的模型建立與求解考慮到模型中有變量相乘的形式，用計算大量數(shù)據(jù)的非線性模型運行時間比較長，因此可以采用分部計算的形式來求解此模型，也就是一共有次會議，可以迭代次來計算，每次迭代只計算一次會議的會面情況，每次迭代時更新目標函數(shù)的系數(shù)，講上一次已經(jīng)會面的代表假設為同一地區(qū)，也就是如果第個代表和第個代表上一次會面，則這次計算時令系數(shù)，只計算未見面的代表會面次數(shù)的最大值，迭代完畢之后將次結果綜合考慮，便得到模型的最優(yōu)方案。其計算過程如下：步驟1：設置初值（是問題一中的系數(shù)，表示第個代表和第個代表不在同一地區(qū)）。步驟2：第一次迭代，計算第一次會議代表的會面情況，且滿足如下約束步驟3：重復步驟2，計算第二次會議代表的會面情況，以此類推，第次迭代為由步驟2求得第次會議代表的會面情況，且滿足約束第次迭代為由步驟二求得第次會議代表的會面情況，滿足的約束同上。步驟四：得出第個代表和第個代表的會面情況其中表示第個代表和第個代表會過面，每步迭代求解得到的就是第個代表第次會議中的分組情況，表示編號為的代表在第次會議中的第組中。4．3問題3的模型建立與求解將問題（1）中的、、分別取做37、5、5，采用問題（1）所建立的模型以及問題（2）設計的算法，運行程序，但由于迭代次數(shù)過多，本文取、、分別為9、5、5，也即表格中前9個代表開5次會，每次會議分為5個小組，下面以表格中前9個代表分為5個小組5次會議來說明模型的正確性。其中常值矩陣為經(jīng)計算得到的結果為矩陣會議的分組方案為：表2會議的分組方案第一組第二組第三組第四組第五組第一次1，72，93，64，85第二次4，91，572，63，8第三次4，67，91，823，5第四次2，56，834，71，9第五次2，83，71，65，94用圖形直觀的表示為如下：221313949485857676圖1代表的見面交流圖圖中兩個數(shù)字之間的連線表示兩個標號的代表已經(jīng)見面交流過了，通過上圖可直觀看出任意兩個代表之間沒有重復的線并且同一地區(qū)的代表不在一個小組內(nèi)開會，從而不同地區(qū)的兩個代表盡可能多的見面交流。5．模型結果的分析與檢驗5次會議通過5次迭代，分別計算出每次會議代表會面的情況，其中矩陣為初始矩陣，表示參加會議的代表不在同一地區(qū)，為對稱矩陣，考慮問題方便只考慮上對角陣，在第一次會議中，9個代表分在5個小組內(nèi)，經(jīng)過計算，第二個矩陣中數(shù)值是2的位置表示兩個代表分在同一組，2的位置有4個，說明至多有4個代表分在同一組，且數(shù)值為2的位置沒有出現(xiàn)在矩陣中數(shù)值為0的位置，這與事實相符。第二次會議中，依舊是9個代表分在5個小組內(nèi)，結果是數(shù)值為3的位置是兩個代表分在同一組，數(shù)值為3的位置依然是4個，且不會出現(xiàn)在數(shù)值為2的位置，因為數(shù)值為2的位置表示兩個代表已經(jīng)見過面，以此類推，相應的數(shù)字和其位置如矩陣所示，數(shù)字不會重復，且數(shù)值均為4，說明是要求的結果，由此可證明模型是正確的。6．模型的推廣與改進方向1）由于在計算過程中目標函數(shù)的矩陣是對稱的，計算整體的矩陣迭代的次數(shù)會更多，會花費更長的時間，而且計算結果還需除以2，因此可以更改目標函數(shù)如下即只需計算矩陣的上對角陣，便得到最終的結果。2）模型是非線性的，直接計算迭代次數(shù)會過多，花費的時間也較長，因此我們可以通過先計算一次會議的會面情況，將會過面的代表當做是同一地區(qū)的代表處理，通過更新的值來計算下一次會面的情況，在解決問題二中用到了此方法。7．模型的優(yōu)缺點優(yōu)點：（1）本算法能盡量使來自不同地區(qū)的代表會面。（2）運用了非線性代數(shù)求解的方法和編程，使得處理得到的結果達到最優(yōu)。缺點：人數(shù)過多且迭代次數(shù)多，導致算法的運行時間大大延長。參考文獻[1]姜啟源．數(shù)學模型（第三版）[M]．北京：高等教育出版社，1999．[2]韓中庚．數(shù)學建模方法及其應用（第二版）[M]．北京：高等教育出版社，2009．[3]茆詩松．概率論與數(shù)理統(tǒng)計（第二版）．北京：高等教育出版社，2011．[4]何曉群．多元統(tǒng)計分析（第二版）．北京，中國人民出版社，2010．

附錄附錄一問題三的Lingo源程序model:sets:peo/r1..r37/;meet/m1..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))>=7));@for(meet(I):@for(group(K):@sum(peo(J):x(I,J,K))<=8));@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=00001111111111111111111111111111111110000111111111111111111111111111111111000011111111111111111111111111111111100001111111111111111111111111111111111111000111111111111111111111111111111111100011111111111111111111111111111111110001111111111111111111111111111111111111001111111111111111111111111111111111100111111111111111111111111111111111111100111111111111111111111111111111111110011111111111111111111111111111111111110011111111111111111111111111111111111001111111111111111111111111111111111111001111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111