第11章整數(shù)規(guī)劃方法

1、第十一章 整數(shù)規(guī)劃方法11.1 整數(shù)規(guī)劃的模型 如果一個(gè)數(shù)學(xué)規(guī)劃的某些決策變量或全部決策變量要求必須取整數(shù)，則這樣的問(wèn)題稱(chēng)為整數(shù)規(guī)劃問(wèn)題，其模型稱(chēng)為整數(shù)規(guī)劃模型。 如果整數(shù)規(guī)劃的目標(biāo)函數(shù)和約束都是線性的，則稱(chēng)此問(wèn)題為整數(shù)線性規(guī)劃問(wèn)題。在里我們只就整數(shù)線性規(guī)劃問(wèn)題進(jìn)行討論，整數(shù)線性規(guī)劃的一般模型為： （11.1） 對(duì)于實(shí)際中的某些整數(shù)規(guī)劃問(wèn)題，我們有時(shí)候可以想到先略去整數(shù)約束的條件，即視為一個(gè)線性規(guī)劃問(wèn)題，利用單純形法求解，然后對(duì)其最優(yōu)解進(jìn)行取整處理。實(shí)際上，這樣得到的解未必是原整數(shù)規(guī)劃問(wèn)題的最優(yōu)解，因此，這種方法是不可取的，但可借鑒于這種思想。 整數(shù)規(guī)劃求解方法總的基本思想是：松弛問(wèn)題(11.

2、1)中的約束條件（譬如去掉整數(shù)約束條件），使構(gòu)成易于求解的新問(wèn)題松弛問(wèn)題(A)，如果這個(gè)問(wèn)題(A)的最優(yōu)解是原問(wèn)題(11.1)的可行解，則就是原問(wèn)題(11.1)的最優(yōu)解；否則，在保證不改變松弛問(wèn)題(A)的可行性的條件下，修正松弛問(wèn)題(A)的可行域(增加新的約束)，變成新的問(wèn)題（B），再求問(wèn)題(B)的解，重復(fù)這一過(guò)程直到修正問(wèn)題的最優(yōu)解在原問(wèn)題(11.1)的可行域內(nèi)為止，即得到了原問(wèn)題的最優(yōu)解。注意到: 如果每個(gè)松弛問(wèn)題的最優(yōu)解不是原問(wèn)題的可行解時(shí)，則這個(gè)解對(duì)應(yīng)的目標(biāo)函數(shù)值一定是原問(wèn)題最優(yōu)值的上界(最大化問(wèn)題)，即，或下界(最小化問(wèn)題)，即。11.2 整數(shù)規(guī)劃的分枝定界法 11.2.1. 分枝定

3、界法的基本思想 將原問(wèn)題（11.1）中整數(shù)約束去掉變?yōu)閱?wèn)題（A），求出問(wèn)題（A）的最優(yōu)解，如果它不是原問(wèn)題（11.1）的可行解，則通過(guò)附加線性不等式約束（整數(shù)），將問(wèn)題（A）分枝變?yōu)槿舾勺訂?wèn)題，即對(duì)每一個(gè)非整變量附加兩個(gè)互相排斥（不交叉）的整型約束，就得兩個(gè)子問(wèn)題，繼續(xù)求解定界，重復(fù)下去，直到得到最優(yōu)解為止。例11.1 用分枝定界法求解下列整數(shù)規(guī)劃問(wèn)題（A） 解（1）去掉為整數(shù)的約束，變?yōu)閱?wèn)題，求解可得的最優(yōu)解為，令，且。顯然不是（A）的可行解。（2）分枝：對(duì)附加約束條件，將（A）分為兩個(gè)子問(wèn)題和： 求解可得：，：。仍不是問(wèn)題（A）的可行解，取。（3）對(duì)問(wèn)題，分枝：對(duì)問(wèn)題附加約束分為問(wèn)題，對(duì)問(wèn)

4、題附加約束分為問(wèn)題， 分別求解可得：；：無(wú)可行解。因?yàn)榈慕鉃椋ˋ）的可行解，故取，注意到，則對(duì)和無(wú)需再分枝，將其剪掉。由可知，已得到了問(wèn)題（A）的最優(yōu)解。11.2.2 分枝定界法的一般步驟（1）將原整數(shù)規(guī)劃問(wèn)題（11.1）去掉所有的整數(shù)約束變?yōu)榫€性規(guī)劃問(wèn)題（A），用線性規(guī)劃的方法求解問(wèn)題（A），則有下列情況：1） 問(wèn)題（A）無(wú)可行解，則原問(wèn)題（11.1）也無(wú)可行解，停止計(jì)算；2）問(wèn)題（A）有最優(yōu)解，并是原問(wèn)題（11.1）的可行解，則此解就是（A）的最優(yōu)解，計(jì)算結(jié)束；3） 問(wèn)題（A）有最優(yōu)解，但不是原問(wèn)題（11.1）的可行解，轉(zhuǎn)下一步。（2）將代入目標(biāo)函數(shù)，其值記為，并用觀察法找出原問(wèn)題（11.

5、1）的一個(gè)可行解（整數(shù)解，不妨可取），求得目標(biāo)函數(shù)值（下界值），記為，則原問(wèn)題（11.1）的最優(yōu)值記為，即有，轉(zhuǎn)下一步；（3）分枝：在問(wèn)題（A）的最優(yōu)解中任選一個(gè)不滿足整數(shù)約束的變量（非整數(shù)），附加兩個(gè)整數(shù)不等式約束：和，分別加入到問(wèn)題（A）中，構(gòu)成兩個(gè)新的子問(wèn)題和，仍不考慮整數(shù)約束，求問(wèn)題和的解。定界：對(duì)每一個(gè)子問(wèn)題的求解結(jié)果，找出最優(yōu)值的最大者為新的上界，從所有符合整數(shù)約束條件的分枝中找出目標(biāo)函數(shù)值最大的一個(gè)為新的下界。（4）比較與剪枝：將各分枝問(wèn)題的最優(yōu)值同比較，如果其值小于，則這個(gè)分枝可以剪掉，以后不再考慮。如果其值大于，且又不是原問(wèn)題（11.1）的可行解，則繼續(xù)分枝，返回（3），直到

6、最后得到最優(yōu)解使，即為原問(wèn)題（11.1）的最優(yōu)解。11.3 整數(shù)規(guī)劃的割平面法11.3.1 割平面法的基本思想首先把原整數(shù)規(guī)劃問(wèn)題（11.1）去掉整數(shù)約束條件變?yōu)榫€性規(guī)劃問(wèn)題（A），然后引入線性約束條件（稱(chēng)為Gomory約束，幾何術(shù)語(yǔ)割平面）使問(wèn)題（A）的可行域逐步縮?。辞懈畹粢徊糠郑看吻懈畹舻氖菃?wèn)題的非整數(shù)解的一部分，不切掉任何整數(shù)解，直到最后使得目標(biāo)函數(shù)達(dá)到最優(yōu)的整數(shù)解（點(diǎn)）成為可行域的一個(gè)頂點(diǎn)為止，這就是原問(wèn)題（11.1）的最優(yōu)解。即利用線性規(guī)劃的求解方法逐步縮小可行域，最后找到整數(shù)規(guī)劃的最優(yōu)解。例11.2 用割平面法求解下列整數(shù)規(guī)劃問(wèn)題 將其化為標(biāo)準(zhǔn)型（A） 去掉整數(shù)約束條件，用

7、單純形法求解相應(yīng)的線性規(guī)劃問(wèn)題，可得非整數(shù)的最優(yōu)解為，由變量之間的關(guān)系可以得到關(guān)系式 將整數(shù)與真分式分開(kāi)有 因?yàn)?，且為整?shù)，即左端為整數(shù)，右端也必為整數(shù)，所以，即為所求的切割方程。將其加到問(wèn)題的約束條件之中，構(gòu)成新的問(wèn)題（B），求解引入松弛變量，則有，即求問(wèn)題 （B） 用單純形法求解，則可得到問(wèn)題（B）的最優(yōu)解為，顯然是原問(wèn)題的可行解，即為所求的最優(yōu)解，其最優(yōu)值為。11.3.2 割平面法的計(jì)算步驟設(shè)原問(wèn)題（11.1）中有個(gè)決策變量，個(gè)松弛變量，共個(gè)變量，略去整數(shù)約束求解線性規(guī)劃問(wèn)題，將最終的求解結(jié)果放入如表11-1（稱(chēng)為單純形表）。其中表示基變量，表示非基變量，則具體計(jì)算步驟如下：(1) 在最

8、優(yōu)解中任取一個(gè)具有分?jǐn)?shù)值的基變量，不妨就是，由表11-1可以得到關(guān)系，即 （11.2） 表11-1：?jiǎn)渭冃伪砘鵥-z（2）將和（為假分?jǐn)?shù)）分為整數(shù)部分和非負(fù)的真分?jǐn)?shù)，即其中和表示整數(shù)，而和表示真分?jǐn)?shù)，代入（11.2）式，并將整數(shù)放在一邊，分?jǐn)?shù)放在一邊，即 （11.3）（3）要使和都有為整數(shù)，（11.3）式的左端必為整數(shù) ，右端也是整數(shù)，而且由是非負(fù)整數(shù)，故此，又因是真分?jǐn)?shù)，于是有 ，則必有 （11.4）這就是所要求的一個(gè)切割方程（Gomory約束條件）。（4）對(duì)（11.4）式引入一個(gè)松弛變量，則（11.4）式變?yōu)?將其代入原問(wèn)題中去，求解新的線性規(guī)劃問(wèn)題。（5）應(yīng)用對(duì)偶單純形法求解，如果所求解

9、為原問(wèn)題的可行解（均為整數(shù)解），則就是原問(wèn)題的最優(yōu)解，計(jì)算結(jié)束。否則繼續(xù)構(gòu)造Gomory約束條件，直到最優(yōu)解為整數(shù)解為止。說(shuō)明：在這里為什么要用對(duì)偶單純形法求解呢？主要是在Gomory方程中，當(dāng)非基變量時(shí)，條件變?yōu)闉樨?fù)數(shù)，變?yōu)椴豢尚校ǔ５膯渭冃畏o(wú)法求解，而用對(duì)偶單純形法從不可行到可行，即可得到最優(yōu)解。11.4 01整數(shù)規(guī)劃11.4.1 01規(guī)劃的模型如果整數(shù)線性規(guī)劃問(wèn)題的所有決策變量?jī)H限于取0或1兩個(gè)數(shù)值，則稱(chēng)此問(wèn)題為01線性整數(shù)規(guī)劃，簡(jiǎn)稱(chēng)為01規(guī)劃。變量稱(chēng)為01變量，或二進(jìn)制變量，其變量取值的約束可變?yōu)榛?，等價(jià)于和，且為整數(shù)，于是01規(guī)劃的一般模型為 例11.3 背包問(wèn)題（或載貨問(wèn)題）

10、 一個(gè)旅行者要在背包里裝一些最有用的東西，但限制最多只能帶b kg物品，每件物品只能是整件攜帶，對(duì)每件物品都規(guī)定了一定的“使用價(jià)值”（有用的程度）。如果共有n件物品，第j件物品重，其價(jià)值為，問(wèn)題是：在攜帶的物品總重量不超過(guò)b kg的條件下，攜帶哪些物品可使總價(jià)值最大？ 設(shè)決策變量，則問(wèn)題的模型為 例11.4 指派（或分配）問(wèn)題182在生產(chǎn)管理上，為了完成某項(xiàng)任務(wù)，總是希望把有關(guān)人員最合理地分派，以發(fā)揮其最大工作效率，創(chuàng)造最大的價(jià)值。例如：設(shè)某單位有4個(gè)人，每個(gè)人都有能力去完成4項(xiàng)科研任務(wù)中的任一項(xiàng)，由于4個(gè)人的能力和經(jīng)驗(yàn)不同，所需完成各項(xiàng)任務(wù)的時(shí)間如表11-2所示。問(wèn)分配何人去完成何項(xiàng)任務(wù)使完

11、成所有任務(wù)的總時(shí)間最少？設(shè)決策變量表示第個(gè)人去完成第項(xiàng)任務(wù)，即表11-2 項(xiàng)目 人員ABCD甲乙丙丁2109715414813141611415139每個(gè)人去完成一項(xiàng)任務(wù)的約束為 每一項(xiàng)任務(wù)必有一人去完成的約束為 完成任務(wù)的總時(shí)間，即目標(biāo)函數(shù)為 記系數(shù)矩陣為，稱(chēng)為效益矩陣，或價(jià)值矩陣，表示第個(gè)人去完成第項(xiàng)任務(wù)時(shí)有關(guān)的效益（時(shí)間、費(fèi)用、價(jià)值等）。故該問(wèn)題的數(shù)學(xué)模型為 一般的指派（或分配）問(wèn)題：設(shè)某單位有n項(xiàng)任務(wù)，正好需要n個(gè)人去完成，由于任務(wù)的性質(zhì)和各人的專(zhuān)長(zhǎng)不同，如果分配每個(gè)人僅能完成一項(xiàng)任務(wù)，應(yīng)如何分派使完成n項(xiàng)任務(wù)的總效益（或效率）最高。設(shè)該指派問(wèn)題有相應(yīng)的效益矩陣，其元素表示分配第個(gè)人去

12、完成第項(xiàng)任務(wù)時(shí)的效益（），或者說(shuō)：以表示給定的第單位資源分配用于第項(xiàng)活動(dòng)時(shí)的有關(guān)效益。設(shè)問(wèn)題的決策變量為是01變量，即 其數(shù)學(xué)模型為 （11.5）11.4.2 01規(guī)劃的隱枚舉法 顯枚舉法（又稱(chēng)為窮舉法）：主要是把問(wèn)題的所有可能的組合情況（共種）列舉出來(lái)進(jìn)行比較，找到所需要的最優(yōu)解。隱枚舉法：主要是從實(shí)際出發(fā)，從問(wèn)題所有可能的組合取值中利用“過(guò)濾條件”排除一些不可能是最優(yōu)解的情況，只需考查其中一部分組合就可得到問(wèn)題的最優(yōu)解。因此，隱枚舉法又稱(chēng)為部分枚舉法。隱枚舉法不需要更多的理論和知識(shí)，當(dāng)問(wèn)題的維數(shù)不是特別大時(shí)，求解01是一種有效的方法，但對(duì)于過(guò)濾條件的確定，要根據(jù)實(shí)際問(wèn)題的具體情況具體分析而

13、定。11.5 指派問(wèn)題的匈牙利方法“匈牙利方法”最早是由匈牙利數(shù)學(xué)家康尼格（D. Konig）用來(lái)求矩陣中0元素的個(gè)數(shù)的一種方法，由此他證明了“矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少直線數(shù)”。1955年由庫(kù)恩（W.W. Kuhn）在求解著名的指派問(wèn)題時(shí)，引用了這一結(jié)論，并對(duì)具體算法做了改進(jìn)，仍然稱(chēng)為“匈牙利方法”。11.5.1 匈牙利方法的基本思想 由于每個(gè)問(wèn)題都有一個(gè)相應(yīng)的效益矩陣，可以通過(guò)初等變換修改效益矩陣的行或列的元素，使得在每一行或每一列中至少有一個(gè)零元素，直到在不同行、不同列中至少有一個(gè)零元素，從而得到與這些零元素相對(duì)應(yīng)的一個(gè)完全分配方案，這個(gè)方案是原問(wèn)題的一個(gè)最優(yōu)分

14、配方案。 定理11.1（指派問(wèn)題的最優(yōu)性） 如果問(wèn)題（11.5）的效益矩陣的第行、第列中的每個(gè)元素分別減去一個(gè)常數(shù)a 、b變?yōu)榫仃?，則以新的矩陣為效益矩陣和新的目標(biāo)函數(shù)與原效益矩陣和原目標(biāo)函數(shù)求得的最優(yōu)解相同，最優(yōu)值只差一個(gè)常數(shù)。 證明 只要證明新目標(biāo)函數(shù)和原目標(biāo)函數(shù)值相差一個(gè)常數(shù)。 事實(shí)上：因?yàn)?，則新的目標(biāo)函數(shù)為 故二者相差一個(gè)常數(shù)a+b，最優(yōu)解相同。11.5.2 匈牙利方法的基本步驟根據(jù)指派問(wèn)題的最優(yōu)性，“若從效益矩陣的一行（一列）各元素分別減去該行（列）的最小元素，得到新矩陣，那么以為效益矩陣所對(duì)應(yīng)問(wèn)題的最優(yōu)解與原問(wèn)題的最優(yōu)解相同”。此時(shí)求最優(yōu)解的問(wèn)題可轉(zhuǎn)化為求效益矩陣的最大1元素組的問(wèn)

15、題。下面給出一般的匈牙利方法的計(jì)算步驟：第1步：對(duì)效益矩陣進(jìn)行變換，使每行每列都出現(xiàn)有0元素。（1）從效益矩陣中每一行減去該行的最小元素；（2）再在所得矩陣中每一列減去該列的最小元素，所得矩陣記為。第2步：將矩陣中0元素置為1元素，非零元置為0元素，記此矩陣為。第3步：確定獨(dú)立1元素組。（1）在矩陣含有1元素的各行中選擇1元素最少的行，比較該行中各1元素所在的列中1元素的個(gè)數(shù)，選擇1元素的個(gè)數(shù)最少的一列的那個(gè)1元素；（2）將所選的1元素所在的行和列清0；（3）重復(fù)第2步和第3步，直到?jīng)]有1元素為止.，即得到一個(gè)獨(dú)立1元素組。第4步：判斷是否為最大獨(dú)立1元素組（1）如果所得獨(dú)立1元素組是原效益矩

16、陣的最大獨(dú)立1元素組（即1元素的個(gè)數(shù)等于矩陣的階數(shù)），則已得到最優(yōu)解，停止計(jì)算。（2）如果所得獨(dú)立1元素組還不是原效益矩陣的最大獨(dú)立1元素組，那么利用尋找可擴(kuò)路的方法對(duì)其進(jìn)行擴(kuò)張，進(jìn)行下一步。第5步：利用尋找可擴(kuò)路方法確定最大獨(dú)立1元素組。（1）做最少的直線覆蓋矩陣的所有0元素；（2）在沒(méi)有被直線覆蓋的部分找出最小元素，在被直線覆蓋的各行減去此最小元素，在被直線覆蓋的各列加上此最小元素，得到一個(gè)新的矩陣，返回第2步。說(shuō)明：上面的算法是按最小化問(wèn)題給出的，如果問(wèn)題是最大化問(wèn)題，即模型（11.5）中的目標(biāo)函數(shù)換為。此令和，則效率矩陣變?yōu)?。于是考慮目標(biāo)函數(shù)為的問(wèn)題，仍用上面的方法步驟求解所得最小解也

17、就是對(duì)應(yīng)原問(wèn)題的最大解。另外，按照匈牙利方法計(jì)算步驟，對(duì)于這一類(lèi)問(wèn)題的求解，我們可以用編程實(shí)現(xiàn)。11.6 玫瑰有約問(wèn)題11.6.1 問(wèn)題的提出目前，在許多城市大齡青年的婚姻問(wèn)題已引起了婦聯(lián)、工會(huì)和社會(huì)團(tuán)體組織的關(guān)注。某單位現(xiàn)有20對(duì)大齡青年男女，每個(gè)人的基本條件都不相同，如外貌、性格、氣質(zhì)、事業(yè)、財(cái)富等。每項(xiàng)條件通?？梢苑譃槲鍌€(gè)等級(jí)A、B、C、D、E，如外貌、性格、氣質(zhì)、事業(yè)可分為很好、好、較好、一般、差；財(cái)富可分為很多、多、較多、一般、少。每個(gè)人的擇偶條件也不盡相同，即對(duì)每項(xiàng)基本條件的要求是不同的。該單位擬根據(jù)他(她)們的年齡、基本條件和要求條件進(jìn)行牽線搭橋。下面給出20對(duì)大齡青年男女的年齡

18、、五項(xiàng)基本條件和要求條件(如表11-3和表11-4)。一般認(rèn)為，男青年至多比女青年大5歲，或女青年至多比男青年大2歲，并且要至少滿足個(gè)人要求5項(xiàng)條件中的2項(xiàng)，才有可能配對(duì)成功。該單位希望根據(jù)每個(gè)人的情況和要求，建立數(shù)學(xué)模型解決下列問(wèn)題：(1) 在盡量滿足個(gè)人要求的條件下，給出一種最佳的配對(duì)方案，并使得配對(duì)成功率盡可能的高。(2) 給出一種20對(duì)男女青年可同時(shí)配對(duì)的最佳方案，使得全部配對(duì)成功的可能性最大。11.6.2 問(wèn)題的分析該問(wèn)題是現(xiàn)實(shí)生活中實(shí)際問(wèn)題，主要就是確定合理配對(duì)方案，使得在盡量滿足個(gè)人要求的條件下，使配對(duì)成功率盡可能高。由于每個(gè)人的基本條件和要求都是給定的，雙方彼此是知道的，而且相

19、互之間有很大的差異，如果完全按照要求條件來(lái)組合配對(duì)，則其成功的可能性是很小的。一對(duì)青年男女能否配對(duì)成功，主要是取決于相互之間的好感的程度“滿意度”，單方面的高滿意度也不一定能配對(duì)成功。任意一對(duì)男女的配對(duì)可以看成一個(gè)隨機(jī)事件，按某一概率可能配對(duì)成功，或不成功。在這里雙方的滿意度主要反映出了一個(gè)人對(duì)另一個(gè)人的客觀和主觀的看法，因此，滿意度的定義成為解決問(wèn)題的一個(gè)關(guān)鍵。所謂的“成功率”，就是男女雙方最終配對(duì)成功的概率。實(shí)際上，可以用他們相互之間的滿意度來(lái)間接刻畫(huà)。相互的滿意度越高，雙方配對(duì)成功的概率就越大。對(duì)題目進(jìn)行分析不難看出，這是一個(gè)分派問(wèn)題，但由于每個(gè)人的要求條件和配對(duì)所要求的最低條件的限制，

20、這又不是一個(gè)標(biāo)準(zhǔn)的分派問(wèn)題，因?yàn)椴荒鼙ＷC每個(gè)人都能配對(duì)成功。對(duì)問(wèn)題（1），要使配對(duì)成功率盡可能的高，也就是給出一種方案，使得20對(duì)男女的配對(duì)后的滿意度之和最高。為此，該問(wèn)題可以用改進(jìn)的匈牙利算法求解。表11-3: 男青年的基本條件和要求條件男青年基 本 條 件要 求 條 件外貌性格氣質(zhì)事業(yè)財(cái)富年齡外貌性格氣質(zhì)事業(yè)財(cái)富ACBCA29AACBDCABAD29BABBCBBABB28BAABCCABBD28CABCDDBCAA30CBBBECBCBB28BBCDCABBDC30CBBDCBABCD30ABCCDADCEB28AAACCDBAAA28ABADEBACDA32ABCDBABCAB29BA

21、BBCBADEC28ACBBCAABBD30ACCDCABBCC28AABCDDEBAA30AAAEEBABAD28BABBCABACB31BBACCCDAAA29ABAEDABCDE27BCBDB表11-4: 女青年的基本條件和要求條件女青年基 本 條 件要 求 條 件外貌性格氣質(zhì)事業(yè)財(cái)富年齡外貌性格氣質(zhì)事業(yè)財(cái)富ACCDA28BABADBABAD25CBBABCBAEA26BACBCABBCD27AABBABDCEC25ABCBBACBCA26BABBCDCBAB30CBAACABAEC31BABABAAACE26CBBBABCDBB27BBAACABBCB28CBABCBECEA26AAB

22、BEEACBB26CABCCBBCAA25BAABDCBAAC29BABBBBACDC28BABBAAEEDA25AADACAABBC28CABACBACCE25BBBAADBACD29BBABB注：表中的要求的條件一般是指不低于所給的條件。11.6.3 模型的假設(shè)與符號(hào)說(shuō)明(1) 模型假設(shè)l 題目所給出的男女青年的評(píng)價(jià)是客觀真實(shí)的；l 每個(gè)人在選擇對(duì)方時(shí)都是理智的；l 五項(xiàng)條件在選擇對(duì)方時(shí)所起的作用是均等的。(2) 符號(hào)約定第個(gè)男青年；第個(gè)女青年；第個(gè)男青年與第個(gè)女青年配對(duì)時(shí)取值1，否則取值0；第個(gè)女青年的第項(xiàng)基本條件的量化指標(biāo)；第個(gè)男青年的第項(xiàng)基本條件的量化指標(biāo)；第個(gè)女青年的第項(xiàng)要求條件的

23、量化指標(biāo)；第個(gè)男青年的第項(xiàng)要求條件的量化指標(biāo)；第個(gè)女青年對(duì)第個(gè)男青年的第項(xiàng)條件的滿意度；第個(gè)男青年對(duì)第個(gè)女青年的第項(xiàng)條件的滿意度；第個(gè)女青年對(duì)第個(gè)男青年的各項(xiàng)條件的綜合滿意度；第個(gè)男青年對(duì)第個(gè)女青年的各項(xiàng)條件的綜合滿意度；第個(gè)男青年與第個(gè)女青年的綜合相互滿意度；第個(gè)男青年與第個(gè)女青年配對(duì)成功的概率；所給方案的使配對(duì)成功的總概率；所有男青年對(duì)女青年的滿意度矩陣；所有女青年對(duì)男青年的滿意度矩陣；男（女）方的要求條件等級(jí)距離最高等級(jí)A的檔數(shù)；男（女）方的基本條件等級(jí)高出對(duì)方所要求條件等級(jí)的檔數(shù)。其中 。11.6.4 模型的準(zhǔn)備1. 條件的量化處理對(duì)于每個(gè)人的外貌、性格、氣質(zhì)、事業(yè)和財(cái)富五項(xiàng)條件的5個(gè)

24、等級(jí)A、B、C、D和E分別作量化處理，根據(jù)層次分析中關(guān)于條件等級(jí)差的度量標(biāo)準(zhǔn)，對(duì)A、B、C、D、E 分別賦權(quán)為9、7、5、3、1。于是根據(jù)表11-3和表11-4可以得到男女青年的基本條件量化矩陣和要求條件量化矩陣（或稱(chēng)權(quán)值矩陣）分別為 （11.6）2. 條件過(guò)濾由于問(wèn)題是明確要求“男青年的年齡至多比女青年大5歲，而女青年的年齡至多比男青年大2歲”，以及“至少滿足個(gè)人要求5項(xiàng)條件中的2項(xiàng)”。在20對(duì)男女青年中所有可能的配對(duì)中首先應(yīng)將不滿足這些基本條件的情況過(guò)濾掉。由（11.6）式用Matlab編程進(jìn)行過(guò)濾可以過(guò)濾掉58對(duì)組合。3. 滿意度的確定(1) 對(duì)單項(xiàng)條件的滿意度要確定對(duì)的第項(xiàng)條件的滿意度

25、。首先要注意到兩個(gè)事實(shí)：其一，如果的基本條件比的要求條件差的越多，則對(duì)的第項(xiàng)條件的滿意度就越小，反之亦然。也就是說(shuō)，如果一方的實(shí)際條件比對(duì)方期望（要求）的條件差距越大，則對(duì)方對(duì)另一方失望就越大，即滿意度就越小。其二，如果的基本條件比的要求條件高，則對(duì)的第項(xiàng)條件的滿意度就會(huì)增加，但增加不會(huì)太多。即當(dāng)一方的實(shí)際條件高于對(duì)方期望（要求）的條件時(shí)，則對(duì)方對(duì)另一方的好感（相對(duì)要求條件）增加不會(huì)太大。 根據(jù)上面的兩個(gè)事實(shí)，先以女青年對(duì)男青年的第項(xiàng)條件的滿意度為例。若的實(shí)際條件比的要求差，那么對(duì)該項(xiàng)指標(biāo)的滿意度將迅速減小，減小的速度一般會(huì)與的要求條件相差的檔數(shù)有關(guān)，二者會(huì)成一定的比例關(guān)系。當(dāng)?shù)膶?shí)際條件比的要求條件差得很大（例如，三個(gè)檔次以上）時(shí)，則認(rèn)為對(duì) “失去信心”，即滿意度為0。若的實(shí)際條件比的要求條件還要好，那么 對(duì) 的這項(xiàng)條件的滿意度會(huì)略有提升，但提升的不會(huì)太大。根據(jù)實(shí)際情況，一般認(rèn)為如果男青年的條件達(dá)到女青年的要求條件時(shí)，那么，會(huì)以90%的可能接受，此時(shí)即可以認(rèn)為對(duì)的第項(xiàng)條件的滿意度=0.9。 下面首先給出對(duì)的第項(xiàng)條件的滿意度的定義： （11.7）如果的第項(xiàng)條件的要求為C ，則根據(jù)的第項(xiàng)條件的不同情況，對(duì)的第項(xiàng)條件的滿意度的取值如圖11-1所示。同理定義對(duì)的第項(xiàng)條件的滿意度如下： （11.8） 10.9 E D C B A 圖11-1