[博弈论书籍].运筹学基础

《[博弈论书籍].运筹学基础》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、运筹学基础胡晓东应用数学研究所中国科学院数学与系统科学研究院Http://wwwamtaccn/member/huxiaodong/Http://www.amt.ac.cn/member/huxiaodong/InstituteofAppliedMathematics提纲20世纪数学的五大指导理论FiveGoldenRules叶其孝、刘宝光GreatTheoriesof20thCenturyMath上海教育出版社，2000-andWhyTheyMatter1.线性规划对偶定理2.博弈论极大极小定理运筹学3.非线性规划K-K-T定理•模型4

2、.计算复杂性理论停机定理,库克定理•理论拓扑学不动点定理奇点理论莫尔斯定理•算法5.组合最优化算法设计技巧2.博弈论-引子“Tobeliterateinthemodernage,youneedtohaveageneralyouneedtohaveageneralunderstandingofgametheory.”--NobelLaureatePaulSamuelson(1991)经济学家、1991年诺贝尔经济学奖得主保罗•萨默尔森说：“如果你想要在现代社会做一个有文化的人，那么你就要对博弈论有一个大致的了解。”xdhu32.博弈论-二战

3、实例Kenney有两种选择-轰炸日军的舰船1.侦察机搜索北线2.侦察机搜索南线日本1943年初新几内亚岛盟国日军有两种选择-护卫舰增援岛上部队1.沿北线航行2.沿南线航行xdhu2.博弈论-二战实例（续一）北线南线北线南线北线南线2123当然，双方实际上并不按照图上建议的顺序来做出决定。相反，双方都是在不知道对方将会怎样做决定的情况下分别独立采取行动的。不过双方所关注/期望的截然相反：对Kenney是好事的，对日军就是坏事；反之亦然。因此当我们用轰炸天数来衡量盟国的支付，而把这个数的负值作为日军的回报，就有一方赢当且仅当一方输。这就是零和

4、局势-双方的支付和是零。xdhu52.博弈论-二战实例（续二）日军俾斯麦海战支付矩阵航行北线航行南线搜索北线222盟国Kenney搜索南线131如果Kenney搜索北线：无论日军走哪，保证有2天轰炸。如果Kenney搜索南线：若日军走北线，才有1天轰炸；若日军走南线，可有3天轰炸。所以，为避免一旦查明日军的决定而感遗憾，Kenney应该选择能轰炸最少天数中的最大值。这意味着他应该选择北线！xdhu62.博弈论-二战实例（续三）俾斯麦海战日军支付矩阵航行北线航行南线搜索北线22盟国Kenney搜索南线1323如果日军走北线：最多有2天被炸；

5、如果日军走南线：最多有3天被炸。所以，为避免一旦查明盟国的决定而觉得遗憾，日军应该选择被炸最多天数中的最小值。这意味着日军应该也选择北线！xdhu72.博弈论-二战实例（续四）合理的一个决策是：寻找能在最坏处境下给他/她最好可能支付的行动方向。显然这导致每个局中人都采取不愿冒风险的决策：为了避免导致不必要的输而舍弃可能的赢的决策。俾斯麦海战日军支付矩阵航行北线航行南线搜索北线22盟国Kenney搜索南线13这样的决策组合导致了一个博弈平衡点(或称为鞍点)：行极小中的极大值(极小极大)等于列极大中的极小值(极大极小)。有趣的是：海战中双方确

6、实是采取了这些策略！xdhu82.博弈论-零和博弈若把一局博弈的支付z视为局中人，x(盟军)和y(日军)，各自所做选择的函数值，则平衡点(x,y)就是：minmaxz(x,y)=maxminz(x,y)。xyyx它被称为纯策略博弈的一个解（不论博弈对局多少次，每个对局人的最佳选择都是其鞍点相对应的博弈策略，否则就是混合策略）。鞍点的重要性在于：任何一个局中人都不能由单方面背离它而做出改进！换句话说：任何一个局中人都能先于另一个局中人宣称他/她的选择，而且不会因为这样做而造成任何的损失。xdhu92.博弈论-零和博弈（续一）假想海战日军(y

7、)支付矩阵北线南线盟国(x)北线414Kenney23南线3*2*1然而，很容易给出一个不存在鞍点的支付矩阵。在这种情况下，对于一个局中人来说，没有容易理解的方法可以用来避免对手(有意/碰巧)事先获悉他/她将要做什么而获利这种情况发生。此时，有关局中人应该如何选择、决策呢？xdhu102.博弈论-零和博弈（续二）练习.所有支付矩阵都满足如下不等式：minmaxz(x,y)≥maxminz(x,y)。xyyx练习：确定右侧矩阵中p和q的取y1y2y3值范围，使其在(x,y)交叉处存x11q622在鞍点。x2p510x3623在不存在鞍点的情

8、况下，我们仿佛不再能有什么期望，因为，我们不知道什么是合理的决策了。xdhu112.博弈论-零和博弈（续三）一个通常的做法就是碰运气(掷硬币)。其实这是一个合理的方案：通过随机选择来使得你对手