决策问题

•玩扑克牌，比大小•两组扑克牌，分别是3、5、7和4、6、8•你们先选，然后先出•为什么我是总能赢？•这就是决策，对策•田忌赛马•田忌赛马是大多数人都熟知的故事，传说战国时期齐王欲与大将田忌赛马，双方约定每人挑选上、中、下三个等级的马各一匹进行比赛，每局赌金为一千金。齐王同等级的马均比田忌的马略胜一筹，似乎必胜无疑。田忌的朋友孙膑给他出了一个主意，让他用下等马比齐王的上等马，上等马对齐王的中等马，中等马对齐王的下等马，结果田忌二胜一败，反而赢了一千金。第一场第二场第三场获胜方齐王上中下田忌1上中下齐王田忌2上下中齐王田忌3中上下齐王田忌4中下上齐王田忌5下上中田忌田忌6下中上齐王•田忌能赢，主要是已知齐王的策略而做出决策•如果田忌和齐王事先都不知道各自采用何种组合来赛马，那结果又如何•两人轮流报数，每次只能报1或2，把两人报的所有数加起来，谁报数后和是10，谁就获胜。想一想，如果让你先报数，为了确报胜利，你第一次应报几?接下来应该怎样报？（囚犯的困惑）警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个人都知道：如果他们双方都不供认，将被以使用和持有大量伪币罪被各判刑18个月；如果双方都供认伪造了钱币，将各被判刑3年；如果一方供认另一方不供认，则供认方将被从宽处理而免刑，但另一方面将被判刑7年。将嫌疑犯A、B被判刑的几种可能情况列表如下：嫌疑犯B供认不供认嫌疑犯A供认不供认（3，3）（0，7）（7，0）（1.5，1.5）表中每对数字表示嫌疑犯A、B被判刑的年数。如果两名疑犯均担心对方供认并希望受到最轻的惩罚，最保险的办法自然是承认制造了伪币。•对策论（博弈论）–解决具有对抗性局势的模型。在这类模型中，参与对抗的各方都有一些可供选择的策略，该模型为对抗各方提供获得最优对策的方法•决策分析–在决策环境不确定和风险情况下对几种被选方案进行决策的准则和方法•预测–对未来的发展作出的推测。如，基于历史数据及相关分析的定量方法、利用专家判断的定性方法主要分支一、对策的基本要素（1）局中人。参加决策的各方被称为决策问题的局中人，一个决策总是可以包含两名局中人（如棋类比赛、人与大自然作斗争等），也可以包含多于两名局中人（如大多数商业中的竞争、政治派别间的斗争）。局中人必须要拥用可供其选择并影响最终结局的策略，在例8.3中，局中人是A、B两名疑犯，警方不是局中人。两名疑犯最终如何判刑取决于他们各自采取的态度，警方不能为他们做出选择。从这些简单实例中可以看出对策现象中包含的几个基本要素。（2）策略集合。局中人能采取的可行方案称为策略，每一局中人可采取的全部策略称为此局中人的策略集合。对策问题中，对应于每一局中人存在着一个策略集合，而每一策略集合中至少要有两个策略，否则该局中人可从此对策问题中删去，因为对他来讲，不存在选择策略的余地。应当注意的是，所谓策略是指在整个竞争过程中对付他方的完整方法，并非指竞争过程中某步所采取的具体局部办法。例如下棋中的某步只能看和一个完整策略的组成部分，而不能看成一个完整的策略。当然，有时可将它看成一个多阶段对策中的子对策。策略集合可以是有限集也可以是无限集。策略集为有限集时称为有限对策，否则称为无限对策。记局中人i的策略集合为Si。当对策问题各方都从各自的策略集合中选定了一个策略后，各方采取的策略全体可用一矢量S表示，称之为一个纯局势（简称局势）。例如，若一对策中包含A、B两名局中人，其策略集合分别为SA={1,…,m}，SB={1,…,n}。若A选择策略i而B选策略j，则（i,j）就构成此对策的一个纯局势。显然，SA与SB一共可构成m×n个纯局势，它们构成表8.3。对策问题的全体纯局势构成的集合S称为此对策问题的局势集合。(m,n)…(m,j)…(m,2)(m,1)m…………………(i,n)…(i,j)…(i,2)(i,1)i…………………(2,n)…(2,j)…(2,2)(2,1)2(1,n)…(1,j)…(1,2)(1,1)1A的策略n…J…21B的策略（3）赢得函数（或称支付函数）。对策的结果用矢量表示，称之为赢得函数。赢得函数F为定义在局势集合S上的矢值函数，对于S中的每一纯局势S，F（S）指出了每一局中人在此对策结果下应赢得（或支付）的值。综上所述，一个对策模型由局中人、策略集合和赢得函数三部分组成。记局中人集合为I={1,…,k}，对每一i∈I，有一策略集合Si，当I中每一局中人i选定策略后得一个局势s；将s代入赢得函数F，即得一矢量F(s)=(F1(s),…,Fk(s))，其中Fi(s)为在局势s下局中人i的赢得（或支付）。本节讨论只有两名局中人的对策问题，即两人对策，其结果可以推广到一般的对策模型中去。对于只有两名局中人的对策问题，其局势集合和赢得函数均可用表格表示。例如，表8.2就给出了例8.3的局势集合和赢得函数。二、零和对策存在一类特殊的对策问题。在这类对策中，当纯局势确定后，A之所得恰为B之所失，或者A之所失恰为B之所得，即双方所得之和总为零。在零和对策中，因F1(s)=－F2(s)，只需指出其中一人的赢得值即可，故赢得函数可用赢得矩阵表示。例如若A有m种策略，B有n种策略，赢得矩阵111212122212nnmnmmmnaaaaaaRaaa表示若A选取策略i而B选取策略j，则A之所得为aij（当aij0时为支付）。在有些两人对策的赢得表中，A之所得并非明显为B之所失，但双方赢得数之和为一常数。例如在表8.4中，无论A、B怎样选取策略，双方赢得总和均为10，此时，若将各人赢得数减去两人的平均赢得数，即可将赢得表化为零和赢得表。表8.4中的对策在转化为零和对策后，具有赢得矩阵表8.4局中人B123局中人A1(8,2)(1,9)(7,3)2(4,6)(9,1)(3,7)3(2,8)(6,4)(8,2)4(6,4)(4,6)(6,4)342142313111R给定一个两人对策只需给出局中人A、B的策略集合SA、SB及表示双方赢得值的赢得矩阵R。综上所述，当遇到零和对策或可转化为零和对策的问题时，R可用通常意义下的矩阵表示，否则R的元素为一两维矢量。故两人对策G又可称为矩阵对策并可简记成G={SA,SB,R}例8.4给定G={SA,SB,R}，其中SA={1,2,3}，SB={1,2,3,4}123412312630221421810601016R从R中可以看出，若A希望获得最大赢利30，需采取策略1，但此时若B采取策略4，A非但得不到30，反而会失去22。为了稳妥，双方都应考虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果。局中人A采取策略1、2、3时，最坏的赢得结果分别为min{12,－6,30,－22}=－22min{14,2,18,10}=2min{－6,0,－10,16}=－10其中最好的可能为max{－22,2,－10}=2。如果A采取策略2，无论B采取什么策略，A的赢得均不会少于2.B采取各方案的最大损失为max{12,14,－6}=14，max{－6,2,0}=2，max{30,18,－10}=30和max{－22,10,16}=16。当B采取策略2时，其损失不会超过2。注意到在赢得矩阵中，2既是所在行中的最小元素又是所在列中的最大元素。此时，只要对方不改变策略，任一局中人都不可能通过变换策略来增大赢得或减小损失，称这样的局势为对策的一个稳定点或稳定解，（注：也被称为鞍点）定义8.1对于两人对策G={SA,SB,R}，若有，则称G具有稳定解，并称VG为对策G的值。若纯局势（）使得，则称（）为对策G的鞍点或稳定解，赢得矩阵中与（）相对应的元素称为赢得矩阵的鞍点，与分别称为局中人A与B的最优策略。maxminminmaxijijGjjiiaaV**,ij**minmaxijijGjjaaV**,ij**,ij**ija*i*j对（8.1）式中的赢得矩阵，容易发现不存在具有上述性质的鞍点。给定一个对策G，如何判断它是否具有鞍点呢？为了回答这一问题，先引入下面的极大极小原理。蕴涵的思想是朴素自然的，可以概括为：“从最坏处着想，去争取最好的结果”定理8.1设G={SA,SB,R}，记，则必有μ+ν≤0maxminminmaxijijjjiiaa，证明:，maxmin(ijija)易见μ为A的最小赢得，ν为B的最小赢得，由于G是零和对策，故μ+ν≤0必成立。定理8.2零和对策G具有稳定解的充要条件为μ+ν=0。证明：（充分性）由μ和ν的定义可知，存在一行（例如p行）μ为p行中的最小元素且存在一列（例如q列），－ν为q列中的最大元素。故有apq≥μ且apq≤－ν又因μ+ν=0，所以μ=－ν，从而得出apq=μ，apq为赢得矩阵的鞍点，（p,q）为G的稳定解。（必要性）若G具有稳定解（p,q），则apq为赢得矩阵的鞍点。故有maxminminijpjpqjjiaaaminmaxmaxijiqpqjiiaaa从而可得μ+ν≥0，但根据定理8.1，μ+ν≤0必成立，故必有μ+ν=0。上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问题有解时，其解可以不唯一。例如，若12345123494311010115185182641513R则易见，（2,2），（2,4），（4,2），（4,4）均为此对策问题的解。一般又可以证明。例：某单位采购员在秋天时要决定冬天取暖用煤的采购量。已知在正常气温条件下需要用煤15吨，在较暖和较冷气温条件下需要用煤10吨和20吨。假定冬季的煤价随着天气寒冷的程度而变化，在较暖、正常、较冷气温条件下每吨煤价为100元、150元、200元。又秋季每吨煤价为100元。在没有关于当年冬季气温情况下，秋季应购多少吨煤，能使总支出最少？解：局中人I（采购员）有三个策略：策略1:10吨,策略2:15吨,策略3:20吨。局中人II（环境）：策略1较暖,策略2正常，策略3较冷现把该单位冬天取暖用煤全部费用（秋季购煤费用与冬天不够时再补购煤费用）作为采购员的赢得矩阵。1231-1000-1750-30002-1500-1500-25003-2000-2000-2000由maxminaij=minmaxaij=a33=-2000Ijji该最优策略为（3，3），即秋季购煤20吨。具有稳定解的零和对策问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍点，任一局中人都不可能通过自己单方面的努力来改进结果。然而，在实际遇到的零和对策中更典型的是μ+ν≠0的情况。由于赢得矩阵中不存在鞍点，至少存在一名局中人，在他单方面改变策略的情况下，有可能改善自己的收益。例如，考察（8.1）中的赢得矩阵R。若双方都采取保守的maxmin原则。将会出现纯局势（4,1）或（4,3）。但如果局中人A适当改换策略，他可以增加收入。例如，如果B采用策略1，而A改换策略1，则A可收益3。但此时若B改换策略2，又会使A输掉4，……。此时，在只使用纯策略的范围内，对策问题无解。这类决策如果只进行一次，局中人除了碰运气以外别无办法。但如果这类决策要反复进行多次，则局中人固定采用一种策略显然是不明智的，因为一旦对手看出你会采用什么策略，他将会选用对自己最为有利的策略。这时，局中人均应根据某种概率来选用各种策略，即采用混合策略的办法，使自己的期望收益尽可能大。设A方用概率xi选用策略i，B方用概率yj选用策略j，，且双方每次选用什么策略是随机的，不能让对方看出规律，111mnijij记X=(x1,…,xm)T，Y=(