矩陣對策專用軟件系統設計與實現研究*

游文霞 ，常俊曉 ，蘇良虎

（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.