清华大学运筹学8对策论.pptxVIP

第十二章博弈论;第一节引言;竞争或对抗的双方或多方为取胜而选择策略称为对策。各方为了到达自己的目的，实现自己的目标和利益，必须考虑对手各种可能的行动方案，并选用对自己最有利或最合理的方案。

对策论就是研究对策中各方是否有最合理的行动方案，以及如何选用的数学分支。;张盛开教授70年代将“齐王赛马”视为矩阵对策，列出了齐王的赢得矩阵，提出了问题的解。;二、对策三要素

对策模型，须有3个根本要素。

1．局中人

有权决策者称为局中人，局中人全体用I表示。假设有n个局中人，那么I={1，2，…，n}。至少有两个局中人。

可以是个人、群体。利益完全一致的参加者只能视为一个局中人。

局中人不能心存侥幸，不能利用其他局中人失误扩大自身利益。

;2．策略

可供局中人选择、可行的完整行动方案称为策略。各局中人的策略集记为S，每一局中人策略集至少应有两个策略。

“齐正赛马”，假设用(上，中，下)表示以上、中、下三等马依次参赛，就是一个策略。齐王和田忌都有6个策略：

(上，中，下)、(上，下，中)、(中，上，下)、(中，下，上)、(下，中，上)、(下，上，中)。;3．赢得(支付)函数

各局中人的策略形成局势。设si是第i个局中人的一个策略，那么n个局中人的策略形成的策略组

s=(s1,s2,…,sn)(12.1)

s就是一个局势。

假设以S记全部局势，那么

S=S1×S2×··×Sn(12.2);局势s形成后，局中人i的赢得或所失值用Hi(s)表示，定义域是S，称为局中人i的赢得函数。

齐王和田忌的策略集可分别用S1=(α1,α2,…,αn)和S2=(β1,β2,…,βn)表示。

齐王任一策略αi和田忌任一策略βj构成局势sij。如果α1=(上，中，下)，β1=(上，中，下)，那么在s11中，齐王赢得H1(s11)=3，田忌赢得为H2(s11)=-3，如此等等。

当局中人、策略集和赢得函数确定后，也就确定了对策模型。;三、对策举例及分类

例2(销售竞争)假定企业I，Ⅱ均于[0,1]期间任一时刻出售某一产品。I和II分别在时刻x和y出售，那么I的收益(赢得)函数为：

c(y-x)假设xy

H(x,y)=c(1-x)/2假设x=y

c(1-x)假设xy

问两个企业各应选择什么时机出售对自己最有利?

此例中，I、II可用策略无穷多。;例3(费用分摊)3个邻城均在某河岸边，可单独建水厂，也可合建大水厂。

合建大水厂加敷设管道的费用要比分建3个小水厂总费用少。

但合建大厂方案能否实施，要看费用分摊是否合理。如果某城分摊的费用比自己单独建多，就不会接受合建方案。应如何合理分摊费用，才能使其愿意合建大水厂?;例4(拍卖)一般先由拍卖人介绍卖品并要价，然后请竞买人报价。每一次报价都比前一次高，最后卖给出价最高者。设n个买主分别报价p1，p2，…，pn，设pnpn-1…p2p1，只要pn略高于pn-1，第n个买主就能买到，即卖品实际上在次高价上卖出。

问：各买主不能确知他人出价时，应如何报价才能以较低价格买到卖品，最后结果又会怎样?;例5(困境难题)警官因事拘二人，分开审讯。

法律规定，假设两人都成认是自己所为，各判7年；假设都不成认，且证据缺乏，各判1年；

假设仅一人成认，认者释放，不认者判9年。

两人要权衡“认”和“不认”利弊得失。;对策的分类：

(1)根据局中人个数，二人对策和多人对策；

(2)根据赢得函数之和，零和与非零和对策；

(3)根据是否允许局中人合作，合作和非合作对策；

(4)根据局中人策略个数，有限和无限对策。

还有许多其他分类方式，

矩阵对策最简单，但表达了对策论的一般思想和方法，是研究其他对策的根底。

本章重点介绍。其他模型只简要介绍。;第二节矩阵对策根本理论;15/119;16/119;17/119;如果双方都不想冒险，不心存侥幸，而是考虑到对方必然设法使自己所得最少，就应从各自可能出现的最不利情形中选择一个最有