運(yùn)籌學(xué)教學(xué)-對(duì)策論市公開課一等獎(jiǎng)省名師優(yōu)質(zhì)課賽課一等獎(jiǎng)?wù)n件

運(yùn)籌帷幄之中決勝千里之外運(yùn)籌學(xué)課件對(duì)策論GameTheory第1頁

第一節(jié)對(duì)策論基本概念和分類發(fā)展簡(jiǎn)史19E.Zermelo“關(guān)于集合論在象棋對(duì)策中應(yīng)用”19E.Borel引入最優(yōu)策略1928年J.V.Neumann證實(shí)了一些猜測(cè)博奕論(GameTheory)也就是運(yùn)籌學(xué)中對(duì)策論。對(duì)策思想最早產(chǎn)生于我國古代。早在兩千多年前春秋時(shí)期，孫武在《孫子兵法》中敘述軍事思想和治國策略，就蘊(yùn)育了豐富和深刻對(duì)策論思想。孫武后代孫臏，為田忌謀劃，巧勝齊王，這個(gè)著名“田忌賽馬”，就是經(jīng)典對(duì)策思想成功利用。產(chǎn)生標(biāo)志作為一門學(xué)科創(chuàng)建，則是以美國數(shù)學(xué)家馮.諾依曼(JohnVonNeumann)和經(jīng)濟(jì)學(xué)家奧斯卡.摩根斯坦(OskarMorgenstern)合著《博奕論與經(jīng)濟(jì)行為》(TheGameTheoryandEconomicBehavior)(1944)一書出版為標(biāo)志，他們奠定和形成了這門學(xué)科理論與方法論基礎(chǔ)。發(fā)展成熟Nash均衡、經(jīng)濟(jì)博奕論、信息不對(duì)稱對(duì)策和廣義對(duì)策基本概念在策略型博奕中，一個(gè)對(duì)策有以下幾個(gè)基本要素：一．局中人(players)：

即博奕參加者，他們是博奕決議主體。依據(jù)自己利益要求決定自己決議，記第i個(gè)局中人為i，局中人集合為{1,2,…,I}，即共有I個(gè)局中人。我們將某個(gè)局中人以外其它局中人稱為“i對(duì)手”，記為-i。對(duì)策中利益一致參加者只能看成一個(gè)局中人，例：橋牌中東、西兩方。

對(duì)策論中對(duì)局中人一個(gè)主要假設(shè)：每個(gè)局中人都是“理智”，即每一個(gè)局中人都不存在僥幸心理，不存在利用其它局中人決議失誤來擴(kuò)大本身利益行為。在策略型博奕中，一個(gè)對(duì)策有以下幾個(gè)基本要素：一．局中人

即指每個(gè)局中人在對(duì)策中能夠選擇采取行動(dòng)方案，但這個(gè)方案必須是一個(gè)完整行動(dòng)，而不是行動(dòng)某一步。每個(gè)局中人都有可供選擇各種策略。

二．策略(strategies)：

基本概念三．支付或收益(payoffs):二．策略一．局中人在策略型博奕中，一個(gè)對(duì)策有以下幾個(gè)基本要素：

是指一局博奕得失。或者說是局中人從各種策略組合中取得效用，它是策略組合函數(shù)。假如局中人得失總和為零，則稱這種對(duì)策為零和對(duì)策（博弈）；不然，稱為非零和對(duì)策(博奕)?；靖拍罹謩?shì)：一個(gè)對(duì)策中，每一個(gè)局中人所出策略形成策略組稱為一個(gè)局勢(shì)。

設(shè)si是第i個(gè)局中人一個(gè)策略，則n個(gè)局中人策略形成策略組s={s1,s2,…,sn},就是一個(gè)局勢(shì)。全部局勢(shì)集合S記為：模型局中人

兩個(gè)或兩個(gè)以上---決議者策略集合策略----決議

局勢(shì)----狀態(tài)支付函數(shù)

支付關(guān)于局勢(shì)函數(shù)----決議依據(jù)和標(biāo)準(zhǔn)模型分類局中人兩人對(duì)策、多人對(duì)策策略有限對(duì)策、無限對(duì)策；非合作對(duì)策、合作對(duì)策支付零和對(duì)策、非零和對(duì)策時(shí)間單階段對(duì)策、多階段對(duì)策對(duì)策模型眾多，但占有主要地位是二人有限零和對(duì)策（矩陣對(duì)策）。它是一類最簡(jiǎn)單對(duì)策模型，

它結(jié)果也是研究其它對(duì)策模型基礎(chǔ)。

第二節(jié)二人有限零和對(duì)策模型二人有限零和對(duì)策二人：參加對(duì)策局中人有兩個(gè)；有限：局中人策略集都為有限集；零和：在任一局勢(shì)下，兩個(gè)局中人贏得之和總等于0，即，一個(gè)局中人所得值恰好是另一個(gè)局中人所失值，雙方利益是完全反抗。設(shè)局中人I和II策略集分別為對(duì)任一純局勢(shì)，記局中人I贏得值為則I贏得矩陣為例：甲、乙各出示一枚硬幣，在不讓對(duì)方看見情況下，將硬幣放在桌子上，若兩個(gè)硬幣都呈正面或都呈反面則甲得1分，乙付出1分；若兩個(gè)硬幣一個(gè)呈正面另一個(gè)呈反面則乙得1分，甲付出1分局中人：甲、乙甲贏得矩陣為例（齊王與田忌賽馬）這個(gè)問題中齊王和田忌各自擁有策略為：S1={(上中下),(上下中),(中上下),(中下上),(下中上),(下上中)}S2={(上中下),(上下中),(中上下),(中下上),(下中上),(下上中)}則對(duì)應(yīng)齊王贏得矩陣為例：甲乙兩人玩猜拳游戲，游戲中雙方同時(shí)分別出石頭、布或剪刀。規(guī)則是剪刀贏布，布贏石頭，石頭贏剪刀，贏者得一分。若出相同，算和局都不得分。試列出甲贏得矩陣。石頭布剪刀石頭0-11布10-1剪刀-110第三節(jié)

矩陣對(duì)策純策略例：設(shè)有一矩陣對(duì)策其中解：對(duì)局中人I而言，最大贏得是9，若想得到這個(gè)贏得，他要選擇純策略，因?yàn)榫种腥薎I也是理智競(jìng)爭(zhēng)者，他已考慮到局中人I打算出心理，則準(zhǔn)備以對(duì)付之，使局中人I不但得不到9，反而失掉10.局中人I當(dāng)然也會(huì)猜到局中人II心理，故而出來對(duì)付，使局中人II得不到10，反而失掉6，……假如雙方都不想冒險(xiǎn)，都不存在僥幸心理，而是考慮到對(duì)方必定會(huì)設(shè)法使自己所得最少這一點(diǎn)，就應(yīng)該從各自可能出現(xiàn)最不利情形中選擇一個(gè)最有利情形作為決議依據(jù)，這就是所謂“理智行為”，也是對(duì)策雙方實(shí)際上能夠接收并采取一個(gè)穩(wěn)妥方法。對(duì)策雙方處于完全反抗環(huán)境中，所以，各自都采取保守態(tài)度，從最壞處著眼，并力爭(zhēng)很好結(jié)局。所以，局中人A采取maxmin準(zhǔn)則，局中人B采取minmax準(zhǔn)則。對(duì)應(yīng)于這種準(zhǔn)則下，對(duì)策雙方采取各自策略稱為對(duì)策解。雙方采取上述策略，連續(xù)重復(fù)進(jìn)行對(duì)策，其輸贏平均值稱為對(duì)應(yīng)對(duì)策問題對(duì)策值，記為v對(duì)策問題選擇解準(zhǔn)則b1b2…bna1c11c12…c1na2c21c22…c2n…amcm1cm2…cmn設(shè)局中人A策略有，局中人B策略有，A贏得矩陣為maxmin準(zhǔn)則:當(dāng)A依據(jù)此標(biāo)準(zhǔn)選擇策略時(shí)，總考慮不論選哪一個(gè)策略都將得到最壞結(jié)局。即minmax準(zhǔn)則:當(dāng)B依據(jù)此標(biāo)準(zhǔn)選擇策略時(shí)，總考慮不論選哪一個(gè)策略都將得到最壞結(jié)局（最大損失）。即均衡解按照這個(gè)定義，例中均衡解為繼續(xù)分析前例:此時(shí)平衡局勢(shì)，對(duì)應(yīng)值既是其所在行最小元素，又是其所在列最大元素，即有普通地，有以下定義和結(jié)論：證實(shí)：其次，對(duì)任意i,j，由由（1），（2）得必要性：設(shè)有i*,j*,使得則由有注以上定理對(duì)策意義為：一個(gè)平衡局勢(shì)應(yīng)該含有這么性質(zhì)：當(dāng)局中人A選擇了策略后，局中人B為了使其損失最小，只能選擇策略，不然就可能損失更多；反之，當(dāng)局中人B選擇了策略后，局中人A為了得到最大贏得也只能選擇策略不然就會(huì)贏得較少，雙方競(jìng)爭(zhēng)在局勢(shì)下到達(dá)了一個(gè)平衡狀態(tài)。例子例子例

求下面矩陣對(duì)策解解：計(jì)算此時(shí)，i*=1,3;j*=2,4所以，(a1,b2),(a1,b4),(a2,b2),(a2,b4)都是對(duì)策解。由以上例子知，對(duì)策均衡解不見得唯一，當(dāng)解不唯一時(shí)，解之間關(guān)系有以下性質(zhì)：性質(zhì)1（無差異性）若和是對(duì)策G兩個(gè)解，則性質(zhì)2（可交換性）若是對(duì)策G兩個(gè)解則也是對(duì)策解。

第三節(jié)優(yōu)勢(shì)標(biāo)準(zhǔn)和含有混和策略矩陣對(duì)策對(duì)一個(gè)矩陣對(duì)策由前面討論知，局中人I能確保最少贏得為局中人II能確保至多損失為所以，總有當(dāng)時(shí)，對(duì)策在純策略意義下有解當(dāng)時(shí)，對(duì)策在純策略意義下沒有解，此時(shí)情況如以下例中所述。例：以下是二人零和對(duì)策支付矩陣b1b2a114a232分析發(fā)覺：此時(shí)若還使用純策略，雙方按照從最不利情形中選擇最有利情形標(biāo)準(zhǔn)，應(yīng)分別選擇a2和b1,此時(shí)局中人I贏得是3，比最少贏得多了1，這是因?yàn)榫种腥薎I選擇了b1，才使得局中人I得到了不該得到贏得，顯然局中人會(huì)考慮出b2,讓局中人I贏得變?yōu)?，而此時(shí)局中人I又會(huì)選擇a1，使得自己贏得為4，…如此下去就會(huì)出現(xiàn)不穩(wěn)定狀態(tài)。處理此問題想法很自然，既然局中人都沒有最優(yōu)策略可出，可否給出一個(gè)選擇不一樣策略概率分布，以到達(dá)一個(gè)平衡狀態(tài)呢，這就是混合策略。定義：混和策略設(shè)有矩陣對(duì)策G={S1,S2;A},其中記則稱則稱為局中人A，B混和策略集，稱x,y為混和策略，（x,y）為混和局勢(shì)。局中人A贏得函數(shù)為：稱為對(duì)策G混和擴(kuò)充。定義：混和策略意義下解設(shè)假如則稱VG為對(duì)策G值，稱使得上式成立混和局勢(shì)是矩陣對(duì)策G={S1,S2;A}混和擴(kuò)充。（x*,y*）為G在混和策略意義下解（平衡局勢(shì)），稱x*,y*分別為局中人A和B最優(yōu)混和策略。注：當(dāng)局中人A選擇混和策略x時(shí)，他預(yù)期所得（按最?。┦撬跃种腥薃應(yīng)選取使得同理，B可確保損失期望值至多是顯然成立：和純策略類似，混合策略意義下一樣有解存在鞍點(diǎn)型充要條件：定理1:矩陣對(duì)策在混和策略下有解充要條件是：存在使得對(duì)任意有例：考慮矩陣對(duì)策解：易知G在純策略意義下無解，所以，設(shè)表示局中人I，II混合策略，則局中人I贏得期望是取則所以分別為局中人I，II最優(yōu)策略。若記則E(i,y)為局中人A取純策略ai時(shí)贏得值；E(x,j)為局中人B取純策略bj時(shí)贏得值,且有則得到一個(gè)和定理1等價(jià)定理2混合策略意義下求解方法相關(guān)理論定理2:則為對(duì)策G解充要條件為：對(duì)任意i=1,2,…,m;j=1,2,…,n,有證實(shí)：設(shè)為對(duì)策G解，則由定理1，成立因?yàn)榧儾呗允腔旌喜呗蕴乩?，所以，?）成立。反之，若（*）成立，則定理2說明：要驗(yàn)證為對(duì)策G解時(shí)，只需要對(duì)上式給出有限個(gè)（m×n）不等式進(jìn)行驗(yàn)證即可，大大簡(jiǎn)化了驗(yàn)證過程。如此，便有了下面等價(jià)定理－定理3定理2得證。定理3:則為：存在數(shù)v，使得為對(duì)策G解充要條件分別為不等式組(1),(2)解,且v=VG定理4:任一矩陣對(duì)策G，一定存在混和策略意義下解。證實(shí):由定理2知，只需證實(shí)存在使得（*）式成立。所以，考慮以下規(guī)劃問題易知，規(guī)劃問題（P）和（D）互為對(duì)偶問題，且分別為（P）和（D）一個(gè)可行解。由對(duì)偶定理知，他們都存在最優(yōu)解，且最優(yōu)目標(biāo)值相等。即，存在和使得對(duì)任意i=1,2,…,m;j=1,2,…,n有或又由得所以,(*)得證。定理5:設(shè)是矩陣對(duì)策G解，v=VG，則證實(shí):由有又因?yàn)樗?，?dāng)時(shí)，必有當(dāng)時(shí)，必有同理，可證（2），（4）。優(yōu)超（優(yōu)勢(shì)標(biāo)準(zhǔn)）算例簡(jiǎn)化簡(jiǎn)化第四節(jié)混和策略解法方法1：圖解法上例中，設(shè)A以概率x和1-x使用策略a1和a2對(duì)付B使用純策略b1時(shí)，A收入為對(duì)付B使用純策略b2時(shí)，A收入為按照maxmin標(biāo)準(zhǔn)混和策略意義下maxmin值為va=5/2，此時(shí)x=1/4為下列圖B點(diǎn)同理，若設(shè)局中人B以y和1-y概率分別使用策略b1,b2,可得到混和策略意義下minmax值為vb=5/2，此時(shí)y=1/2。為下列圖D點(diǎn)問題中求出va=vb=5/2就是混和決議意義下解。普通記做其中，X={x1,…,xm}，Y={y1,…,yn}為局中人A，B使用各自策略概率，滿足注：局勢(shì)平衡分析設(shè)局中人B使用最優(yōu)策略Y*,而局中人A使用某一個(gè)混和策略X，此時(shí)A收入將降至折線ABC上離開B某一點(diǎn)；又設(shè)局中人A使用最優(yōu)策略X*,而局中人B使用某一混和策略Y，此時(shí)，B損失將升高到折線CDE上離開D點(diǎn)某一點(diǎn)。當(dāng)雙方都堅(jiān)持使用最優(yōu)混和策略時(shí)。局勢(shì)得以平衡。方法2：方程組法由定理3知，求矩陣對(duì)策解等價(jià)于求解不等式方程組（1），（2）。又由定理4和5知，若最優(yōu)策略中均不為0，則可將以上兩個(gè)不等式組求解問題轉(zhuǎn)化為下面兩個(gè)方程組求解問題：注：此方法要求均不為0，所以，當(dāng)最優(yōu)策略一些分量實(shí)際為0時(shí)，以上兩個(gè)方程組可能無解。這說明此方法在實(shí)際應(yīng)用中有一定不足。尤其：對(duì)2×2矩陣，若局中人贏得矩陣沒有鞍點(diǎn)時(shí)，各局中人最優(yōu)策略中都大于0。即對(duì)于這種問題，是能夠采取方程組法求解。例：求解矩陣對(duì)策G，其中A為解：利用優(yōu)勢(shì)標(biāo)準(zhǔn)，化簡(jiǎn)矩陣：因?yàn)閍4優(yōu)超于a1，a3優(yōu)超于a2，所以化簡(jiǎn)為又因?yàn)閎1優(yōu)超于b3，b2優(yōu)超于b4,b5，所以化簡(jiǎn)為又因?yàn)閍1優(yōu)超于a3，化簡(jiǎn)為輕易看出矩陣A3沒有鞍點(diǎn)，所以能夠用方程組法解之。對(duì)應(yīng)方程組為：求解，得所以，以矩陣A為贏得矩陣對(duì)策一個(gè)解為例（齊王與田忌賽馬）這個(gè)問題中齊王和田忌各自擁有策