《运筹学—对策论(五)》由会员分享，可在线阅读，更多相关《运筹学—对策论(五)（7页珍藏版）》请在金锄头文库上搜索。
1、四 迭代法 迭代法是求矩阵对策的一种近似方法。 基本思想：假设两个局中人反复进行对策多次，在每一 局中各局中人都从自己的策略集中选取一个使对方获得 最不利结果的策略，即第k局对策纯策略的选择欲使对 手在前k-1局中累计所得（或累计所失）最少（或最多 ）。 具体做法：在第1局中，从两个局中人中任选一个，如局 中人，让他先采取任意一个策略，如i 。然后，局中 人随之采取策略 j ，使采取i的局中人的所得最少 。在第2局中，局中人还认为局中人采取策略 j ，故 采取某策略l使局中人的所失最多，局中人又采取策 略，使采取局中人在这两局中累计赢得最少。在第3局 中，局中人又采取某策略使局中人在前两局的累
2、计 所失最多，然后局中人又采取某策略，使局中局中人在这三局中累计赢得最少。以后各局均照此方 式对策下去，直到迭代的结果达到一定的满意程度为止 。具体做法：在第1局中，从两个局中人中任选一个，如 局中人，让他先采取任意一个策略，如i 。然后，局 中人随之采取策略 j ，使采取i的局中人的所得最 少。在第2局中，局中人还认为局中人采取策略 j ，故采取某策略l使局中人的所失最多，局中人又 采取策略，使采取局中人在这两局中累计赢得最少。 在第3局中，局中人又采取某策略使局中人在前两 局的累计所失最多，然后局中人又采取某策略，使局 中近似解：若设在N局对策中局中人出1,2, ,m的次数 为k1,k2,
3、 ,km ,局中人出 1, 2, , n的次数为l 1, l 2, , l n ，xN=(k1 /N ,k2 /N, ,km /N),yN=(l1/N ,l2/N, ,lm /N) ，则（xN， yN ）就是所求近似解。近似解：若设在N局对策中局中人出1,2, ,m的次数 为k1,k2, ,km ,局中人出 1, 2, , n的次数为l 1, l 2, , l n ，xN=(k1 /N ,k2 /N, ,km /N),yN=(l1/N ,l2/N, ,lm /N) ，则（xN， yN ）就是所求近似解。i=1m aijkimin1 jnVN=() Nj=1n aijljmax1 imVN=()
4、 N令 ：VN=(VNVN+) 2则VN是对策值VG的近似值。说明 ：xN的每一个收敛子列收敛于局中人的最优策 略， yN的每一个收敛子列收敛于局中人的最优策略 。VN收敛于VG 。五 线性规划方法定理4表明，对策G的解x*和y*等价于下面两个不 等式组的解。v , j=1,2, ,ni=1m aijxi1i=1m xixi0 , i=1,2, ,mv , i=1,2, ,mj=1n aijyi1j=1n yiyj0 , j=1,2, ,n和其中 v=max min E(x,y) x S1*y S2*= min max E(x,y) y S2*x S1*就是对策的值VG。定理11 设矩阵对策G
5、=S1，S2；A的值为VG，则VG=max min E(x,j) x S1*1 jn= min max E(i,y) y S2*1 im证明：略。 求解矩阵对策的线性规划方法 ：作变换（根据定理6，不妨设v0): xi= xi /v,i=1,2m， yj= yj /v,j=1,2n，则上述两不等式组变成：1 , j=1,2, ,ni=1m aijxi 1/vi=1m xi xi 0 , i=1,2, ,m1, i=1,2, ,mj=1n aijyi 1/vj=1n yi yj 0 , j=1,2, ,n和v=max min x S1*1 jni=1m aijxi v=min max y S2*
6、1 imj=1n aijyj1 , j=1,2, ,ni=1m aijxi 1/vi=1m xixi 0 , i=1,2, ,m1, i=1,2, ,mj=1n aijyi 1/vj=1n yi yj 0 , j=1,2, ,n和v=max min x S1*1 jni=1m aijxi v=min max y S2*1 imj=1n aijyj显然两不等式组分别等价于下面两线性规划问题：1, i=1,2, ,mj=1n aijyj Max j=1n yi yj 0 , j=1,2, ,n1 , j=1,2, ,ni=1m aijxii=1minzm xi xi 0 , i=1,2, ,m和这
7、是一对对偶问题，可以利用单纯形法或对偶单纯形 法求解。例4 利用线性规划方法求解赢得矩阵为7 2 9 A= 2 9 0 9 0 11的矩阵对策。 解 ：求解问题可化为两个互为对偶的线性规划问题 ：和7 x1+ 2x2 + 9x3 1Minz=x1 + x2 + x32x1+ 9x2 1 9x1+ 11x3 1 x1, x2, x3 07 y1+ 2y2 + 9y3 1Max=y1 + y2 + y32y1+ 9y2 1 9y1+ 11y3 1 y1, y2, y3 0利用单纯形法可求解得 ： x=(1/20,1/10,1/20) ，z=16/80y=(1/20,1/10,1/20) ， =16/80于是x*=5x=(1/4,2/4,1/4) y*=5y=(1/4,2/4,1/4)VG=1/z=80/16=5
