矩阵对策专用软件系统设计与实现研究*

游文霞 ，常俊晓 ，苏良虎

（1.三峡大学 电气与新能源学院，湖北 宜昌 443002；2.晶晨半导体上海有限公司深圳分公司，广东 深圳 518063）

0 引言

矩阵对策又称为二人有限零和对策，现已得到广泛研究，在体育比赛和政治经济谈判等对抗性决策问题应用中取得了很大成就[1-2]，为制定最有利的行动方案提供了理论依据。

国内外已经开发出多种计算矩阵对策的数学工具软 件 ， 有 MATLAB[3]、Lingo[4]与 Mathematic[5]等 ， 虽 然 这 类软件功能强大，但比较复杂，求解矩阵对策问题前需要先建立数学模型，再将原问题转化为线性规划问题。参考文献[6]开发出用于解决矩阵对策问题的程序Matrix Game Solver，输入赢得矩阵，即可计算出对策值、局中人Ⅰ和Ⅱ的最优决策向量，但不能输出计算过程。参考文献[7]设计了用于教学的矩阵对策程序，拥有良好的人机交互界面，可以给出计算过程，但操作步骤不够灵活。

本文借助Qt图形界面框架、C++ Boost数值计算库，通过QtMmlWidget组件解析数学标记语言MathML，以实现对数学公式的渲染，设计开发一款矩阵对策专用软件系统，方便决策双方快速采取合理的方案，同时使其具有跨平台特性，操作简单且能够公式化地显示完整的计算过程。

1 矩阵对策数学模型及求解

记矩阵对策两个局中人为Ⅰ、Ⅱ，策略集S1、S2如式（1）和式（2）所示，式（3）为矩阵对策的赢得矩阵 A。 Ⅰ和Ⅱ分别有m和n个行动策略。

当矩阵A存在鞍点时，其为纯策略矩阵对策，根据式 （4）计算出纯策略下的对策值及Ⅰ与Ⅱ的最优纯策略；反之，A为混合策略矩阵对策，求解时先分解出两个互为对偶的线性规划问题，再采用对偶单纯形法求解出混合策略下的对策值及Ⅰ与Ⅱ的最优纯策略[8]。

2 软件结构设计

根据矩阵对策专用软件使用简单、操作方便的功能需求，以及各模块间相互独立的设计思想，将软件分为程序界面、数值计算和结果、计算过程显示3个模块。软件结构如图1所示，给出了各模块包含的类以及模块之间的关系，通过Qt库提供的信号与槽事件机制可以快速有效地实现各个模块之间的消息传递与事件处理。

图1 软件结构图

3 系统实现

3.1 系统设计平台

Qt是一种跨平台C++图形用户界面应用程序开发框架，具有良好的封装机制，在保证较高模块化程度的同时也维系了很好的扩展性，且其丰富的API为该矩阵对策软件开发提供了很大的便利[9]。

Boost是一个可移植、开放源代码的C++准标准库，相当于C++标准模板库STL的扩充。对比STL，Boost包含了更多工具类，更加实用。

QtMmlWidget属于 Qt Solutions组件，支持 MathML2.0语言，以Unicode字体渲染各种数学符号，能够直接将用MathML2.0语言编写的数学公式对象移植到Qt程序中。

该专用计算软件以Qt框架提供的窗体、菜单等控件设计输入输出界面；以C++为编程语言，使用Boost数值计算库ublas完成矩阵对策问题的数值计算；最后提出公式的描述规则，借助QtMmlWidget解析MathML，实现对数学公式的渲染。

3.2 程序界面模块

程序界面包括主界面、赢得矩阵行列、输入输出窗口、矩阵对策窗体及结果显示界面，为整个软件系统提供与用户间的交互功能。程序主界面类与选项卡类间为一对多的关系，OrtTabWidget与行列输入对话框类为一对一的关系。因此，系统可以接收多个行列数据的输入，同时求解多个矩阵对策问题。

系统采用表格形式接收输入的赢得矩阵数据，输出分为纯策略与混合策略两种情况，再用数学公式显示类将结果显示在矩阵对策窗体类中。纯策略下赢得矩阵的解直接根据式（4）分析矩阵中各元素的值得到，过程简单，不生成中间数据。混合策略下系统给出单纯形法输出窗体，包括两个选项卡：线性规划数学模型及其标准型和计算结果选项卡、迭代计算生成的单纯形数据表显示选项卡。

3.3 数值计算模块

数值计算模块实现矩阵对策求解功能。根据赢得矩阵是否存在鞍点设计算法流程如图2所示，对偶单纯形法求解混合策略下矩阵对策问题的算法步骤如图3所示。当赢得矩阵中存在负数时，将各元素减去最小负数，使矩阵中全部元素值非负。

图2 系统算法流程框图

图3 对偶单纯形法算法步骤

3.4 结果及计算过程显示模块

根据MathML2.0的语法规则，将数学公式分为单节点元素公式与多层嵌套节点树公式。前者为数字、运算符等简单公式，后者为矩阵、上下标等复杂公式。定义如下描述数学公式的语法规则：

（1）单节点元素公式

式中，mx只能为标识符、运算符、数字、文本之一，data为公式的数据，attr和value为mx的属性和值。

（2）多层嵌套节点树公式

其中，各层公式标记用&&隔开，level表示公式标记的层数，从0开始逐层深入，且第0层元素mx不能为标识符、运算符、数字和文本。

上述规则中，数学公式以成对的“#”出现。系统将计算数据按语法规则描述为字符串形式，再传递给FormulaMmlWidget类。该类借助Qt库中与XML相关类与函数将传入的字符串转换为符合MathML2.0标准的XML语句，并以字符串的方式传递给父类QtMmlWidget进行渲染[10]。实现数学公式显示的步骤如图4所示。

图4 数学公式显示的步骤

由于QtMmlWidget对MathML2.0支持并非十分完美，在处理不等式对齐时，采用MathML呈现型标记mphantom处理行与列的对齐问题。经渲染后的公式以Qt窗体元件显示在数学公式显示类与单纯形表窗体类控件中，前者可以显示矩阵对策的解、矩阵、线性规划数学模型及其标准型，后者用于显示迭代过程中生成的单纯形数据表格。

4 应用实例

设式（5）为待计算的矩阵对策问题的赢得矩阵，输入该矩阵后点击“计算”按钮，运行界面如图5所示。

图5 赢得矩阵输入界面及矩阵对策的解

从图5可以读到局中人Ⅰ与Ⅱ最优混合策略分别为 （0.25，0.5，0.25）T与 （0.25，0.5，0.25）T， 且 局 中 人 Ⅱ的期望值为0。点击“显示”按钮，得到图6与图7所示的对偶单纯形法求解过程与中间数据。从图6可以看出，将输入的矩阵各元素加5，使其全部非负。图7显示了经过4次迭代计算求出问题的最优解，单纯形表中用“[]”标记的粗体数字即为主元素。整个计算过程可以公式化地显示在界面中，清晰直观。

图6 线性规划数学模型及计算过程

图7 单纯形数据表

5 结论

本文论述了矩阵对策专用软件系统的图形化界面设计方法，分析了纯策略下与混合策略下矩阵对策问题的模型及其求解方法，给出了数学公式的描述规则，实现了文本、矩阵等数学公式的显示。从计算实例可以看出，软件使用简单，操作方便，输出直观，能够快速方便地求解出任意的矩阵对策问题。在此软件的基础上，可以加入整数规划等优化问题的分析计算模块，从而实现功能更丰富的运筹学优化软件。

[1]杨靛青，李登峰.多目标直觉模糊集矩阵对策的求解方法[J].福州大学学报（自然科学版），2014，42（2）：213-218.

[2]Li Dengfeng.Mathematical-programming approach to matrix games with payoffs represented by atanassov′s interval-valued intuitionistic fuzzy sets[J].IEEE Transactions on Fuzzy Systems，2010，18（6）：1112-1128.

[3]陈杰.MATLAB宝典（第三版）[M].北京：电子工业出版社，2011.

[4]谢金星，薛毅.优化建模与 LINDO/LINGO软件[M].北京：清华大学出版社，2005.

[5]阳明盛，林建华.Mathematica基础及数学软件[M]（第 2版）.大连：大连理工大学出版社，2005.

[6]THOMASS， FERGUSON.Matrixgamesolver[EB/OL].[2014-03-14].（2015-01-10）.http：//www.math.ucla.edu/～tom/gamesolve.html.

[7]刘建永.运筹学算法与编程实践——Delphi实现[M].北京：清华大学出版社，2004.

[8]《运筹学》教材编写组.运筹学（第 4版）[M].北京：清华大学出版社，2012.

[9]李文帆，刘志刚，伍文城，等.基于Qt的电力系统地理接线图绘制软 件设计[J].电力系统自 动 化 ，2013，37（7）：72-76.

[10]张光渝，杨秋辉，詹聪，等.开放式 XML数据的质量分析方法[J].计算机应用研究，2013，30（7）：2082-2086.