[博弈論書籍].運(yùn)籌學(xué)基礎(chǔ)

《[博弈論書籍].運(yùn)籌學(xué)基礎(chǔ)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、運(yùn)籌學(xué)基礎(chǔ)胡曉東應(yīng)用數(shù)學(xué)研究所中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院Http://wwwamtaccn/member/huxiaodong/Http://www.amt.ac.cn/member/huxiaodong/InstituteofAppliedMathematics提綱20世紀(jì)數(shù)學(xué)的五大指導(dǎo)理論FiveGoldenRules葉其孝、劉寶光GreatTheoriesof20thCenturyMath上海教育出版社，2000-andWhyTheyMatter1.線性規(guī)劃對偶定理2.博弈論極大極小定理運(yùn)籌學(xué)3.非線性規(guī)劃K-K-T定理?模型4

2、.計算復(fù)雜性理論停機(jī)定理,庫克定理?理論拓?fù)鋵W(xué)不動點(diǎn)定理奇點(diǎn)理論莫爾斯定理?算法5.組合最優(yōu)化算法設(shè)計技巧2.博弈論-引子“Tobeliterateinthemodernage,youneedtohaveageneralyouneedtohaveageneralunderstandingofgametheory.”--NobelLaureatePaulSamuelson(1991)經(jīng)濟(jì)學(xué)家、1991年諾貝爾經(jīng)濟(jì)學(xué)獎得主保羅?薩默爾森說：“如果你想要在現(xiàn)代社會做一個有文化的人，那么你就要對博弈論有一個大致的了解?！眡dhu32.博弈論-二戰(zhàn)

3、實(shí)例Kenney有兩種選擇-轟炸日軍的艦船1.偵察機(jī)搜索北線2.偵察機(jī)搜索南線日本1943年初新幾內(nèi)亞島盟國日軍有兩種選擇-護(hù)衛(wèi)艦增援島上部隊1.沿北線航行2.沿南線航行xdhu2.博弈論-二戰(zhàn)實(shí)例（續(xù)一）北線南線北線南線北線南線2123當(dāng)然，雙方實(shí)際上并不按照圖上建議的順序來做出決定。相反，雙方都是在不知道對方將會怎樣做決定的情況下分別獨(dú)立采取行動的。不過雙方所關(guān)注/期望的截然相反：對Kenney是好事的，對日軍就是壞事；反之亦然。因此當(dāng)我們用轟炸天數(shù)來衡量盟國的支付，而把這個數(shù)的負(fù)值作為日軍的回報，就有一方贏當(dāng)且僅當(dāng)一方輸。這就是零和

4、局勢-雙方的支付和是零。xdhu52.博弈論-二戰(zhàn)實(shí)例（續(xù)二）日軍俾斯麥海戰(zhàn)支付矩陣航行北線航行南線搜索北線222盟國Kenney搜索南線131如果Kenney搜索北線：無論日軍走哪，保證有2天轟炸。如果Kenney搜索南線：若日軍走北線，才有1天轟炸；若日軍走南線，可有3天轟炸。所以，為避免一旦查明日軍的決定而感遺憾，Kenney應(yīng)該選擇能轟炸最少天數(shù)中的最大值。這意味著他應(yīng)該選擇北線！xdhu62.博弈論-二戰(zhàn)實(shí)例（續(xù)三）俾斯麥海戰(zhàn)日軍支付矩陣航行北線航行南線搜索北線22盟國Kenney搜索南線1323如果日軍走北線：最多有2天被炸；

5、如果日軍走南線：最多有3天被炸。所以，為避免一旦查明盟國的決定而覺得遺憾，日軍應(yīng)該選擇被炸最多天數(shù)中的最小值。這意味著日軍應(yīng)該也選擇北線！xdhu72.博弈論-二戰(zhàn)實(shí)例（續(xù)四）合理的一個決策是：尋找能在最壞處境下給他/她最好可能支付的行動方向。顯然這導(dǎo)致每個局中人都采取不愿冒風(fēng)險的決策：為了避免導(dǎo)致不必要的輸而舍棄可能的贏的決策。俾斯麥海戰(zhàn)日軍支付矩陣航行北線航行南線搜索北線22盟國Kenney搜索南線13這樣的決策組合導(dǎo)致了一個博弈平衡點(diǎn)(或稱為鞍點(diǎn))：行極小中的極大值(極小極大)等于列極大中的極小值(極大極小)。有趣的是：海戰(zhàn)中雙方確

6、實(shí)是采取了這些策略！xdhu82.博弈論-零和博弈若把一局博弈的支付z視為局中人，x(盟軍)和y(日軍)，各自所做選擇的函數(shù)值，則平衡點(diǎn)(x,y)就是：minmaxz(x,y)=maxminz(x,y)。xyyx它被稱為純策略博弈的一個解（不論博弈對局多少次，每個對局人的最佳選擇都是其鞍點(diǎn)相對應(yīng)的博弈策略，否則就是混合策略）。鞍點(diǎn)的重要性在于：任何一個局中人都不能由單方面背離它而做出改進(jìn)！換句話說：任何一個局中人都能先于另一個局中人宣稱他/她的選擇，而且不會因為這樣做而造成任何的損失。xdhu92.博弈論-零和博弈（續(xù)一）假想海戰(zhàn)日軍(y

7、)支付矩陣北線南線盟國(x)北線414Kenney23南線3*2*1然而，很容易給出一個不存在鞍點(diǎn)的支付矩陣。在這種情況下，對于一個局中人來說，沒有容易理解的方法可以用來避免對手(有意/碰巧)事先獲悉他/她將要做什么而獲利這種情況發(fā)生。此時，有關(guān)局中人應(yīng)該如何選擇、決策呢？xdhu102.博弈論-零和博弈（續(xù)二）練習(xí).所有支付矩陣都滿足如下不等式：minmaxz(x,y)≥maxminz(x,y)。xyyx練習(xí)：確定右側(cè)矩陣中p和q的取y1y2y3值范圍，使其在(x,y)交叉處存x11q622在鞍點(diǎn)。x2p510x3623在不存在鞍點(diǎn)的情

8、況下，我們仿佛不再能有什么期望，因為，我們不知道什么是合理的決策了。xdhu112.博弈論-零和博弈（續(xù)三）一個通常的做法就是碰運(yùn)氣(擲硬幣)。其實(shí)這是一個合理的方案：通過隨機(jī)選擇來使得你對手