多次分組會議安排的數(shù)學(xué)模型

一、問題重述二、假設(shè)條件三、變量及符號說明四、問題分析和模型建立五、模型求解六、調(diào)整算法七、模型推廣八、模型優(yōu)缺點內(nèi)容提綱

本文在仔細分析問題條件和要求的基礎(chǔ)上，運用了運籌學(xué)、圖論、矩陣理論和置換等方面的知識和技巧，建立了一個布爾規(guī)劃模型。

由于本模型的目標函數(shù)是非線性的，并且模型中的變量較多，因此若我們用求解一般整數(shù)規(guī)劃的方法去求解它是十分困難的。會議安排數(shù)學(xué)模型會議安排數(shù)學(xué)模型在這里，我們給出了一個求解該模型的迭代算法：首先，我們使用貪婪算法求得問題的初始可行解；然后，我們利用局部優(yōu)化的原理，反復(fù)迭代，逐步逼近最優(yōu)解；最終，我們可得到一個滿意解。我們認為，我們的算法相當(dāng)好地解決了提出的問題。對于有些委員可能臨時缺席或者有些未被安排的人員出席會議的情況，我們也給出了一個調(diào)整算法。利用它，我們能夠在原來的安排表的基礎(chǔ)上，快速地得到新的安排方案。這種調(diào)整算法的優(yōu)點在于它能夠最少地改動安排方案來滿足新的要求，從而更具有實際意義。會議安排數(shù)學(xué)模型由于在前述的模型建立與求解的過程中，所使用的思想方法和技巧具有一般性，因此，模型很容易推廣。我們針對題目的要求推廣了模型，建立了一般會議安排模型。模型中的參數(shù)，例如參加會議的人數(shù)、與會者的類型數(shù)和參與的不同層次數(shù)均是可變的。該模型及算法均能夠得出相當(dāng)好的結(jié)果。本模型有以下優(yōu)點：

(1)它相當(dāng)成功地解決了提出的問題,并能夠迅速地求出一組相當(dāng)優(yōu)化的解。

(2)本模型具有普遍的意義，能針對不同情況，根據(jù)不同參數(shù)，得到令人滿意的結(jié)果。

(3)在模型求解過程中,運用了大量的優(yōu)化思想和數(shù)學(xué)技巧，相當(dāng)好地解決了多變量非線性整數(shù)規(guī)劃問題,具有較大的應(yīng)用價值。

會議安排數(shù)學(xué)模型Smallgroupmeetingforthediscussionofimportantissues,particularlylong-rangeplanning,aregainingpopularity.Itisbelievedthatlargegroupsdiscourageproductivediscussionandthatadominantpersonalitywillusuallycontrolanddirectthediscussion.Thus,incorporateboardmeetingstheboardwillmeetinsmallgroupstodiscussissuesbeforemeetingasawhole.Thesesmallergroupsstillruntheriskofcontrolbyadominantpersonality.Inanattempttoreducethisdangueitiscommontoscheduleseveralsessionswithadiffentmixofpeopleineachgroup.會議安排數(shù)學(xué)模型AmeetingofAnTostalCorporationwillbeattendedby29BoardMembersofwhichninearein-housemembers(i.e.,corporateemployees).Themeetingistobeanall-dayaffairwiththreesessionsscheduledforthemorningandfourfortheafternoon.Eachsessionwilltake45minutes,beginningonthehourfrom9:00A.M.to4:00P.M.,withlunchscheduledatnoonEachmorningsessionwillconsistofsixdiscussiongroupswitheachdiscussiongroupledbyoneofthecorporation’ssixseniorofficers.Noneoftheseofficersareboardmembers.Thuseachseniorofficerwillleadthreedifferentdiscussiongroups.Theseniorofficerswillnotbeinvolvedintheafternoonsessionsandeachofthesesessionswillconsistofonlyfourdifferentdiscussiongroups.會議安排數(shù)學(xué)模型Thepresidentofthecorporationwantsalistofboard-memberassignmentstodiscussiongroupsforeachofthesevensessions.Theassignmentsshouldachieveasmuchofamixofthemembersasmuchaspossible.Theidealassignmentwouldhaveeachboardmemberwitheachotherboardmemberinadiscussiongroupthesamenumberoftimeswhileminimizingcommonmembershipofgroupsforthedifferentsessions.Theassignmentsshouldalsosatisfythefollowingcriteria:Forthemorningsessions,noboardmembershouldbeinthesameseniorofficer’sdiscussiongrouptwice.Nodiscussiongroupshouldcontainadisproportionatenumberofin-housemembers.

會議安排數(shù)學(xué)模型Givealistofassignmentsformembers1-9and10-29andofficers1-6.Indicatehowwellthecriteriainthepreviousparagraphsaremet.Sinceitispossiblethatsomeboardmemberswillcancelatthelastminuteorthatsomenotscheduledwillshowup,analgorithmthatthesecretarycouldusetoadjusttheassignmentswithanhour’snoticewouldbeappreciated.Itwouldbeidealifthealgorithmcouldalsobeusedtomakeassignmentsforfuturemeetingsinvolvingdifferentlevelsofparticipationforeachtypeofattendee.會議安排數(shù)學(xué)模型在討論重要問題時，特別是長遠規(guī)劃的問題，越來越流行的一種做法是召開小組會議．人們相信全體會議會使討論失去活力，而且權(quán)威人士通常將會控制和直接影響討論．這樣，在舉行全體會議之前，委員將以小組形式來討論問題．這些比較小的小組仍有被權(quán)威人士控制的危險．為了減少這種危險，通常將會議安排為幾個場次，每場次中每個開會小組由不同的人混合組成．會議安排數(shù)學(xué)模型Tostal公司將舉行一個由29個委員參加的會議，其中有9個委員是公司成員．這次會議將開一整天，上午分三場，下午分四場，每場45分鐘，開會時間從上午９：００到下午４：００，中午安排午餐．上午的每一場分６個小組開會，每個小組有公司派出的６名資深官員之一作組長．這６名資深官員中沒有一個是與會委員，并且他們不參加下午的會議．下午的每一場分為４個小組開會．會議安排數(shù)學(xué)模型公司負責(zé)人需要７個開會時間場次的每一場各個組中，有哪些委員參加的安排表.這一會議安排應(yīng)使所有委員盡可能相互交流．理想的安排是：每個委員與其他委員在開會小組中都有相同的見面次數(shù)，并且對每個不同的開會場次，各個開會小組中曾在同一組的委員應(yīng)盡可能少．會議的安排也要滿足下列兩個要求：上午的開會場次中，不能有一個委員參加過兩次由同一個資深官員主持的小組會；不允許同一個場次中的討論小組的公司委員數(shù)不合比例．會議安排數(shù)學(xué)模型請給出９個公司委員（編號１—９）非公司委員（編號１０—２９）以及資深官員的一張安排表，并且說明是如何滿足上述兩個要求的．因為有些委員可能臨時不能到會，或者有些未被安排的人員將出席會議，因此最好能設(shè)計一個算法，能夠?qū)聿煌瑓⑴c類型的人參加和各種不同參與水平的會議進行安排則更好．會議安排數(shù)學(xué)模型每種類型的與會者地位相同；與會者堅決服從會議組織者的安排；在整個會議進行過程中，不允許與會者變動

：決策向量；其元素表示在第場會議中，成員是否在第組；：分組矩陣；：第場會議的分組矩陣；：相遇矩陣；：第場會議的相遇矩陣；：總相遇矩陣：Qsum=會議安排數(shù)學(xué)模型會議安排數(shù)學(xué)模型

：目標函數(shù)，定義為中0元素的個數(shù)；：另一個目標函數(shù)，定義為矩陣T的范數(shù)平方

其中k是常數(shù)，表示平均重復(fù)相遇次數(shù)．

會議安排數(shù)學(xué)模型1、預(yù)備知識首先,我們必須先對分組作一個數(shù)學(xué)描述：令與會者集合，我們將他們分為ｎ組．于是，我們能夠得到一個矩陣：

其中會議安排數(shù)學(xué)模型因為矩陣Ｐ清楚地表達了分組情況，我們定義它為分組矩陣．理想的情況是，通過分組矩陣所給出的信息，我們能得到另一個矩陣，用它來判斷元素ｓi和ｓj是否曾在同一個小組中，這個新的矩陣為：其中其中會議安排數(shù)學(xué)模型我們定義它為相遇矩陣．我們可以得到一個關(guān)于分組矩陣和相遇矩陣的基本定理．定理:若為一個分組矩陣，則其對應(yīng)的相遇矩陣為

(E為單位陣)．證明：顯然對于每一位與會者來說，每次只能被分在某一個小組中，因此矩陣的每一行只有一個元素為1，其余均為０．考慮式子，可以很容易地得到該矩陣的元素為：

（１）若和不同時為１，就意味著和不在同一組中，那么；（２）如果和同時為１，就意味著和分在同一組中，那么．所以相遇矩陣．會議安排數(shù)學(xué)模型結(jié)合問題中的條件和要求，我們可以用變量表示第i個人在第j場次會議中被分于第k組．其中i=1~29代表29個參加會議的委員；

i=1~9代表９個公司委員；

i=10~29代表其余２０個非公司委員；

j=1~7代表７個場次的會議；

k=1~6代表每個場次分６個小組；

于是，對每一場次的分組來說，就一定存在一個分組矩陣再根據(jù)問題的條件和要求，我們得到下列約束條件：

(1)在每一次分組中，每人只能分在一組中：

(2)每次分組時,每組中的公司委員數(shù)應(yīng)當(dāng)合比例：

(3)上午階段的每場會議，６個小組每一個都要有一名資深官員主持，每個參加會議的委員都不能與任一名資深官員重復(fù)見面：會議安排數(shù)學(xué)模型

(j=1~7)代表了７次分組的分組矩陣，那么我們?nèi)绾尾拍芘袛啵反畏纸M的效果是好還是壞呢？對于這個問題，我們可以參考問題的要求，問題要求模型給出的分組方案應(yīng)使所有與會委員混合得最好，并且在每個場次中在保證委員們盡可能地相互認識的基礎(chǔ)上，使委員們重復(fù)見面的次數(shù)盡量平均，我們先考慮一個極端情況：29個委員分在一個組中．這樣，充分混合的目標是最好的滿足了，但是，重復(fù)見面的次數(shù)也達到了最大．因此，當(dāng)分組數(shù)小或者各組人數(shù)不均衡時，開會場次越多，與會這重復(fù)見面的次數(shù)就越大．同時，我們還必須注意避免人數(shù)太多影響討論的效果，或者被權(quán)威人士所影響和操縱．在模型的建立和求解過程中，我們只考慮29個委員均分為6組或4組的情況．我們認為，在這樣的劃分前提下所得到分組方案，其重復(fù)見面次數(shù)總和應(yīng)達到最?。畬τ谶@個結(jié)論，我們無法給出嚴格的數(shù)學(xué)推導(dǎo)．但考慮到實際生活中的絕大多數(shù)情況，我們認為均分是最有實際意義的．所以，我們將參加上午會議的29個委員分為５、５、５、５、５、４，共６組；下午的分為７、７、７、８，共４組．

會議安排數(shù)學(xué)模型那么，我們?nèi)绾斡脭?shù)學(xué)語言來描述或評判７次分組的好壞？對于第j次分組來說，有分組矩陣Pi，又存在相遇矩陣Qi．７次分組后，委員1~~29相互見面的總次數(shù)可通過以下公式來計算：其中矩陣稱為分組的總的相識矩陣

考慮到充分交流和任意兩個會員重復(fù)見面次數(shù)盡量相同這兩個目標，我們認為在總的相識矩陣中０元素的個數(shù)必須達到最?。硐氲臓顟B(tài)是，除了主對角線上元素為０之外，中別的元素均為相同（即任意兩個與會成員之間見面次數(shù)相同）．根據(jù)均勻分組的原則，我們可以得到這樣的安排為與會者提供了次相互見面的機會．另一方面，只需要次相互見面的機會就可以使29個與會成員兩兩相遇了．因此，任意兩個與會成員平均能有1.31次機會見面．會議安排數(shù)學(xué)模型令k=532/406=1.31

會議安排數(shù)學(xué)模型其中

我們認為達到最小時，任意兩個成員重復(fù)見面次數(shù)達到盡量平均這個目標得以實現(xiàn)．而當(dāng)達到最小時，充分見面這個目標也得以最好地滿足，這同時也表明了成員之間的充分交流４、建立模型

我們得到如下的模型：

根據(jù)前面的討論，我們有

會議安排數(shù)學(xué)模型因為模型的目標函數(shù)是充分相識的前提下保證成員間兩兩重復(fù)見面次數(shù)平均，所以我們的目標有兩個：Min和Min。事實上，目標函數(shù)表明了成員之間沒有相互見面的程度，越小，相互見面的程度就越高，而之所以引入的原因在于保證任意兩個成員重復(fù)見面的次數(shù)盡量平均。這是一個標準的整數(shù)規(guī)劃和多目標規(guī)劃的問題。我們要做的就是如何對它進行求解。會議安排數(shù)學(xué)模型1、分析我們試圖為這個模型提出一個一般的算法，并根據(jù)這個算法為模型找出一組最優(yōu)解來。由于在模型建立過程中，所有的變量被定義為只能?。盎颍保覀兪紫认氲降氖钦麛?shù)規(guī)劃的方法。而根據(jù)上述模型，這是一個標準的多目標0-1整數(shù)規(guī)劃問題，目前還缺乏切實可行的算法可以找出最優(yōu)解來，能夠證明，這是一個ＮＰ完全問題。如果我們使用窮舉法來搜索最優(yōu)解的話，變量個數(shù)為986個，循環(huán)次數(shù)也將達到６986次。這對于我們的電腦是一個巨大的挑戰(zhàn)，甚至連奔騰級的計算機也無法進行如此大規(guī)模的運算，窮舉法是不可行的。我們首先要指出的是本模型的最優(yōu)解是客觀存在的。我們的想法是先找出一個滿足所有條件的初始可行解，然后在這組解的基礎(chǔ)上，逐步迭代，使這組解不斷逼近最優(yōu)解。最后，我們便可以得到一組近似最優(yōu)解了。（1）迭代我們先通過貪婪算法找到一組初始可行解，然后我們運用坐標輪換法固定其中六組向量（每一組向量均代表一個場次的分組情況），調(diào)整剩下的那一組向量使目標函數(shù)和減少.

會議安排數(shù)學(xué)模型第一步，我們調(diào)整代表第七場次分組情況的向量組使目標函數(shù)減小，下一步，我們再調(diào)整代表第六場次分組情況的向量組是目標函數(shù)值減小，不斷重復(fù)該過程，我們便可以獲得一組近似最優(yōu)解了。同時，目標函數(shù)也逼近最小值。因為目標函數(shù)有兩個，我們使用的是多目標規(guī)劃級別優(yōu)先的策略：在達到最小的條件下使也盡可能小。首先我們利用進行迭代，直到它不再減小為止。然后在不變的基礎(chǔ)上利用迭代，使得它也盡可能小。由于和的值都在不斷減小，且都有界，根據(jù)單調(diào)有界數(shù)列必收斂的原理，最后我們可以得到一組近似最優(yōu)解。會議安排數(shù)學(xué)模型（2）置換我們將不在同一組中的兩個成員交換位置。如果這種交換使得目標函數(shù)減小，則交換是可接受的，否則，交換被拒絕。不斷重復(fù)這樣的過程，目標函數(shù)也就不斷減小了

（3）初始解我們利用貪婪算法獲得一組初始可行解。在每一個階段，該算法將29個成員依次插入到各個組中去。在插入之前，算法將結(jié)合當(dāng)前的分組情況，根據(jù)限制條件和目標函數(shù)找出一個最佳位置供該成員插入。會議安排數(shù)學(xué)模型A：得到一組初始可行解（1）令；（””代表會議的不同場次；“”則代表各個成員的序號．）；（2）；（3）；（4）如果，就必須考慮每一個委員不得與資深官員重復(fù)見面的限制條件。（5）如果，就必須考慮到公司委員被均分的條件。會議安排數(shù)學(xué)模型（6）設(shè)每一個資深官員見過的與會成員的總數(shù)保持平衡。（7）計算目標函數(shù)和，找出一個最佳位置使成員插入后目標函數(shù)和盡可能小。（8）當(dāng)有多個組可選擇時，選擇序號較小的組。（9）如果，回到步驟(3)，否則轉(zhuǎn)到步驟(10)。（10）如果，回到步驟(2)，否則轉(zhuǎn)到算法B。

步驟(6)是為了保證一種均衡。事實上，我們所得到的這個安排方案無論是在整個會議期間還是在每一階段都保持了均衡，而以下的置換算法不會破壞此方案的均衡性。這個初始解為今后得到更好的解奠定了基礎(chǔ)。會議安排數(shù)學(xué)模型B：通過迭代算法優(yōu)化初始解得到最優(yōu)解

（1）;（2）輸入初始可行解；（3）調(diào)整分組矩陣，在保證不變的基礎(chǔ)上交換滿足下列條件的每一對成員的位置：兩個成員必須是同一類型的參與者（同為公司委員或同為非公司委員）；他們必須在不同的組中；他們在上午的三次分組中不得與資深官員重復(fù)見面；目標函數(shù)的值在交換后必須減小。

會議安排數(shù)學(xué)模型（4）交換每一對滿足下列條件的成員：兩個成員必須是同一類型的參與者（同為公司成員或同為非公司成員）；他們必須在不同的組中；他們在上午的三次分組中不得與資深官員重復(fù)見面；目標函數(shù)的值保持不變，目標函數(shù)的值在交換后必須減小。（5）；（6）若，則回到步驟(3)；（7）若一輪循環(huán)后（）沒有一個交換被接受便退出，否則以當(dāng)前解為初始解轉(zhuǎn)回到步驟(2)。會議安排數(shù)學(xué)模型通過貪婪算法，我們得到如下的方案：表1．上午分配表

會議安排數(shù)學(xué)模型表2.下午分配表

=209且=28.25會議安排數(shù)學(xué)模型通過迭代算法得到另一組分配方案：表3.上午分配表

表4.下午分配表會議安排數(shù)學(xué)模型表5.兩組方案比較表會議安排數(shù)學(xué)模型從上面的表格中，我們可以很容易的得到一些結(jié)論。通過貪婪算所得到的初始解滿足所有均衡條件，這意味著這個解也具有某種程度優(yōu)化。而最后通過迭代法得到的解不僅保持了初始解的均衡性，而且也使目標函數(shù)和得以優(yōu)化。我們認為我們所得到的解滿足了問題中的兩個要求：我們的解不僅使0（相互不見面）的個數(shù)降低到26，還使得3（最多相互見面3次）的個數(shù)減少至25。

在下面，我們給出了最佳會議安排表表6。在表中，以“A”開頭的標號代表資深官員，以“B”開頭的標號代表公司內(nèi)部職員。以“C”開頭的標號代表普通職員。

會議安排數(shù)學(xué)模型表6.會議安排最佳安排表表6.會議安排最佳安排表（續(xù)）會議安排數(shù)學(xué)模型現(xiàn)在，我們考慮在最后一刻，一些計劃參加的委員未能參加和一些未計劃參加的委員將出席會議。如我們以上所說，此模型是很容易推廣的。一個簡單的方法是將與會委員重新編號，然后按我們的算法解決這個新問題，但在真正的生活中，我們不希望對已安排好的會議進行太大的改變。因此，我們給出了另一個策略來對此進行調(diào)整。會議安排數(shù)學(xué)模型第一種情況：當(dāng)在最后一刻，一些未計劃參加的委員將出席會議。我們僅考慮如何將這些額外的會員安排到以前已確定的安排中去，而不改變以前的安排，我們使用一種與貪婪算法類似的方法去解決這個新問題，這些額外的會員將被一個一個的安排，對每一個額外的會員我們按照限制條件——保持安排的平衡和使與會者最大可能的相見，為其在每一場次中找到一個最合適的討論組。

會議安排數(shù)學(xué)模型第二種情況：當(dāng)在最后一刻，一些計劃參加的委員未能參加。我們考慮從原定的安排中找出一個同一類型的與會會員，這個會員的缺席將導(dǎo)致最好的混合，也就是他的缺席將使目標函數(shù)值更大的降低，然后，我們讓他去代替那個不能出席的會員，而他以前的會議安排將被取消，如此，我們每次取消一個與會者。最后，我們將解決這個問題，當(dāng)然，我們總是保持安排的平衡。第三種情況：當(dāng)前兩種情況同時發(fā)生時，我們可以轉(zhuǎn)化為第一第二種情況來處理。會議安排數(shù)學(xué)模型表7.三種算法計算結(jié)果比較調(diào)整算法與前述算法計算結(jié)果比較見表7，在表中使用的標號ni代表在矩陣中元素i(i=1,2,3,4,5)的個數(shù)。

會議安排數(shù)學(xué)模型

應(yīng)該說，我們的迭代算法和調(diào)整算法都是令人滿意的?？瓷先ィ烧{(diào)整算法得到的結(jié)果應(yīng)當(dāng)和由迭代算法得到的結(jié)果同樣的好，在幾種情況下（例如：八個公司內(nèi)部委員參加的會議），由調(diào)整算法得到的結(jié)果略微優(yōu)于由迭代算法得到的結(jié)果。這說明在我們的模型求解中仍存在誤差，還需要改進。會議安排數(shù)學(xué)模型在建模和求解過程中，我們對參數(shù)沒有特殊的要求，如：會員的總數(shù)、會議的場次、會員的類型和參與的層次。因為我們的模型有很大可推廣性，我們可以給出一個更一般情況下的模型。現(xiàn)在，讓我們考慮在未來的會議中的安排。在這個會議中，我們假定：有d類會員，整個會議被分成w個階段，第i個階段有Si個場次且每個場次由Gi個討論組組成，安排也應(yīng)滿足以下要求：

1.在每個場次中，每一個會員僅能被安排到一個組中。

2.第個場次中，類型的會員要在每個場次中平衡的分布。

3.整個的安排情況也要保持平衡。