【數(shù)學(xué)建模算法】(22)對策論（下）

4.零和對策的線性規(guī)劃解法

當(dāng)m>2且n>2時(shí)，通常采用線性規(guī)劃方法求解零和對策問題。
局中人Ⅰ選擇混合策略\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個(gè)分量為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)時(shí)到達(dá)最小值u，故\overline{x}應(yīng)為線性規(guī)劃問題：

\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}應(yīng)為線性規(guī)劃。

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

的解。由線性規(guī)劃知識(shí)，上述兩個(gè)線性規(guī)劃問題互為對偶線性規(guī)劃，他們具有相同的最優(yōu)目標(biāo)函數(shù)。
不妨設(shè)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
則想愛你性規(guī)劃問題（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 在一場敵對的軍事行動(dòng)中，甲方擁有三種進(jìn)攻性武器A_{1}, A_{2}, A_{3}，可分別用與摧毀乙方工事；而乙方有三種防御性武器B_{1}, B_{2}, B_{3}來對付甲方。據(jù)平時(shí)演習(xí)得到的數(shù)據(jù)，各種武器間對抗時(shí)，甲方的贏得矩陣如下：
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); %把贏得矩陣的每個(gè)元素變成大于0的數(shù)
[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
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容