關于玫瑰有約的數(shù)學模型摘要：現(xiàn)在城市大齡青年的婚姻問題收起了社會的廣泛關注，針對這一社會現(xiàn)象，我們假設某單位有20對大齡青年男女，每個人的基本條件都不相同，并且每個人的擇偶條件也不相同。該單位的婦聯(lián)組織擬根據他們的年齡，基本條件和要求條件牽線搭橋。本文根據每個人的情況和要求，建立數(shù)學模型幫助婦聯(lián)解決3個問題。關鍵詞：數(shù)學模型；滿意度；匈牙利算法；KM算法The mathematical model about making an appointment for life Li wei(Department of Mathematics and Computational Science Hunan University of Science and Engineering,Yongzhou,425100,Hunan）Abstract: Nowadays, the problem of the youngs marriage has roused more and more publics concern. According to this phenomenon, we assume that there are twenty pairs of aged people in a company, all of which have different basic condition and their demanding。The Women's Federation of this company wants to wire-pull for them on the basis of their age, basic condition and demand. This paper, according to everyones condition and demands, helps the Women's Federation solving this problem.Key words: mathematical model; the measurement of satisfaction; Hungary algorithm; KM algorithm; 1.引言現(xiàn)在在城市大齡青年的婚姻問題引起了社會的廣泛關注，針對這一現(xiàn)象，我們給出20對青年男女的基本條件和擇偶條件的抽樣是真實可靠的。首先，我們將所給的兩個表格按年齡升序重新進行排列，分別編號為1，2，320。并且將外貌、性格、氣質、事業(yè)、財富五個方面的五個等級A、B、C、D、E分別賦值為5、4、3、2、1，這樣我們就得到了男女青年的基本條件和要求條件的四個矩陣；其次，我們定義了“滿意度”的概念，利用圖論（二部圖）的方法解決這個問題。 在模型中，根據男青年的基本條件和女青年的要求條件構造度量矩陣（權值矩陣）A，男1號的基本條件和女1號的要求條件，比如在外貌方面，男1號滿足女1號的要求則賦值為5-3+1，在事業(yè)方面，男1號不滿足女1號的要求，則賦值為0，按照這個方法，如果滿足條件則按公式（男青年基本條件值-女青年相應的要求條件+1）賦值，反之賦值為0，這樣可以得到外貌，性格，氣質，事業(yè)，財富五個方面的數(shù)值，并將這些數(shù)值相加得到，最終得到權值矩陣T=（）2020，同理可得，女青年的基本條件和男青年的要求條件所構成的權值矩陣S=()2020，那么男女青年配對的總權值矩陣（即為滿意度矩陣）為R1=T+S，（因為表示男i號的基本條件對j號的要求條件，表示女j號的基本條件對男i號的要求條件，那么用+ 表示男i號對女j號的總權數(shù)即為他們之間的滿意度）：再次，我們根據年齡的限制在矩陣R1中將不滿足條件的賦0，得到矩陣R，利用匈牙利算法可得到問題（1）的結果。再在矩陣R中將大于2的數(shù)字賦1反之賦0，再利用KM算法可得問題（2）的結果。 由于以上的模型在構造權值矩陣R時，男青年基本條件不滿足女青年要求條件時賦值為0，實際上還存在男女青年的失望度，故在模型改進中針對失望度將模型中賦值為0的另外賦值為（女青年要求條件值男青年相應的基本條件值）即考慮到可能單向面的滿意度較大而另一方面的失望度也較大時同樣不能配對成功，且在把模型無向化時是采用把每個結點分成兩個結點的方法即把有向的平行邊分成各自帶自己權的無向邊，同時在此模型中將初等模型中的五個等級A、B、C、D、E量化為9、7、5、3、1（由于模型中的賦值尺度比較粗糙），其余的步驟與模型相同，從而得到了模型改進。2.問題的提出目前，在許多城市大齡青年的婚姻問題已引起了婦聯(lián)和社會團體組織的關注。某單位現(xiàn)在有20對大齡青年男女，每個人的基本條件都不相同，如外貌、性格、氣質、事業(yè)、財富等。每項條件通?？梢苑譃槲鍌€等級A、B、C、D、E，如外貌、性格、氣質、事業(yè)可分為很好、好、較好、一般、差；財富可以分為很多、多、較多、一般、少。每個人的擇偶條件也不盡相同，即對每項基本條件的要求是不同的。該單位的婦聯(lián)組織擬根據他（她）們的年齡、基本條件和要求條件進行牽線搭橋。下面給出20對大齡青年男女的年齡、基本條件和要求條件（如下表）。一般認為，男青年至多比女青年的年齡大5歲，或女青年的年齡比男青年的大2歲，并且要至少滿足個人要求5項條件中的2項，才有可能配對成功。本文根據每個人的情況要求，建立數(shù)學模型幫助婦聯(lián)解決如下問題：(1)給出可能的配對方案，使得在盡量滿足個人要求的條件下，使得配對成功率盡可能的高。(2)給出一種20對男女青年可同時配對的最佳方案，使得全部配對成功的可能性最大。(3)假設男女雙方都相互了解了對方的條件和要求，讓每一個人出一次選擇，只有當男女雙方相互選中對方時才認為配對成功，每一個人只有一次選擇機會。怎樣告訴20對男女青年都應該如何做出選擇，使得自己的成功的可能性最大？選擇的方案最多能配對成功多少對？男青年 基本條件要求條件外貌 性格 氣質 事業(yè) 財富年齡外貌性格氣質事業(yè)財富ACBCA29AACBDCABAD29BABBCBBABB28BAABCCABBD28CABCDDBCAA30CBBBECBCBB28BBCDCABBDC30CBBDCBABCD30ABCCDADCEB28AAACCDBAAA28ABADEBACDA32ABCDBABCAB29BABBCBADEC28ACBBCAABBD30ACCDCABBCC28AABCDDEBAA30AAAEECABAD28AAAEEABACB31BBACCCDAAA29ABAEDABCDE27BCBDB女青年基 本 條 件要 求 條 件 外貌 性格 氣質 事業(yè)財富 年齡 外貌 性格 氣質 事業(yè) 財富ACCDA28BABADBABAD25CBBABCBAEA26BACBCABBCD27AABBABDCEC25ABCBBACBCA26BABBCDCBAB30CBAACABAEC31BABABAAACE26CBBBABCDBB27BBAACABBCB28CBABCBECEA26AABBEEACBB26CABCCBBCAA25BAABDCBAAC29BABBBBACDC28BABBAAEEDA25AADACAABBC28CABACBACCE25BBBAADBACD29BBABB注：表中的要求條件一般是指不低于所給的條件。為了方便后面的計算，我們按年齡升序重新對上述兩個表格進行排列并且編號：男青年基 本 條 件要 求 條 件 外貌 性格 氣質 事業(yè)財富 年齡 外貌 性格 氣質 事業(yè) 財富1ABCDE27BCBDB2BBABB28BAABC3CABBD28CABCD4CBCBB28BBCDC5ADCEB28AAACC6DBAAA28ABADE7BADEC28ACBBC8ABBCC28AABCD9CABAD28BABBC10ACBCA29AACBD11CABAD29BABBC12ABCAB29BABBC13CDAAA29ABAED14DBCAA30CBBBE15ABBDC30CBBDC16BABCD30ABCCD17AABBD30ACCDC18DEBAA30AAAEE19ABACB31BBACC20BACDA32ABCDB女青年基 本 條 件要 求 條 件 外貌 性格 氣質 事業(yè)財富 年齡 外貌 性格 氣質 事業(yè) 財富1BABAD25CBBAB2BDCEC25ABCAB3BBCAA25BAABD4AEEDA25AADAC5BACCE25BBBAA6CBAEA26BACBC7ACBCA26BABBC8AAACE26CBBBA9BECEA26AABBE10EACBB26CABCC11ABBCD27AABBA12BCDBB27BBAAC13ACCDA28BABAD14ABBCB28CBABC15BACDC28BABBA16AABBC28CABAC17CBAAC29BABBB18DBACD29BBABB19DCBAB30CBAAC20ABAEC31BABAB注：表格中的要求條件一般是指不低于所給條件3.問題分析 該問題是現(xiàn)實生活中的實際問題，主要就是確定合理配對方案，使得在盡量滿足個人要求條件下，使配對成功率盡可能的高。由于每個人的基本條件和要求條件都是給定的，雙方彼此是知道的，而且是相互之間有很大的差異，如果完全按照要求條件組合配對成功。任意一對男女的配對可以看成一個隨機事件，按某一概率可能配對成功，或不成功。在這里雙方的滿意度主要反映出一個人對另一個人的客觀和主觀看法，因此，滿意度的定義成為解決問題的一個關鍵。所謂的“成功率”，就是男女雙方最終配對的概率。實際上，可以用他們相互之間的滿意度來間接刻畫。相互的滿意度越高，雙方配對的成功率就越大。對于問題（1），要使配對成功率盡可能的高明，也就是給出一種方案，使得20對男女的配對后的滿意度之和最高。對于問題（2），要使20對男女青年同時配對，使得全部同時成功的可能性（概率）最大。對于問題（3），因為每人個只能選擇一次，能不配對成功取決于雙方是不是選中對方，即要看雙方彼此的滿意度如何。實際中，假如一個男青年（）對一個女青年（）的滿意度最高，但對的滿意度不一定最高，即若選擇，但不一定選擇。因此，與不一定配成對，反之亦然?，F(xiàn)在的問題是誰選誰，使配對成功的可能性最大呢？這個問題實際上是男女雙方在彼此基本了解的情況下，在保證自己一定滿意的條件下做出自己的選擇，也需要猜測對方會做出怎樣的選擇。因此，這個問題可能轉化為男女雙方的對策問題，即轉化為求男女雙方的非零和對策的納什平衡點的問題。4. 模型的假設與符號說明41模型的假設 (1)題目所給出的男女青年的評價是客觀真實的;(2)每個人在選擇雙方的時候是理智的; (3)男女青年不會受當時環(huán)境的影響。42符號說明K=1,2,3,4,5.分別表示外貌、性格、氣質、事業(yè)、財富這5個條件；(i=1,2 20)表示年齡升序排列后男青年編號；（j=1,2 20）表示年齡升序排列后女青年編號；( i=1,2 20,k=1,2,3,4,5)表示男青年在k方面的基本條件； ( i=1,2 20,k=1,2,3,4,5)表示男青年在k方面的要求； ( j=1,2 20,k=1,2,3,4,5)表示女青年在k方面的基本條件；( j=1,2 20,k=1,2,3,4,5)表示女青年在k方面的要求；表示男青年i對女青年j在k方面的滿意度；表示女青年j對男青年i在k方面的滿意度；表示男青年i與女青年j在k方面的滿意度之和.5模型的建立和求解5.1條件量化處理 對于每個人的外貌、性格、氣質、事業(yè)、財富五項條件的5個等級A，B，C，D，E分別作量化處理為5，4，3，2，1。于是根據上表可以得到男女青年的基本條件量化矩陣和要求條件量化矩陣（或稱權值矩陣）以及滿意度分量分別記為：5.2 滿意度現(xiàn)在，我們對滿意度進行說明，要確定對的第K項條件的滿意度。先對年齡進行篩選，年齡為大于或大于的滿意度為0；如果基本條件達不到的要求即,給它賦值為0值.否則，滿意度記為剛好達到為1，超過一個等級加1。即滿意度為。這樣就體現(xiàn)了，當一方實際條件高于對方期望（要求）條件時，則對方對他（她）的好感（相對于要求條件）就會增加，超過得越多，好感增加得越多。5.3模型的建立 我們把二十個青年男女抽象化為40個結點得到一個帶權二部圖，其中Aj表示二十個男青年，Bj表示二十個女青年，而從男青年到女青年有一條帶權邊，權則由上面求得的滿意度矩陣決定，然后，我們用最大二部圖匹配算法（匈牙利算法）求出一個最大匹配的解；但是，一開始所求得的是一個有向圖，因此我們必須把它無向化，至此對問題（1）我們僅僅是采用把兩結點間權值相加而轉化為一個無向圖，進而就可以用匈牙利算法對其求解了。而對于問題（2）則要采用圖的完美匹配算法（KM算法）進行求解，從而使全部配對成功的可能性最大，對于問題（3），則同樣采用匈牙利算法只是把權值改變即可，這里我們把結點間有向邊的權值同時大于2且滿意度和不滿意度差別不是很大時才有可能配對成功此時把它賦為1，而在不滿足條件時則賦為0,從而得出能配對成功最多的方案。下面對匈牙利算法和KM算法進行說明。匈牙利算法的主要思想是在每次增廣的時候不是找一條增廣路而是同時找?guī)讞l點不相交的最短增廣路，形成極大增廣路集，隨后可以沿著這幾條增廣路同時進行增廣。可以證明在尋找增廣路集的每一個階段所尋找到的最短增廣路都具有相等的長度，并且隨著算法的進行最短增廣路的長度是越來越長的，更進一步分析可以證明最多只需增廣ceil(sqrt(n)次就可以得到最大匹配（證明在這里略去）。KM算法：（全稱是Kuhn-Munkras,是這二個人在1957年提出來的），首先為每個點設立一個頂標Li，設vi,j-為（i,j）邊的權，如果可以求得一個完美匹配，使得每條匹配邊vi,，其余邊。此時的解就是最優(yōu)的，因為匹配邊的權和=，其余任意解的權和都不可能比這個大。5.4模型的求解以題中所給數(shù)據為例，我們用EXCEL處理后得到權值，然后編程求得結果為：問題(1)男A1A2A3A4A5A6A7A8A9A10女B18B17B16B15B2B19B3B12B1B14男A11A12A13A14A15A16A17A18A19A20女B20B10B7B8B6B5B4B11B9B13問題(2)男A1A2A3A4A5A6A7A8A9A10女B11B12B19B18B8B5B3B6B2B20男A11A12A13A14A15A16A17A18A19A20女B1B17B7B14B15B13B16B9B4B10問題(3)男A1A3A5A10A12A14A15A17A18A19女B15B18B19B9B2B6B4B14B11B85.5模型修正（1）對滿意度的說明首先要注意到兩個事實：其一，如果基本條件比的要求條件差得越多，則對的第K項條件的滿意度就越小，反之亦然。也就是說，如果一方的實際條件比對方期望（要求）的條件差距越大，則對方對另一方失望就越大，即滿意度就越小。其二，如果的基本條件比的要求條件高，則對的第k項條件的滿意度（k）就會增加，但增加不會太多。即當一方的實際條件高于對方期望（要求）的條件時，則對方對加一方的好感（相對要求條件）增加不會太大。而在模型中只考慮了實際條件高于要求條件，好感會增加并考慮到實際條件低于要求條件時，失望會增加，即滿意度會減小?，F(xiàn)在模型的基礎上加以改進：如果的基本條件達不到的要求，即（）時，給它賦值它是一個負值，體現(xiàn)了當一方實際條件低于期望（要求）的條件時，則對方對他（她）失望（相對于要求條件）就會增加差距越大，失望度就越大，相應的滿意度就越小。顯然，改進后成功的解決了上面所提出的問題，所以顯得更加合理。滿意度矩陣中的各分量分別表示如下：(2) 模型的重新建立 首先,我們把量化的尺度改為1-9尺度把A,B,C,D,E五個等級分別量化為9、7、5、3、1，然后在給出的二部圖轉化為無向圖時則把每個結點分為兩個結點，從而問題轉化為求40對結點的二部圖的最大匹配和完美匹配問題了，對問題1和問題2用同樣算法求解，而對于問題3則當滿意度矩陣中的權大于零時賦為1而在小于零時則賦為0。（3）以題中所給數(shù)據為例，我們用EXCEL處理后得到權值，然后編程求得結果為：問題(1)男A1A2A3A4A5A6A7A8A9A10女B4B18B15B20B2B5B3B13B17B9男A11A12A13A14A15A16A17A18A19A20女B16B10B7B1B6B19B14B11B8B12問題(2)男A1A2A3A4A5A6A7A8A9A10女B2B18B6B14B19B5B3B13B11B20男A11A12A13A14A15A16A17A18A19A20女B1B17B7B12B15B9B16B8B4B10問題(3)男A1A3A5A10A12A14A15A17A18A19女B15B18B19B9B2B6B4B14B11B86. 模型結果的分析 從所得的結果分析可知，模型改進后所得到的結果比改進前所得到的結果更加合理，對問題1是為了要盡量滿足個人要求的條件使配對成功率更高，即要使得二部圖中的邊的權值相對來說是比較大的，而對問題2則是要全部配對成功的可能性最高，即是要使得所得到的完美配對圖的權值之和最大即使得要20對同進配對的可能性最大的方案。而對問題3則要在男女雙方都滿意的前提下并且是雙方都選擇了雙方。則從我們得到的結果可知模型改進后得到的結果比模型要更優(yōu)。7. 模型的優(yōu)缺點 對于兩個模型，改進前的模型顯然比改進后的模型粗糙得多，但是運行起來相對簡單，而且在模型中我們運用了匈牙利算法使問題更加簡單化，充分體現(xiàn)了熟練運用數(shù)學軟件在我們運用數(shù)學思想解決實際問題中的重要性。而在改進后的模型中，我們利用圖論的思想，運用匈牙利算法（二部圖的最大匹配算法）和KM算法（二部圖的完美匹配算法），并且將原精度提高，采用1-9尺度，使得問題的解答更加精確，但是由于算法太復雜，在計算機計算方面顯得比較吃力，運行也相對難以實現(xiàn)一點。在社會上各人的擇偶標準不同，所以他們在選擇對象的側重點也會不同，比方說；有的人會特別注重外表，然而有的人特別注重對方的事業(yè)和個人的氣質等等。而我們在兩個模型中，只是簡單的將五個方面的五個等級分別賦值為幾個數(shù)值，不能體現(xiàn)個人的側重點。同時，我們在模型中假設了對各人的抽樣是真實可靠的，然而各人的擇偶標準還會隨時間不斷改變，所以假設不一定會長久成立，若在模型的改進方向上再注意這些問題，結果會更接近現(xiàn)實。參考文獻1韓中庚.數(shù)學建模方法及其應用M.北京:高等教育出版社，2005.5.2邊馥萍,侯文華,梁馮珍.數(shù)學模型方法與算法M.北京:高等教育出版社,2005.4.3姜啟源,謝金星.數(shù)學模型(第三版)M.北京:高等教育出版社,2003.8.4吳乃陵,況迎輝.C+程序設計(第二版)M.北京:高等教育出版社,2006.3.5 Bczdek J, Pal S. Fuzzy Models for Pattern Recognition M. Piscataway: IEEE Press, 1992. 6 zdek J. Pattern Recognition with KM Algorithm M. New York: PlenumBe Press, 1981. 致謝 本文的選題得到了林依勤老師的指導，從撰寫到完稿都得到了曾立波老師的悉心指導，在此，對曾立波老師和林依勤老師的幫助表示衷心的感謝。另外本文的完成還得到了羅光輝同學和李鵬同學的幫助，在此也對他們表示衷心的感謝。附 錄匈牙利算法#include<iostream> #include<string> #include<vector> using namespace std; bool mark1100,mark2100; int list100; int n,m,edge,num;c ector<vector<int> > v; bool dfs(int to) register int i,point,s = listto; for(i=0;i<vs.size();i+) point = vsi; if(!mark2point) continue; mark2point = false; if(listpoint=-1 | dfs(point) listpoint = s; return true; return false; void Solve() int i,j,point; bool flog = false; memset(mark1,true,sizeof(mark1); memset(list,-1,sizeof(list); num=0; for(i=0;i<n;i+) for(j=0;j<vi.size();j+) if(listvij = -1) mark1i = false; listvij = i; num+; if(i=0) flog = true; break; for(i=0;i<n;i+) if(mark1i) if(!vi.empty() memset(mark2,true,sizeof(mark2); for(j=0;j<vi.size();j+) point = vij; if(!mark2point) continue; mark2point = false; if(listpoint = -1 | dfs(point) listpoint = i; num+; break; mark1i = false; if(flog | list0 != -1) cout << num-1 << endl; else cout << num << endl; int main() int i,j,s,d; while(cin>>n) if(n = 0)break; v.clear(); v.resize(n); cin >> m >> edge; for(i=0;i<edge;i+) cin >> j >> s >> d; vs.push_back(d); Solve(); return 0; KM算法：#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int size = 160; const int INF = 100000000;  /  相對無窮大 bool mapsizesize;         / 二分圖的相等子圖, mapij = true 代表Xi與Yj有邊 bool xckdsize, yckdsize;  / 標記在一次DFS中，Xi與Yi是否在交錯樹上 int matchsize;             / 保存匹配信息，其中i為Y中的頂點標號，matchi為X中頂點標號 bool DFS(int, const int); void KM_Perfect_Match(const int n, const int edgesize)    int i, j;    int lxsize, lysize;   /  KM算法中Xi與Yi的標號    for(i = 0; i < n; i+)       lxi = -INF;       lyi = 0;       for(j = 0; j < n; j+)          lxi = max(lxi, edgeij);                bool perfect = false;     while(!perfect)       /  初始化鄰接矩陣         for(i = 0; i < n; i+)             for(j = 0; j < n; j+)             if(lxi+lyj = edgeij) mapij = true;             else mapij = false;                        / 匹配過程       int live = 0;       memset(match, -1, sizeof(match);       for(i = 0; i < n; i+)          memset(xckd, false, sizeof(xckd);          memset(yckd, false, sizeof(yckd);          if(DFS(i, n) live+;          else             xckdi = true;             break;                        if(live = n) perfect = true;       else          / 修改標號過程          int ex = INF;          for(i = 0; i < n; i+)             for(j = 0; xckdi && j < n; j+)                if(!yckdj) ex = min(ex, lxi+lyj-edgeij);                                 for(i = 0; i < n; i+)             if(xckdi) lxi -= ex;             if(yckdi) lyi += ex;                      / 此函數(shù)用來尋找是否有以Xp為起點的增廣路徑，返回值為是否含有增廣路 bool DFS(int p, const int n)    int i;    for(i = 0; i < n; i+)       if(!yckdi && mappi)          yckdi = true;          int t = matchi;          matchi = p;          if(t = -1 | DFS(t, n)             return true;                    matchi = t;          if(t != -1) xckdt = true;               return false; int main()    int n, edgesizesize; /  edgeij為連接Xi與Yj的邊的權值    int i;        /*     *       在此處要做的工作 :     *       讀取二分圖每兩點間邊的權并保存在edge中,     *  若X與Y數(shù)目不等，應添加配合的頂點     *       保存二分圖中X與Y的頂點數(shù)n,若上一步不等應保     *  存添加頂點完畢后的n     */        KM_Perfect_Match(n, edge);    int cost = 0;    for(i = 0; i < n; i+)       cost += edgematchii;        / cost 為最大匹配的總和, match中保存匹配信息        return 0; 17