用匈牙利算法解決相親類型問題的數(shù)學模型(編輯修改稿)
2025-05-04 02:54 本頁面
【文章內(nèi)容簡介】 的問題是誰選誰，使配對成功的可能性最大呢？這個問題實際上是男女雙方在彼此基本了解的情況下，在保證自己一定滿意的條件下做出自己的選擇，也需要猜測對方會做出怎樣的選擇。因此，這個問題可能轉(zhuǎn)化為男女雙方的對策問題，即轉(zhuǎn)化為求男女雙方的非零和對策的納什平衡點的問題。4. 模型的假設與符號說明4．1模型的假設 (1)題目所給出的男女青年的評價是客觀真實的。(2)每個人在選擇雙方的時候是理智的。 (3)男女青年不會受當時環(huán)境的影響。4．2符號說明K=1,2,3,4,、性格、氣質(zhì)、事業(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．模型的建立和求解 對于每個人的外貌、性格、氣質(zhì)、事業(yè)、財富五項條件的5個等級A，B，C，D，E分別作量化處理為5，4，3，2，1。于是根據(jù)上表可以得到男女青年的基本條件量化矩陣和要求條件量化矩陣（或稱權值矩陣）以及滿意度分量分別記為： 滿意度現(xiàn)在，我們對滿意度進行說明，要確定對的第K項條件的滿意度。先對年齡進行篩選，年齡為大于或大于的滿意度為0；如果基本條件達不到的要求即,，滿意度記為剛好達到為1，超過一個等級加1。即滿意度為。這樣就體現(xiàn)了，當一方實際條件高于對方期望（要求）條件時，則對方對他（她）的好感（相對于要求條件）就會增加，超過得越多，好感增加得越多。 我們把二十個青年男女抽象化為40個結(jié)點得到一個帶權二部圖，其中Aj表示二十個男青年，Bj表示二十個女青年，而從男青年到女青年有一條帶權邊，權則由上面求得的滿意度矩陣決定，然后，我們用最大二部圖匹配算法（匈牙利算法）求出一個最大匹配的解；但是，一開始所求得的是一個有向圖，因此我們必須把它無向化，至此對問題（1）我們僅僅是采用把兩結(jié)點間權值相加而轉(zhuǎn)化為一個無向圖，進而就可以用匈牙利算法對其求解了。而對于問題（2）則要采用圖的完美匹配算法（KM算法）進行求解，從而使全部配對成功的可能性最大，對于問題（3），則同樣采用匈牙利算法只是把權值改變即可，這里我們把結(jié)點間有向邊的權值同時大于2且滿意度和不滿意度差別不是很大時才有可能配對成功此時把它賦為1，而在不滿足條件時則賦為0,從而得出能配對成功最多的方案。下面對匈牙利算法和KM算法進行說明。匈牙利算法的主要思想是在每次增廣的時候不是找一條增廣路而是同時找?guī)讞l點不相交的最短增廣路，形成極大增廣路集，隨后可以沿著這幾條增廣路同時進行增廣?？梢宰C明在尋找增廣路集的每一個階段所尋找到的最短增廣路都具有相等的長度，并且隨著算法的進行最短增廣路的長度是越來越長的，更進一步分析可以證明最多只需增廣ceil(sqrt(n))次就可以得到最大匹配（證明在這里略去）。KM算法：（全稱是KuhnMunkras,是這二個人在1957年提出來的），首先為每個點設立一個頂標Li，設vi,j為（i,j）邊的權，如果可以求得一個完美匹配，使得每條匹配邊vi,，其余邊。此時的解就是最優(yōu)的，因為匹配邊的權和=，其余任意解的權和都不可能比這個大。以題中所給數(shù)據(jù)為例，我們用EXCEL處理后得到權值，然后編程求得結(jié)果為：問題(1)男A1A2A3A4A5A6A7A8A9A10女B18B17B16B15B2B19B3B12B1B14男A11A12A13A14A15A16A17A18A19A20女B20B10B7B8B6B5B4B11B9B13問題(2)男A1A2A3A4A5A6A7A8A9A10女B11B12B19B18B8B5B3B6B2B20男A11A12A13A14A15A16A17A18A19A20女B1B17B7B14B15B13B16B9B4B10問題(3)男A1A3A5A10A12A14A15A17A18A19女B15B18B19B9B2B6B4B14B11B8（1）對滿意度的說明首先要注意到兩個事實：其一，如果基本條件比的要求條件差得越多，則對的第K項條件的滿意度就越小，反之亦然。也就是說，如果一方的實際條件比對方期望（要求）的條件差距越大，則對方對另一方失望就越大，即滿意度就越小。其二，如果的基本條件比的要求條件高，則對的第k項條件的滿意度（k）就會增加，但增加不會太多。即當一方的實際條件高于對方期望（要求）的條件時，則對方對加一方的好感（相對要求條件）增加不會太大。而在模型中只考慮了實際條件高于要求條件，好感會增加并考慮到實際條件低于要求條件時，失望會增加，即滿意度會減小?，F(xiàn)在模型的基礎上加以改進：如果的基本條件達不到的要求，即（）時，給它賦值它是一個負值，體現(xiàn)了當一方實際條件低于期望（要求）的條件時，則對方對他（她）失望（相對于要求條件）就會增加差距越大，失望度就越大，相應的滿意度就越小。顯然，改進后成功的解決了上面所提出的問題，所以顯得更加合理。滿意度矩陣中的各分量分別表示如下：(2) 模型的重新建立 首先,我們把量化的尺度改為19尺度把A,B,C,D,E五個等級分別量化為1，然后在給出的二部圖轉(zhuǎn)化為無向圖時則把每個結(jié)點分為兩個結(jié)點，從而問題轉(zhuǎn)化為求40對結(jié)點的二部圖的最大匹配和完美匹配問題了，對問題1和問題2用同樣算法求解，而對于問題3則當滿意度矩陣中的權大于零時賦為1而在小于零時則賦為0。（3）以題中所給數(shù)據(jù)為例，我們用EXCEL處理后得到權值，然后編程求得結(jié)果為：問題(1)男A1A2A3A4A5A6A7A8A9A10女B4B18B15B20B2B5B3B13B17B9男A11A12A13A14A15A16A17A18A19A20女B16B10B7B1B6B19B14B11B8B12問題(2)男A1A2A3A4A5A6A7A8A9A10女B2B18B6B14B19B5B3B13B11B20男A11A12A13A14A15A16A17A18A19A20女B1B17B7B12B15B9B16B8B4
數(shù)學相關推薦
鄂ICP備17016276號-1