【数学建模算法】(22)对策论（下）

作者: 热爱学习的高老板 | 来源:发表于2019-08-20 14:03 被阅读3次

4.零和对策的线性规划解法

当 $m>2$ 且 $n>2$ 时，通常采用线性规划方法求解零和对策问题。
局中人Ⅰ选择混合策略 $\overline{x}$ 的目的是使得：
$\begin{aligned} \overline{x}^{T} A \overline{y} &=\max _{x} \min _{y} x^{T} A y=\max _{x} \min _{y} x^{T} A\left(\sum_{j=1}^{n} y_{j} e_{j}\right) \\ &=\max _{x} \min _{y} \sum_{j=1}^{n} E_{j} y_{j} \end{aligned}$

其中 $e_{j}$ 为只有第 $j$ 个分量为1而其余分量的单位向量， $E_{j}=x^{T} A e_{j}$ 。记 $u \equiv E_{k}=\min _{j} E_{j}$ ，由于 $\sum_{j=1}^{n} y_{j}=1, \quad \min _{Y} \sum_{j=1}^{n} E_{j} y_{j}$ 在 $y_{k}=1, \quad y_{j}=0(j \neq k)$ 时到达最小值 $u$ ，故 $\overline{x}$ 应为线性规划问题：

$\max u$
s.t. $\left\{\begin{array}{l}{\sum_{i=1}^{m} a_{i j} x_{i} \geq u, \quad j=1,2, \cdots, n}（即E_{j} \geq E_{k}） \\ {\sum_{i=1}^{m} x_{i}=1} \\ {x_{i} \geq 0, \quad i=1,2, \cdots, m}\end{array}\right.$
的解。

同理， $\overline{y}$ 应为线性规划。

$\min v$
s.t. $\left\{\begin{array}{l}{\sum_{j=1}^{n} a_{i j} y_{j} \leq v, \quad i=1,2, \cdots, m} \\ {\sum_{j=1}^{n} y_{j}=1} \\ {y_{j} \geq 0, \quad j=1,2, \cdots, n}\end{array}\right.$

的解。由线性规划知识，上述两个线性规划问题互为对偶线性规划，他们具有相同的最优目标函数。
不妨设 $u>0$ ，做变换
$x_{i}^{\prime}=\frac{x_{i}}{u}, \quad i=1,2, \cdots, m$

则线性变换问题化为：

$\min \sum_{i=1}^{m} x_{i}^{\prime}$
s.t. $\left\{\begin{array}{l}{\sum_{i=1}^{m} a_{i j} x_{i}^{\prime} \geq 1, \quad j=1,2, \cdots, n} \\ {x_{i}^{\prime} \geq 0, \quad i=1,2, \cdots, m}\end{array}\right.$

同理，做变换：
$y^{\prime}_{j}=\frac{y_{j}}{v}, \quad j=1,2, \cdots, n$
则想爱你性规划问题（3）化为：

$\max \sum_{i=1}^{m} y_{i}^{\prime}$
s.t. $\left\{\begin{array}{l}{\sum_{j=1}^{n} a_{i j} y_{j}^{\prime} \leq 1, \quad i=1,2, \cdots, m} \\ {y_{j}^{\prime} \geq 0, \quad j=1,2, \cdots, n}\end{array}\right.$

例1 在一场敌对的军事行动中，甲方拥有三种进攻性武器 $A_{1}, A_{2}, A_{3}$ ，可分别用与摧毁乙方工事；而乙方有三种防御性武器 $B_{1}, B_{2}, B_{3}$ 来对付甲方。据平时演习得到的数据，各种武器间对抗时，甲方的赢得矩阵如下：
$A=\left[\begin{array}{ccc}{1 / 3} & {1 / 2} & {-1 / 3} \\ {-2 / 5} & {1 / 5} & {-1 / 2} \\ {1 / 2} & {-3 / 5} & {1 / 3}\end{array}\right]$

编写成分如下：

clear
a=[1/3,1/2,-1/3;-2/5,1/5,-1/2;1/2,-3/5,1/3];b=10;
a=a+b*ones(3); %把赢得矩阵的每个元素变成大于0的数
[x0,u]=linprog(ones(3,1),-a',-ones(3,1),[],[],zeros(3,1));
x=x0/u,u=1/u-b
[y0,v]=linprog(-ones(3,1),a,ones(3,1),[],[],zeros(3,1));
y=y0/(-v),v=1/(-v)-b

解得 $\overline{x}=(0.5283,0,0.4717)^{\mathrm{T}}, \quad \overline{y}=(0,0.3774,0.6226)^{\mathrm{T}}, \quad u=-0.0189$ ，故乙方有利。
下面我们使用式 $x$ 和 $y$ 分别作为模型主题用Lingo编程。

model:
sets:
player1/1..3/:x;
player2/1..3/:y;
game(player1,player2):c;
endsets
data:
ctrl=?; !ctrl取1求局中人1的策略，ctrl取0求局中人2的策略;
c=0.3333333 0.5 -0.3333333
-0.4 0.2 -0.5
0.5 -0.6 0.3333333;
enddata
max=u*ctrl-v*(1-ctrl);
@free(u);@free(v);
@for(player2(j):@sum(player1(i):c(i,j)*x(i))>u);
@for(player1(i):@sum(player2(j):c(i,j)*y(j))<v);
@sum(player1:x)=1;
@sum(player2:y)=1;
end

【数学建模算法】(22)对策论（下）

4.零和对策的线性规划解法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

【散人】数学建模

数学建模课程笔记

数学建模艺术