【文章內(nèi)容簡介】 對花色 ， 甲付給乙小石子三個；猜不對 ， 乙付給甲一個石子 ， 試求游戲的解 。 解 據(jù)題意 ， 該游戲可歸結(jié)為矩陣模型 G={S甲 ,S乙 ,A}，其中甲小孩的贏得 ?????????????????3111131111311113A矩陣30 顯然該對策無鞍點 ， 為簡化計算 ， 對 A中各元素減 1， 得 ??????????????????4000040000400004A于是有 014141414111 ????????? ?GV , 且 ? = 1 ， X * =Y * = ( 1/ 4, 1/ 4, 1/ 4, 1/ 4) 。 即甲、乙兩小孩應(yīng)以 1/4的概率出（或猜）各種花色的牌，互不吃虧。 5. 設(shè) A 為 n 階矩陣。 若 ????????njijniij nibanjba11), . . . ,2,1(),. . . ,2,1( , 則 X * =Y * = ( 1/n,1 /n,1/n ,1/n) ，且 V G = b/n 。 31 “齊王賽馬”的羸得矩陣滿足上述條件，故由此可得 X*=Y*=(1/6,1/6,1/6,1/6)， 且 VG=6/6=1。 對于矩陣對策 ， 該選用哪種方法進行求解 ？ 一般可按以下順序進行考慮： 1176。 首先 ， 用最大最小原則試求鞍點 。 若無 ， 則考慮以下方法； 2176。 若 A為特殊矩陣 ， 則可選用上述 4,5給出的結(jié)論 ， 直接求解； 3176。 對 3 3階以上的贏得矩陣 A， 試用優(yōu)超法將 A降階 4176。 對 2 n對策 ， 可轉(zhuǎn)化為 Cn2個 2 2對策 ， 分別用公式法求解 ， 并從中求出原對策的解； 5176。 以上方法均不可行時 ， 則可用 LP法或迭代法求解 。 32 167。 兩人有限非零和對策 在許多對策問題中，對策雙方的得失之和并不等于零，即局中人一方的得并不等于另一方得失，這就是兩人有限非零和對策。如兩家企業(yè)競爭某種商品的市場占有率，當(dāng)他們采取某些策略時，有可能產(chǎn)生雙贏的結(jié)果。 一、兩人有限非零和對策的數(shù)學(xué)模型 例 18 甲、乙兩家面包店在市場競爭中，各自都在考慮是否要降價，如果兩家都降價，則各家可得 3百元的利潤，如果都不降價，則各家可得利潤 5百元，如果一家降價，另一家不降，則降價的一家可得利潤 6百元，不降價的一家由于剩余損壞等原因而虧損 4百元，問雙方應(yīng)如何選擇行動較為合理？ 33 甲面包店 乙面包店 ?1（降價） ?2（不降價） ?1 （降價） （ 3， 3） （ 6，－ 4） ?2 （不降價） （－ 4， 6） （ 5， 5） 依題意，把上述問題表述成如下表格： 這個問題的數(shù)學(xué)模型可表示為： 的贏得矩陣。為局中人的贏得矩陣為局中人其中25643B,15463A},{},{)}B,A(。,{21221121SSSS?????? ?????????????? ????一般地 ， 兩人有限零和對策的數(shù)學(xué)模型可表示為 為其贏得矩陣。的純策略集，為局中人＝的贏得矩陣；為局中人的純策略集，為局中人其中B2},{1A1},{)} ,B,A(。,{n212m21121SSSS???????????34 隨著 A,B的確定，兩人有限非零和對策也就確定，因此兩人有限非零和對策又稱為雙矩陣對策。特別，當(dāng) A=B時，雙矩陣對策就是矩陣對策。 在上述這個競爭對策中，兩家面包店在沒有互通信息非合作情況下，各自都有兩種策略的選擇，降價或不降價。顯然，雙方最好策略的選擇都是降價，即（ ?1， ?1）。 因為選擇降價至少可以得到 3百元的利潤，如果選擇不降價，則可能由于對方降價而蒙受 4百元的損失。當(dāng)然，在兩店互通信息，進行合作的情況下，雙方采取不降價的策略，各自都能得到 5百元的利潤。 例 19 設(shè)想一個壟斷企業(yè)已占領(lǐng)市場（稱為在位者），另一個企業(yè)很想進入市場（稱為進入者）。在位者想保持其壟斷地位，就要阻繞進入者進入。假定進入者進入之前在位者的壟斷利潤為 300，進入后兩者的利潤合為 100（各得 50），進入成本為 10。試分析兩者的最佳策略。 35 根據(jù)題意，可得如下表格： 在位者 進入者 ?1（默許） ?2（斗爭） ?1（進入） （ 40， 50） （－ 10， 0） ?2(不進入） （ 0， 300） （ 0， 300） 對于這個對策問題，經(jīng)過分析容易得到（ ?1， ?1）（進入，默許）和 （ ?2， ?2）（不進入，斗爭）是雙方選擇的最好的局勢。 二、非合作兩人對策的解法 在這里所討論的兩人有限非零和對策中，假定對策雙方都了解對方的純策略集和贏得函數(shù)，但不合作，并且局中人在選擇自己的策略時不知道對方的選擇。 （ 1）非合作兩人對策的解 —— 納什均衡 一般地，對于非合作兩人對策 ?＝ {S1,S2。(A,B)},如果?i*?S1, ?j*?S2分別是局中人 1和 2的最優(yōu)純策略，則稱局勢 (?i*, ?j*)是一個納什均衡 . 36 求非合作兩人對策的納什均衡解的步驟如下： 在雙矩陣對策（ A,B)表中，對于矩陣 A的每列，分別找出贏得最大的數(shù)字，并在其下劃一橫線； 在雙矩陣對策（ A,B)表中，對于矩陣 B的每行，分別找出贏得最大的數(shù)字，并在其下劃一橫線； 如果表中某格的數(shù)字下面都被劃上橫線，則此格對應(yīng)于兩個局中人相應(yīng)策略的組合就是一個（純策略下的）納什均衡。否則，該對策不存在純策略下的納什均衡。 例如： 甲面包店 乙面包店 ?1（降價） ?2（不降價） ?1 （降價） （ 3， 3） （ 6，－ 4） ?2 （不降價） （－ 4， 6） （ 5， 5） 在位者 進入者 ?1（默許） ?2（斗爭） ?1（進入） （ 40， 50） （－ 10， 0） ?2(不進入） （ 0， 300） （ 0， 300） 37 （ 2）混合策略納什均衡 上面所介紹的非合作兩人有限對策是在純策略下有解的對策問題，其特點是納什均衡中的策略是每一個局中人的一個完整策略。但是有些對策并不存在純策略下的納什均衡，如下例： 例 20 局中人是政府和一個流浪漢，流浪漢有兩個策略：尋找工作或游蕩；政府也有兩個策略：救濟或不救濟。政府幫助流浪漢的前提是后者必須試圖尋找工作；否則，前者不予幫助；而流浪漢只有在得不到救濟時才會尋找工作。下表給出了對策的贏得雙矩陣： 流浪漢 政府 ?1（尋找工作） ?2（游蕩） ?1 （救濟） （ 3， 2） （－ 1， 3） ?2 （不救濟） （－ 1， 1） （ 0， 0） 因此，在這個對策問題中，沒有一個純局勢可以構(gòu)成純策略下的納什均衡。為求得納什均衡，必須對矩陣加以擴充 38 設(shè) A,B分別為局中人 1和 2的贏得矩陣，且皆為 m?n矩陣，局中人 1， 2的混合策略集為： }1,0|x{ m1iii*1 xxs ??? ??}1,0|Y{ n1i ii*2 yys ??? ??如果一個混合策略組合（ X*,Y*） 同時滿足 YXYXYXY T**T*T**T* BB,AXA ??則稱策略組合 —— 局勢（ X*,Y*） 是一個混合策略納什均衡。 39 對于上述例題，假定政府以概率 x選擇救濟，以概率 1x選擇不救濟，即政府的混合策略為 (x,1x)， 流浪漢以概率 y選擇尋找工作，以概率 1y選擇游蕩，即流浪漢的混合策略為 (y,1y)。 那么政府的期望贏得函數(shù)為： yxxy5y1y0113)x1,x(XA)Y,X( YE TA???????????????????????用微分求極值的方法： 51,1y5x yE *A ????? 得這就是說，在混合策略中，流浪漢在對付給定政府的混合策略下，最優(yōu)策略是以 1/5的概率選擇尋找工作， 4/5的概率選擇游蕩，即 Y*=(1/5,4/5) 40 同樣流浪漢的期望贏得函數(shù)為： yx3xy2y1y0132)x1,x(XB)Y,X( YE TB??????????????????????用微分極值法求： 21,01x2y xE *B ??????? 得即在混合策略均衡中，政府在對付給定流浪漢的混合策略下，最優(yōu)策略是 X*=(1/2,1/2)。 由于納什均衡要求每個局中人的混合策略是在給定對方的混合策略下的最優(yōu)選擇，因此，由 x*=(1/2,1/2)和Y*=(1/5,4/5)構(gòu)成的 (x*,Y*)是唯一的納什均衡。且此時贏得函數(shù)值為： EA(X,Y)=1/5, EB(X,Y)=3/2 41 第六章 圖與網(wǎng)絡(luò)分析 (graph and work analysis) 一、圖與網(wǎng)絡(luò)分析的實例 例 1. 哥尼斯堡七橋問題 18世紀(jì)的哥尼斯堡城中有一條普雷格爾河 ,河的兩岸和河中的兩個小島有 7座橋彼此相接 ,當(dāng)?shù)氐木用駸嶂杂谟懻撨@樣一個話題 :一個步行者能否通過每座橋一次且僅一次回到原出發(fā)地 . C島 B島 A D B A C D 化為如上的簡圖,1736年數(shù)學(xué)家歐拉證明了這個問題是不可能的 42 例 2 公路連接問題 某一地區(qū)有若干個主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來， 使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市 . 假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？ 例 3 旅行商問題 /貨郎 （ 擔(dān) ） 問題 (TSPTraveling Salesman Problem) 一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品 . 如何為他 (她 )設(shè)計一條最短的旅行路線 (從駐地出發(fā) ， 經(jīng)過每個城市恰好一次 ， 最后返回駐地 )？ 這一問題的研究歷史十分悠久 ，通常稱之為旅行商問題 . 43 例 4 穩(wěn)定婚配問題 (Stable Marriage Problem) 假設(shè)有 n個男人和 n個女人 , 每人都希望從 n個異性中選擇一位自己的配偶 . 假設(shè)每人都對 n個異性根據(jù)自己的偏好進行了排序 , 以此作為選擇配偶的基礎(chǔ) . 當(dāng)給定一種婚配方案 (即給每人指定一個配偶 )后 , 如果存在一個男人和一個女人不是互為配偶 , 但該男人喜歡該女人勝過其配偶 , 且該女人喜歡該男人也勝過其配偶 , 則該婚配方案稱為不穩(wěn)定的 . 安排穩(wěn)定的婚配方案的問題稱為 穩(wěn)定婚配問題 。 44 二 .圖與網(wǎng)絡(luò)分析基本內(nèi)容框架 網(wǎng)絡(luò)工程優(yōu)化 關(guān)鍵路線法 CPM 計劃評審法 PERT 45 167。 1. 圖與網(wǎng)絡(luò)的基本概念 一、圖及其分類 本章研究的圖與平面幾何中的圖不同 ， 我們只關(guān)心圖中有多少個點 ， 點與點之間有無線連接 ， 至于連線的方式是直線還是曲線 ， 點與點的相對位置如何 ， 都是無關(guān)緊要的 。 下面介紹有關(guān)圖的基本概念 。 ， 圖是點和線所組成的圖形 ， 即圖是一個有序二元組( V,E)， 記為 G=(V,E)， 其中 V={v1,v2,… vp}是 p個點的集合 ，E={e1,e2,… eq}是 q條邊的集合 。 V中的元素 vi稱為頂點 ， E中的元素 ek稱為邊 。 如圖 1所示：其中 圖 1 v4 v3 v1 v2 e1 e2 e3 e4 e5 e6 V={v1,v2,v3,v4},E={e1,e2,e3,e4,e5,e6} e1={v1,v1},e2={v1,v2},e3={v2,v3} e4={v2,v3},e5={v3,v4},e6={v1,v3} 46 對于邊 (vi,vj)， 則稱 vi,vj兩點相鄰 ， 也稱 vi,vj為邊 (vi,vj)的端點 。 若兩條邊有一個公共端點 u， 則稱這兩邊是相鄰的 ， 也稱這兩邊為點 u的關(guān)聯(lián)邊 。 若兩端之間多于一條邊的 ， 稱為多重邊 。 如圖 1中的 ee4。