下面是小编为大家整理的用Markov链,解决资源分配问题,供大家参考。
用 Markov 链 解决资源分配问题 摘要：资源分配一直以来都是人们关心的问题，解决资源分配也有很多种方式。本文利用相关的数学知识包括矩阵、Markov 链等知识，结合某旅游公司旅游客车在各个景区的分配来说明资源在随机概率中的分配情况。文章主要是通过分析现实问题，简化复杂的现实条件建立平面图形，将原有的资源合理地分配的到各个地方。
关键词：马氏链 资源分配
随机概率
现实问题一、绪论 资源分配一直以来都是资源合理利用的重中之重，我国地大物博，人口众多， 资源丰富，在复杂的现实问题中，资源分配一直以来都存在着很大问题。对于资源分配，国内外学者给出了众多不同的分配资源的方式方法，比如建立两层结构资源分配模型来解决资源分配的有效性，多层系统结构冗余分配问题等等。这些关于资源分配的方式给了我们很多启示，也帮助我们完成了很多资源的有效分配方案。
我们知道四川是久负盛名的旅游地，从成都青城山，都江堰到峨眉再到西昌， 名胜古迹不乏吸引到世界各地来四川旅游。近年来，随着四川经济不断发展，游客数量越来越多，由此对旅游公司的要求也不断提高。假设对于某一跨地区的旅游公司而言，游客的数量与承载游客的客车数量是相辅相成的，客车在不同的城市或者地区待命时，数量要如何确定呢？同样地，对于任何需要分配的固定资源， 要如何合理地将其分配到各个需要的地方呢？本文将提出一个合理的解决方案。
二、用 Markov 链 解决资源分配问题
1、问题的提出及假设条件
1.1 问题的提出
假设某一垮地区的旅游公司，为了在竞争激烈的市场中得到更合理的资源安排，公司要规划旅游区的客车数目，以免在车辆使用时浪费，那么要如何确定各个旅游区需要的客车数目才能避免这样的浪费是我们需要解决的问题。
假设公司有一批既定数目的车辆，将其分配到四川几个主要的旅游景区，包括九寨沟、康定、西昌、攀枝花、宜宾市、自贡市、峨眉、西岭雪山等。设公司既定车辆数目是 M，将其看作单位 1，那么对于这些旅游景区公司将分别安排多少辆车在景区内待命呢？ 1.2 假设条件：
（1）
旅游公司是垮地区性的服务公司；
（2）
旅游公司拥有的客车数目是已知的；
（3）
旅游公司所到的景点是固定的路线的；
（4）
旅游客车总是将游客从一个景点载往相临的另一个景点；
（5）
旅游客车只在白天工作，夜间停在景点待命。
1.3 资源分配的解决
1.3.1 分析：由于旅游时间关系，车辆从一个景点出发只能向临近的景点开出，且每到达一个景点，车辆就得留宿，以便旅客游玩后在休息住宿，第二天才出发开往另一个景点。不难看出，车辆从一个景点开往另一个景点是个随机事件，
一辆车从一个景点开往临近另一个景点的概率是相等的，根据 Markov 链的相关理论知识来分配车辆数目。
1.3.2 平面图形建立及研究过程
为了简化关系，下面将景点用数字表示 九寨沟-----1 康定-----2 西昌-----3 攀枝花 ---- 4 宜宾市-----5 自贡市----6 峨眉-7 西岭雪山 ---- 8 为了简化关系，本文将景点之间的路径简化为直线连接。先讨论 1 →7 这七个景点客车分配情况：
模型一 由于某一景点向临近另一景点发车是随机事件，所以 Markov 链的转移矩阵 为
它 的 不 变 分 布 为 ：
1/3π2+1/3π6+1/6π7=π1 1/3π1+1/3π3+1/6π7=π2
1/3π2+1/3π4+1/6π7=π3
1/3π3+1/3π5+1/6π7=π4
1/3π4+1/3π6+1/6π7=π5
1/3π1+1/3π5+1/6π7=π6
1/3π1+1/3π2+1/3π3+1/3π4+1/3π5+1/3π6=π7 求解不变分布得 π=（1/8 , 1/8 , 1/8 , 1/8 , 1/8 , 1/8 , 1/4）
1.3.3 用等概率知识来解释验证所得的结果
等概率原理是说对于处在平衡状态的孤立系统，系统各个可能的微观状态出现的概率是相等的。在此问题中，某一景点向临近的另一景点发车是随机的，且概率相等，用等概率来计算站点建设规模如下， 设此概率为 p，那么景点 1-6 所占概率均为 3p，景点 7 所占概率为 6p， 得 3p+3p+3p+3p+3p+3p+6p=1 则 p=1/24
那么，景点 1-6 车辆分配数目为 3p=1/8,景点 7 分配车辆数目为 6p=1/4。这个结果与上面相同，则计算无误。
1.3.4 小结
把公司需要分配的车辆数目看成单位 1 的话，在每个景点，由景点 1→7 的顺序分别分配的车辆数目为 1/8、1/8、1/8、1/8、1/8、1/8、1/4 ，这样的比例。我们得出一个意外的结论：景点的车辆数目与它和临近的景点道路联通情况
有关，即景点交通越发达，景点分配的车辆越多。然而这个结论是不是存在巧合呢？现在我们加入一个景点来验证这个结论。景点 1-8 如图所示：
模型二
同样得到 Markov 链的转移矩阵为：
它 的 不 变 分 布 为 ：
1/4π2+1/4π6+1/4π8=π1 1/3π1+1/3π3+1/6π7+1/4π8=π2
1/4π2+1/3π4+1/6π7=π3
1/3π3+1/3π5+1/6π7=π4
1/3π4+1/4π6+1/6π7=π5
1/3π1+1/3π5+1/6π7+1/4π8=π6
1/4π2+1/3π3+1/3π4+1/3π5+1/4π6+1/4π8=π7
1/3π1+1/4π2+1/4π6+1/6π7=π8 解得 π=（ 1/10 , 2/15, 1/10 , 1/10 , 1/10 , 2/15, 1/5,
即 2/15, ）
各城市所建站点为整个车辆中的比例分别为：1/10、2/15、1/10、1/10 、 1/10、 2/15、1/5、2/15。同样可以得到这样的结论：景点的车辆数目与它和 临近的景点道路联通情况有关，即景点交通越发达，景点分配的车辆越多。
三、结论：通过对以上两种情况的分析，我们发现把分配问题数学化之后， 运用数学的知识来解决问题，问题简单了很多。这给我们解决其他类似的分配问 题提供了一个参考，比如银行工作人员的调派，物流公司车辆人员的分配均可以 用此方法解决。