"求解矩阵对策的直接线性规划法 (2010年)"
矩阵对策是两人零和博弈的一种形式,通常涉及到两个玩家(局中人I和局中人II)各自有一组策略选择,且每个策略组合对应一个确定的赢得值。在矩阵对策中,玩家的目标是最大化自己的赢得,而对方的目标是使其最小化。这类问题在理论和实际应用中都有广泛的研究。
传统的解决矩阵对策的方法包括线性规划法、迭代法和微分方程法。线性规划法是一种常见方法,但其要求对策值必须大于零。如果对策值小于或等于零,需要先进行转换。此外,即使对策值满足条件,线性规划法也需要通过变量变换将矩阵对策转化为线性规划问题来求解,这增加了求解的复杂性。
文章“求解矩阵对策的直接线性规划法”提出了一种新的方法,称为直接线性规划法,它能够直接从原始问题出发,建立一个特殊的线性规划模型,并求解得到矩阵对策的值以及两个玩家的最优策略。这种方法无需进行变量变换,也不要求对策值大于零,简化了解决过程。
直接线性规划法的工作原理是将矩阵对策问题与线性规划问题之间的等价关系建立起来。对于一个矩阵对策G={(s1, s2); A},其中s1和s2分别代表局中人I和II的策略集,A是一个m×n的赢得矩阵。通过局中人I的混合策略集St和局中人II的混合策略集S2,可以构建赢得函数E(x, y),它表示在策略x和y下的赢得值。文章中证明了这个赢得函数与线性规划的最优解之间存在等价关系。
在直接线性规划法中,首先构造一个线性规划模型,然后直接求解该模型,就能得到矩阵对策的最优值以及两个玩家的最优策略。这种方法尤其适用于解决对称对策问题,即两个局中人在对策中有相同的策略集和赢得矩阵的情况。
文章还讨论了如何应用直接线性规划法解决对称对策问题,进一步阐述了这种方法的优势和具体实施步骤。通过这种方法,研究者和实践者可以更有效地解决矩阵对策问题,而不必担心对策值的正负或复杂的变量变换,从而提高了计算效率和实用性。
直接线性规划法为矩阵对策问题提供了一个简洁、直接的求解途径,减少了传统方法的繁琐步骤,对于理解和应用矩阵对策具有重要的理论和实际意义。