第6章-马尔可夫决策和群决策

2023/12/26第六章马尔可夫决策和群决策1目录1马尔可夫链的基本概念2马尔可夫决策方法3群决策方法系统运行过程中的“无后效性”某些系统运行过程中存在或近似存在“无后效性”的特征系统在每一时刻的状态仅仅取决于前一时刻的状态，而与其过去的历史状态无关池塘荷叶与青蛙池塘里有三张荷叶1,2,3，一只青蛙在荷叶上随机地跳来跳去，初始时刻t0，它位于荷叶2上，时刻t1，它可能仍在荷叶2上，也可能跳到1或3上，时刻t2，它位于哪张荷叶上与t0无关，只和t1有关可以近似认为无后效性的例子商店库存市场占有率车间的设备状态……马尔可夫预测和决策法是应用随机过程中的马尔可夫链的理论和方法来研究分析有关系统状态变化规律并籍此对未来进行预测和决策的一种方法——基于“无后效性”假设2123随机过程随机过程（StochasticProcess）随机过程是含有一个时间参数的随机变量族：{xt}，t∈T随机变量的取值称为状态，可以连续或离散比如设备状态、产品库存、产品每日需求量等离散型随机过程（DiscreteStochasticProcess）如若T

为离散集（设）同时的取值(状态)也是离散的，则称为离散型随机过程，用{1,2,3,…,k}表示状态集3马尔可夫链马尔可夫链（MarkovChain）任何一个未来事件的条件概率只和现在状态有关，而与过去的状态无关——“马尔可夫性”或“无后效性”离散型随机过程：时间离散，状态离散称为状态转移概率(一步转移概率)4有限状态的马尔可夫链齐次性特征：有限状态的马尔可夫链{xt}具有有限种(k种)状态具有马尔可夫性转移概率满足齐次性特征一步状态转移矩阵5例16阴天晴天下雨

晴天阴天下雨晴天0.500.250.25阴天0.3750.250.375下雨0.250.1250.625P=例2企业销售状况变化某产品销售情况分为畅销和滞销两种，1代表畅销，2代表滞销。以xt表示第t个季度的味精销售状态，则xt可取1或2的值。若未来的味精市场状态只与现在的市场状态有关，与以前的市场状态无关，则市场状态{xt}构成一个马尔可夫链。若：则状态转移矩阵：7例3考察一台机床的运行状态机床的运行存在正常和故障两种状态。S={1,2}。机床在运行中出现故障：1

2；处于故障中的机床经维修，恢复到正常状态：2

1以一个月为单位，经观察统计，知其从某个月份到下月份，机床出现故障的概率为0.3。在这一段时间内，故障机床经维修恢复到正常状态的概率为0.98故障2正常10.30.90.70.1例4某企业为使技术人员具有多方面的经验，实行技术人员在技术部门、生产部门和销售部门的轮换工作制度。轮换采用随机形式，每半年一次。初始状态，技术人员在某部门工作的概率用

表示，Pij表示处在第i个部门的技术人员在半年后转移到第j个部门的概率，已知一步状态转移矩阵如下，求n步后它在第i个部门工作的概率9对于二步转移矩阵：，可证明：递推：n步后技术人员在第i个部门工作的概率：比如1年后在某部门的工作概率10稳态概率(1)由转移概率和初始状态的概率分布可以确定任意步上的转移概率和绝对概率分布稳态概率：稳态概率的计算：对于例4：11稳态概率(2)初始状态对n步转移后所处状态的影响随n的增大而减少——稳态概率和初始状态无关不是所有的马尔可夫链都存在稳态概率——具有遍历性的马尔可夫链才有稳态概率1213目录1马尔可夫链的基本概念2马尔可夫决策方法3群决策方法例1——市场竞争策略决策某生产商标为α的产品的厂商为了与另外两个生产同类产品β和γ的厂家竞争，有三种可供选择的措施：措施1为发放有奖债券，措施2为开展广告宣传，措施3为优质售后服务三种方案实施后，经调查可知，该类产品的“用户转移矩阵”如下。已知三种商标的商品的月总销量为1000万件，每件可获利1元，另外，三种措施的成本费分别为150万元，40万元和30万元从长远利益考虑，α生产厂商应该采取何种措施？14

15例2——最佳维修策略的选择某化工企业对循环泵进行季度维修，每次检查中，把泵按其外壳及叶轮的腐蚀程度定为五种状态之一。分别为：状态1：优秀状态，无任何故障或缺陷状态2：良好状态，稍有腐蚀状态3：及格状态，轻度腐蚀状态4：可用状态，大面积腐蚀状态5：不可运行状态，腐蚀严重16该公司可采用的维修策略有以下几种：单状态策略：泵处于状态5时才进行修理，修理费用500元两状态策略：泵处于状态4和5时进行修理，处于状态4时的修理费用为250元，处于状态5时的修理费用为500元三状态策略：泵处于状态3,4,5时进行修理，处于状态3时的修理费用为200元，处于状态4和5时的修理费用同前例2——最佳维修策略的选择目前，该公司采用的维修策略为“单状态”策略假定不管处于何种状态，只要进行修理，泵都将恢复为状态1。已知在不进行任何修理时状态转移概率如下表所示问题：确定哪个策略的费用最低17泵在周期n+1的状态

泵在周期n的状态

1

2

3

4

5

1

0.00

0.60

0.20

0.10

0.10

2

0.00

0.30

0.40

0.20

0.10

3

0.00

0.00

0.40

0.40

0.20

4

0.00

0.00

0.00

0.50

0.50

5

0.00

0.00

0.00

0.00

1.00

求解(1)单状态维修策略下：18状态转移矩阵：稳态概率：求解(2)两状态维修策略下：19状态转移矩阵：稳态概率：求解(3)三状态维修策略下：20状态转移矩阵：稳态概率：结论单状态维修策略下：两状态维修策略下：三状态维修策略下：21因此，“两状态维修策略”是最佳决策非稳定概率的例子(1)某高校教师状态分为5类：助教、讲师、副教授、教授、流失及退休。目前状态：根据历史资料：试分析三年后的教师结构以及三年内为保持编制不变应进多少研究生充实教师队伍？22非稳定概率的例子(2)一年后：要保持550人的总编制，流失76人，故第一年应进76位研究生二年后：补充74人三年后：补充72人在第三年底，人员结构：2324目录1马尔可夫链的基本概念2马尔可夫决策方法3群决策方法群决策的概念现实生活中，决策往往是群体行为，是由多人参加进行的行动方案选择活动——群决策(GroupDecisionMaking)在不同场合群有不同的名称，例如，代表大会、委员会、集体、组织、团队(Team)、议会、俱乐部、协会和小组等等群决策的基本目标是：将群中成员的不同偏好按某种规则集结（aggregation或称并合，归纳，简化）成为单一的群整体的偏好25群决策的三个前提①自主性。决策者有独立选择机会，其行动不受较高层权利的支配，但不排除群体成员间相互影响②共存性。决策成员都在已知的共同条件下进行选择③共意性。群体做出的必然是所有参与者一致能够接受的方案26群决策的复杂性群体决策研究比个人决策研究要复杂很多。这主要由几个因素引起：①优先度。集体中每个成员都有各自的目标和优先观念以及不同的效用函数②主观概率判断。群体中各成员由于信息的感受和处理方式不一样，对未来状态出现概率的估计也不同③沟通。集体决策可以在完全没有沟通信息的情况下进行，而更多的决策是在有相互沟通信息的情况下进行27非排序式选举方法—简单多数投票法基本过程：群成员进行无记名投票按得票多少，即票数最多者获胜，叫做简单多数制或相对多数制得票超过半数才获胜，叫过半数代表制或绝对多数制，可能需要反复投票表决或取舍表决存在不公平现象28投票人编号1234567891011偏好次序第一位aaabbbbcccd第二位cccaaaaaaaa第三位dddccccdddc第四位bbbddddbbbb排序式选举(1)—康多西特原则在投票时，不仅要让投票人表达他最希望看到多个候选人中哪一个被选上，还应该让投票人说明他是以何种方式对这些候选人排序的，即在投票时表达他对各候选人的偏好次序，这就是排序式选举，又称偏好选举，由Borda提出29康多西特原则Condorcet原则的例子30Condorcet投票悖论31排序式选举(2)—波德原则集体中每一个成员将各种方案排序，如果有n个方案，则最优方案打分为n-1，次优方案打分n-2，依次类推，最劣方案打分为0统计每个方案的Borda数之和，最大者为最优方案比如五个方案：A、B、C、D、E，甲认为A＞C＞D＞E＞B，乙认为B＞A＞C＞D＞E，由于A的Borda数大于B的Borda数，所以A是最优的32波德原则的相悖现象A、B、C不分优劣。加入方案D，保持原先对A、B、C的优先判断次序，结果C比A和B差33ABC甲012已120丙201波德数333ABCD甲0123已1302丙3012波德数4437几种常见的策略性投票(1)谎报偏好而获益34几种常见的策略性投票(1)35谎报偏好而获益几种常见的策略性投票(2)选票交易36几种常见的策略性投票(3)小集团操纵群37社会选择函数群决策的关键问题：找出能正确反映群中成员意愿的公平合理的方法38群决策规则——社会选择函数(SC